tilly18 (tilly18)
Junior Mitglied Benutzername: tilly18
Nummer des Beitrags: 8 Registriert: 12-2002
| Veröffentlicht am Mittwoch, den 25. Juni, 2003 - 15:00: |
|
Das folgende Problem stellt mich vor große Rätsel. Die Aufgabe lautet: Zeige, dass es für jede Boolesche Funktion f element B[Index n] eine Ringsummendarstellung gibt, die keine negativen Literale enthält. D.h., beweise folgende Aussage: Jede Funktiou f element B[Index n] lässt sich folgendermaßen darstellen: f = EXOR von i=1 bis m (X[Index i[Index 1]]...x[index i[Index l[Index i]]]) (=> mehrere Minterme mit EXOR verbunden) mit - für alle 1<=i<=k((x[Index i[Index j]] element {x[index 1]...x[index n]} v (l[Index i] = 1 ^ für alle p != q(x[Index i[Index p]] != x[Index p[Index q]])), (!= entspricht ungleich) d.h ein Monom ist entweder die Konstante 1 oder besteht vollständig aus positiven Literalen und kein Literal kommt zweimal in einem Monom vor, - x[Index i[Index 1]]...x[Index i[Index l[Index i]]] != x[Index j[Index 1]]...x[Index j[Index l [Index j]]] für x != j D.h. jedes Monom darf maximal einmal auftreten. b) Zeige oder widerlege: Die in obiger Gleichung angegebene Darstellung ist für jedes f element B[index n] eindeutig Wenn einer von euch mir Tipps zur Lösung geben könnte, wäre es eine große Hilfe für mich. Grüße, Tilly18 |