---
tags: vaje, ds, predikatni
hackmd: https://hackmd.io/q2_NwHSlQQqnDLaOoaz5cA
plugins: mathjax
---
# Diskretne strukture (FiM) - vaje 20.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, \Rightarrow, \lnot, \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 atlet
* $Q(x)$ ... $x$ je močen
* $\forall x: (P(x) \Rightarrow Q(x))$
2. * $\exists x: (P(x) \land Q(x))$
3. * $R(x)$ ... $x$ je nogometaš
* $S(x)$ ... $x$ je hiter
* $\forall x: (P(x) \lor R(x) \Rightarrow Q(x) \land S(x))$
4. DN
5. DN
6. DN
7. * $\mathcal{D} =$ ljudje
* $P(x, y)$ ... $x$ in $y$ sta prijatelja
* $a, b$ ... Andreja, Bojan
* $\forall x: (P(a, x) \Rightarrow P(b, 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 število je praštevilo ali sodo.
* **Ni res**, protiprimer: $x = 9$
* $\lnot \forall x: (P(x) \lor D(2, x)) \sim \exists x: (\lnot P(x) \land \lnot D(2, x))$
2. DN
3. * Obstaja praštevilo, ki je deljivo s 5.
* **Res**, primer $x = 5$.
4. DN
5. * Vsako število, ki je deljivo s 4, je sodo.
* **Res**, vzamemo poljuben $x$, predpostavimo $D(4, x)$, potem obstaja $k$, da je $x = 4k = 2 \cdot (2k)$, zato $D(2, x)$.
6. * Vsako število ima večkratnik.
* **Res**, za poljuben $x$ najdemo primer $y = x$.
7. * Neko število je večkratnik vseh števil.
* Če $0 \in \mathbb{N}$, potem **je res**, primer $y = 0$.
* Sicer **ni res**, za poljuben $y$ imamo protiprimer $x = y+1$.

---

### 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 (\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.

----

Izjavi sta **enakovredni**, če imata enako resničnostno vrednost pri vsaki domeni in interpretaciji predikatov (konstant, funkcijskih simbolov).

$$
\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. DN
2. * $\mathcal{D} = \lbrace a, b \rbrace$
* $P(a) \sim 0$, $P(b) \sim 1$, $Q(a) \sim 0$, $Q(b) \sim 0$
* $\exists x:(P(x) \Leftrightarrow Q(x)) \sim 1$ (primer: $x = a$)
* $\exists x: P(x) \Leftrightarrow \exists x: Q(x) \sim 1 \iff 0 \sim 0$
* izjavi **nista enakovredni**

---

### 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?