umwformung aussagenlogische Formel ¬(((p∧¬q)∨(¬r∧¬s)) ⇒ (¬t∧u))

Question

¬(((p∧¬q)∨(¬r∧¬s)) ⇒ (¬t∧u)) Formen Sie diese Formel mit logischen Äquivalenzen so um (mit Angabe und Erklärung der Zwischenschritte), dass eine neue Formel mit folgenden Eigenschaften entsteht: •

Es werden nur noch Konjunktionen, Disjunktionen und Negationen verwendet. •

Negationen werden nur noch direkt auf die elementaren Aussagen p,q,r,s,t,u, aber nicht mehr auf zusammengesetzte Teilformeln angewendet. •

Ebenfalls dürfen Disjunktionen nur noch auf andere Disjunktionen oder (eventuell negierte) elementare Aussagen angewendet werden. •

Also: Innerhalb von Negationen keine Disjunktionen und Konjunktionen mehr, inner- halb von Disjunktionen keine Konjunktionen mehr...

Answer 1

$$\neg (((p\wedge \neg q)\vee (\neg r\wedge \neg s))\Rightarrow (\neg t\wedge u))$$

Umformung der negierten Implikation. Es gilt:

¬ ( A => B ) ist äquivalent A ∧ ¬ B

also:

$$\Leftrightarrow$$$$((p\wedge \neg q)\vee (\neg r\wedge \neg s))\wedge \neg (\neg t\wedge u)$$

Nun "ausmultiplizieren". Es gilt:

( A ∧ B ) ∨ ( C ∧ D ) ist äquivalent ( A ∨ C ) ∧ ( A ∨ D ) ∧ ( B ∨ C ) ∧ ( B ∨ D )

also:

$$\Leftrightarrow$$$$(p\vee \neg r)\wedge (p\vee \neg s)\wedge (q\vee \neg r)\wedge (q\vee \neg s)\wedge (t\vee \neg u)$$

Dies ist die geforderte Form.

Man bezeichnet diese Form auch als konjunktive Normalform.