Logo

DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

Aussagenlogik

Die mathematische Logik kann zur Formalisierung und Lösung alltäglicher Situationen beitragen (siehe auch hier).

Eine Aussage ist ein sprachliches Gebilde, dem man einen Wahrheitswert---"wahr" oder "falsch" (abgekürzt "w" oder "f")---zuordnen kann. Aussagen werden durch aussagenlogische Operationen (Junktoren) zu neuen Aussagen verknüpft, wobei der Wahrheitswert der verknüpften Aussage nur von den Wahrheitswerten der Teilaussagen abhängen soll (Extensionalitätsprinzip). Die Aussagenlogik ist die Theorie der aussagenlogischen Operationen.

Bei einer Formel (oder Aussageform) werden Aussagevariable A,B,C, ... bzw. Formeln durch endlich viele Junktoren miteinander verknüpft. Es gibt Regeln, was eine Formel ist, und was nicht. Formeln haben keinen Wahrheitswert, erst wenn der Wahrheitswert der Aussagenvariablen spezifiziert wird, ist auch der Wahrheitswert der Formel festgelegt.

Eine n-stellige Verknüpfung auf einer Menge M ist eine Abbildung f: Mn M. Formeln sind demnach Verknüpfungen auf der Menge {w,f} (mit dem Unterschied, daß zwei Abbildungen zwischen denselben Mengen, die für gleiche Werte gleiche Bilder haben "gleich" genannt werden, --- entsprechende Formeln werden nicht "gleich" sondern "äquivalent" genannt). Die Negation "¬" ist eine einstellige Verknüpfung auf {w,f}, während Konjunktion ("und") "", Disjunktion ("oder") "", Implikation ("wenn ... dann") "", Äquivalenz ("genau dann ... wenn") "", NAND ("nicht und") "|", EXOR ("ausschliessliches oder") "", und "" ("Peirce Pfeil") zweistellige Verknüpfungen auf {w,f} sind. Dies sind die Grundverknüpfungen. Als Abbildungen auf einer endlichen Menge {w,f}2 sind sie durch die Werte der Bilder der 4 Elemente definiert.
AB¬ AA B A B A B A B A B A | B A B
ffwff wwfw w
fwwfw wfww f
wfffw ffww f
wwfww wwff f
Folglich gibt es genau 24 = 16 zweistellige Verknüpfungen auf {w,f}.

Beispiele von Formeln, n-stellige Verknüpfungen auf {w,f}, sind (a b) (c ¬ a) oder auch (((a ¬ b) c) a) c.

In der folgenden Demo können Sie sich eine 2-stellige Verknüpfung basteln und auswerten. In die zweistelligen Felder werden "" (bitte "&&" tippen) oder "" ("||") eingetragen, in die 4 einstelligen Felder der Formel kann Negation (bitte "!" tippen) eingetragen werden. Die Formel wird ausgewertet indem für X und Y "w" bzw. "f" eingetippt wird. Versuchen Sie mal eine der Grundverknüpfungen zu erzeugen.

X: Y:
Formel: ( Y ( X Y)) X
Ergebnis:

Die folgenden Konventionen dienen dazu, Klammern sparen zu helfen.
1) "¬" hat Vorrang vor "" hat Vorrang vor "" hat Vorrang vor "" hat Vorrang vor "Äquivalenz "
2) "" kann weggelassen werden.

Eine Ausageform ist (kontradiktorisch/tautologisch), falls sie für beliebige Belegung der Aussagevariablen einen (falschen/wahren) Wahrheitswert liefert. Beispielsweise ist a ¬ a kontradiktorisch und Sein ¬ Sein tautologisch. Kompliziertere Tautologien, wie etwa ((A B) C) ¬ ((A B) C), erhält man wie folgt:

1. Substitutionsregel: A sei eine Aussagevariable der Tautologie B, und C sei eine feste Formel. Ersetzt man in B alle Auftritte von A durch C, so erhält man wieder eine Tautologie.

Äquivalenz von Formeln

Zwei Formeln A und B sind äquivalent, A B, wenn sie bei gleicher Belegung der in einer oder beiden Formeln vorkommenden Variablen dieselben Wahrheitswerte liefern. Eine Formel ist also tautologisch, wenn sie zu zu w äquivalent ist, und kontradiktorisch, wenn sie zu f äquivalent ist. Zwei Formeln A und B sind genau dann äquivalent, wenn A B tautologisch ist.

Es gibt einige wichtige Regeln zum Rechnen mit "","", und "¬":

Ersetzt man überall "" durch "=", so erhalten wir: ({w,f},,) ist eine Boolesche Algebra mit "w" als 1, "f" als 0, sowie ¬a als Inversem von a.

Für Formeln, die weitere Junktoren enthalten, gibt es eine Menge weiterer Regeln. So sind etwa, für beliebige Formeln A und B äquivalent:

Allerdings werden wir sehen, daß sich alle diese Regeln auf die obigen zurückführen lassen.

2. Substitutionsregel: B sei eine Teilformel der Formel A, und die Formel B' sei zu B äquivalent. Ersetzt man in A einige Auftritte von B durch B', so erhält man eine zu A äquivalente Formel.

Erfüllbarkeit

Anders als in der Analysis sind wir bei gegebener Formel g(x1,x2,...,xn) nicht an Nullstellen, sondern an Belegungen von x1, x2, ...,xn interessiert, mit g(x1,x2,...,xn)=w, also Belegungen, die den Ausdruck erfüllen.

Beispiel: Gibt es Werte für a,b,c,d, so daß
(¬ a (c d)) ((a c) (¬ b c) (b d))
(¬ b (a c ¬ d)) ((¬ a b) (¬ b d))
wahr ist?

a: b: c: d:
¬ a (c d)
(a c) (¬ b c) (b d)
¬ b (a c ¬ d)
(¬ a b) (¬ b d)
(¬ a (c d)) ((a c) (¬ b c) (b d))
(¬ b (a c ¬ d)) ((¬ a b) (¬ b d))

Allgemeiner ist eine Menge X von Formeln erfüllbar, wenn es eine sogenannte Realisierung gibt, d.h. eine Belegung aller vorkommenden Aussagenvariablen, unter der alle Formeln der Menge wahr sind. Ist X = {A1, ... An} endlich, so ist X genau dann erfüllbar, wenn (A1 ... An) erfüllbar ist.

Logisches Folgern

Angenommen Sie sind genauso wie ich davon überzeugt daß die folgenden drei Aussageformen Tautologien sind: Hat sie nun Tennis gespielt oder nicht? Klar hat sie, ist ja logisch! Genauer gesagt folgt es aus den obigen Prämissen.

X sei eine Menge von Formeln. Formel B folgt aus X, wenn B unter jeder Belegung, die jede Formel aus X erfüllt, erfüllt ist. Ist X = {A1, ... An} endlich, so folgt B aus X genau dann wenn (A1 ... An) B tautologisch ist. Im obigen Beispiel folgt aus der Formelmenge { S D, ¬ T S, ¬ D } die Formel T.
Eine Formelmenge Y folgt aus X, wenn jede Formel von Y aus X folgt.

Ob eine Formel aus einer endlichen Formelmenge folgt, kann mit Hilfe der Wahrheitstabellen nachgeprüft werden (semantische Methode). Das erste Rätsel auf der WaFa-Seite ist ein Beispiel. Der Aufwand ist nur u.U. gewaltig (aber nicht für Computer). Außerdem scheint das oft übertrieben, da ja eigentlich nur die (eventuell sehr wenigen) Realisierungen der Menge geprüft werden müssten. Leider sind diese Realisierungen i.A. auch nicht von vornherein bekannt.
Deshalb ist die Idee verlockend, zu versuchen eine Formel durch gewisse syntaktische Umformungen gemäß erlaubter Ableitungsregeln zu erhalten. Diese Ableitungsregeln haben selbst wieder die Form von Schlüssen, wobei allerdings die Variablen durch Formeln substituiert werden können. Hier finden Sie eine Tabelle von Ableitungsregeln mit wohlklingenden Namen.

Eine Formelmenge X ist widersprüchlich, wenn es eine Formel A gibt, so daß {A, ¬A} aus X folgt.

X ist genau dann widersprüchlich, wenn jede Formel aus X folgt, oder, gleichwertig dazu, wenn X unerfüllbar ist.


Weiter zu Normalformen, Junktorbasen oder zur Booleschen Algebra ...
Erich Prisner
erstellt im Februar 2000.