Diskretne strukture (FiM)

« nazaj

Diskretne strukture (FiM) - vaje 9.10.2020


Izjavni račun

$p$ $q$ $p \land q$ $p \lor q$ $p \Rightarrow q$
0 0 0 0 1
0 1 0 1 1
1 0 0 1 0
1 1 1 1 1

Naloga 1

Zapiši z izjavnim izrazom.

  1. Iz $p$ sledi $q$, ali pa iz $q$ sledi $p$.
  2. Če velja $p$ in če velja $q$, potem velja $r$.

  1. $(p \Rightarrow q) \lor (q \Rightarrow p)$
    • $p \land q \Rightarrow r$
    • $p \Rightarrow (q \Rightarrow r)$
    • $(p \Rightarrow q) \Rightarrow r$ ni enakovredna, protiprimer: $p, q, r \sim 0$

Naloga 2

Naslednje izjave razbij na enostavne in jih zapiši v obliki izjavnih izrazov.

  1. Če ceste niso mokre, potem zunaj ne dežuje.
  2. Število 6 je praštevilo ali pa je število 5 praštevilo.
  3. Če grem po filmu na burek, bom prepozno doma.
  4. Če me pokličeš in me ni doma, potem sem na Rožniku.

    • $p$ … ceste so mokre
    • $q$ … zunaj dežuje

    $\lnot p \Rightarrow \lnot q$

    • $p$ … 6 je praštevilo (ni res)
    • $q$ … 5 je praštevilo (res)

    $p \lor q \sim 1$

    • $p$ … po filmu grem na burek
    • $q$ … prepozno bom doma

    $p \Rightarrow q$

    • $p$ … pokličeš me
    • $q$ … sem doma
    • $r$ … sem na Rožniku

    $p \land \lnot q \Rightarrow r$


Naloga 3

Preberi izjavni izraz in zapiši njegovo resničnostno tabelo.

  1. $p \wedge \lnot q \vee \lnot p \wedge q$,
  2. $(p \Rightarrow q) \wedge (\lnot p \Rightarrow r)$.

  1. $p$ $q$ $(p \wedge \lnot q)$ $\vee$ $(\lnot p \wedge q)$
    0 0 0 0 0
    0 1 0 1 1
    1 0 1 1 0
    1 1 0 0 0

    Natanko eden od $p$ in $q$ je resničen ($p \oplus q$).

  2. $p$ $q$ $r$ $(p \Rightarrow q)$ $\wedge$ $(\lnot p \Rightarrow r)$
    0 0 0 1 0 0
    0 0 1 1 1 1
    0 1 0 1 0 0
    0 1 1 1 1 1
    1 0 0 0 0 1
    1 0 1 0 0 1
    1 1 0 1 1 1
    1 1 1 1 1 1

    Če $p$, potem $q$, sicer $r$ (IF $p$ THEN $q$ ELSE $r$).


Naloga 4

Izračunaj resničnostne tabele izrazov

  1. $(p \vee q \Rightarrow p) \vee \lnot p$,
  2. $p \Rightarrow (q \Rightarrow p) \Rightarrow q$,
  3. $\lnot{}p\lor{}q\lor{}r\Rightarrow{}(r\Rightarrow{}q\land{}p)$.

  1. $p$ $q$ $(p \vee q$ $\Rightarrow p)$ $\vee$ $\lnot p$
    0 0 0 1 1 1
    0 1 1 0 1 1
    1 0 1 1 1 0
    1 1 1 1 1 0

    Izjavni izraz je tavtologija.

  2. $p$ $q$ $(p \Rightarrow$ $(q \Rightarrow p))$ $\Rightarrow q$
    0 0 1 1 0
    0 1 1 0 1
    1 0 1 1 0
    1 1 1 1 1
  3. $p$ $q$ $r$ $\lnot{}p\lor{}q\lor{}r$ $\Rightarrow{}$ $(r\Rightarrow{}$ $q\land{}p)$
    0 0 0 1 1 1 0
    0 0 1 1 0 0 0
    0 1 0 1 1 1 0
    0 1 1 1 0 0 0
    1 0 0 0 1 1 0
    1 0 1 1 0 0 0
    1 1 0 1 1 1 1
    1 1 1 1 1 1 1

Naloga 5

Ali so naslednji izjavni izrazi tavtologije, protislovja, ali so kontingentni?

  1. $p\Rightarrow(q\Rightarrow p)$
  2. $((p\vee q)\wedge(p\Rightarrow r)\wedge(q\Rightarrow r))\Rightarrow r$
  3. $(p\Rightarrow q)\iff (p\wedge\lnot q)$
  4. $\lnot(p\wedge q)\iff \lnot p\wedge\lnot q$

  1. $p$ $q$ $p\Rightarrow$ $(q\Rightarrow p)$
    0 0 1 1
    0 1 1 0
    1 0 1 1
    1 1 1 1

    Izraz je tavtologija.

  2. $p$ $q$ $r$ $((p\vee q)$ $\wedge(p\Rightarrow r)$ $\wedge$ $(q\Rightarrow r))$ $\Rightarrow r$
    0 0 0 0 1 0 1 1
    0 0 1 0 1 0 1 1
    0 1 0 1 1 0 0 1
    0 1 1 1 1 1 1 1
    1 0 0 1 0 0 1 1
    1 0 1 1 1 1 1 1
    1 1 0 1 0 0 0 1
    1 1 1 1 1 1 1 1

    Izraz je tavtologija.

  3. $p$ $q$ $(p\Rightarrow q)$ $\iff$ $(p\wedge\lnot q)$
    0 0 1 0 0
    0 1 1 0 0
    1 0 0 0 1
    1 1 1 0 0

    Izraz je protislovje.

  4. $p$ $q$ $\lnot(p\wedge q)$ $\iff$ $\lnot p\wedge\lnot q$
    0 0 1 1 1
    0 1 1 0 0
    1 0 1 0 0
    1 1 0 1 0

    Izraz je kontingenten.