Formelsammlung Logik

Aussagenlogik

Logische Werte:

• wahr (true) 1
• falsch (false) 0

Erweiterte Logik:

• unbestimmt (Don’t care) X

Logische Verknüpfungen werden Junktionen genannt. Es gibt drei grundlegende Junktionen, welche auch logische Operatoren genannt werden.

Operation	sparachliche Umschreibung	Definition	Operator (Junktor) und Symbol
Negation	„nicht“	Die Negation eines logischen Werts ist genau dann wahr, wenn der Wert falsch ist.	Negator $\neg$
Konjunktion	„und“	Die Konjunktion von zwei Werten ist genau dann wahr, wenn beide Werte wahr sind.	Konjunktor $\wedge$
Disjunktion	„oder“	Die Disjunktion von zwei Werten ist genau dann wahr, wenn mindestens ein Wert wahr ist.	Disjunktor $\vee$

Um die Symbole des Konjunktor und des Disjunktor leicht auseinander halten zu können, gibt es die Eselsbrücke mit den drei O: "Oder ist Oben Offen"

Darüber hinaus gibt es noch folgende, auf eine Kombination der Grundoperatoren rückführbare Junktoren:

Operation	Umschreibung	Definition	Operator und Symbol
Subjunktion (materiale Implikation)	„wenn …, dann …“		Subjunktor $\rightarrow$ (Pfeil)
Bisubjunktion (Äquivalenz)	„wenn … dann … und umgekehrt“		Bisubjunktor $\leftrightarrow$ (Doppelpfeil)

Die Wahrheitstafeln der Junktoren

$a$ $\neg a$ w f f w

$a$ $b$ $(a\wedge b)$ w w w w f f f w f f f f

$a$ $b$ $(a \vee b)$ w w w w f w f w w f f f

$a$ $b$ $(a \rightarrow b)$ w w w w f f f w w f f w

$a$ $b$ $(a \leftrightarrow b)$ w w w w f f f w f f f w

Logische Grundgesetze

Gesetz der doppelten Negation	$x = \neg (\neg x)$
Kommutativgesetze	$x \and y = y \and x$	$x \or y = y \or x$
Assoziativgesetze	$x \and ( y \and z )=(x \and y) \and z$	$(x\or y)\or z=x\or(y\or z)$
Distributivgesetze	$x \and ( y \or z ) = ( x \and y ) \or ( x \and z )$	$x \or ( y \and z ) = ( x \or y ) \and ( x \or z )$
Idempotenz	$x \and x = x$	$x \or x = x$
Gesetze der Negation (Tautologie / Kontradiktion)	$x \or \neg x = 1$	$x \and \neg x = 0$
Absorptionsgesetze	$x \and ( x \or y ) = x$	$x \or ( x \and y ) = x$
Neutralität	$(x \and \neg x) \or y = y$	$(x \or \neg x) \and y = y$
De Morgansche Gesetze	$\neg ( x \and y ) = \neg x \or \neg y$	$\neg ( x \or y ) = \neg x \and \neg y$
Operationen mit 0 und 1	$0 \and x = 0$	$1 \or x = 1$
	$1 \and x = x$	$0 \or x = x$
	$\neg 0 = 1$	$\neg 1 = 0$

Implikation

$(a \rightarrow b) \leftrightarrow \neg a \or b$

$(a \rightarrow b) \leftrightarrow (\neg b \rightarrow \neg a)$

$(a \rightarrow b) \leftrightarrow \neg(a \and \neg b)$

Äquivalenz und Antivalenz

$(a \leftrightarrow b) = (a \and b) \or (\neg a \and \neg b) = (a \or \neg b) \and (\neg a \or b) = (a \rightarrow b) \and (b \rightarrow a)$

$(a \not \leftrightarrow b) = (a \and \neg b) \or (\neg a \and b) = (a \or b) \and (\neg a \or \neg b)$

Sheffer-Strich (NAND)

• $\neg a$ ist äquivalent zu $(a | a)\,$
• $(a \wedge b)$ ist äquivalent zu $((a | b) | (a | b))\,$
• $(a \vee b)$ ist äquivalent zu $((a | a) | (b | b))\,$

Schlussregeln

Modus Ponens	$((a \rightarrow b) \and a) \rightarrow b$
Modus Tollens	$((a \rightarrow b) \and \neg b) \rightarrow \neg a$
Hypothetischer Syllogismus	$(a \rightarrow b) \and (b \rightarrow c) \rightarrow (a \rightarrow c)$
Disjunktiver Syllogismus	$((a \or b) \and \neg a) \rightarrow b$

Prädikatenlogik

Quantoren

$\forall _x p=\neg (\exist _x \neg p)$	$\exist _x p=\neg (\forall _x \neg p)$
$\neg \forall _x p= (\exist _x \neg p)$	$\neg \exist _x p= (\forall _x \neg p)$

Pränexform

$(\forall x \phi) \land \psi$ = $\forall x ( \phi \land \psi)$,	$(\forall x \phi) \lor \psi$ = $\forall x ( \phi \lor \psi)$;
$(\exists x \phi) \land \psi$ = $\exists x (\phi \land \psi)$,	$(\exists x \phi) \lor \psi$ = $\exists x (\phi \lor \psi)$.
$\lnot \exists x \phi$ = $\forall x \lnot \phi$	$\lnot \forall x \phi$ = $\exists x \lnot \phi$.
$(\forall x \phi ) \rightarrow \psi$ = $\exists x (\phi \rightarrow \psi)$,	$(\exists x \phi ) \rightarrow \psi$ = $\forall x (\phi \rightarrow \psi)$.
$\phi \rightarrow (\exists x \psi)$ = $\exists x (\phi \rightarrow \psi)$,	$\phi \rightarrow (\forall x \psi)$ = $\forall x (\phi \rightarrow \psi)$.