Logik

Verknüpfungen

• Negation
  $\neg a$: nicht $a$
• Implikation
  $a\Rightarrow b$: aus $a$ folgt $b$
• Äquivalenz
  $a\Longleftrightarrow b$: $a$ und $b$ sind äquivalent (gleichwertig)
• Konjunktion
  $a\wedge b$: $a$ und $b$
• Disjunktion
  $a\vee b$: $a$ oder $b$

Rechenregeln

• Kommutativgesetz
  $a\wedge b=b\wedge a$
  $a\vee b=b\vee a$
• Assoziativgesetz
  $\left(a\wedge b\right)\wedge c=a\wedge\left(b\wedge c\right)$
  $\left(a\vee b\right)\vee c=a\vee\left(b\vee c\right)$
• Distributivgesetz
  $a\wedge\left(b\vee c\right)=\left(a\wedge b\right)\vee\left(a\wedge c\right)$
  $a\vee\left(b\wedge c\right)=\left(a\vee b\right)\wedge\left(a\vee c\right)$
• De Morgan
  $\neg\left(a\vee b\right)=\left(\neg a\right)\wedge\left(\neg b\right)$
  $\neg\left(a\wedge b\right)=\left(\neg a\right)\vee\left(\neg b\right)$
• doppelte Negation
  $\neg\left(\neg a\right)=a$
• neutrales Element
  $a\vee\textrm{f}=a$
  $a\wedge\textrm{f}=\textrm{f}$
  $a\vee\textrm{w}=\textrm{w}$
  $a\wedge\textrm{w}=a$
• inverses Element
  $a\vee\left(\neg a\right)=\textrm{w}$
  $a\wedge\left(\neg a\right)=\textrm{f}$

Quantoren

• Allquantor $\forall x:\varphi(x)$
  für alle $x$ gilt $\varphi(x)$.
  z.B. $\forall x\in\mathbb{N}:x^{2}\in\mathbb{N}=\forall_{\mathbb{N}}^{x}:x^{2}\in\mathbb{N}$
• Existenzquantor $\exists x:\varphi(x)$
  es gibt (mindestens) ein $x$ für das $\varphi(x)$ gilt.
  z.B. $\exists x\in\mathbb{N}:\varphi(x)=\exists_{\mathbb{N}}^{x}:\varphi(x)$
• $\exists!x:\varphi(x)$ oder $\exists^{1}x:\varphi(x)$
  es gibt genau ein $x$ für das $\varphi(x)$ gilt.
• Negation $\forall x:H(x)\Leftrightarrow\neg\exists x:\neg H(x)$
  Es gilt für alle $x$, $H(x)$ $\Leftrightarrow$ Es gibt nicht ein $x$, für das $H(x)$ nicht gilt.

Eigenschaften von Aussagen

Widerspruch

heißt eine zusammengesetzte Aussage, wenn sie immer falsch ist.
z.B. $A\wedge\neg A$

Tautologie

(Symbol: Blitz) heißt eine Aussage, wenn sie immer wahr ist.
z.B. $A\vee\neg A$