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

  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 š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
    • Obstaja praštevilo, ki je deljivo s 5.
    • Res, primer \(x = 5\).
  4. 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.

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

  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)\)
  1. 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?

Select a repo