Betrachten wir die Formel
In der
Äquivalenz
können wir (wie im vorherigen Kapitel gezeigt)
- a durch !p, und
- b durch !q
substituieren, und erhalten die Äquivalenz
Ersetzen wir nun die Teilformel
von
γ durch die äquivalente Formel
so erhalten wir die zu
γ äquivalente Formel
Nun wollen wir eine weiter
Äquivalenz einführen:
Substituieren wir hier
so erhalten wir
und somit durch
Ersetzung der entsprechenden Teilformel in
γ1 die zu
γ äquivalente Formel
Wiederholen wir diesen Vorgang für !!q, so erhalten wir die zu
γ äquivalente Formel
Betrachten wir nun die
Äquivalenz
und
substituieren wir
so erhalten wir
und somit durch
Ersetzung der entsprechenden Teilformel in
γ3 die zu
γ äquivalente Formel
Nachdem auch die folgende
Äquivalenz gilt:
erhalten wir durch
Substitution und
Ersetzung der entsprechenden Teilformel aus
γ4 die zu
γ äquivalente Formel
Die Äquivalenz kann durch die folgenden Tabellen überprüft werden:
|
p
|
q
|
!p
|
!q
|
!p&!q
|
!(!p&!q)
|
!(!p&!q)|p
|
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
|
1
|
0
|
0
|
1
|
0
|
1
|
1
|
|
1
|
1
|
0
|
0
|
0
|
1
|
1
|
|
p
|
q
|
p|q
|
|
0
|
0
|
0
|
|
0
|
1
|
1
|
|
1
|
0
|
1
|
|
1
|
1
|
1
|