Formelsammlung Logik

Verknüpfungen zweier Aussagen

Weitere Informationen , ...

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

Schließen

Insgesamt sind 16 Funktionen mit zwei Input-Variablen möglich. Zu den genannten zehn Funktionen kommen noch die eher uninteressanten Funktionen konstant_0, konstant_1, ${\displaystyle A,\neg A,B,\neg B}$ dazu.

Logische Grundgesetze

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

Schlussregeln

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

Quantoren

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

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).

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

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