1.2 Verknüpfungen und Beweise

Logische Verknüpfungen

Als Nächstes legen wir fest, wie sich aus zwei Aussagen neue Aussagen bilden lassen.

Definition 1.3 (Junktoren). Die Wahrheitswerte der wichtigsten Verknüpfungen zweier Aussagen \(a\) und \(b\) werden durch eine Wahrheitstabelle festgelegt:

Zeichen Name gelesen als
\(a\wedge b\) Konjunktion „\(a\) und \(b\)“
\(a\vee b\) Disjunktion „\(a\) oder \(b\) oder beides“
\(a\mathbin{\dot\vee}b\) Kontravalenz „entweder \(a\) oder \(b\)“
\(a\Rightarrow b\) Implikation „wenn \(a\), dann \(b\)“
\(a\Leftrightarrow b\) Äquivalenz „\(a\) genau dann, wenn \(b\)“

Die zugehörige Wahrheitstabelle ist:

\(a\) \(b\) \(a\wedge b\) \(a\vee b\) \(a\mathbin{\dot\vee}b\) \(a\Rightarrow b\) \(a\Leftrightarrow b\)
\(1\) \(1\) \(1\) \(1\) \(0\) \(1\) \(1\)
\(1\) \(0\) \(0\) \(1\) \(1\) \(0\) \(0\)
\(0\) \(1\) \(0\) \(1\) \(1\) \(1\) \(0\)
\(0\) \(0\) \(0\) \(0\) \(0\) \(1\) \(1\)

Implikationen lesen

Um sprachlich auszudrücken, dass eine Implikation \(a\Rightarrow b\) gilt, gibt es viele gleichwertige Formulierungen:

  • \(a\) impliziert \(b\)
  • aus \(a\) folgt \(b\)
  • wenn \(a\) gilt dann gilt auch \(b\)
  • \(a\) ist hinreichend für \(b\)
  • \(b\) ist notwendig für \(a\)

Das folgende Beispiel übersetzt die abstrakten Begriffe „notwendig“ und „hinreichend“ in eine konkrete Teilbarkeitsaussage.

Beispiel: Implikation

Für eine ganze Zahl \(n\) betrachten wir

\[a:\Leftrightarrow\; 4\mid n \qquad\text{und}\qquad b:\Leftrightarrow\; 2\mid n.\]

Aufgabenstellung. Untersuchen Sie, welche der beiden Bedingungen notwendig beziehungsweise hinreichend für die andere ist und ob \(a\Leftrightarrow b\) gilt.

\(4\mid n\) bedeutet „\(4\) teilt \(n\)“, also ist \(n\) ein ganzzahliges Vielfaches von \(4\). Ist eine Zahl durch 4 teilbar, dann ist sie auch durch 2 teilbar, anders ausgedrückt gilt: Aus \(4\mid n\) folgt \(2\mid n\), also gilt \(a\Rightarrow b\).

  • Hinreichend: Aus \(4\mid n\) folgt \(n=4k=2(2k)\) für ein \(k\in\mathbb Z\). Also ist \(n\) durch 2 teilbar (also gerade). Durch \(4\) teilbar zu sein ist damit hinreichend dafür, durch 2 teilbar zu sein.
  • Notwendig: Soll \(4\mid n\) gelten, muss \(n\) insbesondere durch 2 teilbar sein. Gerade zu sein reicht allein aber nicht: \(6\) ist gerade, jedoch nicht durch \(4\) teilbar. Gerade zu sein ist notwendig dafür, durch \(4\) teilbar zu sein (aber nicht hinreichend)

Deshalb gilt \(b\not\Rightarrow a\) und insbesondere \(a\not\Leftrightarrow b\).

Bindungsstärke und Klammern

Ohne Klammern gilt die Konvention

\[ \text{Negation }\bar a \quad\text{vor}\quad \wedge \quad\text{vor}\quad \vee \quad\text{vor}\quad \mathbin{\dot\vee} \quad\text{vor}\quad \Rightarrow \quad\text{vor}\quad \Leftrightarrow. \]

Tautologien und De Morgan

Für das Erkennen allgemeingültiger Schlussformen benötigen wir einen weiteren Begriff.

Definition 1.4 (Tautologie). Eine zusammengesetzte Aussage heißt Tautologie, wenn sie für jede Belegung ihrer Teilaussagen wahr ist.

Beispiele sind der Satz „Heute regnet es oder es regnet nicht“ und die mathematische Aussage

\[ (x\ge 0)\vee(x<0),\qquad x\in\mathbb R. \]

Beide haben die Form \(a\vee\bar a\) und sind unabhängig vom konkreten Wahrheitswert von \(a\) wahr.

Die wichtigsten Regeln für die Negation zusammengesetzter Aussagen fasst der folgende Satz zusammen.

Satz 1.1 (De-Morgansche Regeln). Für Aussagen \(a\) und \(b\) gilt

\[ \overline{a\wedge b} \Leftrightarrow (\bar a\vee\bar b), \qquad \overline{a\vee b} \Leftrightarrow (\bar a\wedge\bar b). \tag{1.1}\]

In Gleichung 1.1 werden beim Negieren „und“ und „oder“ vertauscht und beide Teilaussagen negiert.

Im nächsten Beispiel wird eine der beiden Regeln auf eine alltagssprachliche Aussage angewendet.

Beispiel: De Morgan im Alltag

Aufgabenstellung. Negieren Sie die Aussage „Die Datei ist lokal oder in der Cloud gespeichert“.

Die Negation lautet: „Die Datei ist nicht lokal und nicht in der Cloud gespeichert“. Es genügt für die Negation also nicht, nur einen der beiden Speicherorte auszuschließen. Genau dies beschreibt Gleichung 1.1.

Rechengesetze

Die Rechenregeln werden in drei Gruppen zusammengefasst. Wie in der gewöhnlichen Algebra erlauben die ersten Regeln das Vertauschen, Umklammern und Verteilen.

Satz 1.2 (Kommutativ-, Assoziativ- und Distributivgesetze). Für Aussagen \(a\), \(b\) und \(c\) gelten die folgenden Äquivalenzen.

Kommutativgesetze

\[ a\wedge b \Leftrightarrow b\wedge a, \qquad a\vee b \Leftrightarrow b\vee a. \]

Assoziativgesetze

\[ \begin{aligned} (a\wedge b)\wedge c &\Leftrightarrow a\wedge(b\wedge c),\\ (a\vee b)\vee c &\Leftrightarrow a\vee(b\vee c). \end{aligned} \]

Distributivgesetze

\[ \begin{aligned} a\wedge(b\vee c) &\Leftrightarrow (a\wedge b)\vee(a\wedge c),\\ a\vee(b\wedge c) &\Leftrightarrow (a\vee b)\wedge(a\vee c). \end{aligned} \]

Die zweite Gruppe vereinfacht verschachtelte Aussagen und führt Implikation und Äquivalenz auf die grundlegenden Junktoren zurück.

Satz 1.3 (Absorptionsgesetze und Umschreiben von Implikation und Äquivalenz). Für Aussagen \(a\) und \(b\) gilt:

Absorptionsgesetze

\[ a\wedge(a\vee b) \Leftrightarrow a, \qquad a\vee(a\wedge b) \Leftrightarrow a. \]

Implikation und Äquivalenz

\[ \begin{aligned} a\Rightarrow b &\Leftrightarrow \bar a\vee b,\\ a\Leftrightarrow b &\Leftrightarrow (a\Rightarrow b)\wedge(b\Rightarrow a). \end{aligned} \]

Die dritte Gruppe beschreibt, wie sich identische Aussagen, feste Wahrheitswerte und eine doppelte Negation vereinfachen lassen.

Satz 1.4 (Elementarregeln für Wahrheitswerte und Negation). Für jede Aussage \(a\) gelten die folgenden Äquivalenzen.

Gesetze mit wahr und falsch

\[ \begin{aligned} a\wedge1&\Leftrightarrow a, & a\vee0&\Leftrightarrow a,\\ a\wedge0&\Leftrightarrow0, & a\vee1&\Leftrightarrow1. \end{aligned} \]

Idempotenz und doppelte Negation

\[ a\wedge a \Leftrightarrow a, \qquad a\vee a \Leftrightarrow a, \qquad \overline{\bar a} \Leftrightarrow a. \]

Ausgeschlossenes Drittes und Widerspruch

\[ a\vee\bar a \Leftrightarrow1, \qquad a\wedge\bar a \Leftrightarrow0. \]

Beweisverfahren

Um eine Aussage \(b\) unter einer Voraussetzung \(a\) zu beweisen, sind besonders wichtig:

  1. Direkter Beweis: von \(a\) schrittweise zu \(b\) gelangen.
  2. Kontraposition: statt \(a\Rightarrow b\) die äquivalente Aussage \(\bar b\Rightarrow\bar a\) beweisen.
  3. Widerspruchsbeweis: \(a\) und \(\bar b\) annehmen und daraus einen Widerspruch herleiten.

Beim Widerspruchsbeweis muss klar benannt werden, welche Behauptung negiert wird und worin der Widerspruch besteht. Ein überraschendes Zwischenergebnis allein ist noch kein Widerspruch.

Das folgende Beispiel zeigt, wie eine Implikation durch ihre Kontraposition bewiesen werden kann.

Beispiel: Kontraposition

Aufgabenstellung. Beweisen Sie: Ist \(n^2\) gerade, so ist \(n\) gerade.

Die Kontraposition lautet: Ist \(n\) ungerade, so ist auch \(n^2\) ungerade. Jede ungerade ganze Zahl besitzt die Form \(n=2k+1\) mit \(k\in\mathbb Z\). Damit folgt

\[ n^2=(2k+1)^2 =4k^2+4k+1 =2(2k^2+2k)+1. \]

Da \(2k^2+2k\) eine ganze Zahl ist, hat der letzte Ausdruck die Form \(2\ell+1\). Also ist \(n^2\) ungerade und die ursprüngliche Aussage bewiesen.

Ein direkter Beweis beginnt dagegen bei den Voraussetzungen und führt ohne Umweg zur behaupteten Aussage.

Beispiel: Direkter Beweis

Aufgabenstellung. Beweisen Sie direkt: Die Summe zweier gerader ganzer Zahlen ist gerade.

Seien \(m\) und \(n\) gerade. Dann existieren \(k,\ell\in\mathbb Z\) mit \(m=2k\) und \(n=2\ell\). Folglich

\[m+n=2k+2\ell=2(k+\ell).\]

Da \(k+\ell\in\mathbb Z\) gilt, ist \(m+n\) gerade. \(\square\)

Zusammenfassung

  • Wahrheitstabellen legen die Bedeutung der logischen Verknüpfungen eindeutig fest; eine Implikation ist nur im Fall \(1\Rightarrow0\) falsch.
  • In \(a\Rightarrow b\) ist \(a\) hinreichend für \(b\) und \(b\) notwendig für \(a\).
  • Bindungsregeln und Klammern bestimmen, in welcher Reihenfolge eine zusammengesetzte Aussage gelesen wird.
  • Tautologien, die De-Morganschen Regeln und weitere Rechengesetze ermöglichen das systematische Umformen logischer Ausdrücke.
  • Aussagen lassen sich insbesondere direkt, durch Kontraposition oder durch einen Widerspruch beweisen.