0 Daumen
269 Aufrufe

Aufgabe: Wandeln Sie α = ((a ∧ b) ∨ ¬c) → ((c ∧ b) ∨ ¬a) ins KNF um.


Meine Lösung bisher ist Folgendes:

((a ∧ b) ∨ ¬c) → ((c ∧ b) ∨ ¬a) ⇔
¬((a ∧ b) ∨ ¬c) ∨ ((c ∧ b) ∨ ¬a) ⇔
(¬a ∨ ¬(b ∨ ¬c)) ∨ ((c ∧ b) ∨ ¬a) ⇔
(¬a ∨ (¬b ∧ c)) ∨ ((c ∧ b) ∨ ¬a) ⇔
(¬a ∨ (¬b ∧ c)) ∨ ((c ∨ ¬a) ∧ (b ∨ ¬a)) ⇔
((¬a ∨ ¬b) ∧ (¬a ∨ c)) ∨ ((¬a ∨ c) ∧ (b ∨ ¬a))

ich habe aber keine Ahnung wie ich weiter machen soll, welche schritte fehlen mir bis die aussage ins KNF umgewandelt ist?

Avatar von

2 Antworten

0 Daumen

Du kannst doch einfach alle 8 Fälle durchgehen:

a   b   c  ((a ∧ b) ∨ ¬c)   ((c ∧ b) ∨ ¬a)     ((a ∧ b) ∨ ¬c) → ((c ∧ b) ∨ ¬a)
0    0    0           1                        1                                    1
0    0    1            0                       1                                     1
etc. und zu der letzten Spalte die

passenden Maxterme bestimmen.

Avatar von 287 k 🚀

Ich darf keine Wahrheitstabellen nutzen, ich soll es durch algebraische Transformation ins KNF transformieren.





0 Daumen

Hallo, späte Antwort, aber ich wollte es der Vollständigkeit halber mal ergänzen. Meine Antwort ist nicht besonders elegant, also ginge es sicher schneller, bin kein Mathematiker, aber ich habe Folgendes (die Konjunktion oder Disjunktion in der Mitte ist kursiv für den Überblick, manchmal farbliche Markierungen, wenn Terme sehr lang sind):

I. ((a ∧ b) ∨ ¬c) → (( c ∧ B) ∨ ¬a) ⇔ 

II. ¬((a ∧ b) ∨ ¬c) ((c ∧ b) ∨ ¬a) ⇔ ⟨Ersatz Implikation mit Disjunktion⟩

III. ((¬a ∨ ¬b) ∧ c) ((c ∧ b) ∨ ¬a) ⇔ ⟨Doppelte Anwendung der De Morganschen Regel ganz links⟩

IV. ((c ∧ ¬a) ∨ (¬b ∧ c)) ((¬a ∨ c) ∧ (¬a ∨ b)) ⇔ ⟨Distributivgesetz; folgt jetzt ständig⟩

V. (((¬a ∨ c) ∧ (¬ab)) ∨ (c ∧ ¬a)) (((¬a ∨ c) ∧ (¬a b)) ∨ (¬b ∧ c)) ⇔ ⟨Distribuiert "mit ganzer rechten Seite"⟩

VI. ((((¬a ∨ c) ∧ ¬a) ((¬a ∨ c) ∧ b)) ∨ (c ∧ ¬a)) ((((¬a ∨ c) ∧ ¬a ((¬a ∨ c) ∧ b)) ∨ (¬b ∧ c)) ⇔ ⟨Distributiv⟩

VII. (((¬a ∨ ((¬a ∨ c) ∧ b)) ∨ (c ∧ ¬a)) (((¬a ∨ ((¬a ∨ c) ∧ b)) ∨ (¬b ∧ c)) ⇔ ⟨Absorptionsgesetz⟩

VIII. (¬a ∨ ((¬a ∨ c) ∧ b)) ((c ∧ ¬a) ∨ (¬b ∧ c)) ⇔ ⟨Ausklammern, ginge auch schon unter V.⟩

IX. (¬a ∨ ((¬a ∨ c) ∧ b)) (c ∧ ((c ∧ ¬a) ∨ ¬b)) ⇔ ⟨Distribuiert und absorbiert rechts⟩

X. ((¬a ∨ c) ∧ (¬a ∨ b)) ((c ∧ ¬a) (c ∧ ¬b)) ⇔ ⟨Beide Seiten distribuieren und absorbieren⟩

XI. ((¬a ∨ c) ∧ (¬a ∨ b)) ∨ (c ∧ ((¬a ∨ ¬b)) ⇔ ⟨Ausklammern rechts⟩

XII. ((¬a ∨ (c ∧ (¬a ∨ b))) (c ∧ ((¬a ∨ ¬b)) ⇔ ⟨Distribuiert und absorbiert links⟩

XIII. ((c ∧ ((¬a ∨ ¬b)) ∨ ¬a ) ((c ∧ ((¬a ∨ ¬b)) ∨ (c ∧ (¬a ∨ b))) ⇔ ⟨Distribuiert⟩

XIV. ((¬a ∨ c) ∧ (¬a ∨ b)) c ⇔⟨Simplifizieren und absorbieren⟩

XV. ((¬a ∨ c) ∨ c) (¬a ∨ b ∨c) ⇔ ⟨Distributiv wieder; theoretisch schon KNF? Geht aber noch kürzer⟩

XVI. (¬a ∨ c) (¬a ∨ c ∨ b) ⇔

XVII. (¬a ∨ c) ⇔ a → c

Der ein oder andere Schritt wirkt unnötig, aber ich müsste das jetzt länger mir anschauen, so hab ich das jetzt auf den ersten Blick gemacht

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community