3.2.1 ,,Am Papier”

Wie in Kapitel 2.2 beschrieben, gehen wir in vier Schritten vor.

 

Schritt 1: Alle Operatoren auf $\wedge$, $\vee$ und $\neg$ zurückführen:  

F	=	((t ↑ ¬¬C) ∨ (A ⊅ B)) ⊃ ¬(¬¬B ↓ ¬A)
	=	¬((t ↑ ¬¬C) ∨ (A ⊅ B)) ∨ ¬(¬¬B ↓ ¬A)
	=	¬((t ↑ ¬¬C) ∨ (A ⊅ B)) ∨ ¬(¬¬B ↓ ¬A)
	=	¬((¬t ∨ ¬¬¬C) ∨ (A ⊅ B)) ∨ ¬(¬¬B ↓ ¬A)
	=	¬((¬t ∨ ¬¬¬C) ∨ (A ∧¬ B)) ∨ ¬(¬¬B ↓ ¬A)
	=	¬((¬t ∨ ¬¬¬C) ∨ (A ∧¬ B)) ∨ ¬(¬¬¬B ∧ ¬¬A)

 

Schritt 2: Negationen nach innen ziehen:  

	=	(¬(¬t ∨ ¬¬¬C) ∧ ¬(A ∧¬ B)) ∨ ¬(¬¬¬B ∧ ¬¬A)
	=	((¬¬t ∧ ¬¬¬¬C) ∧ ¬(A ∧¬ B)) ∨ ¬(¬¬¬B ∧ ¬¬A)
	=	((t ∧ ¬¬¬¬C) ∧ ¬(A ∧¬ B)) ∨ ¬(¬¬¬B ∧ ¬¬A)
	=	((t ∧ ¬¬C) ∧ ¬(A ∧¬ B)) ∨ ¬(¬¬¬B ∧ ¬¬A)
	=	((t ∧ C) ∧ ¬(A ∧¬ B)) ∨ ¬(¬¬¬B ∧ ¬¬A)
	=	((t ∧ C) ∧ (¬A ∨¬¬ B)) ∨ ¬(¬¬¬B ∧ ¬¬A)
	=	((t ∧ C) ∧ (¬A ∨ B)) ∨ ¬(¬¬¬B ∧ ¬¬A)
	=	((t ∧ C) ∧ (¬A ∨ B)) ∨ (¬¬¬¬B ∨ ¬¬¬A)
	=	((t ∧ C) ∧ (¬A ∨ B)) ∨ (¬¬B ∨ ¬¬¬A)
	=	((t ∧ C) ∧ (¬A ∨ B)) ∨ (B ∨ ¬¬¬A)
	=	((t ∧ C) ∧ (¬A ∨ B)) ∨ (B ∨ ¬A)

 

Schritt 3: Konstanten eliminieren:  

=

(C ∧ (¬A ∨ B)) ∨ (B ∨ ¬A)

 

Schritt 4 (DNF): Ausdistributieren  

=

((C ∧ ¬A) ∨ (C ∧ B)) ∨ (B ∨ ¬A)

 
Dies ist nun eine Formel in disjunktiver Normalform. Unter Zuhilfenahme einiger aussagenlogischer Rechenregeln lässt sich diese Formel in die äquivalente Form $\neg A \wedge B$ umformen.

 

Schritt 4 (KNF): Ausdistributieren

 

=

(C ∨ (B ∨¬A)) ∧ ((¬A ∨ B) ∨ (B ∨¬A))

 
Dies ist nun eine Formel in konjunktiver Normalform. Durch eine sture Konvertierung in (Multi-)Mengennotation erhalten wir

$$\left\{\left\{C,B,\neg A\right\},\left\{\neg A,B,B,\neg A\right\}\right\}$$

Nach Duplikatelimination erhalten wir ,,echte” Mengen:

$$\left\{\left\{C,B,\neg A\right\},\left\{\neg A,B\right\}\right\}$$

Tautologien (Klauseln, die sowohl eine Variable als auch ihre Negation enhalten) gibt es nicht, dadurch ändert sich durch einen entsprechenden Vereinfachungsschritt nichts. Jedoch ist $\left\{\neg A,B\right\}$ eine Untermenge von $\left\{C,B,\neg A\right\}$, was bedeutet, dass $\left\{C,B,\neg A\right\}$ von $\left\{\neg A,B\right\}$ subsumiert wird. Übrig bleibt die Menge

$$\left\{\left\{\neg A,B\right\}\right\}$$

Sortieren (siehe Kapitel 3.3) ändert auch nichts. Nun haben wir eine möglichst einfache Klauselform, die wir wieder als Formel anschreiben wollen. Wir erhalten schließlich die Formel:

$$\neg A\vee B$$