Formelsammlung Logik

Dies i​st eine Formelsammlung z​um mathematischen Teilgebiet d​er Logik.

Aussagenlogik

Logische Werte:

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

Erweiterte Logik:

• unbestimmt (Don’t-Care) X

Aussagen können d​urch logische Operatoren, a​uch Junktoren genannt, verknüpft werden. Die üblichen Junktoren sind:

Name	Symbol	sprachliche Umschreibung	Operation	Definition
Negator	${\displaystyle \neg }$	nicht	Negation	Die Negation eines logischen Werts ist genau dann wahr, wenn der Wert falsch ist.
Konjunktor	${\displaystyle \land }$	und	Konjunktion	Die Konjunktion von zwei Werten ist genau dann wahr, wenn beide Werte wahr sind.
Disjunktor	${\displaystyle \lor }$	oder	Disjunktion	Die Disjunktion von zwei Werten ist genau dann wahr, wenn mindestens ein Wert wahr ist.

Um d​ie Symbole d​es Konjunktors u​nd des Disjunktors leicht auseinanderhalten z​u können, g​ibt es d​ie Eselsbrücke m​it den d​rei O: „Oder i​st Oben Offen.“ Alternativ m​erkt man s​ich "And" (Englisch) für und, s​owie "vel" (Latein) für oder.

Verknüpfungen zweier Aussagen

Name		sprachliche Umschreibung	Darstellung		Wahrheitstabelle				Logik­gatter
			durch Negator, Konjunktor und Disjunktor	durch andere Junktoren	A=1		A=0
					B=1	B=0	B=1	B=0
Konjunktion		A und B	${\displaystyle A\land B}$	${\displaystyle \neg (B\implies \neg A)}$	1	0	0	0	AND
Exklusion, konträrer Gegensatz		nicht zugleich A und B	${\displaystyle \neg (A\land B)\iff \neg A\lor \neg B}$	${\displaystyle A\mid B\iff (A\implies \neg B)\iff (B\implies \neg A)}$	0	1	1	1	NAND
Disjunktion		A oder B (oder beide)	${\displaystyle A\lor B}$	${\displaystyle (\neg A\implies B)\iff (\neg B\implies A)}$	1	1	1	0	OR
Nihilition, Rejektion		weder A noch B	${\displaystyle \neg (A\lor B)\iff \neg A\land \neg B}$		0	0	0	1	NOR
Kontravalenz, kontradiktorischer Gegensatz		entweder A oder B	${\displaystyle (A\land \neg B)\lor (\neg A\land B)\iff (A\lor B)\land (\neg A\lor \neg B)}$	${\displaystyle A\veebar B\iff \neg (A\iff B)}$	0	1	1	0	XOR
Bikonditional, Bisubjunktion, materiale Äquivalenz		nur wenn A dann B, genau dann B wenn A	${\displaystyle (A\land B)\lor (\neg A\land \neg B)\iff (A\lor \neg B)\land (\neg A\lor B)}$	${\displaystyle (A\iff B)\iff (A\implies B)\land (B\implies A)}$	1	0	0	1	XNOR
Konditional, Subjunktion, materiale Implikation	Implikation	wenn A dann B	${\displaystyle \neg A\lor B}$	${\displaystyle (A\implies B)\iff (\neg B\implies \neg A)}$	1	0	1	1
	Replikation	wenn B dann A	${\displaystyle \neg B\lor A}$	${\displaystyle (B\implies A)\iff (\neg A\implies \neg B)}$	1	1	0	1
Inhibition	Postsektion	A und nicht B	${\displaystyle A\land \neg B}$	${\displaystyle \neg (A\implies B)}$	0	1	0	0
	Präsektion	B und nicht A	${\displaystyle B\land \neg A}$	${\displaystyle \neg (B\implies A)}$	0	0	1	0

Logische Grundgesetze

Gesetz der doppelten Negation	${\displaystyle x=\neg (\neg x)}$
Kommutativgesetze	${\displaystyle x\land y=y\land x}$	${\displaystyle x\lor y=y\lor x}$
Assoziativgesetze	${\displaystyle x\land (y\land z)=(x\land y)\land z}$	${\displaystyle (x\lor y)\lor z=x\lor (y\lor z)}$
Distributivgesetze	${\displaystyle x\land (y\lor z)=(x\land y)\lor (x\land z)}$	${\displaystyle x\lor (y\land z)=(x\lor y)\land (x\lor z)}$
Idempotenz	${\displaystyle x\land x=x}$	${\displaystyle x\lor x=x}$
Gesetze der Negation (Tautologie / Kontradiktion)	${\displaystyle x\lor \neg x=1}$	${\displaystyle x\land \neg x=0}$
Absorptionsgesetze	${\displaystyle x\land (x\lor y)=x}$	${\displaystyle x\lor (x\land y)=x}$
Neutralität	${\displaystyle x\lor 0=x}$	${\displaystyle x\land 1=x}$
De Morgansche Gesetze	${\displaystyle \neg (x\land y)=\neg x\lor \neg y}$	${\displaystyle \neg (x\lor y)=\neg x\land \neg y}$

Schlussregeln

Modus ponens	${\displaystyle ((a\rightarrow b)\land a)\rightarrow b}$
Modus tollens	${\displaystyle ((a\rightarrow b)\land \neg b)\rightarrow \neg a}$
Hypothetischer Syllogismus	${\displaystyle (a\rightarrow b)\land (b\rightarrow c)\rightarrow (a\rightarrow c)}$
Disjunktiver Syllogismus	${\displaystyle ((a\lor b)\land \neg a)\rightarrow b}$

Prädikatenlogik

Quantoren

p i​st Platzhalter für e​ine prädikatenlogische Aussageform.

${\displaystyle \forall _{x}p=\neg (\exists _{x}\neg p)}$	${\displaystyle \exists _{x}p=\neg (\forall _{x}\neg p)}$
${\displaystyle \neg \forall _{x}p=(\exists _{x}\neg p)}$	${\displaystyle \neg \exists _{x}p=(\forall _{x}\neg p)}$

Pränexform

${\displaystyle \phi }$ und ${\displaystyle \psi }$ sind im Folgenden Platzhalter für prädikatenlogische Aussageformen. Die Umformungen in Zeilen 1, 2, 4 und 5 der Tabelle gelten nur, wenn x innerhalb von ${\displaystyle \psi }$ nicht frei vorkommt, d. h. wenn durch das Verschieben des Quantors keine Variablenbindung entsteht (bzw. aufgelöst wird), die zuvor nicht da war (bzw. da war). Die letzte Umformung gilt nur, wenn x innerhalb von ${\displaystyle \phi }$ nicht frei vorkommt, d. h. wenn durch das Verschieben des Quantors keine Variablenbindung entsteht (bzw. aufgelöst wird), die zuvor nicht da war (bzw. da war).

Unproblematisch ist das, wenn die Variablen in den Aussageformen ${\displaystyle \phi }$ und ${\displaystyle \psi }$ jeweils unterschiedlich benannt sind.

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

Minimale Schlussregeln

Quasiordnung

${\displaystyle \vdash }$ ist im Folgenden eine Quasiordnung zwischen Aussagen.

${\displaystyle {\begin{array}{c}{~}\\\hline A\vdash A\end{array}}\qquad {\begin{array}{c}A\vdash B\qquad B\vdash C\\\hline A\vdash C\end{array}}}$

Konjunktion

${\displaystyle \top }$ und ${\displaystyle \land }$ werden durch folgende Regeln definiert.

${\displaystyle {\begin{array}{c}{~}\\\hline A\vdash \top \end{array}}\qquad {\begin{array}{c}A\vdash B\qquad A\vdash C\\\hline A\vdash B\land C\end{array}}{\uparrow }{\downarrow }}$

Disjunktion

${\displaystyle \bot }$ und ${\displaystyle \lor }$ werden durch folgende Regeln definiert.

${\displaystyle {\begin{array}{c}{~}\\\hline \bot \vdash A\end{array}}\qquad {\begin{array}{c}A\vdash C\qquad B\vdash C\\\hline A\lor B\vdash C\end{array}}{\uparrow }{\downarrow }}$

Heyting-Implikation und -Negation

${\displaystyle \to }$ wird durch die Regel

${\displaystyle {\begin{array}{lcr}A\land B&\vdash &C\\\hline A&\vdash &B\to C\end{array}}{\uparrow }{\downarrow }}$

definiert, und ${\displaystyle \lnot }$ per ${\displaystyle \lnot A:=A\to \bot }$.

Es gelten

• ${\displaystyle A\land \lnot A\vdash \bot }$,
• ${\displaystyle \lnot \top \vdash \bot }$ und
• ${\displaystyle \top \vdash \lnot \bot }$.

Ko-Heyting-Implikation und -Negation

Dual zu ${\displaystyle \to }$ und ${\displaystyle \lnot }$ sind ${\displaystyle \setminus }$ und ${\displaystyle \sim }$.

${\displaystyle {\begin{array}{lcr}A\setminus B&\vdash &C\\\hline A&\vdash &B\lor C\end{array}}{\uparrow }{\downarrow }}$,

${\displaystyle {\sim }A:=\top \setminus A}$.

Es gelten

• ${\displaystyle \top \vdash A\lor {\sim }A}$
• ${\displaystyle {\sim }\top \vdash \bot }$ und
• ${\displaystyle \top \vdash {\sim }\bot }$.

Beziehung zwischen den Negationen

Es gilt immer ${\displaystyle \lnot A\vdash {\sim }A}$. Gilt auch ${\displaystyle {\sim }A\vdash \lnot A}$, erhält man klassische Logik.

Quantoren

Es sei ${\displaystyle f\colon X\to Y}$ eine Abbildung. Eine beliebige Aussage ${\displaystyle A}$ über Elemente von ${\displaystyle Y}$ kann per ${\displaystyle f}$ in eine Aussage über ${\displaystyle X}$-Elemente transformiert werden. Notation: ${\displaystyle A\circ f}$. ${\displaystyle (-\circ f)}$ ist ein Funktor. Seine rechts- und linksadjungierten sind, respektive, All- und Existenzquantor. D.h.

${\displaystyle {\begin{array}{lcr}A\circ f&\vdash _{X}&B\\\hline A&\vdash _{Y}&\forall _{f}B\end{array}}{\uparrow }{\downarrow }\qquad {\begin{array}{rcl}C&\vdash _{X}&A\circ f\\\hline \exists _{f}C&\vdash _{Y}&A\end{array}}{\uparrow }{\downarrow }}$.