Formelsammlung Logik

Dies ist eine Formelsammlung zum mathematischen Teilgebiet der Logik.

Logische Werte:

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

Erweiterte Logik:

• unbestimmt (Don’t-Care) X

Aussagen können durch logische Operatoren, auch 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 die Symbole des Konjunktors und des Disjunktors leicht auseinanderhalten zu können, gibt es die Eselsbrücke mit den drei O: „Oder ist Oben Offen.“ Alternativ merkt man sich "And" (Englisch) für und, sowie "vel" (Latein) für oder.

Name		sprachliche Umschreibung	äquivalente Darstellungen		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\to \neg A)}$	1	0	0	0	AND
Exklusion, konträrer Gegensatz		nicht zugleich A und B	${\displaystyle \neg (A\land B)}$, ${\displaystyle \neg A\lor \neg B}$	${\displaystyle A\mid B}$, ${\displaystyle A\to \neg B}$, ${\displaystyle B\to \neg A}$	0	1	1	1	NAND
Disjunktion		A oder B (oder beide)	${\displaystyle A\lor B}$	${\displaystyle \neg A\to B}$, ${\displaystyle \neg B\to A}$	1	1	1	0	OR
Nihilition, Rejektion		weder A noch B	${\displaystyle \neg (A\lor B)}$, ${\displaystyle \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)}$, ${\displaystyle (A\lor B)\land (\neg A\lor \neg B)}$	${\displaystyle A\veebar B}$, ${\displaystyle \neg (A\leftrightarrow B)}$	0	1	1	0	XOR
Bikonditional, Bisubjunktion, materiale Äquivalenz		B dann und nur dann, wenn A; genau dann B, wenn A	${\displaystyle (A\land B)\lor (\neg A\land \neg B)}$, ${\displaystyle (A\lor \neg B)\land (\neg A\lor B)}$	${\displaystyle (A\leftrightarrow B)}$, ${\displaystyle (A\to B)\land (B\to A)}$	1	0	0	1	XNOR
Konditional, Subjunktion, materiale Implikation	Implikation	wenn A, dann B	${\displaystyle \neg A\lor B}$	${\displaystyle A\to B}$, ${\displaystyle \neg B\to \neg A}$	1	0	1	1
	Replikation	wenn B, dann A	${\displaystyle \neg B\lor A}$	${\displaystyle B\to A}$, ${\displaystyle \neg A\to \neg B}$	1	1	0	1
Inhibition	Postsektion	A und nicht B	${\displaystyle A\land \neg B}$	${\displaystyle \neg (A\to B)}$	0	1	0	0
	Präsektion	B und nicht A	${\displaystyle B\land \neg A}$	${\displaystyle \neg (B\to A)}$	0	0	1	0

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

Modus ponens	${\displaystyle \{a\rightarrow b,a\}\vdash b}$
Modus tollens	${\displaystyle \{a\rightarrow b,\neg b\}\vdash \neg a}$
Hypothetischer Syllogismus	${\displaystyle \{a\rightarrow b,b\rightarrow c\}\vdash a\rightarrow c}$
Disjunktiver Syllogismus	${\displaystyle \{a\lor b,\neg a\}\vdash b}$

p ist Platzhalter für eine prädikatenlogische Aussageform.

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

${\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).

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

${\displaystyle (\forall x\phi )\land \psi \leftrightarrow \forall x(\phi \land \psi )}$	${\displaystyle (\forall x\phi )\lor \psi \leftrightarrow \forall x(\phi \lor \psi )}$
${\displaystyle (\exists x\phi )\land \psi \leftrightarrow \exists x(\phi \land \psi )}$	${\displaystyle (\exists x\phi )\lor \psi \leftrightarrow \exists x(\phi \lor \psi )}$
${\displaystyle \lnot \exists x\phi \leftrightarrow \forall x\lnot \phi }$	${\displaystyle \lnot \forall x\phi \leftrightarrow \exists x\lnot \phi }$
${\displaystyle ((\forall x\phi )\rightarrow \psi )\leftrightarrow \exists x(\phi \rightarrow \psi )}$	${\displaystyle ((\exists x\phi )\rightarrow \psi )\leftrightarrow \forall x(\phi \rightarrow \psi )}$
${\displaystyle (\psi \rightarrow (\exists x\phi ))\leftrightarrow \exists x(\psi \rightarrow \phi )}$	${\displaystyle (\psi \rightarrow (\forall x\phi ))\leftrightarrow \forall x(\psi \rightarrow \phi )}$

${\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}}}$

${\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 }}$

${\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 }}$

${\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 }$.

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 }$.

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

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 ({\mathord {-}}\circ f)}$ ist ein Funktor. Sein Rechts- und Linksadjungierter ist der All- bzw. 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 }}$.