De-Morgan-Regeln der Logik

Studium

\neg(A \wedge B) \Leftrightarrow \neg A \vee \neg B, \qquad \neg(A \vee B) \Leftrightarrow \neg A \wedge \neg B

$A, B$: Aussagen, die wahr oder falsch sind
$\neg$: Negation, „nicht“
$\wedge, \vee$: Konjunktion „und“ sowie Disjunktion „oder“ (nicht ausschließend)
$\Leftrightarrow$: logische Äquivalenz, beide Seiten haben immer denselben Wahrheitswert

Eine verneinte Und-Aussage wird zu einer Oder-Aussage der Verneinungen und umgekehrt.

Erklärung

Die De-Morgan-Regeln sagen, wie man eine Und- oder Oder-Verknüpfung verneint: Die Negation wird auf beide Teile verteilt, und dabei wird aus „und“ ein „oder“ und aus „oder“ ein „und“.

Wahrheitstafel der ersten Regel ( $w$ = wahr, $f$ = falsch):

$A$	$B$	$A \wedge B$	$\neg(A \wedge B)$	$\neg A \vee \neg B$
$w$	$w$	$w$	$f$	$f$
$w$	$f$	$f$	$w$	$w$
$f$	$w$	$f$	$w$	$w$
$f$	$f$	$f$	$w$	$w$

Die letzten beiden Spalten stimmen in jeder Zeile überein. Die zweite Regel prüft man genauso.

Für Quantoren gelten die entsprechenden Regeln:

\neg\, \forall x : P(x) \;\Leftrightarrow\; \exists x : \neg P(x), \qquad \neg\, \exists x : P(x) \;\Leftrightarrow\; \forall x : \neg P(x)

Man braucht sie beim Widerspruchsbeweis, bei der Kontraposition und beim Vereinfachen von Bedingungen in Programmen: !(a && b) ist dasselbe wie !a || !b.

Beispiele

Die Aussage „ $x > 0$ und $x < 5$ “ beschreibt das Intervall $(0, 5)$ . Ihre Verneinung ist

\neg(x > 0 \wedge x < 5) \;\Leftrightarrow\; x \leq 0 \vee x \geq 5

Die Verneinung von „Jede Folge ist beschränkt“ lautet „Es gibt eine Folge, die nicht beschränkt ist“, nicht „Keine Folge ist beschränkt“.

Stetigkeit verneinen: Aus $\forall \varepsilon > 0\ \exists \delta > 0\ \forall x : |x - x_0| < \delta \Rightarrow |f(x) - f(x_0)| < \varepsilon$ wird

\exists \varepsilon > 0\ \forall \delta > 0\ \exists x : |x - x_0| < \delta \wedge |f(x) - f(x_0)| \geq \varepsilon

Typische Fehler

Den Junktor nicht umdrehen. $\neg(A \wedge B)$ ist nicht $\neg A \wedge \neg B$ . „Nicht beide Lampen brennen“ ist auch dann wahr, wenn genau eine brennt.
Bei Ungleichungen falsch verneinen. Die Verneinung von $x < 5$ ist $x \geq 5$ , nicht $x > 5$ .
Quantoren nicht mitdrehen. Beim Verneinen wird jeder $\forall$ zu $\exists$ und umgekehrt, und die Implikation $P \Rightarrow Q$ wird zu $P \wedge \neg Q$ .

De-Morgan-Regeln der Logik