Unterabschnitte

© 1999 François Bry
Dieses Lehrmaterial wird ausschließlich zur privaten Verwendung angeboten. Eine nichtprivate Nutzung (z.B. im Unterricht oder eine Veröffentlichung von Kopien oder Übersetzungen) dieses Lehrmaterials bedarf der Erlaubnis des Autors.


2.1 Aussagenlogik

Mit der Aussagenlogik werden hauptsächlich logische Verknüpfungen wie ,,nicht``, ,,und``, ,,oder`` untersucht. Zur syntaktischen Repräsentation dieser Verknüpfungen von Aussagen dienen sogenannte Junktoren: ¬ für die einstellige Verknüpfung ,,nicht``, ∧ für die zweistellige Verknüpfung ,,und``, ∨ für ,,oder``, ⇒ für ,,wenn dann``, ⇔ für ,,genau dann wenn``.

Die einfachsten Aussagen, die damit verknüpft werden können, sind die konstant wahre Aussage, repräsentiert durch T (gesprochen ,,top`` oder auch ,,verum``) und die konstant falsche Aussage, repräsentiert durch ⊥ (gesprochen ,,bottom`` oder auch ,,falsum``). Man nennt T und ⊥ die nullstelligen Junktoren.

Welche weiteren Aussagen in der formalen Sprache repräsentiert werden müssen, hängt von der Anwendung ab, für die die Sprache verwendet wird. Es gibt deshalb nicht ,,die`` Sprache der Aussagenlogik, sondern verschiedene Sprachen der Aussagenlogik, die sich in ihrem anwendungsspezifischen Teil unterscheiden. Den anwendungsspezifischen Teil einer Sprache einer Logik nennt man üblicherweise die Signatur der Sprache.

Die Signatur einer Sprache der Aussagenlogik definiert sogenannte ,,Aussagenvariablen``. Jede Aussagenvariable dient zur syntaktischen Repräsentation irgend einer Aussage, die wahr oder falsch sein kann, wie etwa ,,es regnet`` oder ,,Franz ist krank``. Die durch Aussagenvariablen repräsentierten Aussagen werden als elementar betrachtet, das heißt, dass die Aussagenlogik keine sprachlichen Mittel zur Darstellung der inneren Struktur solcher Aussagen bietet. Beispielsweise ist einer aussagenlogischen Repräsentation nicht zu entnehmen, dass die Aussage ,,Franz ist krank`` mit der Aussage ,,Hans ist krank`` mehr gemeinsam hat als mit der Aussage ,,es regnet``.

Definition 2.1.1 (Sprache [Aussagenlogik]) Eine Sprache der Aussagenlogik ist gegeben durch ihre Signatur. Zusätzlich gehören zu die logischen Symbole der Aussagenlogik.

Die Menge der Aussagenvariablen ist abzählbar (üblicherweise sogar aufzählbar) und mit jeder der anderen erwähnten Mengen disjunkt, und keine Aussagenvariable besteht aus einer Sequenz von Symbolen, in der ein Symbol aus einer der anderen Mengen vorkommt.

Die alternative Bezeichnung ,,nullstellige Relationssymbole`` für Aussagenvariablen hat ihren Grund darin, dass sie ein Spezialfall der Relationssymbole der Prädikatenlogik erster Stufe sind und zu einer völlig anderen syntaktischen Kategorie gehören als die ,,Variablen`` der Prädikatenlogik erster Stufe (siehe Abschnitt 2.3).

In Kapitel 3 werden wir sehen, dass auch andere Junktoren möglich sind als die in Definition 2.1.1 genannten. Das ist der Grund, warum manche Autoren mehr oder weniger Junktoren einführen. Die Schreibweise der Junktoren variiert auch ein wenig von Autor zu Autor: zum Beispiel wird der Implikationsjunktor statt ⇒ manchmal ⊃ geschrieben.

Als Aussagenvariablen dienen häufig Großbuchstaben mit oder ohne Indizes. In manchen Anwendungen benutzt man für die Aussagenvariablen auch Bezeichner wie in Programmiersprachen. Wir werden in Beispielen meistens Kleinbuchstaben wie p, q, r als Aussagenvariablen verwenden.


Definition 2.1.2 (Formel [Aussagenlogik]) Sei eine Sprache der Aussagenlogik.

Informell und ungenau, weil dabei die Klammerung implizit bleibt, kann die Definition auch so formuliert werden: Sind F1, ..., F1 (für n=0, 1, 2) -Formeln, so sind es auch ihre Verknüpfungen mit n-stelligen Junktoren.

Zum Beispiel ist (p ∨ ¬(q ∧ r)) eine -Formel für jede Sprache der Aussagenlogik, deren Signatur die Symbole p, q und r als Aussagenvariablen definiert. ¬(T ⇒ ⊥) ist eine -Formel jeder Sprache der Aussagenlogik.

Bemerkungen:
  1. In der Terminologie der Theoretischen Informatik würde nicht als ,,Sprache`` bezeichnet, sondern als ,,Alphabet``, und die Menge der -Formeln als eine ,,Sprache`` über .
  2. T und ⊥ sind besondere, nicht zusammengesetzte -Formeln. Wir haben sie nicht als atomare Formeln definiert (eine willkürliche Entscheidung, die aber später gewisse technische Sonderfälle vermeidet).
  3. Die Menge aller -Formeln ist abzählbar, weil nach Definition die Menge der Aussagenvariablen von abzählbar ist. Ist diese Menge darüberhinaus aufzählbar, so ist auch aufzählbar.

Existiert die ,,kleinste Menge``, von der in Definition 2.1.2 die Rede ist? Aus den folgenden Gründen lautet die Antwort ,,ja``.

Zum einen gibt es überhaupt eine Menge, die die Bedingungen 1 bis 3 der Definition 2.1.2 erfüllt, nämlich die Menge aller Wörter, die aus den Symbolen unserer Sprache , also T, ⊥, Aussagenvariablen, Junktoren und Klammern, gebildet werden können (siehe Vorlesung Informatik IV).

Zum anderen erfüllt der Durchschnitt jeder Menge von Mengen, die die Bedingungen 1 bis 3 von Definition 2.1.2 erfüllen, ebenfalls diese Bedingungen. Der Durchschnitt der Menge aller Mengen, die die Bedingungen 1 bis 3 erfüllen, ist also die kleinste Menge, von der Definition 2.1.2 spricht. Jede Menge, die die Bedingungen 1 bis 3 erfüllt, enthält unter anderem das Element T, deshalb ist die kleinste Menge nicht leer.

Prinzip der induktiven Definition.

Das Prinzip, nach dem die -Formeln definiert werden, heißt ,,induktive Definition``. Die Definition von aussagenlogischen Formeln und später von Termen und Formeln der Prädikatenlogik erster Stufe ist nach folgendem Schema ausgedrückt:
,,die Menge der X ist die kleinste Menge, die die folgenden Bedingungen erfüllt: ...``.
Statt dieses Schemas wird oft auch wie folgt formuliert:
,,X werden induktiv definiert durch folgende Bedingungen:...``
wobei manche (vorsichtigen) Autoren am Ende noch hinzufügen:
,,nichts anderes ist ein(e) X``.
Beide Ausdrucksweisen bedeuten das Gleiche. Genauer gesagt: die erste Ausdrucksweise, die auch in Definition 2.1.2 gewählt wurde, ist die Definition der zweiten. Eine Definition der Formeln durch eine kontextfreie Grammatik ist eine ähnliche Definition, da die Menge aller von der Grammatik erzeugten Wörter induktiv definiert ist.

Wir überzeugen uns nun, dass tatsächlich ,,nichts anderes`` eine -Formel sein kann als das, was in den drei Fällen der induktiven Definition vorkommt.

Satz 2.1.3 (Formelgestalt)  Sei eine Sprache der Aussagenlogik. Jede -Formel hat eine der Gestalten T, ⊥ oder atomar oder ¬ G für eine -Formel G oder (G θ H) für -Formeln G und H und einen zweistelligen Junktor θ.

Beweis: Angenommen, das wäre nicht der Fall, und es gäbe eine -Formel F ∈ , die weder die Gestalt T oder ⊥ oder atomar besitzt, noch die Gestalt ¬ G, noch die Gestalt (G θ H). Dann betrachten wir die Menge = \{F} Sie hat folgende Eigenschaften:
(i)
T, ⊥ sowie alle atomaren Formeln sind in , da F keine dieser Gestalten hat.
(ii)
Sei G ∈ , dann ist auch ¬ G ∈ , da F nicht diese Gestalt hat.
(iii)
Seien G ∈ und H ∈ und θ ein zweistelliger Junktor, dann ist auch (G θH) ∈ , da F nicht diese Gestalt hat.
Damit erfüllt die Eigenschaften 1 bis 3 von Definition 2.1.2 und ist andererseits eine echte Teilmenge von , im Widerspruch dazu, dass die kleinste derartige Menge ist. Demnach ist die Annahme falsch. Also hat jede -Formel eine der genannten Gestalten.

Mit diesem Ergebnis ist aber noch nicht ausgeschlossen, dass eine -Formel mehrere dieser Gestalten haben könnte, zum Beispiel durch verschiedene Klammerungen bei verschachtelten zweistelligen Junktoren. Um die Eindeutigkeit der Gestalt von Formeln nachweisen zu können, müssen wir erst eine spezielle Beweistechnik einführen, das sogenannte Prinzip der strukturellen Induktion, das eng mit induktiven Definitionen verwandt ist.

Satz 2.1.4 (strukturelle Induktion)   Sei eine Sprache der Aussagenlogik. Um zu zeigen, dass alle -Formeln eine Eigenschaft  ε haben, genügt es, zu zeigen:
  1. Basisfälle: T und ⊥ sowie alle atomaren -Formeln besitzen die Eigenschaft  ε.
  2. Induktionsfälle:
    1. Wenn eine -Formel F die Eigenschaft ε besitzt, so besitzt auch die Formel ¬ F die Eigenschaft  ε.
    2. Wenn zwei -Formeln F1 und F2 die Eigenschaft  ε besitzen, dann besitzt für jeden zweistelligen Junktor θ auch die Formel (F1 θ F2) die Eigenschaft  ε.


Beweis: Sei die Menge aller -Formeln mit Eigenschaft ε. Die genannten Basisfälle und Induktionsfälle seien für ε erfüllt. Dann ist eine Menge, die die drei Eigenschaften von Definition 2.1.2 erfüllt. Da die kleinste derartige Menge ist, gilt ⊆ , also = .

Im Fall 2(b) ist das Wort ,,zwei`` so gemeint, dass F1 und F1 nicht notwendigerweise verschieden sind. Dies ist ein typisches Beispiel für die Art von Mehrdeutigkeiten, die formale Sprachen vermeiden sollen.

Die Argumentation im obigen Beweis beruht, wie im Beweis des Satzes zuvor, wesentlich auf der in der induktiven Definition geforderten Minimalität der Menge. Bevor wir das neue Beweisprinzip seinerseits verwenden, (u.a. zum Beweis des Eindeutigkeitssatzes), gehen wir noch kurz auf eine Verallgemeinerung ein.

Definition 2.1.5   Sei S eine Menge und Rel eine Menge von Relationen über S. Eine Teilmenge T ⊆ S heißt abgeschlossen bezüglich Rel, wenn für alle R ∈ Rel und für alle x1,...xn-1, y ∈ S gilt: falls x1 ∈ T,...,xn-1 ∈ T und (x1,...xn-1, y) ∈ R, dann y ∈ T.

Zur Veranschaulichung sei S die Menge der natürlichen Zahlen und T die Menge der geraden Zahlen. Die Relation R sei die Menge aller Tripel (x1,x2, y) von natürlichen Zahlen, für die x1+ x2=y ist. Dann ist T abgeschlossen bezüglich {R}, weil die Summe von zwei geraden Zahlen nicht nur eine beliebige natürliche Zahl, sondern eine gerade Zahl ist. Dagegen ist die Menge der ungeraden Zahlen nicht abgeschlossen bezüglich {R}.

Satz 2.1.6 (strukturelle Induktion, Verallgemeinerung)  
Seien S eine Menge, B (für Basis) eine Teilmenge von S, und Rel eine Menge von Relationen über S. Sei T eine Menge mit B ⊆ T ⊆ S, sei T abgeschlossen bezüglich Rel, und es gelte ferner T ⊆ ∪i ∈ ΝBi , wobei

B0:= B
Bi+1:= Bi ∪ ∪R ∈ Rel {yI x1∈ Bi,...xn-1∈ Bi, (x1,...xn-1,y)∈ R}

Dann gilt:T = ∪i ∈ ΝBi.


Beweis: Es reicht, nachzuweisen dass für jedes i ∈ Ν gilt Bi ⊆ T. Diesen Nachweis führen wir durch vollständige Induktion über i.
Induktionsbasis i = 0: Nach Voraussetzung gilt B0 = B und B ⊆ T. Also ist B0 ⊆ T.
Induktionsschritt i → i + 1: Sei Bi ⊆ T. Nach Definition besteht Bi+1 aus Bi sowie zusätzlichen Elementen y ∈ S. Da T abgeschlossen bezüglich Rel ist, gilt für jedes dieser Elemente dass y ∈ T ist. Also ist Bi+1 ⊆ T.

Das verallgemeinerte Beweisprinzip der strukturellen Induktion wird also auf das herkömmliche Beweisprinzip der vollständigen Induktion über die natürlichen Zahlen zurückgeführt, das vorausgesetzt wird. Die herkömmliche vollständige Induktion ist Teil der Axiomatisierung der natürlichen Zahlen - siehe Abschnitt 3.10.

Auf die aussagenlogischen Formeln wird dieses verallgemeinerte Prinzip anwendbar für den Sonderfall S = Menge der -Formeln, B = Menge der atomaren -Formeln sowie und , Rel = {R¬, R∧, R∨, R⇒, R⇔}, wobei R¬ = {(F, ¬F)I F ∈ } und R∧ = {(F, G, (F ∧ G))I F ∈ und G ∈ } usw. und T = Menge der -Formeln mit Eigenschaft ε.

Doch nun zu der Frage, ob die Gestalt von aussagenlogischen Formeln eindeutig bestimmt ist.

Satz 2.1.7 (Eindeutigkeitssatz [Formel, Aussagenlogik])  
Sei eine Sprache der Aussagenlogik. Für jede -Formel F gilt genau eine der folgenden Aussagen:
  1. F = oder F = oder F ist atomar.
  2. Es gibt eine eindeutige -Formel G, so dass F = ¬ G.
  3. Es gibt ein eindeutiges Paar (G, H) von -Formeln und einen eindeutigen zweistelligen Junktor θ, so dass F = (G θ H).

Beweis: Da F in jedem der Fälle mit einem anderen Symbol beginnt, gilt trivialerweise für jede -Formel höchstens eine der drei Aussagen. Um zu zeigen, dass mindestens eine der drei Aussagen auf F zutrifft, verwenden wir Satz 2.1.3. Demnach hat F eine der Gestalten, die in den drei Aussagen vorkommen.
Wenn dieser letzte Nachweis erbracht ist, ist Satz 2.1.7 bewiesen.

Dieser Nachweis ist nicht schwierig, aber etwas mühsam. Wir verwenden folgende Hilfsmittel: für ein Wort H, also eine Sequenz von Symbolen, seien l(H) bzw. r(H) die Anzahl der in H vorkommenden linken (öffnenden) Klammern bzw. rechten (schließenden) Klammern. Unter einem Präfix einer Formel verstehen wir ein nichtleeres Wort, mit dem die Formel beginnt. Ein echter Präfix einer Formel ist ein Präfix, der nicht gleich der Formel ist.

(a)
Jede -Formel hat die Eigenschaft, gleich viele linke wie rechte Klammern zu enthalten.

Durch strukturelle Induktion.
Basisfälle: T, ⊥ und atomare -Formeln enthalten weder linke noch rechte Klammern, also gleich viele.
Induktionsfall Negation: Es gelte l(F) = r(F). Wegen l(¬ F) = l(F) und r(¬ F) = r(F) gilt dann auch l(¬ F) = r(¬ F).
Induktionsfall zweistelliger Junktor θ: Es gelte l(F) = r(F) sowie l(G) = r(G). Wegen l(F θ G) = 1 + l(F) + l(G) und r(F θ G) = 1 + r(F) + r(G) gilt dann auch l(F θ G) = r(F θ G).

(b)
Jede -Formel hat die Eigenschaft, ein vom Negationssymbol verschiedenes Symbol zu enthalten.

Durch strukturelle Induktion.
Basisfälle: Das gilt offensichtlich für T, ⊥ und atomare -Formeln.
Induktionsfall Negation: F enthalte ein vom Negationssymbol verschiedenes Symbol. Dann enthält auch ¬ F dieses Symbol.
Induktionsfall zweistelliger Junktor θ: unabhängig von F und G enthält (F θ G) das vom Negationssymbol verschiedene Symbol (.

(c)
Ein echter Präfix P einer -Formel ist entweder eine Sequenz von Negationssymbolen oder es gilt l(P) > r(P).

Durch strukturelle Induktion.
Basisfälle: Die Behauptung gilt für T, ⊥ und atomare -Formeln , da diese gar keinen echten Präfix haben.
Induktionsfall Negation: Für F gelte, dass jeder echte Präfix Q eine Sequenz von Negationssymbolen ist oderl(Q) > r(Q) ist. Sei P ein echter Präfix von ¬ F. Ist P = ¬, so ist P eine Sequenz von Negationssymbolen und die Behauptung gilt. Ist P = ¬ Q für einen echten Präfix Q von F, so ist entweder P eine Sequenz von Negationssymbolen oder l(P) = l(Q) > r(Q) = r(P) und die Behauptung gilt für ¬ F.
Induktionsfall zweistelliger Junktor θ: Für F und G gelte, dass jeder echte Präfix Q eine Sequenz von Negationssymbolen ist oder l(Q) > r(Q) ist. In jedem der beiden Fälle gilt also l(Q) ≥ r(Q). Sei P ein echter Präfix von (F θ G). Ist P = (, so gilt l(P) > r(P). Ist P= (Q mit Q echter Präfix von F, so gilt l(P) = 1 + l(Q) ≥ 1 + r(Q) > r(Q) = r(P). Ist P = (F oder P = (F θ, so ist l(P) = 1 + l(F) = 1 + r(F) > r(F) = r(P). Ist P = (F θ Q mit Q echter Präfix G, so ist l(P) = 1 + l(F) + l(Q = 1 + r(F) + l(Q) ≥ 1 + r(F) + r(Q) > r(F) + r(Q) = r(P). Stets gilt also l(P) > r(P) und damit die Behauptung für (F θ G).

(d)
Ein echter Präfix einer -Formel ist keine -Formel.

Dies ergibt sich unmittelbar aus (c), (b) und (a).

(e)
Ist eine -Formel von der Gestalt (G1 θ1 H1) sowie von der Gestalt (G2 θ2 H2), so gilt G1 = G2 und θ1 = θ2 und H1 = H2.

Sonst wäre G1 ein echter Präfix von G2 oder G2 ein echter Präfix von G1, im Widerspruch zu (d).

Damit ist die gewünschte Eindeutigkeit für die dritte Aussage von Satz 2.1.7 nachgewiesen.

Der Satz 2.1.7 besagt, dass die in der Definition 2.1.2 implizite Grammatik eindeutig ist. Diese Eindeutigkeit berechtigt dazu, aussagenlogische Formeln in der vertrauten Weise durch Bäume darzustellen, wie z.B. die Formel (p ∨ ¬ (q ∧ r)) durch den Baum:

∨
/     \
p     ¬
      I
      ∧
     /     \
     q     r

Die Eindeutigkeit wird wesentlich durch die Klammerung von Formeln der Gestalt (F θ G) erreicht. Ohne diese Klammern wäre zum Beispiel die syntaktische Struktur der Symbolfolge p ∧ q ∨ r nicht eindeutig.

Warum will man die Syntax so definieren, dass der Eindeutigkeitssatz gilt? Wenn die Syntax mehrdeutig ist, gilt dies auch für die Semantik. Ohne eindeutige Syntax hätte man also auch keine eindeutige Bedeutung. Mehrdeutigkeiten können Missverständnisse verursachen. Der Zweck einer formalen Sprache besteht aber gerade darin, Missverständnisse auszuschließen. Mehrdeutigkeiten erschweren überdies die Automatisierung oder machen sie sogar ganz unmöglich.

Für die natürliche Sprache gilt kein Eindeutigkeitssatz. Der englische Satz ,,Male guides fish.`` hat zum Beispiel zwei völlig verschiedene syntaktische Strukturen, bei denen die Wörter unterschiedlichen Wortarten zugeordnet werden: zum einen die Struktur Subjekt-Verb-Objekt mit dem Verb ,,to guide`` und der Bedeutung ,,Männchen führt Fisch(e)``, zum anderen die Struktur Subjekt-Verb mit dem Verb ,,to fish`` und der Bedeutung ,,Männliche Führer fischen``. Im Deutschen sind solche Beispiele wegen der Flexionsendungen und der Groß-/Kleinschreibung seltener, aber es gibt sie, zum Beispiel die Frage: ,,Fliegen sieben Bienen ?`

Meistens bevorzugt man in solchen Beispielen zwar jeweils eine der Lesarten, aber nicht aus syntaktischen Gründen, sondern aus semantischen.

Definition 2.1.8 (Teilformel) 
Sei eine Sprache der Aussagenlogik. Die unmittelbaren Teilformeln einer -Formel werden wie folgt definiert:
  1. T, ⊥ und atomare -Formeln haben keine unmittelbare Teilformel.
  2. F ist die einzige unmittelbare Teilformel von ¬ F.
  3. F und G sind die einzigen unmittelbaren Teilformeln von (F θ G), wobei θ ein zweistelliger Junktor ist.

Die Menge der Teilformeln einer -Formel F ist die kleinste Menge, die F enthält sowie alle unmittelbaren Teilformeln aller ihrer Elemente.

Informell (weil unpräzis) können die Teilformeln einer Formel F als die Teilwörter von F definiert werden, die -Formeln sind.

Meta- und Objektsprachen.

Eine Aussage wie ,,wenn eine Formel die Gestalt (F ⇒ G) hat, dann sind F und G eindeutig bestimmt`` enthält eine Implikation in der Objektsprache, in der wir Formeln bilden können, und eine andere Implikation in der Metasprache, in der wir über Formeln und andere Dinge der Objektsprache reden. Man darf die beiden Sprachebenen nicht durcheinanderbringen. Wir reservieren deshalb Symbole wie ⇒ für die Objektsprache und benutzen in der Metasprache nie Symbole, sondern verbale Umschreibungen wie ,,wenn ...dann``.

Wenn eine Objektsprache z.B. Integrale oder Halbgruppen oder Wahrscheinlichkeitsverteilungen beschreibt, kommen Junktoren und Quantoren nur in der Metasprache vor, und man benutzt dann üblicherweise die Symbole auf der Ebene der Metasprache. In diesen Fällen kann kein Konflikt mit den Symbolen der Objektsprache entstehen. Die Logik ist das einzige wissenschaftliche Gebiet, in dem die Symbole für Junktoren und Quantoren in der Objektsprache vorkommen und deshalb nicht mehr für die Metasprache zur Verfügung stehen, also das einzige Gebiet, in dem das Problem eines Konflikts zwischen den Symbolen überhaupt auftritt.

Validierung