---
tags: vaje, ds, predikatni
hackmd: https://hackmd.io/X1TB2MzFSNy4m-RCcQ-Vuw
plugins: mathjax
---
# Diskretne strukture (FiM) - vaje 19.11.2020

---

## Predikatni račun

* $\mathcal{D}$ ... domena (območje pogovora)
* $x, y, \ldots \in \mathcal{D}$ ... spremenljivke
* $a, b, \ldots \in \mathcal{D}$ ... konstante
* $f, g, \ldots : \mathcal{D}^k \to \mathcal{D}$ ... funkcijski simboli
* $P, Q, \ldots : \mathcal{D}^k \to \{0, 1\}$ ... predikati
* $\land, \lor, \lnot, \Rightarrow, \ldots$ ... vezniki
* $\forall x: \phi(x)$, $\exists x : \phi(x)$ ... kvantifikatorja

---

### Naloga 1

Prevedi naslednje stavke v predikatni račun.

1. Vsi atleti so močni.
2. Nekateri atleti so močni.
3. Atleti in nogometaši so močni in hitri.
4. Vse zelene žabe skačejo.
5. Nekatere gobe so užitne, če jih skuhaš.
6. Nekateri uspešni poslovneži niso zabavni.
7. Vsi Andrejini prijatelji so tudi Bojanovi prijatelji.
8. Andreja pozna vse Bojanove prijatelje.
9. Vsak, ki pozna kakega Andrejinega prijatelja, pozna tudi nekega Bojanovega prijatelja.

----

1. * $\mathcal{D} =$ ljudje
* $P(x)$ ... $x$ je močen
* $Q(x)$ ... $x$ je atlet
* $\forall x: (Q(x) \Rightarrow P(x))$
2. * $\exists x: (Q(x) \land P(x))$
3. * $R(x)$ ... $x$ je nogometaš
* $S(x)$ ... $x$ je hiter
* $\forall x: (Q(x) \lor R(x) \Rightarrow P(x) \land S(x))$
4. DN
5. * $\mathcal{D} =$ gobe
* $P(x)$ ... užitna
* $f(x)$ ... goba $x$ po kuhanju
* $\exists x: P(f(x))$

---

### Naloga 2

Naj bodo področje pogovora naravna števila. Enomestni predikat <i>$P$</i> in dvomestni predikat <i>$D$</i> interpretiramo kot:

* <i>$P(x)$</i> ... <i>$x$</i> je praštevilo,
* <i>$D(x,y)$</i> ... število <i>$x$</i> deli število <i>$y$</i>.

Določi logične vrednosti formul in zapiši njihove negacije.

1. <i>$\forall x: (P(x) \lor D(2, x))$</i>
2. <i>$\exists x: (P(x) \land D(2, x))$</i>
3. <i>$\exists x: (P(x) \land D(5, x))$</i>
4. <i>$\forall x: (P(x) \Rightarrow \lnot D(10, x))$</i>
5. <i>$\forall x: (D(4, x) \Rightarrow D(2, x))$</i>
6. <i>$\forall x \exists y: D(x, y)$</i>
7. <i>$\exists y \forall x: D(x, y)$</i>
8. <i>$\forall x \exists y: (P(y) \land D(y,x))$</i>
9. <i>$\exists x \forall y: (D(x,y) \Rightarrow \lnot P(y))$</i>
10. <i>$\forall x \exists y: (P(x) \Rightarrow P(y) \land D(y,x))$</i>

----

1. * Vsako naravno število je praštevilo ali sodo.
* **Ni res**, protiprimer: $x = 15$
* $\lnot \forall x: (P(x) \lor D(2, x)) \sim \exists x: (\lnot P(x) \land \lnot D(2, x))$
2. * Obstaja sodo praštevilo.
* **Res**, primer: $x = 2$
3. DN
4. * Praštevila niso deljiva z 10.
* **Res**, velja vedno.
5. DN
6. * Vsako število ima svoj večkratnik.
* **Res**, za vsak $x$ imamo primer $y = x$.
7. * Neko naravno število je večkratnik vsakega naravnega števila.
* Če $0 \in \mathbb{N}$, potem **je res**, imamo primer $y = 0$.
* Sicer **ni res**, za poljuben $y$ imamo protiprimer $x = y+1$.
* $\lnot \exists y \forall x: D(x, y) \sim \forall y \exists x: \lnot D(x, y)$

---

### Naloga 3

Za spodnje formule poišči enakovredne formule, v katerih negacija nastopa le neposredno pred predikati.

1. <i>$\lnot \forall x: (A(x) \lor B(x))$</i>
2. <i>$\lnot \exists x: (A(x) \land \lnot B(x))$</i>
3. <i>$\lnot((\lnot \exists x: P(x) \lor \forall x: Q(x)) \land (R(x) \Rightarrow \forall x:S(x)))$</i>

----

1. $$
\begin{aligned}
\lnot \forall x: (A(x) \lor B(x))
&\sim \exists x: (\lnot A(x) \land \lnot B(x))
\end{aligned}
$$
2. $$
\begin{aligned}
\lnot \exists x: (A(x) \land \lnot B(x))
&\sim \forall x: (\lnot A(x) \lor B(x)) \\
&\sim \forall x: (A(x) \Rightarrow B(x))
\end{aligned}
$$
3. $$
\begin{aligned}
&\quad \lnot((\lnot \exists x: P(x) \lor \forall x: Q(x)) \land (R(x) \Rightarrow \forall x:S(x))) \\
&\sim \lnot((\lnot \exists y: P(y) \lor \forall z: Q(z)) \land (R(x) \Rightarrow \forall w: S(w))) \\
&\sim (\exists y: P(y) \land \exists z: \lnot Q(z)) \lor \lnot (\lnot R(x) \lor \forall w: S(w)) \\
&\sim (\exists y: P(y) \land \exists z: \lnot Q(z)) \lor (R(x) \land \exists w: \lnot S(w)) \\
&\sim (\exists y \exists z: (P(y) \land \lnot Q(z))) \lor \exists w: (R(x) \land \lnot S(w)) \\
&\sim \exists y : (\exists z: (P(y) \land \lnot Q(z)) \lor (R(x) \land \lnot S(y))) \\
&\sim \exists y \exists z: ((P(y) \land \lnot Q(z)) \lor (R(x) \land \lnot S(y)))
\end{aligned}
$$

---

### Naloga 4

Pokaži, da sta formuli <i>$\exists x:(P(x) \Rightarrow Q(x))$</i> in <i>$\forall x: P(x) \Rightarrow \exists x: Q(x)$</i> enakovredni.

----

Formuli sta **enakovredni**, če imata enako resničnostno vrednost za vsako domeno in vsako interpretacijo predikatov.

$$
\begin{aligned}
\forall x: P(x) \Rightarrow \exists x: Q(x)
&\sim \exists x: \lnot P(x) \lor \exists x: Q(x) \\
&\sim \exists x: (\lnot P(x) \lor Q(x)) \\
&\sim \exists x: (P(x) \Rightarrow Q(x))
\end{aligned}
$$

---

### Naloga 5

Pokaži, da formuli nista enakovredni.

1. <i>$\lnot \exists x:(P(x) \Leftrightarrow Q(x))$</i> in <i>$\lnot \exists x: P(x) \Leftrightarrow \lnot \exists x: Q(x)$</i>
2. <i>$\exists x:(P(x) \Leftrightarrow Q(x))$</i> in <i>$\exists x: P(x) \Leftrightarrow \exists x: Q(x)$</i>

----

1. * $\mathcal{D} = \mathbb{N}$
* $P(x)$ ... $x$ je praštevilo
* $Q(x)$ ... $x$ ima natanko tri delitelje
* $\lnot \exists x:(P(x) \Leftrightarrow Q(x)) \sim 0$
* $\lnot \exists x: P(x) \Leftrightarrow \lnot \exists x: Q(x) \sim 0 \iff 0 \sim 1$

ali
- $\mathcal{D} = \lbrace a \rbrace$
- $P(a) \sim 1$, $Q(a) \sim 1$
- $\lnot \exists x:(P(x) \Leftrightarrow Q(x)) \sim 0$
- $\lnot \exists x: P(x) \Leftrightarrow \lnot \exists x: Q(x) \sim 0 \iff 0 \sim 1$

---

### Naloga 6

Pokaži, da je formula

$$
\forall x \exists y: P(x,y) \Rightarrow (\exists x \forall y: \lnot P(x,y) \Rightarrow \exists x \forall y: P(x,y))
$$

logično veljavna.

---

### Naloga 7

Ali je formula

$$
\exists x \forall y : (P(x,y) \Leftrightarrow P(y,y))
$$

logično veljavna?