Diskretne strukture (FiM)

« nazaj

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)$

2. • $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.

---

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

   $\lnot p \Rightarrow \lnot q$

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

   $p \lor q \sim 1$

3. • $p$ … grem po filmu na burek
   • $q$ … pravočasno bom doma

   $p \Rightarrow \lnot q$

4. • $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.

Ta stran je odprtokodna. Izboljšaj to stran.

Ta zapisek je dostopen tudi na HackMD.