Aussagenlogische Beweismuster

 Viele häufig zu findende Beweisstrukturen der Mathematik beruhen auf aussagenlogischen Äquivalenzen. Wir wollen einige von ihnen zusammenstellen.

 Zunächst betrachten wir Beweismuster, die die Implikation betreffen. Dabei verwenden wir die Gleichwertigkeit von ¬ A und A → ⊥. Bei unserem ∧, →, ⊥-Ansatz gilt sie per Definition, und bei der Wahl von ∧ und ¬ als Basisjunktoren ist ¬ A ↔ A → ⊥ eine Tautologie, wobei ⊥ definiert wird als A₀ ∧ ¬ A₀ für eine beliebige Aussage A₀.

 Die Äquivalenz von ¬ A und A → ⊥ wird in der Mathematik für die berühmt-berüchtigten Widerspruchsbeweise verwendet, die in gelehrten Kreisen auch als Beweise des Typs reductio ad absurdum bekannt sind. Sollen wir eine Aussage B beweisen, so können wir wie folgt vorgehen. Wir nehmen ¬ B an und argumentieren dann solange, bis wir eine offenbar falsche Aussage abgeleitet haben. Damit haben wir dann ¬ B  →  ⊥, also ¬ ¬ B gezeigt. Streichen der doppelten Negation liefert nun wie gewünscht B. Wir halten fest:

 Ist die Aussage, die wir beweisen wollen, von der Form ¬ A, so nehmen wir natürlich nicht ¬ ¬ A an, sondern gleich A selbst. Wir zeigen dann ⊥, und haben also A → ⊥ und damit wie gewünscht ¬ A gezeigt. Hier kann man sich also das Streichen der doppelten Negation sparen.

 Eng mit den Widerspruchsbeweisen verwandt sind die sog. indirekten Beweise, die auf dem Kontrapositionsgesetz beruhen. Das Prinzip des indirekten Beweisens besteht darin, anstelle von A → B zu zeigen, dass ¬ B → ¬ A gilt:

 Indirekte Beweise werden in der Mathematik sehr häufig verwendet. Ob einem die Beweisstruktur A → B oder aber ¬ B → ¬ A angemessener, klarer, oder einfacher erscheint, muss man von Fall zu Fall entscheiden, und oft ist es auch eine Frage des Geschmacks. Speziell gilt dies für Implikationen der Form A → ¬ B, da dann die Kontraposition gleichwertig ist zu B → ¬ A.

 Ein weiteres wichtiges Beweismuster ist die Fallunterscheidung. Zu zeigen ist eine Aussage A. Dies kann dadurch erreicht werden, dass man eine geeignete Aussage B findet, für die man sowohl B → A als auch ¬ B → A beweisen kann. Dann hat man A bewiesen, denn für alle B ist A ↔ (B → A) ∧ (¬ B → A) eine Tautologie. Wir halten wieder fest:

 Auch hier hat man sich also eine zusätzliche Voraussetzung verschafft, allerdings auf Kosten eines zweigeteilten Arguments. Das Finden einer geeigneten Aussage B ist eine Frage der mathematischen Erfahrung und Kreativität. Auch Varianten können hilfreich sein, zum Beispiel eine Aufspaltung des zweiten Falls in zwei Unterfälle.

 Schließlich gibt es noch das Muster des ökonomischen Beweises einer Äquivalenzenkette. Zu zeigen ist, dass Aussagen A₁, …, A_n paarweise äquivalent sind. D. h. zu zeigen ist, dass A_i ↔ A_j für alle i ≠ j gilt. Hierzu kann man wie folgt zyklisch vorgehen:

 Hinter diesem Beweismuster steckt die sog. Transitivität der Implikation, die auch als Kettenschluss bezeichnet wird: Gilt A → B und B → C, so gilt auch A → C.

 Es kann bei diesem Vorgehen sehr nützlich sein, die Aussagen A₁, …, A_n in einer geeigneten Reihenfolge so anzuordnen, dass die zu zeigenden Implikationen sich natürlich auseinander ergeben und dadurch der Beweis möglichst einfach und kurz wird. Wie man eine solche gute Anordnung findet, ist eine Frage, die sich oft nur experimentell beantworten lässt.

 Die paarweise Äquivalenz von drei Aussagen A₁, A₂, A₃ ist gleichwertig zu (A₁ ↔ A₂) ∧ (A₂ ↔ A₃), nicht aber zu (A₁ ↔ A₂) ↔ A₃ oder zu A₁ ↔ (A₂ ↔ A₃). Üblicherweise wird aber vereinbart, dass die klammerfreie Äquivalenzenkette die paarweise Äquivalenz der beteiligten Aussagen bedeuten soll, d. h.

A₁ ↔ A₂ ↔ A₃  ist definiert als  (A₁ ↔ A₂)  ∧  (A₂ ↔ A₃).

 Analoges gilt für A₁ ↔ A₂ ↔ … ↔ A_n. Dagegen wird A₁ → A₂ → A₃ oft nicht als (A₁ → A₂) ∧ (A₂ → A₃) gelesen, sondern als A₁ → (A₂ → A₃). Der Grund ist, dass A₁ → (A₂ → A₃) äquivalent ist zu A₁ ∧ A₂ → A₃. Unter iterierter Rechtsklammerung gilt dann allgemeiner

A₁ → A₂ → … → A_n → A_n + 1  gdw  A₁ ∧ … ∧ A_n → A_n + 1.

Damit haben von rechts her geklammerte Implikationsketten eine überraschend einfache und sympathische Bedeutung.

 Welche Bedeutung eine Kette von Folgerungen hat, ist meistens aus dem Kontext heraus klar. Z. B. bedeutet

A ∧ B  →  C ∨ D,

dass (A → C) → (A ∧ B → C), und dass (A ∧ B → C) → (A ∧ B → C ∨ D). Man kann hier auch stilisierte Pfeile oder Doppelpfeile statt „impliziert“ verwenden. Erfahrungsgemäß führen die speziell vom Anfänger gerne im Übermaß verwendeten Doppelpfeile aber zu schlecht lesbaren Argumenten, insbesondere dann, wenn das nächste Glied der Implikationskette nicht unmittelbar aus dem vorhergehenden folgt, sondern weitere Voraussetzungen oder Zwischenresultate in den Schluss eingehen. In der Regel ist dann ein Ausschreiben des Arguments in ganzen Sätzen vorzuziehen.