Formelsammlung Logik
# Formelsammlung Logik

Dies ist eine Formelsammlung zum mathematischen Teilgebiet der Logik.

## Aussagenlogik

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 | $\neg$ | nicht | Negation | Die Negation eines logischen Werts ist genau dann wahr, wenn der Wert falsch ist. |
| Konjunktor | $\land$ | und | Konjunktion | Die Konjunktion von zwei Werten ist genau dann wahr, wenn beide Werte wahr sind. |
| Disjunktor | $\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.

### Verknüpfungen zweier Aussagen

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

### Logische Grundgesetze

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

### Schlussregeln

| Modus ponens | $((a\rightarrow b)\land a)\rightarrow b$ |
| - | - |
| Modus tollens | $((a\rightarrow b)\land \neg b)\rightarrow \neg a$ |
| Hypothetischer Syllogismus | $(a\rightarrow b)\land (b\rightarrow c)\rightarrow (a\rightarrow c)$ |
| Disjunktiver Syllogismus | $((a\lor b)\land \neg a)\rightarrow b$ |

## Prädikatenlogik

### Quantoren

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

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

### Pränexform

$\phi$ und $\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 $\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 $\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 $\phi$ und $\psi$ jeweils unterschiedlich benannt sind.

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

## Minimale Schlussregeln

### Quasiordnung

$\vdash$ ist im Folgenden eine Quasiordnung zwischen Aussagen.

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

$\top$ und $\land$ werden durch folgende Regeln definiert.

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

$\bot$ und $\lor$ werden durch folgende Regeln definiert.

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

$\to$ wird durch die Regel

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

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

Es gelten

* $A\land \lnot A\vdash \bot$,
* $\lnot \top \vdash \bot$ und
* $\top \vdash \lnot \bot$.

### Ko-Heyting-Implikation und -Negation

Dual zu $\to$ und $\lnot$ sind $\setminus$ und $\sim$.

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

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

Es gelten

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

### Beziehung zwischen den Negationen

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

### Quantoren

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

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

