Predicate Logic

Bausteine

• Universum $U$ : $U=\mathbb{R},U=\{0,1\}\dots$
• Konstanten aus $U$ : $0,1,\pi \dots$
• Prädikate $P$,$Q$ : $prime(x),less(x)\dots$
• Funktionen: $f,g$ : $square(x),add(x)\dots$
• Operatoren: $\neg ,\wedge ,\vee ,\to ,\leftrightarrow$ similar to Propositional Logic
• Quantoren: $\forall x$, $\exists x$

Syntax

Semantics

basic Equivalences

Example

Spezielle Interpretation $U=\mathbb{N}$

• $\forall x(0\le x)$ wahr
• $(\exists x(x\le 2))\wedge (\exists x(3\le x))$ wahr $prime(x)\stackrel{def}{⟺}(x>1)\wedge (\forall y(y|x)\to (y=1\vee y=x))$ $y|x\stackrel{def}{⟺}(y>0)\wedge (\exists k(y\cdot k=x))$

Allgemein

• $\exists x(F\wedge G)\models (\exists xF)\wedge (\exists xG)$
• $\forall x(F\wedge G)\equiv (\forall xF)\wedge (\forall xG)$
• $\neg \forall xF\equiv \exists x\neg F$
• $\neg \exists xF\equiv \forall x\neg F$
• $\forall x\forall y\forall z((P(x,y)\wedge P(y,z))\to P(x,z))$ Transitivität
• $\forall x\forall y(P(x,y)\to P(y,x))$ Symmetrie
• $\forall x(P(x)\to Q(x))\models (\forall xP(x))\to (\forall xQ(x))$ Was können wir über $\forall x(P(x)\to \neg P(x))$ sagen?

Beispiel: Verwandtschaftsbeziehung

$U=$Menschen (idealisiert) $par(x,y)$ $child(x,y)\stackrel{def}{⟺}par(y,x)$ $sibl(x,y)\stackrel{def}{⟺}\exists k(par(k,x)\wedge par(k,y)\wedge x\ne y)$ $grandpar(x,y)\stackrel{def}{⟺}\exists k(child(k,x)\wedge par(k,y))$ $ancestor(x,y)$ definition nicht möglich

Beispiel: exists only 1

$${\exists }_{1}xF\stackrel{def}{⟺}\exists \tilde{x}\forall x(x=\tilde{x}\leftrightarrow F)$$

Prenex normal form (PNF)

For every formula there is an equivalent formula in prenex form