Database Reference
In-Depth Information
Theorem 3.35 ( Aquivalenzen fur die Aussagenlogik)
Es gelten:
F
∧
F
≡
F
1.
(Idempotenz)
F
∨
F
≡
F
F
∧
G
≡
G
∧
F
2.
(Kommutativitat)
F
∨
G
≡
G
∨
F
(F
∧
G)
∧
H
≡
F
∧
(G
∧
H)
3.
(Assoziativitat)
(F
∨
G)
∨
H
≡
F
∨
(G
∨
H)
F
∧
(F
∨
G)
≡
F
4.
(Absorption)
F
∨
(F
∧
G)
≡
F
F
∧
(G
∨
H)
≡
(F
∧
G)
∨
(F
∧
H)
5.
(Distributivitat)
F
∨
(G
∧
H)
≡
(F
∨
G)
∧
(F
∨
H)
6.
¬¬
F
≡
F
(Doppelnegation)
¬
(F
∧
G)
≡¬
F
∨¬
G
7.
(de Morgansche Regeln)
¬
(F
∨
G)
≡¬
F
∧¬
G
F
∨
G
≡
F
8.
falls F allgemeingultig
(Tautologieregeln)
F
∧
G
≡
G
F
∨
G
≡
G
9.
falls F unerfullbar
(Unerfullbarkeitsregeln)
F
∧
G
≡
F
10.
F
⇒
G
≡¬
G
⇒¬
F
(Kontraposition)
11.
F
⇒
G
≡¬
F
∨
G
(Implikation)
12.
F ⇔ G
≡
(F ⇒ G) ∧ (G ⇒ F )
(Koimplikation)
Mit den in Theorem 3.35 angegebenen Transformationen lasst sich jede aussa-
genlogische Formel semantisch aquivalent transformieren, so dass darin als Junkto-
ren nur noch Konjunktion, Disjunktion und Negation auftreten, wobei die Negation
dabei nur unmittelbar vor Atomen auftritt. Dass dies gilt, kann man sich daran
klarmachen, dass man mit (12.) und (11.) nacheinander alle Koimplikationen und
Implikationen eliminieren und mit den de Morganschen Regeln (7.) und der Eli-
mination der Doppelnegation (6.) das Negationszeichen ganz “nach innen” ziehen
kann. Auf weitere Normalisierungen werden wir im Zusammenhang mit der Pradi-
katenlogik 1. Stufe eingehen (Abschnitt 3.5.6).
Selbsttestaufgabe 3.36 (Implikation und Assoziativitat)
Zeigen Sie, dass
die Formeln (A
⇒
B)
⇒
C und A
⇒
(B
⇒
C)nichtaquivalent sind.
Daher ist die Zeichenkette “A
C”
keine
korrekt gebildete Formel; wegen der
Assoziativitat der Konjunktion schreibt man aber z.B. oft ohne Klammern A
⇒
B
⇒
∧
B
∧
C.
