---
tags: vaje, ds, izjavni
hackmd: https://hackmd.io/hgA4ilAsTzqBItgGjpXrpw
plugins: mathjax
---
# Diskretne strukture (FiM) - vaje 9.10.2020

---

## Izjavni račun

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

$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)$
2. * $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.

----

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 (res)

$p \lor q \sim 1$

3. * $p$ ... po filmu grem na burek
* $q$ ... prepozno bom doma

$p \Rightarrow q$

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