Logik und Beweise

Logik

$A\to B\equiv \neg A\vee B$

Klausel: Disjunktion über Literale (pos. / neg.)
KNF: Konjunktion von Disjunktionen

Quantoren-Umformungen

Für jede Menge $X$:
$(\exists x\in X:\phi (x))\wedge A\equiv \exists x\in X:(\phi (x)\wedge A)$
$(\forall x\in X:\phi (x))\vee A\equiv \forall x\in X:(\phi (x)\vee A)$

Für jede nicht-leere Menge $X$:
$(\exists x\in X:\phi (x))\vee A\equiv \exists x\in X:(\phi (x)\vee A)$
$(\forall x\in X:\phi (x))\wedge A\equiv \forall x\in X:(\phi (x)\wedge A)$

Begriffe

Pränexform: Quantoren nur zu Beginn

Logische Äquivalenz: gleiche Wahrheitswerte für alle Belegungen): $\phi \equiv \psi$

---

Beweisemethoden

Beweis von Mengeninklusionen und Mengengleichheit

Seien $A$ und $B$ Mengen. Möchte man zeigen, dass $A\subseteq B$, so zeigt man $\forall a\in A:a\in B$. Man wählt sich also ein beliebiges aber festes $a\in A$ und zeigt dann, dass $a\in B$ auch gilt. Darüber kann man nun auch Mengengleichheit zeigen: Möchte man $A=B$ zeigen, so zeigt man $A\subseteq B\wedge B\subseteq A$, also zunächst $\forall a\in A:a\in B$ und danach $\forall a\in B:a\in A$.