TU Wien:Mathematik 1 VO (Panholzer)/Stoff WS05/11. VO 08.11.2005

Mathematische Logik:

• Binden von Variablen mittels Quantoren (in Prädikaten):
  • Existenzquantor $\exists {\text{ x }}P(x)$
  • Allquantor $\forall {\text{ x }}P(x)$

Beispiel: P(x,y): x < y; x,y $\in \mathbb {N}$

$\forall {\text{ x }}\exists {\text{ y }}P(x,y)$: Warum wahr?

$\exists {\text{ y }}\forall {\text{ x }}P(x,y)$: Warum wahr?

$\exists {\text{ x }}P(x,y)\Rightarrow Q(y)$: Prädikat, von y abhängig

Q(0) ... falsch; Q(10) .... wahr

• Verknüpfen von Aussagen mittels Junktoren:
  • Negation $\neg$
  • Konjunktion $\wedge$
  • Disjunktion $\vee$
  • $\rightarrow$ Impliaktion
  • $\leftrightarrow$ Äquivalenz
  • NOR, NAND

Wahrheitstafel:

A	B	$\neg A$	$A\wedge B$	$A\vee B$	$A\rightarrow B$	$A\leftrightarrow B$
1	1	0	1	1	1	1
1	0	0	0	1	0	0
0	1	1	0	1	1	0
0	0	1	0	0	1	1

$A\rightarrow B$ gleichbedeutend mit $\neg A\vee B$

Beweis durch Wahrheitstabelle:

A	B	$\neg A$	$\neg A\vee B$	$A\rightarrow B$
1	1	0	1	1
1	0	0	0	0
0	1	1	1	1
0	0	1	1	1

$A\leftrightarrow B$ gleichbedeutend mit $(A\rightarrow B)\vee (B\rightarrow B)$

(Anm.: Müsste das nicht $(A\rightarrow B)\vee (B\rightarrow A)$ heißen?)

Definition: Unter einer Formel der Aussagenlogik versteht man einen Ausdruck F(A,B,C,...) der in endlich vielen Schritten aus den Aussagen von A,B,C .... durch Verknüpfung mit Junktioren gebildet werden kann.

Definition: Eine Formel F(A,B,C,...) heißt

• gültig, wenn der Ausdruck für alle möglichen Belegungen der Aussagenvariablen mit Werten aus $\mathbb {B}$ wahr ist. (Tautologie)
• erfüllbar, wenn es zumindest eine Belegung gibt, sodass der Ausdruck wahr ist.
• Kontraktion (nicht erfüllbar), wenn der Auedruck für alle Belegungen falsch ist.

Beispiel: F(A,B) = $\neg A\rightarrow (A\rightarrow B)$

Behauptung: F(A,B) ist Tautologie

Beweis: Wahrheitstafel

A	B	$\neg A$	$A\rightarrow B$	$\neg A\rightarrow (A\rightarrow B)$
1	1	0	1	1
1	0	0	0	1
0	1	1	1	1
0	0	1	1	1

Definition: Tautologie: $A\vee \neq$ (Satz vom ausgeschlossenen Dritten)

Erfüllbare Formel: $A\wedge B$ ... Belegung: A=1, B=1 OK

Kontradiktion: $A\wedge \neg A$ (Satz vom Widespruch)

Resolution, "Schlußregeln"

Kombinatorik

• Grundlagen des Abzählens endlicher Mengen
  • "Summenregel": Gib es n Elemente vom Typ A und m Elemente vom Typ B dann gibt es m + n Möglichkeiten ein Element vom Typ A oder B auszuwählen.

$|A\cup B|=|A|+|B|$, fals $|A|\cap B=\emptyset$

• • "Produktregel": Gibt es n Element vom Typ A und m Elemente vom Typ B, dann gibt es n*m Möglichkeiten ein Element vom Typ A und ein Element vom Typ B auszuwählen.

Beispiel: Es gibt $2^{n}$ Binärfolgen der Länge n

$\{0,1\}\times \{0,1\}\times ...\times \{0,1\}=\{0,1\}^{n}$

$|\{0,1\}^{n}|=2*2*2*..*2=2^{n}$

• • "Gleichheitsregel": Entsprechen einander die Typen A und B umkehrbar eindeutig, dann gibt es gleich viele Möglichkeiten, Elemente aus A auszuwählen wie es Möglichkeiten, Elemente aus B auszuwählen.

A $\cong$ B ... es bsteht Bijektion zwischen Elementen vom Typ A und Elementen vom Typ B

Beispiel: Menge M mit n Elementen $\{a_{1},...,a_{n}\}$

zu zeigen: $|P(M)|=|\{0,1\}^{n}|$ (= $2^{n}$)

Satz: Es gibt gleich viele Elemenze der Potenzmenge einer n-elementigen Menge, wie es Binärfolgen der Länge n gibt.

Beweis: Abgabe einer Funktiion, d.h. zeigen, dass $P(M)\cong \{0,1\}^{n}$

geg.: $A\in P(M)$

Annahme. $A=\{a_{1},a_{2},a_{4},a_{n}\}$

Umwandlung in Binärfolge:

  1 1 0 1 0 . . . . 0 1
  1 2 3 4 5 . . . . * n    * = n -1

Eindeutig zurückverfolgbar!

$|P(M)|=|\{0,1\}^{n}|$

Geg.: n-elementige Menge A

Eine Permutation von A ist eine (lineare) Anordnung der Elemente von A

$A=\{B,W,S\}$

Kombinationsmöglichkeiten:

  BWS   WBS   SBW
  BSW   WSB   SWB

$\Rightarrow$ 6 Permutationen der Elemente von A