Formelsammlung Mathematik: Logik

Aussagenlogik

Boolesche Algebra

UND	ODER
$A\wedge B\iff B\wedge A$	$A\vee B\iff B\vee A$	Kommutativgesetze
$A\wedge (B\wedge C)\iff (A\wedge B)\wedge C$	$A\vee (B\vee C)\iff (A\vee B)\vee C$	Assoziativgesetze
$A\wedge A\iff A$	$A\vee A\iff A$	Idempotenzgesetze
$A\wedge 1\iff A$	$A\vee 0\iff A$	Neutralitätsgesetze
$A\wedge 0\iff 0$	$A\vee 1\iff 1$	Extremalgesetze
$A\wedge \bar{A}\iff 0$	$A\vee \bar{A}\iff 1$	Komplementärgesetze
$\overline{A\wedge B}\iff \bar{A}\vee \bar{B}$	$\overline{A\vee B}\iff \bar{A}\wedge \bar{B}$	De Morgansche Gesetze
$A\wedge (A\vee B)\iff A$	$A\vee (A\wedge B)\iff A$	Absorptionsgesetze

Distributivgesetze:

1. $A\wedge (B\vee C)\iff (A\wedge B)\vee (A\wedge C)$
2. $A\vee (B\wedge C)\iff (A\vee B)\wedge (A\vee C)$

Involution:

$\overline{\stackrel{‾}{A}}\iff A$

Zweistellige Funktionen

A	B	Wert
0	0	a
0	1	b
1	0	c
1	1	d

Nr.	dcba	Fkt.	Name
0	0000	$0$	Kontradiktion
1	0001	$\overline{A\vee B}$
2	0010	$\overline{B\Rightarrow A}$
3	0011	$\bar{A}$
4	0100	$\overline{A\Rightarrow B}$
5	0101	$\bar{B}$
6	0110	$A\oplus B$	Kontravalenz
7	0111	$\overline{A\wedge B}$
8	1000	$A\wedge B$	Konjunktion
9	1001	$A\iff B$	Äquivalenz
10	1010	$B$
11	1011	$A\Rightarrow B$	Implikation
12	1100	$A$
13	1101	$B\Rightarrow A$
14	1110	$A\vee B$	Disjunktion
15	1111	$1$	Tautologie

Darstellung mit Negation, Konjunktion und Disjunktion

1. $A\Rightarrow B⟺\bar{A}\vee B$
2. $(A\iff B)⟺(\bar{A}\wedge \bar{B})\vee (A\wedge B)$
3. $A\oplus B⟺(\bar{A}\wedge B)\vee (A\wedge \bar{B})$

Vorlagen für KV-Diagramme

Tautologien

Modus ponens:

$(A\Rightarrow B)\wedge A⟹B$

Modus tollens:

$(A\Rightarrow B)\wedge \bar{B}⟹\bar{A}$

Modus tollendo ponens:

$(A\vee B)\wedge \bar{A}⟹B$

Modus ponendo tollens:

$\overline{A\wedge B}\wedge A⟹\bar{B}$

Kontraposition:

$A\Rightarrow B⟺\bar{B}\Rightarrow \bar{A}$

Beweis durch Widerspruch:

$(\bar{A}\Rightarrow B\wedge \bar{B})⟹A$

Zerlegung einer Äquivalenz:

$(A\iff B)⟺(A\Rightarrow B)\wedge (B\Rightarrow A)$

Kettenschluss:

$(A\Rightarrow B)\wedge (B\Rightarrow C)⟹(A\Rightarrow C)$

Ringschluss:

$(A\Rightarrow B)\wedge (B\Rightarrow C)\wedge (C\Rightarrow A)$

$⟹(A\iff B)\wedge (A\iff C)\wedge (B\iff C)$

Ringschluss, allgemein:

$(A_1\Rightarrow A_2)\wedge \dots \wedge (A_{n-1}\Rightarrow A_n)\wedge (A_n\Rightarrow A_1)$

$⟹\mathrm{\forall }i,j[A_i\iff A_j]$

Regeln zum Tableaukalkül

φ∧ψ φ ψ

¬(φ∧ψ) ¬φ ¬ψ

φ∨ψ φ ψ

¬(φ∨ψ) ¬φ ¬ψ

φ→ψ ¬φ ψ

¬(φ→ψ) φ ¬ψ

φ↔ψ φ ψ ¬φ ¬ψ

¬(φ↔ψ) φ ¬ψ ψ ¬φ

Schlussregeln

Modus ponens:

$\{\phi ,\phi \to \psi \}⊢\psi$

Metatheoreme

Sei $M=\{{\phi }_1,\dots ,{\phi }_n\}$ eine endliche Menge von Formeln.

Formelsammlung Mathematik: Vorlage:tbox

Formelsammlung Mathematik: Vorlage:tbox

Formelsammlung Mathematik: Vorlage:tbox Infolge gilt auch:

$(\{{\phi }_1,\dots ,{\phi }_n\}⊢\psi )⟺(⊢{\phi }_1\wedge \dots \wedge {\phi }_n\to \psi ).$

Formelsammlung Mathematik: Vorlage:tbox Infolge gilt auch:

$(\{{\phi }_1,\dots ,{\phi }_n\}\models \psi )⟺(\models {\phi }_1\wedge \dots \wedge {\phi }_n\to \psi ).$

Formelsammlung Mathematik: Vorlage:tbox

Beispiel. Man überzeugt sich z. B. mittels einer Wahrheitstabelle von

$\models A\wedge (A\to B)\to B.$

Unter Anwendung der Einsetzungsregel lassen sich die zwei Variablen simultan gegen Formeln austauschen:

$\models \phi \wedge (\phi \to \psi )\to \psi .$

Zieht man nun die Vollständigkeit und das Deduktionstheorem heran, ergibt sich der Modus ponens:

$\{\phi ,\phi \to \psi \}⊢\psi .$

Syntax der Aussagenlogik

Formelsammlung Mathematik: Vorlage:dbox Bemerkung:

1. Für die Praxis wird $V=\{A,B,C,\dots \}$ definiert.
2. Außerdem können Klammernpaare wie bei Punktrechnung-vor-Strichrechnung weggelassen werden, wobei die Bindungsstärke in absteigender Reihenfolge $\mathrm{\neg },\wedge ,\vee ,\to ,\leftrightarrow$ ist.
3. Anstelle von $\mathrm{\neg }\phi$ wird auch $\bar{\phi }$ geschrieben.

Formales System der Aussagenlogik

Es folgen historische Axiomatisierungen. Formelsammlung Mathematik: Vorlage:dbox

Formelsammlung Mathematik: Vorlage:dbox Das Axiom (P4) ist redundant.

Semantik der Aussagenlogik

Formelsammlung Mathematik: Vorlage:dbox

Formelsammlung Mathematik: Vorlage:dbox

Formelsammlung Mathematik: Vorlage:dbox Eine Formel ist genau dann tautologisch, wenn sie durch die leere Menge modelliert wird:

$(\models \phi )⟺(\{\}\models \phi ).$

Formelsammlung Mathematik: Vorlage:dbox

Formelsammlung Mathematik: Vorlage:dbox

Formelsammlung Mathematik: Vorlage:dbox

Prädikatenlogik

Rechenregeln

Verneinung (De Morgansche Gesetze):

1. $\mathrm{\neg }\mathrm{\forall }x[P(x)]⟺\mathrm{\exists }x[\mathrm{\neg }P(x)]$
2. $\mathrm{\neg }\mathrm{\exists }x[P(x)]⟺\mathrm{\forall }x[\mathrm{\neg }P(x)]$

Verallgemeinerte Distributivgesetze:

1. $P\wedge \mathrm{\exists }x[Q(x)]⟺\mathrm{\exists }x[P\wedge Q(x)]$
2. $P\vee \mathrm{\forall }x[Q(x)]⟺\mathrm{\forall }x[P\vee Q(x)]$

Verallgemeinerte Idempotenzgesetze:

1. $\mathrm{\exists }x\in M[P]⟺(M\ne \{\})\wedge P⟺\{\begin{array}{cc}P& \text{wenn}M\ne \{\}\\ 0& \text{wenn}M=\{\}\end{array}$
2. $\mathrm{\forall }x\in M[P]⟺(M=\{\})\vee P⟺\{\begin{array}{cc}P& \text{wenn}M\ne \{\}\\ 1& \text{wenn}M=\{\}\end{array}$

Äquivalenzen:

1. $\mathrm{\forall }x\mathrm{\forall }y[P(x,y)]⟺\mathrm{\forall }y\mathrm{\forall }x[P(x,y)]$
2. $\mathrm{\exists }x\mathrm{\exists }y[P(x,y)]⟺\mathrm{\exists }y\mathrm{\exists }x[P(x,y)]$
3. $\mathrm{\forall }x[P(x)\wedge Q(x)]⟺\mathrm{\forall }x[P(x)]\wedge \mathrm{\forall }x[Q(x)]$
4. $\mathrm{\exists }x[P(x)\vee Q(x)]⟺\mathrm{\exists }x[P(x)]\vee \mathrm{\exists }x[Q(x)]$
5. $\mathrm{\forall }x[P(x)\Rightarrow Q]⟺\mathrm{\exists }x[P(x)]\Rightarrow Q$
6. $\mathrm{\forall }x[P\Rightarrow Q(x)]⟺P\Rightarrow \mathrm{\forall }x[Q(x)]$
7. $\mathrm{\exists }x[P(x)\Rightarrow Q(x)]⟺\mathrm{\forall }x[P(x)]\Rightarrow \mathrm{\exists }x[Q(x)]$

Implikationen:

1. $\mathrm{\exists }x\mathrm{\forall }y[P(x,y)]⟹\mathrm{\forall }y\mathrm{\exists }x[P(x,y)]$
2. $\mathrm{\forall }x[P(x)]\vee \mathrm{\forall }x[Q(x)]⟹\mathrm{\forall }x[P(x)\vee Q(x)]$
3. $\mathrm{\exists }x[P(x)\wedge Q(x)]⟹\mathrm{\exists }x[P(x)]\wedge \mathrm{\exists }x[Q(x)]$
4. $\mathrm{\forall }x[P(x)\Rightarrow Q(x)]⟹(\mathrm{\forall }x[P(x)]\Rightarrow \mathrm{\forall }x[Q(x)])$
5. $\mathrm{\forall }x[P(x)\iff Q(x)]⟹(\mathrm{\forall }x[P(x)]\iff \mathrm{\forall }x[Q(x)])$

Endliche Mengen

Sei $M=\{x_1,\dots ,x_n\}$.

1. $\mathrm{\forall }x\in M[P(x)]⟺P(x_1)\wedge \dots \wedge P(x_n)$
2. $\mathrm{\exists }x\in M[P(x)]⟺P(x_1)\vee \dots \vee P(x_n)$

Beschränkte Quantifizierung

1. $\mathrm{\forall }x\in M[P(x)]:⟺\mathrm{\forall }x[x\notin M\vee P(x)]⟺\mathrm{\forall }x[x\in M\Rightarrow P(x)]$
2. $\mathrm{\exists }x\in M[P(x)]:⟺\mathrm{\exists }x[x\in M\wedge P(x)]$
3. $\mathrm{\forall }x\in M\setminus N[P(x)]⟺\mathrm{\forall }x\in M[x\notin N\Rightarrow P(x)]$

Quantifizierung über Produktmengen

1. $\mathrm{\exists }(x,y)[P(x,y)]⟺\mathrm{\exists }x\mathrm{\exists }y[P(x,y)]$
2. $\mathrm{\forall }(x,y)[P(x,y)]⟺\mathrm{\forall }x\mathrm{\forall }y[P(x,y)]$

Analog gilt

1. $\mathrm{\exists }(x,y,z)[P(x,y,z)]⟺\mathrm{\exists }x\mathrm{\exists }y\mathrm{\exists }z[P(x,y,z)]$
2. $\mathrm{\forall }(x,y,z)[P(x,y,z)]⟺\mathrm{\forall }x\mathrm{\forall }y\mathrm{\forall }z[P(x,y,z)]$

usw.

Alternative Darstellung

Sei $P:G\to \{0,1\}$ und $M\subseteq G$. Mit $P(M)$ ist die Bildmenge von $P$ bezüglich $M$ gemeint.

1. $\mathrm{\forall }x\in M[P(x)]⟺P(M)=\{1\}⟺M\subseteq \{x\in G\mid P(x)\}$
2. $\mathrm{\exists }x\in M[P(x)]⟺\{1\}\subseteq P(M)⟺M\cap \{x\in G\mid P(x)\}\ne \{\}$

Substitution

Sei $g:M\to N$ eine Injektion. Es gilt:

1. $\mathrm{\forall }x\in M[P(x)]⟺\mathrm{\forall }y\in g(M)[P(g^{-1}(y))]$
2. $\mathrm{\exists }x\in M[P(x)]⟺\mathrm{\exists }y\in g(M)[P(g^{-1}(y))]$

Ist $g$ eine bijektive Selbstabbildung auf $M$, so gilt speziell:

1. $\mathrm{\forall }x\in M[P(x)]⟺\mathrm{\forall }x\in M[P(g^{-1}(x))]$
2. $\mathrm{\exists }x\in M[P(x)]⟺\mathrm{\exists }x\in M[P(g^{-1}(x))]$

Eindeutigkeit

Quantor für eindeutige Existenz:

$\mathrm{\exists }!x[P(x)]$

$:⟺\mathrm{\exists }x[P(x)\wedge \mathrm{\forall }y[P(y)\Rightarrow x=y]]$

$⟺\mathrm{\exists }x[P(x)]\wedge \mathrm{\forall }x\mathrm{\forall }y[P(x)\wedge P(y)\Rightarrow x=y]$