changed 4 years ago  
Linked with GitHub jaanos/diskretne-strukture-fim/zapiski/2020-21/2020-11-19.md

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.
    • \(\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))\)
  4. 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.

  1. \(\forall x: (P(x) \lor D(2, x))\)
  2. \(\exists x: (P(x) \land D(2, x))\)
  3. \(\exists x: (P(x) \land D(5, x))\)
  4. \(\forall x: (P(x) \Rightarrow \lnot D(10, x))\)
  5. \(\forall x: (D(4, x) \Rightarrow D(2, x))\)
  6. \(\forall x \exists y: D(x, y)\)
  7. \(\exists y \forall x: D(x, y)\)
  8. \(\forall x \exists y: (P(y) \land D(y,x))\)
  9. \(\exists x \forall y: (D(x,y) \Rightarrow \lnot P(y))\)
  10. \(\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\)
  3. DN
    • Praštevila niso deljiva z 10.
    • Res, velja vedno.
  5. 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.

  1. \(\lnot \forall x: (A(x) \lor B(x))\)
  2. \(\lnot \exists x: (A(x) \land \lnot B(x))\)
  3. \(\lnot((\lnot \exists x: P(x) \lor \forall x: Q(x)) \land (R(x) \Rightarrow \forall x:S(x)))\)
  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 \(\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.

  1. \(\lnot \exists x:(P(x) \Leftrightarrow Q(x))\) in \(\lnot \exists x: P(x) \Leftrightarrow \lnot \exists x: Q(x)\)
  2. \(\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?

Select a repo