Database Reference
In-Depth Information
¬
P
PQP
∧
Q
PQP
∨
Q
P
00
0
00
0
0
1
01
0
01
1
1
0
10
0
10
1
11
1
11
1
PQP
⇒
Q
PQP
⇔
Q
00
1
00
1
01
1
01
0
10
0
10
0
11
1
11
1
Abbildung 3.4
Wahrheitstafeln fur die Aussagenlogik
Aquivalenzen und Normalformen
3.4.3
Die Menge der aussagenlogischen Formeln ist reich an Redundanzen. So werden z.B.
die Formeln A und A
A sicherlich von genau den gleichen Interpretationen erfullt.
In vielen Situationen werden aber sog. Normalformen benotigt, die eine gewisse
Standarddarstellung fur Formeln sind.
∨
Definition 3.33 (Semantische Aquivalenz)
Zwei Formeln F und G sind
(se-
mantisch) aquivalent
, geschrieben F
≡
G, falls fur alle Interpretationen I gilt
[[ F ]]
I
=[G]]
I
Da Formeln beliebig verschachtelt sein konnen, wird in Inferenzsystemen oft zu-
nachst versucht, diese Formeln in semantisch aquivalente, technisch aber einfacher
zu handhabende Formeln zu transformieren. Der folgende Satz liefert die Basis
dafur.
Theorem 3.34 (Semantische Ersetzbarkeit)
Seien
F
und
G
aquivalente For-
meln. Sei
H
eine Formel mit mindestens einem Vorkommen der Teilformel
F
.Dann
ist
H
aquivalent zu einer Formel
H
,dieaus
H
dadurch gewonnen ist, dass (ir-
gend)ein Vorkommen von
F
durch
G
ersetzt worden ist.
Das Theorem 3.34 besagt, dass man durch Austausch semantisch aquivalenter
Teilformeln wieder eine semantisch aquivalente Formel erhalt. Das folgende Theo-
rem listet die gebrauchlichsten Aquivalenzen auf, die sich alle auf Basis der Wahr-
heitstafeln aus Abbildung 3.4 ableiten lassen.
