« nazaj
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.
- Vsi atleti so močni.
- Nekateri atleti so močni.
- Atleti in nogometaši so močni in hitri.
- Vse zelene žabe skačejo.
- Nekatere gobe so užitne, če jih skuhaš.
- Nekateri uspešni poslovneži niso zabavni.
- Vsi Andrejini prijatelji so tudi Bojanovi prijatelji.
- Andreja pozna vse Bojanove prijatelje.
- Vsak, ki pozna kakega Andrejinega prijatelja, pozna tudi nekega Bojanovega prijatelja.
-
- $\mathcal{D} =$ ljudje
- $P(x)$ … $x$ je atlet
- $Q(x)$ … $x$ je močen
- $\forall x: (P(x) \Rightarrow Q(x))$
-
- $\exists x: (P(x) \land Q(x))$
-
- $R(x)$ … $x$ je nogometaš
- $S(x)$ … $x$ je hiter
- $\forall x: (P(x) \lor R(x) \Rightarrow Q(x) \land S(x))$
- DN
- DN
- DN
-
- $\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 $P$ in dvomestni predikat $D$ interpretiramo kot:
- $P(x)$ … $x$ je praštevilo,
- $D(x,y)$ … število $x$ deli število $y$.
Določi logične vrednosti formul in zapiši njihove negacije.
- $\forall x: (P(x) \lor D(2, x))$
- $\exists x: (P(x) \land D(2, x))$
- $\exists x: (P(x) \land D(5, x))$
- $\forall x: (P(x) \Rightarrow \lnot D(10, x))$
- $\forall x: (D(4, x) \Rightarrow D(2, x))$
- $\forall x \exists y: D(x, y)$
- $\exists y \forall x: D(x, y)$
- $\forall x \exists y: (P(y) \land D(y,x))$
- $\exists x \forall y: (D(x,y) \Rightarrow \lnot P(y))$
- $\forall x \exists y: (P(x) \Rightarrow P(y) \land D(y,x))$
-
- 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))$
- DN
-
- Obstaja praštevilo, ki je deljivo s 5.
- Res, primer $x = 5$.
- DN
-
- 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)$.
-
- Vsako število ima večkratnik.
- Res, za poljuben $x$ najdemo primer $y = x$.
-
- 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.
- $\lnot \forall x: (A(x) \lor B(x))$
- $\lnot \exists x: (A(x) \land \lnot B(x))$
- $\lnot((\lnot \exists x: P(x) \lor \forall x: Q(x)) \land (R(x) \Rightarrow \forall x:S(x)))$
-
\[\begin{aligned}
\lnot \forall x: (A(x) \lor B(x))
&\sim \exists x: (\lnot A(x) \land \lnot B(x))
\end{aligned}\]
-
\[\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}\]
-
\[\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 $\exists x:(P(x) \Rightarrow Q(x))$ in $\forall x: P(x) \Rightarrow \exists x: Q(x)$ 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.
- $\lnot \exists x:(P(x) \Leftrightarrow Q(x))$ in $\lnot \exists x: P(x) \Leftrightarrow \lnot \exists x: Q(x)$
- $\exists x:(P(x) \Leftrightarrow Q(x))$ in $\exists x: P(x) \Leftrightarrow \exists x: Q(x)$
- DN
-
- $\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?