Implikation und Kontraposition

Implikation und Kontraposition

Studium
(A⇒B)  ⇔  (¬B⇒¬A)  ⇔  (¬A∨B)(A \Rightarrow B) \;\Leftrightarrow\; (\neg B \Rightarrow \neg A) \;\Leftrightarrow\; (\neg A \vee B)
A,BA, B
Aussagen, die wahr oder falsch sind; A heißt Voraussetzung, B Folgerung
⇒\Rightarrow
Implikation, „wenn A, dann B“
¬\neg
Negation, „nicht“
∨\vee
Disjunktion „oder“ (nicht ausschließend)
⇔\Leftrightarrow
logische Äquivalenz, beide Seiten haben immer denselben Wahrheitswert

Eine Implikation A ⇒ B ist gleichwertig zu ihrer Kontraposition ¬B ⇒ ¬A und zur Aussage ¬A ∨ B.

Erklärung

Eine Implikation A⇒BA \Rightarrow B („wenn AA, dann BB“) ist nur in einem Fall falsch: wenn AA wahr und BB falsch ist. Ist AA falsch, ist die Implikation immer wahr, egal was BB ist.

AABBA⇒BA \Rightarrow B¬B⇒¬A\neg B \Rightarrow \neg A¬A∨B\neg A \vee BB⇒AB \Rightarrow A
wwwwwwwwwwww
wwffffffffww
ffwwwwwwwwff
ffffwwwwwwww

Die Spalten drei bis fünf stimmen überein. Daraus folgen zwei Umformungen:

  • Kontraposition: A⇒BA \Rightarrow B ist gleichwertig zu ¬B⇒¬A\neg B \Rightarrow \neg A. Statt „aus AA folgt BB“ kann man zeigen „wenn BB nicht gilt, gilt auch AA nicht“.
  • Als Oder-Aussage: A⇒BA \Rightarrow B ist gleichwertig zu ¬A∨B\neg A \vee B. Mit den De-Morgan-Regeln folgt daraus die Verneinung: ¬(A⇒B)⇔A∧¬B\neg(A \Rightarrow B) \Leftrightarrow A \wedge \neg B.

Die letzte Spalte zeigt: Die Umkehrung B⇒AB \Rightarrow A ist nicht gleichwertig. Gelten beide Richtungen, schreibt man A⇔BA \Leftrightarrow B.

Sprechweisen: Bei A⇒BA \Rightarrow B ist AA hinreichend für BB und BB notwendig für AA.

Beispiele

Beweis durch Kontraposition: Zu zeigen ist „Ist n2n^2 gerade, dann ist nn gerade“ für ganze Zahlen nn. Direkt ist das umständlich. Die Kontraposition lautet „Ist nn ungerade, dann ist n2n^2 ungerade“. Mit n=2k+1n = 2k + 1 folgt

n2=(2k+1)2=4k2+4k+1=2(2k2+2k)+1n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1

also ist n2n^2 ungerade. Für n=7n = 7: 49=2⋅24+149 = 2 \cdot 24 + 1.

Alltagssprache: „Wenn es regnet, ist die Straße nass.“ Kontraposition: „Wenn die Straße nicht nass ist, regnet es nicht.“ Die Umkehrung „Wenn die Straße nass ist, regnet es“ folgt daraus nicht; die Straße kann auch aus anderen Gründen nass sein.

Verneinung: Die Verneinung von „Wenn eine Zahl durch 4 teilbar ist, ist sie gerade“ lautet „Es gibt eine Zahl, die durch 4 teilbar und nicht gerade ist“, nicht „Wenn eine Zahl durch 4 teilbar ist, ist sie ungerade“.

Typische Fehler

  • Umkehrung statt Kontraposition beweisen. Aus A⇒BA \Rightarrow B folgt nicht B⇒AB \Rightarrow A. Auch ¬A⇒¬B\neg A \Rightarrow \neg B ist nicht gleichwertig, sondern nur eine andere Form der Umkehrung.
  • Bei der Kontraposition nur negieren, nicht vertauschen. Richtig ist ¬B⇒¬A\neg B \Rightarrow \neg A, nicht ¬A⇒¬B\neg A \Rightarrow \neg B.
  • Eine Implikation mit falscher Voraussetzung für falsch halten. „Wenn 1=21 = 2, dann ist der Mond aus Käse“ ist wahr, weil die Voraussetzung falsch ist.
  • Die Verneinung wieder als Implikation schreiben. ¬(A⇒B)\neg(A \Rightarrow B) ist A∧¬BA \wedge \neg B, keine Wenn-dann-Aussage.

Verwandte Formeln