changed 4 years ago  
Linked with GitHub

Diskretne strukture (FiM) - vaje 8.10.2020

Izjavni račun

  • \(p, q, \dots\): izjavne spremenljivke
  • \(1 = \top\), \(0 = \bot\): konstanti
  • vezniki:
    • \(\lnot\): "ne" - negacija
    • \(\land\): "in" - konjunkcija
    • \(\lor\): "ali" - disjunkcija
    • \(\Rightarrow\): implikacija
    • \(\Leftrightarrow\): ekvivalenca
    • \(\oplus\): "ekskluzivni ali" (XOR)
    • \(\uparrow\): Shefferjev veznik (NAND)
    • \(\downarrow\): Łukasiewiczev veznik (NOR)
  • oklepaji

\(\phi \sim \psi\): izraza \(\phi\) in \(\psi\) sta enakovredna

\(p\) \(q\) \(p \Rightarrow q\)
0 0 1
0 1 1
1 0 0
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 ekvivalentno (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 (je res)

    \(p \lor q \sim 1\)

    • \(p\) … grem po filmu na burek
    • \(q\) … pravočasno bom doma

    \(p \Rightarrow \lnot q\)

    • \(p\) … me pokličeš
    • \(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\) in ne \(q\)) ali (ne \(p\) in \(q\))

    \(p\) \(q\) \(p \wedge \lnot q\) \(\lor\) \(\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)\) \(\land\) \((\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 \lor q\) \(\Rightarrow p)\) \(\lor\) \(\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

    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.

Select a repo