Formelsammlung Mathematik: Logik

↑ Formelsammlung Mathematik

Aussagenlogik

Boolesche Algebra

UND	ODER
$A\land B\Leftrightarrow B\land A$	$A\lor B\Leftrightarrow B\lor A$	Kommutativgesetze
$A\land (B\land C)\Leftrightarrow (A\land B)\land C$	$A\lor (B\lor C)\Leftrightarrow (A\lor B)\lor C$	Assoziativgesetze
$A\land A\Leftrightarrow A$	$A\lor A\Leftrightarrow A$	Idempotenzgesetze
$A\land 1\Leftrightarrow A$	$A\lor 0\Leftrightarrow A$	Neutralitätsgesetze
$A\land 0\Leftrightarrow 0$	$A\lor 1\Leftrightarrow 1$	Extremalgesetze
$A\land {\overline {A}}\Leftrightarrow 0$	$A\lor {\overline {A}}\Leftrightarrow 1$	Komplementärgesetze
${\overline {A\land B}}\Leftrightarrow {\overline {A}}\lor {\overline {B}}$	${\overline {A\lor B}}\Leftrightarrow {\overline {A}}\land {\overline {B}}$	De Morgansche Gesetze
$A\land (A\lor B)\Leftrightarrow A$	$A\lor (A\land B)\Leftrightarrow A$	Absorptionsgesetze

Distributivgesetze:

$A\land (B\lor C)\Leftrightarrow (A\land B)\lor (A\land C)$
$A\lor (B\land C)\Leftrightarrow (A\lor B)\land (A\lor C)$

Involution:

{\overline {\overline {A}}}\Leftrightarrow 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\lor B}}$
2	0010	${\overline {B\Rightarrow A}}$
3	0011	${\overline {A}}$
4	0100	${\overline {A\Rightarrow B}}$
5	0101	${\overline {B}}$
6	0110	$A\oplus B$	Kontravalenz
7	0111	${\overline {A\land B}}$
8	1000	$A\land B$	Konjunktion
9	1001	$A\Leftrightarrow B$	Äquivalenz
10	1010	$B$
11	1011	$A\Rightarrow B$	Implikation
12	1100	$A$
13	1101	$B\Rightarrow A$
14	1110	$A\lor B$	Disjunktion
15	1111	$1$	Tautologie

Darstellung mit Negation, Konjunktion und Disjunktion

$A\Rightarrow B\iff {\overline {A}}\lor B$
$(A\Leftrightarrow B)\iff ({\overline {A}}\land {\overline {B}})\lor (A\land B)$
$A\oplus B\iff ({\overline {A}}\land B)\lor (A\land {\overline {B}})$

Vorlagen für KV-Diagramme

Tautologien

Modus ponens:

(A\Rightarrow B)\land A\implies B

Modus tollens:

(A\Rightarrow B)\land {\overline {B}}\implies {\overline {A}}

Modus tollendo ponens:

(A\lor B)\land {\overline {A}}\implies B

Modus ponendo tollens:

{\overline {A\land B}}\land A\implies {\overline {B}}

Kontraposition:

A\Rightarrow B\iff {\overline {B}}\Rightarrow {\overline {A}}

Beweis durch Widerspruch:

({\overline {A}}\Rightarrow B\land {\overline {B}})\implies A

Zerlegung einer Äquivalenz:

(A\Leftrightarrow B)\iff (A\Rightarrow B)\land (B\Rightarrow A)

Kettenschluss:

(A\Rightarrow B)\land (B\Rightarrow C)\implies (A\Rightarrow C)

Ringschluss:

(A\Rightarrow B)\land (B\Rightarrow C)\land (C\Rightarrow A)

\implies (A\Leftrightarrow B)\land (A\Leftrightarrow C)\land (B\Leftrightarrow C)

Ringschluss, allgemein:

(A_{1}\Rightarrow A_{2})\land \ldots \land (A_{n-1}\Rightarrow A_{n})\land (A_{n}\Rightarrow A_{1})

\implies \forall i,j\,[A_{i}\Leftrightarrow A_{j}]

Regeln zum Tableaukalkül

`φ`∧`ψ`
`φ`
`ψ`

¬(`φ`∧`ψ`)
¬`φ`	¬`ψ`

`φ`∨`ψ`
`φ`	`ψ`

¬(`φ`∨`ψ`)
¬`φ`
¬`ψ`

`φ`→`ψ`
¬`φ`	`ψ`

¬(`φ`→`ψ`)
`φ`
¬`ψ`

φ↔ψ

`φ`
`ψ`

¬`φ`
¬`ψ`

¬(φ↔ψ)

`φ`
¬`ψ`

`ψ`
¬`φ`

Schlussregeln

Modus ponens:

\{\varphi ,\varphi \rightarrow \psi \}\vdash \psi

Metatheoreme

Sei $M=\{\varphi _{1},\ldots ,\varphi _{n}\}$ eine endliche Menge von Formeln.

Korrektheit der Aussagenlogik.

Es gilt:

(M\vdash \psi )\implies (M\models \psi ).

Vollständigkeit der Aussagenlogik.

Es gilt:

(M\models \psi )\implies (M\vdash \psi ).

Deduktionstheorem (syntaktisch).

Es gilt:

(M\cup \{\varphi \}\vdash \psi )\iff (M\vdash \varphi \rightarrow \psi ).

Infolge gilt auch:

(\{\varphi _{1},\ldots ,\varphi _{n}\}\vdash \psi )\iff (\vdash \varphi _{1}\land \ldots \land \varphi _{n}\rightarrow \psi ).

Deduktionstheorem (semantisch).

Es gilt:

(M\cup \{\varphi \}\models \psi )\iff (M\models \varphi \rightarrow \psi ).

Infolge gilt auch:

(\{\varphi _{1},\ldots ,\varphi _{n}\}\models \psi )\iff (\models \varphi _{1}\land \ldots \land \varphi _{n}\rightarrow \psi ).

Einsetzungsregel.

Sei v eine logische Variable. Ist φ eine tautologische Formel, dann ergibt sich wieder eine tautologische Formel, wenn man jedes Vorkommen von v in φ durch eine Formel ψ ersetzt. Formal:

(\models \varphi )\implies (\models \varphi [v:=\psi ]).

Das gilt auch für die simultane Substitution:

(\models \varphi )\implies (\models \varphi [v_{1}:=\psi _{1},\ldots ,v_{n}:=\psi _{n}]).

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

\models A\land (A\rightarrow B)\rightarrow B.

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

\models \varphi \land (\varphi \rightarrow \psi )\rightarrow \psi .

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

\{\varphi ,\varphi \rightarrow \psi \}\vdash \psi .

Syntax der Aussagenlogik

Definition. Formale Sprache der Aussagenlogik.

Sei $V=\{A_{1},A_{2},A_{3},\ldots \}$ die Menge der logischen Variablen.

Die Menge der wohlgeformten Formeln ist durch die folgende formale Grammatik definiert:

Bei 0 und 1 handelt es sich um Formeln.
Jede Variable aus V ist eine Formel.
Sind φ und ψ Formeln, dann sind es auch $(\neg \varphi ),(\varphi \land \psi ),(\varphi \lor \psi ),(\varphi \rightarrow \psi ),(\varphi \leftrightarrow \psi )$ .

Die Menge der wohlgeformten Formeln ist die formale Sprache der Aussagenlogik.

Bemerkung:

Für die Praxis wird $V=\{A,B,C,\ldots \}$ definiert.
Außerdem können Klammernpaare wie bei Punktrechnung-vor-Strichrechnung weggelassen werden, wobei die Bindungsstärke in absteigender Reihenfolge $\neg ,\land ,\lor ,\rightarrow ,\leftrightarrow$ ist.
Anstelle von $\neg \varphi$ wird auch ${\overline {\varphi }}$ geschrieben.

Formales System der Aussagenlogik

Definition. Formales System der Aussagenlogik.

Einzige Schlussregel. Modus ponens:

(MP)

\{\varphi ,\varphi \rightarrow \psi \}\vdash \psi .

Axiome.

(A1)

\varphi \rightarrow (\psi \rightarrow \varphi )

,

(A2)

(\varphi \rightarrow (\psi \rightarrow \chi ))\rightarrow ((\varphi \rightarrow \psi )\rightarrow (\varphi \rightarrow \chi ))

,

(A3)

(\neg \varphi \rightarrow \neg \chi )\rightarrow (\chi \rightarrow \varphi )

.

Hierbei ist:

$\varphi \lor \psi$ definiert als $\neg \varphi \rightarrow \psi$ ,
$\varphi \land \psi$ definiert als $\neg (\varphi \rightarrow \neg \psi )$ ,
$\varphi \leftrightarrow \psi$ definiert als $(\varphi \rightarrow \psi )\land (\psi \rightarrow \varphi )$ .

Es folgen historische Axiomatisierungen.

Axiome (Rosser, 1953).

(R1)

\varphi \rightarrow \varphi \land \varphi

,

(R2)

\varphi \land \psi \rightarrow \varphi

,

(R3)

(\varphi \rightarrow \psi )\rightarrow (\neg (\psi \land \chi )\rightarrow \neg (\chi \land \psi ))

.

Axiome (Principia Mathematica, 1910).

(P1)

\varphi \lor \varphi \rightarrow \varphi

,

(P2)

\psi \rightarrow \varphi \lor \psi

,

(P3)

\varphi \lor \psi \rightarrow \psi \lor \varphi

,

(P4)

\varphi \lor (\psi \lor \chi )\rightarrow \psi \lor (\varphi \lor \chi )

,

(P5)

(\psi \rightarrow \chi )\rightarrow (\varphi \lor \psi \rightarrow \varphi \lor \chi )

.

Das Axiom (P4) ist redundant.

Semantik der Aussagenlogik

Definition. Interpretation.

Eine Interpretation $I\colon V\to \{0,1\}$ ist eine Abbildung, die jeder logischen Variablen einen Wahrheitswert zuordnet.

Der Definitionsbereich der Interpretation wird wie folgt auf die Menge der Formeln erweitert:

I(0)=0

,

I(1)=1

,

I(\neg \varphi )=(\neg I(\varphi ))

,

I(\varphi \land \psi )=(I(\varphi )\land I(\psi ))

,

I(\varphi \lor \psi )=(I(\varphi )\lor I(\psi ))

,

I(\varphi \rightarrow \psi )=(I(\varphi )\rightarrow I(\psi ))

,

I(\varphi \leftrightarrow \psi )=(I(\varphi )\leftrightarrow I(\psi ))

.

Die rechte Seite der Zeile wird hierbei jeweils nach ihrer Wahrheitstabelle ausgewertet.

Definition. Modell.

Eine Interpretation $I$ heißt Modell von $\varphi$ , wenn $I(\varphi )=1$ gilt. Kurz:

(I\models \varphi )\;:\Longleftrightarrow \;I(\varphi )=1.

Sei $M=\{\varphi _{1},\ldots ,\varphi _{n}\}$ eine Menge von Formeln. Eine Interpretation $I$ heißt Modell von M, wenn $I$ ein Modell jeder Formel aus M ist. Kurz:

(I\models M)\;:\Longleftrightarrow \;\forall \varphi {\in }M\;(I(\varphi )=1).

Definition. Modellrelation.

Eine Formelmenge M modelliert eine Formel ψ, wenn jedes Modell von M auch ein Modell von ψ ist. Kurz:

(M\models \psi )\;:\Longleftrightarrow \;\forall I[(I\models M)\implies (I\models \psi )].

Definition. Tautologie.

Eine Formel wird tautologisch (allgemeingültig) genannt, wenn jede Interpretation für sie auch ein Modell ist. Kurz:

(\models \varphi )\;:\Longleftrightarrow \;\forall I(I(\varphi )=1).

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

(\models \varphi )\iff (\{\}\models \varphi ).

Definition. Erfüllbare Formel.

Eine Formel wird erfüllbar genannt, wenn sie ein Modell besitzt. Kurz:

\operatorname {erf} [\varphi ]\;:\Longleftrightarrow \;\exists I(I(\varphi )=1).

Definition. Unerfüllbare Formel.

Eine Formel wird unerfüllbar genannt, wenn sie kein Modell besitzt. Kurz:

\neg \operatorname {erf} [\varphi ]\iff \forall I(I(\varphi )=0).

Definition. Erfüllbarkeitsäquivalenz.

Zwei Formeln φ und ψ heißen erfüllbarkeitsäquivalent, wenn gilt:

\operatorname {erf} [\varphi ]\iff \operatorname {erf} [\psi ].

Das Modell der ersten Formel braucht dabei nicht mit dem Modell der zweiten Formel übereinzustimmen.

Prädikatenlogik

Rechenregeln

Verneinung (De Morgansche Gesetze):

$\neg \forall x[P(x)]\iff \exists x[\neg P(x)]$
$\neg \exists x[P(x)]\iff \forall x[\neg P(x)]$

Verallgemeinerte Distributivgesetze:

$P\land \exists x[Q(x)]\iff \exists x[P\land Q(x)]$
$P\lor \forall x[Q(x)]\iff \forall x[P\lor Q(x)]$

Verallgemeinerte Idempotenzgesetze:

$\exists x{\in }M\,[P]\iff (M\neq \{\})\land P\iff {\begin{cases}P&{\text{wenn}}\;M\neq \{\}\\0&{\text{wenn}}\;M=\{\}\end{cases}}$
$\forall x{\in }M\,[P]\iff (M=\{\})\lor P\iff {\begin{cases}P&{\text{wenn}}\;M\neq \{\}\\1&{\text{wenn}}\;M=\{\}\end{cases}}$

Äquivalenzen:

$\forall x\forall y[P(x,y)]\iff \forall y\forall x[P(x,y)]$
$\exists x\exists y[P(x,y)]\iff \exists y\exists x[P(x,y)]$
$\forall x[P(x)\land Q(x)]\iff \forall x[P(x)]\land \forall x[Q(x)]$
$\exists x[P(x)\lor Q(x)]\iff \exists x[P(x)]\lor \exists x[Q(x)]$
$\forall x[P(x)\Rightarrow Q]\iff \exists x[P(x)]\Rightarrow Q$
$\forall x[P\Rightarrow Q(x)]\iff P\Rightarrow \forall x[Q(x)]$
$\exists x[P(x)\Rightarrow Q(x)]\iff \forall x[P(x)]\Rightarrow \exists x[Q(x)]$

Implikationen:

$\exists x\forall y[P(x,y)]\implies \forall y\exists x[P(x,y)]$
$\forall x[P(x)]\lor \forall x[Q(x)]\implies \forall x[P(x)\lor Q(x)]$
$\exists x[P(x)\land Q(x)]\implies \exists x[P(x)]\land \exists x[Q(x)]$
$\forall x[P(x)\Rightarrow Q(x)]\implies (\forall x[P(x)]\Rightarrow \forall x[Q(x)])$
$\forall x[P(x)\Leftrightarrow Q(x)]\implies (\forall x[P(x)]\Leftrightarrow \forall x[Q(x)])$

Endliche Mengen

Sei $M=\{x_{1},\ldots ,x_{n}\}$ .

$\forall x{\in }M\,[P(x)]\iff P(x_{1})\land \ldots \land P(x_{n})$
$\exists x{\in }M\,[P(x)]\iff P(x_{1})\lor \ldots \lor P(x_{n})$

Beschränkte Quantifizierung

$\forall x{\in }M\,[P(x)]\,:\Longleftrightarrow \,\forall x[x\notin M\vee P(x)]\iff \forall x[x\in M\Rightarrow P(x)]$
$\exists x{\in }M\,[P(x)]\,:\Longleftrightarrow \,\exists x[x\in M\wedge P(x)]$
$\forall x{\in }M{\setminus }N\,[P(x)]\iff \forall x{\in }M\,[x\notin N\Rightarrow P(x)]$

Quantifizierung über Produktmengen

$\exists (x,y)\,[P(x,y)]\iff \exists x\exists y\,[P(x,y)]$
$\forall (x,y)\,[P(x,y)]\iff \forall x\forall y\,[P(x,y)]$

Analog gilt

$\exists (x,y,z)[P(x,y,z)]\iff \exists x\exists y\exists z\,[P(x,y,z)]$
$\forall (x,y,z)[P(x,y,z)]\iff \forall x\forall y\forall z\,[P(x,y,z)]$

usw.

Alternative Darstellung

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

$\forall x{\in }M\,[P(x)]\iff P(M)=\{1\}\iff M\subseteq \{x{\in }G\mid P(x)\}$
$\exists x{\in }M\,[P(x)]\iff \{1\}\subseteq P(M)\iff M\cap \{x{\in }G\mid P(x)\}\neq \{\}$