Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Blatt 3, Aufgabe 5
Da ich gerade danach gefragt wurde: Ihr dürft natürlich → mithilfe von ¬ und ∨ ausdrücken, dabei handelt es sich ja noch nicht um eine Vereinfachung, sondern ein „Definition-Einsetzen“.
Bei der 5.3 steht ja
A → ¬B ^ ¬C
Was bindet hier stärker?
Würde sagen: nicht, und, implikation
Wenn ich das recht in Erinnerung habe gilt:
Negation bindet immer am stärksten.
Konjunktion bindet stärker als Disjunktion und diese wiederum stärker als Implikation
OK, google sagt das gleiche 
Na wenn Google das sagt. 
Hätte Google ja ruhig etwas früher sagen können.
¬ bindet auf jeden Fall stärker als ∧ und ∨ und die wiederum stärker als →. Aber gerade bei ∧ und ∨ finde ich in jedem Fall Klammerung sinnvoll (bzw. notwendig, falls man sich nicht darauf geeinigt hat, dass ∧ stärker bindet als ∨; warum sollte es auch? Vielleicht weil ({⊤,⊥},∨,⊥,∧,⊤) isomorph ist zu (ℤ/2ℤ,+,0,·,1)?). Gerade wenn man viele ∧ und ∨ geschachtelt hat oder es um so Sachen wie DNFs geht.
Darf man bei der CNF eine Formel wie ¬(A ∧ B) vorübergehend in den Fehlzustand (A ∨ B) überführen, solange man am Ende eine Formel dastehen hat, wo die obersten Teilformeln nur mit Konjunktionen verknüpft sind?
Und darf man sowas wie CNF(¬(A ∧ B ∧ C)) ganz am Ende vereinfachen zu ¬A ∨ ¬B ∨¬C ?
Aeh ja, klar. Solange du richtige Umformungen machst und am Ende eine CNF dasteht, ist es ok.
wieso nicht?
Wäre auch irgendwie blöd, so einen Term nicht vereinfachen zu dürfen.
Unter der Konjunktiven Normalform hatte ich mir eben vorgestellt, sieht man eine aussagenlogische Formel mal als Baum mit Wurzel oben, dass die obersten Verknüpfungen halt Konjunktionen sein müssen und keine Disjunktionen. Das irritiert mich daran.
Naja, eine ganz wichtige Sache ist: bei einer CNF darf ¬ nur vor Atomen stehen. Also ist ¬(A∧B∧C) noch keine. ¬A∨¬B∨¬C schon (warum?).
Zum Thema Baum: Der hat höchstens Höhe drei. Auf der obersten Ebene ∧, darunter ∨ und darunter wiederum ¬. Die Blätter sind dann die Atome.