Aufgabe:
1. Gegeben sei die Boolesche Algebra B = ({f, w}, ⊕, ∧) und eine Menge von Variablen V = {v1, . . . , vn | vi ∈ {f, w}}.
Betrachten Sie folgende Boolesche Formel: (v1 ⊕ v2 ⊕ v6) ∧ (v1 ⊕ v2 ⊕ v5) ∧ (v2 ⊕ ¬v4 ⊕ ¬v5 ⊕ ¬v6) ∧ (v2 ⊕ ¬v3 ⊕ v4) ∧ (v1 ⊕ v3) ∧ (v2 ⊕ v3 ⊕ ¬v5).
Die sechs Ausdrucke in Klammern, z.B. ( v1 ⊕ v2 ⊕ v6), bezeichnet man mit Klauseln. Im folgenden soll entschieden werden, ob es v1, . . . , v6 ∈ {f, w} gibt, die alle Klauseln erfüllen
Beachten Sie: Es ist B ∼= (Z2, ⊕, )
(a) Beschreiben Sie die gegebene Formel als lineares Gleichungssystem mit Koeffizienten und Unbekannten aus Z2. Geben Sie eine spezielle Lösung an, die alle Klauseln erfüllt
(b) Bringen Sie das homogene LGS (in Matrixschreibweise) auf Stufenform und geben Sie den Rang und die Dimension des Kerns der Matrix an. Sie dürfen hierzu die folgenden Umformungen verwenden (und annehmen, dass die Lösungsmenge sich nicht ändert):
• Vertauschen von Zeilen,
• Addition von Zeilen.
(c) Beschreiben Sie die Lösungsmenge des LGS in der Form {x0+h | h ∈ H}, wobei H die Lösungsmenge des homogenen LGS ist und x0 die spezielle Lösung aus (a) ist.
(d) Wieviele Vektoren sind in der Lösungsmenge?
(e) Angenommen obige sechs Klauseln sind so gewählt, dass die Dimension des Kerns 0 ≤ k ≤ 6 ist. Wieviele Lösungen gibt es dann?
