UND
ODER
A
∧
B
⇔
B
∧
A
{\displaystyle A\land B\Leftrightarrow B\land A}
A
∨
B
⇔
B
∨
A
{\displaystyle A\lor B\Leftrightarrow B\lor A}
Kommutativgesetze
A
∧
(
B
∧
C
)
⇔
(
A
∧
B
)
∧
C
{\displaystyle A\land (B\land C)\Leftrightarrow (A\land B)\land C}
A
∨
(
B
∨
C
)
⇔
(
A
∨
B
)
∨
C
{\displaystyle A\lor (B\lor C)\Leftrightarrow (A\lor B)\lor C}
Assoziativgesetze
A
∧
A
⇔
A
{\displaystyle A\land A\Leftrightarrow A}
A
∨
A
⇔
A
{\displaystyle A\lor A\Leftrightarrow A}
Idempotenzgesetze
A
∧
1
⇔
A
{\displaystyle A\land 1\Leftrightarrow A}
A
∨
0
⇔
A
{\displaystyle A\lor 0\Leftrightarrow A}
Neutralitätsgesetze
A
∧
0
⇔
0
{\displaystyle A\land 0\Leftrightarrow 0}
A
∨
1
⇔
1
{\displaystyle A\lor 1\Leftrightarrow 1}
Extremalgesetze
A
∧
A
¯
⇔
0
{\displaystyle A\land {\overline {A}}\Leftrightarrow 0}
A
∨
A
¯
⇔
1
{\displaystyle A\lor {\overline {A}}\Leftrightarrow 1}
Komplementärgesetze
A
∧
B
¯
⇔
A
¯
∨
B
¯
{\displaystyle {\overline {A\land B}}\Leftrightarrow {\overline {A}}\lor {\overline {B}}}
A
∨
B
¯
⇔
A
¯
∧
B
¯
{\displaystyle {\overline {A\lor B}}\Leftrightarrow {\overline {A}}\land {\overline {B}}}
De Morgansche Gesetze
A
∧
(
A
∨
B
)
⇔
A
{\displaystyle A\land (A\lor B)\Leftrightarrow A}
A
∨
(
A
∧
B
)
⇔
A
{\displaystyle A\lor (A\land B)\Leftrightarrow A}
Absorptionsgesetze
Distributivgesetze:
A
∧
(
B
∨
C
)
⇔
(
A
∧
B
)
∨
(
A
∧
C
)
{\displaystyle A\land (B\lor C)\Leftrightarrow (A\land B)\lor (A\land C)}
A
∨
(
B
∧
C
)
⇔
(
A
∨
B
)
∧
(
A
∨
C
)
{\displaystyle A\lor (B\land C)\Leftrightarrow (A\lor B)\land (A\lor C)}
Involution:
A
¯
¯
⇔
A
{\displaystyle {\overline {\overline {A}}}\Leftrightarrow A}
A
B
Wert
0
0
a
0
1
b
1
0
c
1
1
d
Nr.
dcba
Fkt.
Name
0
0000
0
{\displaystyle 0}
Kontradiktion
1
0001
A
∨
B
¯
{\displaystyle {\overline {A\lor B}}}
2
0010
B
⇒
A
¯
{\displaystyle {\overline {B\Rightarrow A}}}
3
0011
A
¯
{\displaystyle {\overline {A}}}
4
0100
A
⇒
B
¯
{\displaystyle {\overline {A\Rightarrow B}}}
5
0101
B
¯
{\displaystyle {\overline {B}}}
6
0110
A
⊕
B
{\displaystyle A\oplus B}
Kontravalenz
7
0111
A
∧
B
¯
{\displaystyle {\overline {A\land B}}}
8
1000
A
∧
B
{\displaystyle A\land B}
Konjunktion
9
1001
A
⇔
B
{\displaystyle A\Leftrightarrow B}
Äquivalenz
10
1010
B
{\displaystyle B}
11
1011
A
⇒
B
{\displaystyle A\Rightarrow B}
Implikation
12
1100
A
{\displaystyle A}
13
1101
B
⇒
A
{\displaystyle B\Rightarrow A}
14
1110
A
∨
B
{\displaystyle A\lor B}
Disjunktion
15
1111
1
{\displaystyle 1}
Tautologie
Bearbeiten
A
⇒
B
⟺
A
¯
∨
B
{\displaystyle A\Rightarrow B\iff {\overline {A}}\lor B}
(
A
⇔
B
)
⟺
(
A
¯
∧
B
¯
)
∨
(
A
∧
B
)
{\displaystyle (A\Leftrightarrow B)\iff ({\overline {A}}\land {\overline {B}})\lor (A\land B)}
A
⊕
B
⟺
(
A
¯
∧
B
)
∨
(
A
∧
B
¯
)
{\displaystyle A\oplus B\iff ({\overline {A}}\land B)\lor (A\land {\overline {B}})}
Modus ponens:
(
A
⇒
B
)
∧
A
⟹
B
{\displaystyle (A\Rightarrow B)\land A\implies B}
Modus tollens:
(
A
⇒
B
)
∧
B
¯
⟹
A
¯
{\displaystyle (A\Rightarrow B)\land {\overline {B}}\implies {\overline {A}}}
Modus tollendo ponens:
(
A
∨
B
)
∧
A
¯
⟹
B
{\displaystyle (A\lor B)\land {\overline {A}}\implies B}
Modus ponendo tollens:
A
∧
B
¯
∧
A
⟹
B
¯
{\displaystyle {\overline {A\land B}}\land A\implies {\overline {B}}}
Kontraposition:
A
⇒
B
⟺
B
¯
⇒
A
¯
{\displaystyle A\Rightarrow B\iff {\overline {B}}\Rightarrow {\overline {A}}}
Beweis durch Widerspruch:
(
A
¯
⇒
B
∧
B
¯
)
⟹
A
{\displaystyle ({\overline {A}}\Rightarrow B\land {\overline {B}})\implies A}
Zerlegung einer Äquivalenz:
(
A
⇔
B
)
⟺
(
A
⇒
B
)
∧
(
B
⇒
A
)
{\displaystyle (A\Leftrightarrow B)\iff (A\Rightarrow B)\land (B\Rightarrow A)}
Kettenschluss:
(
A
⇒
B
)
∧
(
B
⇒
C
)
⟹
(
A
⇒
C
)
{\displaystyle (A\Rightarrow B)\land (B\Rightarrow C)\implies (A\Rightarrow C)}
Ringschluss:
(
A
⇒
B
)
∧
(
B
⇒
C
)
∧
(
C
⇒
A
)
{\displaystyle (A\Rightarrow B)\land (B\Rightarrow C)\land (C\Rightarrow A)}
⟹
(
A
⇔
B
)
∧
(
A
⇔
C
)
∧
(
B
⇔
C
)
{\displaystyle \implies (A\Leftrightarrow B)\land (A\Leftrightarrow C)\land (B\Leftrightarrow C)}
Ringschluss, allgemein:
(
A
1
⇒
A
2
)
∧
…
∧
(
A
n
−
1
⇒
A
n
)
∧
(
A
n
⇒
A
1
)
{\displaystyle (A_{1}\Rightarrow A_{2})\land \ldots \land (A_{n-1}\Rightarrow A_{n})\land (A_{n}\Rightarrow A_{1})}
⟹
∀
i
,
j
[
A
i
⇔
A
j
]
{\displaystyle \implies \forall i,j\,[A_{i}\Leftrightarrow A_{j}]}
Modus ponens:
{
φ
,
φ
→
ψ
}
⊢
ψ
{\displaystyle \{\varphi ,\varphi \rightarrow \psi \}\vdash \psi }
Sei
M
=
{
φ
1
,
…
,
φ
n
}
{\displaystyle M=\{\varphi _{1},\ldots ,\varphi _{n}\}}
Korrektheit der Aussagenlogik.
Es gilt:
(
M
⊢
ψ
)
⟹
(
M
⊨
ψ
)
.
{\displaystyle (M\vdash \psi )\implies (M\models \psi ).}
Vollständigkeit der Aussagenlogik.
Es gilt:
(
M
⊨
ψ
)
⟹
(
M
⊢
ψ
)
.
{\displaystyle (M\models \psi )\implies (M\vdash \psi ).}
Deduktionstheorem (syntaktisch).
Es gilt:
(
M
∪
{
φ
}
⊢
ψ
)
⟺
(
M
⊢
φ
→
ψ
)
.
{\displaystyle (M\cup \{\varphi \}\vdash \psi )\iff (M\vdash \varphi \rightarrow \psi ).}
Infolge gilt auch:
(
{
φ
1
,
…
,
φ
n
}
⊢
ψ
)
⟺
(
⊢
φ
1
∧
…
∧
φ
n
→
ψ
)
.
{\displaystyle (\{\varphi _{1},\ldots ,\varphi _{n}\}\vdash \psi )\iff (\vdash \varphi _{1}\land \ldots \land \varphi _{n}\rightarrow \psi ).}
Deduktionstheorem (semantisch).
Es gilt:
(
M
∪
{
φ
}
⊨
ψ
)
⟺
(
M
⊨
φ
→
ψ
)
.
{\displaystyle (M\cup \{\varphi \}\models \psi )\iff (M\models \varphi \rightarrow \psi ).}
Infolge gilt auch:
(
{
φ
1
,
…
,
φ
n
}
⊨
ψ
)
⟺
(
⊨
φ
1
∧
…
∧
φ
n
→
ψ
)
.
{\displaystyle (\{\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:
(
⊨
φ
)
⟹
(
⊨
φ
[
v
:=
ψ
]
)
.
{\displaystyle (\models \varphi )\implies (\models \varphi [v:=\psi ]).}
Das gilt auch für die simultane Substitution:
(
⊨
φ
)
⟹
(
⊨
φ
[
v
1
:=
ψ
1
,
…
,
v
n
:=
ψ
n
]
)
.
{\displaystyle (\models \varphi )\implies (\models \varphi [v_{1}:=\psi _{1},\ldots ,v_{n}:=\psi _{n}]).}
Beispiel. Man überzeugt sich z. B. mittels einer Wahrheitstabelle von
⊨
A
∧
(
A
→
B
)
→
B
.
{\displaystyle \models A\land (A\rightarrow B)\rightarrow B.}
Unter Anwendung der Einsetzungsregel lassen sich die zwei Variablen simultan gegen Formeln austauschen:
⊨
φ
∧
(
φ
→
ψ
)
→
ψ
.
{\displaystyle \models \varphi \land (\varphi \rightarrow \psi )\rightarrow \psi .}
Zieht man nun die Vollständigkeit und das Deduktionstheorem heran, ergibt sich der Modus ponens:
{
φ
,
φ
→
ψ
}
⊢
ψ
.
{\displaystyle \{\varphi ,\varphi \rightarrow \psi \}\vdash \psi .}
Definition. Formale Sprache der Aussagenlogik.
Sei
V
=
{
A
1
,
A
2
,
A
3
,
…
}
{\displaystyle V=\{A_{1},A_{2},A_{3},\ldots \}}
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
(
¬
φ
)
,
(
φ
∧
ψ
)
,
(
φ
∨
ψ
)
,
(
φ
→
ψ
)
,
(
φ
↔
ψ
)
{\displaystyle (\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
,
…
}
{\displaystyle V=\{A,B,C,\ldots \}}
Außerdem können Klammernpaare wie bei Punktrechnung-vor-Strichrechnung weggelassen werden, wobei die Bindungsstärke in absteigender Reihenfolge
¬
,
∧
,
∨
,
→
,
↔
{\displaystyle \neg ,\land ,\lor ,\rightarrow ,\leftrightarrow }
Anstelle von
¬
φ
{\displaystyle \neg \varphi }
φ
¯
{\displaystyle {\overline {\varphi }}}
Das Axiom (P4) ist redundant.
Definition. Modellrelation.
Eine Formelmenge M modelliert eine Formel ψ , wenn jedes Modell von M auch ein Modell von ψ ist. Kurz:
(
M
⊨
ψ
)
:⟺
∀
I
[
(
I
⊨
M
)
⟹
(
I
⊨
ψ
)
]
.
{\displaystyle (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:
(
⊨
φ
)
:⟺
∀
I
(
I
(
φ
)
=
1
)
.
{\displaystyle (\models \varphi )\;:\Longleftrightarrow \;\forall I(I(\varphi )=1).}
Eine Formel ist genau dann tautologisch, wenn sie durch die leere Menge modelliert wird:
(
⊨
φ
)
⟺
(
{
}
⊨
φ
)
.
{\displaystyle (\models \varphi )\iff (\{\}\models \varphi ).}
Definition. Erfüllbare Formel.
Eine Formel wird erfüllbar genannt, wenn sie ein Modell besitzt. Kurz:
erf
[
φ
]
:⟺
∃
I
(
I
(
φ
)
=
1
)
.
{\displaystyle \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:
¬
erf
[
φ
]
⟺
∀
I
(
I
(
φ
)
=
0
)
.
{\displaystyle \neg \operatorname {erf} [\varphi ]\iff \forall I(I(\varphi )=0).}
Definition. Erfüllbarkeitsäquivalenz.
Zwei Formeln φ und ψ heißen erfüllbarkeitsäquivalent, wenn gilt:
erf
[
φ
]
⟺
erf
[
ψ
]
.
{\displaystyle \operatorname {erf} [\varphi ]\iff \operatorname {erf} [\psi ].}
Das Modell der ersten Formel braucht dabei nicht mit dem Modell der zweiten Formel übereinzustimmen.
Verneinung (De Morgansche Gesetze):
¬
∀
x
[
P
(
x
)
]
⟺
∃
x
[
¬
P
(
x
)
]
{\displaystyle \neg \forall x[P(x)]\iff \exists x[\neg P(x)]}
¬
∃
x
[
P
(
x
)
]
⟺
∀
x
[
¬
P
(
x
)
]
{\displaystyle \neg \exists x[P(x)]\iff \forall x[\neg P(x)]}
Verallgemeinerte Distributivgesetze:
P
∧
∃
x
[
Q
(
x
)
]
⟺
∃
x
[
P
∧
Q
(
x
)
]
{\displaystyle P\land \exists x[Q(x)]\iff \exists x[P\land Q(x)]}
P
∨
∀
x
[
Q
(
x
)
]
⟺
∀
x
[
P
∨
Q
(
x
)
]
{\displaystyle P\lor \forall x[Q(x)]\iff \forall x[P\lor Q(x)]}
Verallgemeinerte Idempotenzgesetze:
∃
x
∈
M
[
P
]
⟺
(
M
≠
{
}
)
∧
P
⟺
{
P
wenn
M
≠
{
}
0
wenn
M
=
{
}
{\displaystyle \exists x{\in }M\,[P]\iff (M\neq \{\})\land P\iff {\begin{cases}P&{\text{wenn}}\;M\neq \{\}\\0&{\text{wenn}}\;M=\{\}\end{cases}}}
∀
x
∈
M
[
P
]
⟺
(
M
=
{
}
)
∨
P
⟺
{
P
wenn
M
≠
{
}
1
wenn
M
=
{
}
{\displaystyle \forall x{\in }M\,[P]\iff (M=\{\})\lor P\iff {\begin{cases}P&{\text{wenn}}\;M\neq \{\}\\1&{\text{wenn}}\;M=\{\}\end{cases}}}
Äquivalenzen:
∀
x
∀
y
[
P
(
x
,
y
)
]
⟺
∀
y
∀
x
[
P
(
x
,
y
)
]
{\displaystyle \forall x\forall y[P(x,y)]\iff \forall y\forall x[P(x,y)]}
∃
x
∃
y
[
P
(
x
,
y
)
]
⟺
∃
y
∃
x
[
P
(
x
,
y
)
]
{\displaystyle \exists x\exists y[P(x,y)]\iff \exists y\exists x[P(x,y)]}
∀
x
[
P
(
x
)
∧
Q
(
x
)
]
⟺
∀
x
[
P
(
x
)
]
∧
∀
x
[
Q
(
x
)
]
{\displaystyle \forall x[P(x)\land Q(x)]\iff \forall x[P(x)]\land \forall x[Q(x)]}
∃
x
[
P
(
x
)
∨
Q
(
x
)
]
⟺
∃
x
[
P
(
x
)
]
∨
∃
x
[
Q
(
x
)
]
{\displaystyle \exists x[P(x)\lor Q(x)]\iff \exists x[P(x)]\lor \exists x[Q(x)]}
∀
x
[
P
(
x
)
⇒
Q
]
⟺
∃
x
[
P
(
x
)
]
⇒
Q
{\displaystyle \forall x[P(x)\Rightarrow Q]\iff \exists x[P(x)]\Rightarrow Q}
∀
x
[
P
⇒
Q
(
x
)
]
⟺
P
⇒
∀
x
[
Q
(
x
)
]
{\displaystyle \forall x[P\Rightarrow Q(x)]\iff P\Rightarrow \forall x[Q(x)]}
∃
x
[
P
(
x
)
⇒
Q
(
x
)
]
⟺
∀
x
[
P
(
x
)
]
⇒
∃
x
[
Q
(
x
)
]
{\displaystyle \exists x[P(x)\Rightarrow Q(x)]\iff \forall x[P(x)]\Rightarrow \exists x[Q(x)]}
Implikationen:
∃
x
∀
y
[
P
(
x
,
y
)
]
⟹
∀
y
∃
x
[
P
(
x
,
y
)
]
{\displaystyle \exists x\forall y[P(x,y)]\implies \forall y\exists x[P(x,y)]}
∀
x
[
P
(
x
)
]
∨
∀
x
[
Q
(
x
)
]
⟹
∀
x
[
P
(
x
)
∨
Q
(
x
)
]
{\displaystyle \forall x[P(x)]\lor \forall x[Q(x)]\implies \forall x[P(x)\lor Q(x)]}
∃
x
[
P
(
x
)
∧
Q
(
x
)
]
⟹
∃
x
[
P
(
x
)
]
∧
∃
x
[
Q
(
x
)
]
{\displaystyle \exists x[P(x)\land Q(x)]\implies \exists x[P(x)]\land \exists x[Q(x)]}
∀
x
[
P
(
x
)
⇒
Q
(
x
)
]
⟹
(
∀
x
[
P
(
x
)
]
⇒
∀
x
[
Q
(
x
)
]
)
{\displaystyle \forall x[P(x)\Rightarrow Q(x)]\implies (\forall x[P(x)]\Rightarrow \forall x[Q(x)])}
∀
x
[
P
(
x
)
⇔
Q
(
x
)
]
⟹
(
∀
x
[
P
(
x
)
]
⇔
∀
x
[
Q
(
x
)
]
)
{\displaystyle \forall x[P(x)\Leftrightarrow Q(x)]\implies (\forall x[P(x)]\Leftrightarrow \forall x[Q(x)])}
Sei
M
=
{
x
1
,
…
,
x
n
}
{\displaystyle M=\{x_{1},\ldots ,x_{n}\}}
∀
x
∈
M
[
P
(
x
)
]
⟺
P
(
x
1
)
∧
…
∧
P
(
x
n
)
{\displaystyle \forall x{\in }M\,[P(x)]\iff P(x_{1})\land \ldots \land P(x_{n})}
∃
x
∈
M
[
P
(
x
)
]
⟺
P
(
x
1
)
∨
…
∨
P
(
x
n
)
{\displaystyle \exists x{\in }M\,[P(x)]\iff P(x_{1})\lor \ldots \lor P(x_{n})}
∀
x
∈
M
[
P
(
x
)
]
:⟺
∀
x
[
x
∉
M
∨
P
(
x
)
]
⟺
∀
x
[
x
∈
M
⇒
P
(
x
)
]
{\displaystyle \forall x{\in }M\,[P(x)]\,:\Longleftrightarrow \,\forall x[x\notin M\vee P(x)]\iff \forall x[x\in M\Rightarrow P(x)]}
∃
x
∈
M
[
P
(
x
)
]
:⟺
∃
x
[
x
∈
M
∧
P
(
x
)
]
{\displaystyle \exists x{\in }M\,[P(x)]\,:\Longleftrightarrow \,\exists x[x\in M\wedge P(x)]}
∀
x
∈
M
∖
N
[
P
(
x
)
]
⟺
∀
x
∈
M
[
x
∉
N
⇒
P
(
x
)
]
{\displaystyle \forall x{\in }M{\setminus }N\,[P(x)]\iff \forall x{\in }M\,[x\notin N\Rightarrow P(x)]}
∃
(
x
,
y
)
[
P
(
x
,
y
)
]
⟺
∃
x
∃
y
[
P
(
x
,
y
)
]
{\displaystyle \exists (x,y)\,[P(x,y)]\iff \exists x\exists y\,[P(x,y)]}
∀
(
x
,
y
)
[
P
(
x
,
y
)
]
⟺
∀
x
∀
y
[
P
(
x
,
y
)
]
{\displaystyle \forall (x,y)\,[P(x,y)]\iff \forall x\forall y\,[P(x,y)]}
Analog gilt
∃
(
x
,
y
,
z
)
[
P
(
x
,
y
,
z
)
]
⟺
∃
x
∃
y
∃
z
[
P
(
x
,
y
,
z
)
]
{\displaystyle \exists (x,y,z)[P(x,y,z)]\iff \exists x\exists y\exists z\,[P(x,y,z)]}
∀
(
x
,
y
,
z
)
[
P
(
x
,
y
,
z
)
]
⟺
∀
x
∀
y
∀
z
[
P
(
x
,
y
,
z
)
]
{\displaystyle \forall (x,y,z)[P(x,y,z)]\iff \forall x\forall y\forall z\,[P(x,y,z)]}
usw.
Sei
P
:
G
→
{
0
,
1
}
{\displaystyle P\colon G\to \{0,1\}}
M
⊆
G
{\displaystyle M\subseteq G}
P
(
M
)
{\displaystyle P(M)}
P
{\displaystyle P}
M
{\displaystyle M}
∀
x
∈
M
[
P
(
x
)
]
⟺
P
(
M
)
=
{
1
}
⟺
M
⊆
{
x
∈
G
∣
P
(
x
)
}
{\displaystyle \forall x{\in }M\,[P(x)]\iff P(M)=\{1\}\iff M\subseteq \{x{\in }G\mid P(x)\}}
∃
x
∈
M
[
P
(
x
)
]
⟺
{
1
}
⊆
P
(
M
)
⟺
M
∩
{
x
∈
G
∣
P
(
x
)
}
≠
{
}
{\displaystyle \exists x{\in }M\,[P(x)]\iff \{1\}\subseteq P(M)\iff M\cap \{x{\in }G\mid P(x)\}\neq \{\}}
Sei
g
:
M
→
N
{\displaystyle g\colon M\to N}
∀
x
∈
M
[
P
(
x
)
]
⟺
∀
y
∈
g
(
M
)
[
P
(
g
−
1
(
y
)
)
]
{\displaystyle \forall x{\in }M\,[P(x)]\iff \forall y\in g(M)\,[P(g^{-1}(y))]}
∃
x
∈
M
[
P
(
x
)
]
⟺
∃
y
∈
g
(
M
)
[
P
(
g
−
1
(
y
)
)
]
{\displaystyle \exists x{\in }M\,[P(x)]\iff \exists y\in g(M)\,[P(g^{-1}(y))]}
Ist
g
{\displaystyle g}
M
{\displaystyle M}
∀
x
∈
M
[
P
(
x
)
]
⟺
∀
x
∈
M
[
P
(
g
−
1
(
x
)
)
]
{\displaystyle \forall x{\in }M\,[P(x)]\iff \forall x{\in }M\,[P(g^{-1}(x))]}
∃
x
∈
M
[
P
(
x
)
]
⟺
∃
x
∈
M
[
P
(
g
−
1
(
x
)
)
]
{\displaystyle \exists x{\in }M\,[P(x)]\iff \exists x{\in }M\,[P(g^{-1}(x))]}
Quantor für eindeutige Existenz:
∃
!
x
[
P
(
x
)
]
{\displaystyle \exists !x\,[P(x)]}
:⟺
∃
x
[
P
(
x
)
∧
∀
y
[
P
(
y
)
⇒
x
=
y
]
]
{\displaystyle :\Longleftrightarrow \;\exists x\,[P(x)\land \forall y\,[P(y)\Rightarrow x=y]]}
⟺
∃
x
[
P
(
x
)
]
∧
∀
x
∀
y
[
P
(
x
)
∧
P
(
y
)
⇒
x
=
y
]
{\displaystyle \iff \exists x\,[P(x)]\land \forall x\forall y[P(x)\land P(y)\Rightarrow x=y]}
![{\displaystyle \implies \forall i,j\,[A_{i}\Leftrightarrow A_{j}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8da12d02356a7ac773d13ce14e32313421b99b19)
![{\displaystyle (\models \varphi )\implies (\models \varphi [v:=\psi ]).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c829a4cacb14ce322652c0b4afe1985920f1ac41)
![{\displaystyle (\models \varphi )\implies (\models \varphi [v_{1}:=\psi _{1},\ldots ,v_{n}:=\psi _{n}]).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d3922063d562037158aeee5b0bc5db21b0b2b6ef)
![{\displaystyle (M\models \psi )\;:\Longleftrightarrow \;\forall I[(I\models M)\implies (I\models \psi )].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e393926fb0627ffc84f84da96d915c6cc09b1a00)
![{\displaystyle \operatorname {erf} [\varphi ]\;:\Longleftrightarrow \;\exists I(I(\varphi )=1).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/83dd811a5eff2648ea647af57024de76795cc3e0)
![{\displaystyle \neg \operatorname {erf} [\varphi ]\iff \forall I(I(\varphi )=0).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/23726a63f27c202654141b2753ba4cf3cda37ecd)
![{\displaystyle \operatorname {erf} [\varphi ]\iff \operatorname {erf} [\psi ].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/101385805233d7ba5c44a1c75af7f42f9b4a6d2d)
![{\displaystyle \neg \forall x[P(x)]\iff \exists x[\neg P(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/62a89e794f4aeef6649697ac605d4e95fbd4c9db)
![{\displaystyle \neg \exists x[P(x)]\iff \forall x[\neg P(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3d4ed0a8577c409586d4551ff26e3efc11773c16)
![{\displaystyle P\land \exists x[Q(x)]\iff \exists x[P\land Q(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a865705386c7cac2f541914ecf2cc06f310e72aa)
![{\displaystyle P\lor \forall x[Q(x)]\iff \forall x[P\lor Q(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/168734450d98f2bad2460d0588c1c711bb526c3c)
![{\displaystyle \exists x{\in }M\,[P]\iff (M\neq \{\})\land P\iff {\begin{cases}P&{\text{wenn}}\;M\neq \{\}\\0&{\text{wenn}}\;M=\{\}\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/60a7e73d515cb886397773e4b72984cc09cb671f)
![{\displaystyle \forall x{\in }M\,[P]\iff (M=\{\})\lor P\iff {\begin{cases}P&{\text{wenn}}\;M\neq \{\}\\1&{\text{wenn}}\;M=\{\}\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e9e9caec7a4720faf3089422806a72e5a93ae6d)
![{\displaystyle \forall x\forall y[P(x,y)]\iff \forall y\forall x[P(x,y)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b90226c80062f3fd15343bb1f742b9968a10bf8)
![{\displaystyle \exists x\exists y[P(x,y)]\iff \exists y\exists x[P(x,y)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9eaf4d427581b1b9302fb80a699fddad02e32af)
![{\displaystyle \forall x[P(x)\land Q(x)]\iff \forall x[P(x)]\land \forall x[Q(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e5c325b3967273188efc1305e78281e2026be04f)
![{\displaystyle \exists x[P(x)\lor Q(x)]\iff \exists x[P(x)]\lor \exists x[Q(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10954544fd0a6140d53063ddf369da789b9b664f)
![{\displaystyle \forall x[P(x)\Rightarrow Q]\iff \exists x[P(x)]\Rightarrow Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/197b0d7da8c1c1c6523d452d59092890fb42058a)
![{\displaystyle \forall x[P\Rightarrow Q(x)]\iff P\Rightarrow \forall x[Q(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e41fa4b0f450aa19843b68c44ec38c94ee556241)
![{\displaystyle \exists x[P(x)\Rightarrow Q(x)]\iff \forall x[P(x)]\Rightarrow \exists x[Q(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb3bb3df29c39088d8260519cbcd5895d1f22050)
![{\displaystyle \exists x\forall y[P(x,y)]\implies \forall y\exists x[P(x,y)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9b5b950d4ce172109e000e35e9b37112df6831a)
![{\displaystyle \forall x[P(x)]\lor \forall x[Q(x)]\implies \forall x[P(x)\lor Q(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4f559cd8a3262b6429025a65097a54a022704fa6)
![{\displaystyle \exists x[P(x)\land Q(x)]\implies \exists x[P(x)]\land \exists x[Q(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3d3b4f31615784181fc9a3f2e9658b5940c296c3)
![{\displaystyle \forall x[P(x)\Rightarrow Q(x)]\implies (\forall x[P(x)]\Rightarrow \forall x[Q(x)])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de48500bc136458631862177605c295a97b9f3f7)
![{\displaystyle \forall x[P(x)\Leftrightarrow Q(x)]\implies (\forall x[P(x)]\Leftrightarrow \forall x[Q(x)])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0abfeb9a2cf63e78de92a36d49dba42618860da1)
![{\displaystyle \forall x{\in }M\,[P(x)]\iff P(x_{1})\land \ldots \land P(x_{n})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/117da61f5b6d9f542907d5f05de6921f403389e4)
![{\displaystyle \exists x{\in }M\,[P(x)]\iff P(x_{1})\lor \ldots \lor P(x_{n})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e4f7fc7f8e5988695be6d548424864277fd5f2c)
![{\displaystyle \forall x{\in }M\,[P(x)]\,:\Longleftrightarrow \,\forall x[x\notin M\vee P(x)]\iff \forall x[x\in M\Rightarrow P(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a4639ba98d1b1827c56e8df4a7faae56deab7d7)
![{\displaystyle \exists x{\in }M\,[P(x)]\,:\Longleftrightarrow \,\exists x[x\in M\wedge P(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e908c0518b63c3f36bbddce9381f79270b045f55)
![{\displaystyle \forall x{\in }M{\setminus }N\,[P(x)]\iff \forall x{\in }M\,[x\notin N\Rightarrow P(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/16c4c48857e12f3952c66f133a34f432f1d2fdb2)
![{\displaystyle \exists (x,y)\,[P(x,y)]\iff \exists x\exists y\,[P(x,y)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f47430bd8c15b370977a1ccb0809ce121ce8285f)
![{\displaystyle \forall (x,y)\,[P(x,y)]\iff \forall x\forall y\,[P(x,y)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f1ac9e70ab80ef25b952693272743fe800fedd0a)
![{\displaystyle \exists (x,y,z)[P(x,y,z)]\iff \exists x\exists y\exists z\,[P(x,y,z)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0309c3ef8b56872f7ac5dc78b11cd59d020b53a9)
![{\displaystyle \forall (x,y,z)[P(x,y,z)]\iff \forall x\forall y\forall z\,[P(x,y,z)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/650e4491eee513721619de32fe341b9f4a2f61ea)
![{\displaystyle \forall x{\in }M\,[P(x)]\iff P(M)=\{1\}\iff M\subseteq \{x{\in }G\mid P(x)\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b601c75a300c41b101533fc565942db6b04b176a)
![{\displaystyle \exists x{\in }M\,[P(x)]\iff \{1\}\subseteq P(M)\iff M\cap \{x{\in }G\mid P(x)\}\neq \{\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0004039fb0f641c24b235a8ab5c76cab8221d097)
![{\displaystyle \forall x{\in }M\,[P(x)]\iff \forall y\in g(M)\,[P(g^{-1}(y))]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ba4aa82c7489e45fb52ee38e36ae6a44110af06e)
![{\displaystyle \exists x{\in }M\,[P(x)]\iff \exists y\in g(M)\,[P(g^{-1}(y))]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ff4bf2823b86316ec1c5e7ba48622f12ce9fe7a)
![{\displaystyle \forall x{\in }M\,[P(x)]\iff \forall x{\in }M\,[P(g^{-1}(x))]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/944574dd5eeb64327a404ab00d5a1febd65dd231)
![{\displaystyle \exists x{\in }M\,[P(x)]\iff \exists x{\in }M\,[P(g^{-1}(x))]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2fa3a38972c31e35c57e8aa856ecd15681572d73)
![{\displaystyle \exists !x\,[P(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2de5632d68703e84c626b7d4a72758f038bb328d)
![{\displaystyle :\Longleftrightarrow \;\exists x\,[P(x)\land \forall y\,[P(y)\Rightarrow x=y]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4109df6763f826cc8d32be042bd2aaf31d531c9)
![{\displaystyle \iff \exists x\,[P(x)]\land \forall x\forall y[P(x)\land P(y)\Rightarrow x=y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f2474413c4a267d4ea1283bd4a98e150a9587f1e)