« nazaj
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.
- 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 močen
- $Q(x)$ … $x$ je atlet
- $\forall x: (Q(x) \Rightarrow P(x))$
-
- $\exists x: (Q(x) \land P(x))$
-
- $R(x)$ … $x$ je nogometaš
- $S(x)$ … $x$ je hiter
- $\forall x: (Q(x) \lor R(x) \Rightarrow P(x) \land S(x))$
- DN
-
- $\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 $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 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))$
-
- Obstaja sodo praštevilo.
- Res, primer: $x = 2$
- DN
-
- Praštevila niso deljiva z 10.
- Res, velja vedno.
- DN
-
- Vsako število ima svoj večkratnik.
- Res, za vsak $x$ imamo primer $y = x$.
-
- 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.
- $\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 (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 $\exists x:(P(x) \Rightarrow Q(x))$ in $\forall x: P(x) \Rightarrow \exists x: Q(x)$ 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.
- $\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)$
-
- $\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?