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.
| A | B | Ø A | A Ù B | A Ú B | A ® B | A « B | A Å B | A | B | A ¯ B |
|---|---|---|---|---|---|---|---|---|---|
| f | f | w | f | f | w | w | f | w | w |
| f | w | w | f | w | w | f | w | w | f |
| w | f | f | f | w | f | f | w | w | f |
| w | w | f | w | w | w | w | f | f | 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.
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 "Ø":
(A Ù B) Ù C,
(A Ú B) Ú C .
B Ù A,
B Ú A,
A,
A.
A,
A.
(A Ù B) Ú
(A Ù C),
(A Ú B) Ù
(A Ú C)
A,
A,
f,
w,
A.
Ø A Ú
Ø B,
(die eine der de Morganschen Regeln)
Ø A Ù
Ø B. (die andere der de Morganschen Regeln)
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:
Ø A Ú B,
(Ø B ®
ØA).
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?
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:
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.