161026 Vorlesung

Aussageformeln p,q

heißen logisch äquivalent, wenn $p\leftrightarrow q$ eine Tautologie ist. Schreibweise: $p\equiv q$ p impliziert q bedeutet: $p\to q$ ist Tautologie

Z.Bsp. $p⟹q\equiv \neg q⟹\neg p,p\wedge (p⟹q)$ impliziert q. Regeln:

• $p\wedge q\equiv p\wedge q$
• $p\vee q=q\vee p$
• $p\wedge (q\vee r)=(p\wedge q)\vee (p\wedge r)$
• $p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)$
• $p\wedge (q\wedge r)\equiv (p\wedge q)\wedge r$
• $p\vee (q\vee r)\equiv (p\vee q)\vee r$
• $\neg \neg p\equiv p$
• $\neg (p\wedge q)\equiv \neg p\vee \neg q$
• $\underbrace{\neg (p\vee q)\equiv \neg p\wedge \neg q}$
• $\underbrace{p⟹q\equiv \neg p\vee q}$

---

$$\begin{array}{ccccccc}p& q& p\vee q& \neg (p\vee q)& \neg o& \neg q& \neg p\wedge \neg q\\ w& w& w& f& f& f& f\\ w& f& w& f& f& w& f\\ f& w& w& f& w& f& f\\ f& f& f& w& w& w& w\end{array}$$ $$\begin{array}{ccccc}p& q& p⟹q& \neg p& \neg p\vee q\\ w& w& w& f& w\\ w& f& f& f& f\\ f& w& w& w& w\\ f& f& w& w& w\end{array}$$

$\neg (p⟹q)\equiv \neg (\neg p\vee q)\equiv \neg \neg p\wedge \neg q\equiv p\wedge \neg q$

---

Eine Aussageform

über den Universen $U_1,\dots ,U_n$ ist ein Satz mit Variablen $x_1,\dots ,x_n$ der bei Einsetzung jedes $x_j$ durch ein Objekt aus $U_j$ zu einer Aussage wird Beispiel:

• “x ist primzahl” ist Aussageform (in der Variable x), über den Universum der positiven ganzen Zahlen.
• "$x<y$" ist Aussageform mit Variablen x,y über den Universen $\mathbb{R},\mathbb{R}$ der reelen Zahlen Nach Ersetzung dǘon x in der Aussageform "$x<y$" durch ein ko kretes Objekt des Universums $\mathbb{R}$, etwa 17, ensteht eine Aussageform in der Variable y, etwa "$17<y$"

Eine Aussageform in nur einer Variablen x, etwa über dem Universum U, heißt Prädikat von U.

Sei $p(x)$ ein solches Prädikat. $\underset{\text{Allquantor}}{\underbrace{\forall }}x:p(x)$ ist die Aussage: “Für alle x aus U ist $p(x)$ wahr” Ihr Wahrheitswert ist $\left\{\begin{array}{c}w\text{ falls }p(x)\text{ den Wert w fu¨r jeden x aus U hat}\\ f\text{ falls }p(x)\text{ fu¨r wenigstens ein x aus U den Wert f hat}\end{array}\right\}$ "$\exists x:p(x)$" ist die Aussage: “Es gibt wenigsten ein $x$ aus U für das $p(x)$ wahr ist” Ihr Wahrheitswert ist $\left\{\begin{array}{c}w\text{ falls }p(x)\text{ fu¨r wenigstens ein x aus U den Wert w hat}\\ f\text{ falls }p(x)\text{ den Wert f fu¨r jeden x aus U hat}\end{array}\right\}$

Für ein leeres Universum U (U hat keine Objekte) gilt $\forall x:p(x)$ ist wahr $\exists x:p(x)$ ist falsch

Spätere Schreibweise, falls U eine Menge ist $\forall x\in U:p(x),\exists x\in U:p(x),\underset{x\in U}{\underbrace{\forall }}p(x),\underset{x\in U}{\underbrace{\exists }}p(x)$

Ist U ein endliches Universum, etwa mit den Objekten $x_1,\dots ,x_n$ (und keine weiteren) gilt: $\forall x:p(x)$ äquivalent zu $p(x_1)\wedge \cdots \wedge (p(x_n))$ $\exists x:p(x)$ äquivalent zu $p(x_1)\vee \cdots \vee p(x_n)$ Daher gibt es folgende Alternativschreibweisen für $\forall ,\exists$ $\bigwedge x:p(x),\bigvee x:p(x),\underset{x\in U}{\bigwedge }p(x),\underset{x\in U}{\bigvee }p(x)$

Schachtelung von Quantoren: Sei $p(x,y)$ eine Aussageform mit zwei Unbekannten x,y über den Universen U, V Betrachte: $\underset{\text{Aussage}}{\underbrace{\forall x:\underset{\text{Aussageform in der Variablen x}}{\underbrace{\exists \underset{\text{fu¨r jede Ersetzung von x durch ein Objekt aus U ensteht eine Aussageform y}}{\underbrace{y:p(x,y)}}}}}}$ Achtung: verschiedene Quantoren ($\forall \exists$ dürfen nicht vertauscht werden) Beispiel: Betrachte "$x<y$" als Aussageform in der Variablen x,y über $\mathbb{R},\mathbb{R}$ $\forall x:\exists y:x<y$ ist wahr: Beweis: Sei $x\in \mathbb{R}$. Setze $y:=x+1$ Dann ist $y\in \mathbb{R}\text{ und }y<x$ q.e.d (Beweis zu ende) $\exists x:\forall y:x<y$ ist falsch: Beweis Annahme es gibt ein $x\in \mathbb{R}$ mit. $\forall y:x<y$ wahr. Dann gilt insbesondere (für den Fall $y=x$): $x<x$, ist ein Widerspruch daher muss die Annahme verworfen werden q.e.d (Beweis zu ende)

Gleichartige Quantoren fürfen vertauscht werden: $\forall x\forall y:p(x,y)\equiv \forall y\forall x:p(x,y)$ $\exists x\exists y:p(x,y)\equiv \exists y\exists x:p(x,y)$

Große Assoziativgesetz: Sind p,q Prädikate über U. so gilt: $\forall x:p(x)\wedge q(x)\equiv \forall x:p(x)\wedge \forall x:q(x)$ $\exists x:p(x)\vee q(x)\equiv \exists x:p(x)\vee \exists x:q(x)$ Großer Satz von de Morgan: $\neg (\forall x:p(x))\equiv \exists x:\neg p(x)$ $\neg (\exists x:p(x))\equiv \forall x:\neg p(x)$ Beispiel: $\neg (\forall x\exists y\forall z\forall v\exists w:p(x,y,z)⟹q(v,w))$ $\equiv \exists x:\neg (\exists y\forall z\forall v\exists w:p(x,y,z)⟹q(v,w))$ $\equiv \exists :\forall y:\neg (\forall z\forall v\exists w:p(x,y,z)⟹q(v,w))$ $\dots$ $\equiv \exists x\forall y\exists z\exists v\forall w:\neg (p(x,y,z)⟹q(v,w))$ $\equiv \exists x\forall y\exists z\exists v\forall w:(p(x,y,z)\wedge \neg (q(v,w)))$

Zitat: nächste Woche wird sie ficken!!!!