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

---

## Normalne oblike

### Naloga 1

Poišči izjavni izraz, ki ima v resničnostni tabeli vrednosti:

1. $11001110$
2. $01110101$

----

| $p$ | $q$ | $r$ | 1. | 2. |
| --- | --- | --- | -- | -- |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 |

1. $$
\begin{aligned}
(p \lor \lnot q \lor r) \land (p \lor \lnot q \lor \lnot r) \land (\lnot p \lor \lnot q \lor \lnot r)
&\sim \lnot q \lor ((p \lor r) \land (p \lor \lnot r) \land (\lnot p \lor \lnot r)) \\
&\sim \lnot q \lor \lnot (\lnot p \lor r) \\
&\sim \lnot q \lor (p \land \lnot r) \\
&\sim q \Rightarrow p \land \lnot r
\end{aligned}
$$

2. $$
\begin{aligned}
(p \lor q \lor r) \land (\lnot p \lor q \lor r) \land (\lnot p \lor \lnot q \lor r)
&\sim ((p \lor q) \land (\lnot p \lor q) \land (\lnot p \lor \lnot q)) \lor r \\
&\sim (\lnot p \land q) \lor r
\end{aligned}
$$

---

## Polni nabori

* Nabor izjavnih veznikov je **poln**, če lahko z njimi izrazimo poljuben izjavni izraz.
* Primeri polnih naborov: $\lbrace \lnot, \land, \lor \rbrace$, $\lbrace \lnot, \land \rbrace$, $\lbrace \lnot, \lor \rbrace$
* Nabor $N$ je poln, če lahko vsak veznik znanega polnega nabora $Z$ izrazimo samo z vezniki nabora $N$.
- Primer: $N = \lbrace \uparrow \rbrace$, $Z = \lbrace \lnot, \lor \rbrace$
- $\lnot p \sim \lnot (p \land p) \sim p \uparrow p$
- $p \lor q \sim \lnot (\lnot p \land \lnot q) \sim \lnot p \uparrow \lnot q \sim (p \uparrow p) \uparrow (q \uparrow q)$
* Nabor $N$ ni poln, če vsaj ena od sledečih lastnosti velja za vse veznike $\Delta \in N$:
1. ohranjanje 0: $\Delta(0, 0, \dots, 0) \sim 0$
- $\land, \lor$ ohranjata 0, $\lnot$ ne ohranja 0
2. ohranjanje 1: $\Delta(1, 1, \dots, 1) \sim 1$
- $\land, \lor$ ohranjata 1, $\lnot$ ne ohranja 1
3. afinost:
- veznik lahko izrazimo z naborom $\lbrace \oplus, 1 \rbrace$
- vsak vhod bodisi vedno vpliva na izhod, bodisi nikoli ne vpliva
- $\lnot p \sim 1 \oplus p$ je afina
- $0 \land 1 \not\sim 1 \land 1$, $0 \land 0 \sim 1 \land 0$, $\land$ ni afin veznik
- $\lor$ ni afin veznik
4. monotonost: <i>$\Delta(p_1, p_2, \dots, 0, \dots, p_n) \le \Delta(p_1, p_2, \dots, 1, \dots, p_n)$</i>
- $\land, \lor$ sta monotona, $\lnot$ ni monotona
5. sebi dualnost: <i>$\lnot \Delta(p_1, p_2, \dots, p_n) \sim \Delta(\lnot p_1, \lnot p_2, \dots, \lnot p_n)$</i>
- $\land, \lor$ nista sebi dualna, $\lnot$ je sebi dualna

---

### Naloga 2

Pokaži, da so naslednji nabori izjavnih povezav polni.

1. <i>$\lbrace \land, \oplus, 1 \rbrace$</i>
2. <i>$\lbrace \Rightarrow, \lnot \rbrace$</i>
3. <i>$\lbrace \Rightarrow, 0 \rbrace$</i>

----

1. * $Z = \lbrace \lnot, \land \rbrace$
* $\lnot p \sim 1 \oplus p$
* $p \land q \sim p \land q$

2. * $Z = \lbrace \lnot, \lor \rbrace$
* $\lnot p \sim \lnot p$
* $p \lor q \sim \lnot p \Rightarrow q$

3. * $Z = \lbrace \lnot, \lor \rbrace$
* $\lnot p \sim p \Rightarrow 0$
* $p \lor q \sim (p \Rightarrow 0) \Rightarrow q$

---

### Naloga 3

Pokaži, da je nabor <i>$\lbrace \land, 0, 1, \Delta \rbrace$</i> poln, pri čemer je <i>$\Delta(p,q,r) \equiv p \oplus q \oplus r$</i>.

----

* $Z = \lbrace \lnot, \land \rbrace$
* $\lnot p \sim 1 \oplus p \oplus 0 \sim \Delta(1, p, 0)$
* $p \land q \sim p \land q$

---

### Naloga 4

Pokaži, da naslednji nabori izjavnih veznikov niso polni.

1. <i>$\lbrace \land, \Leftrightarrow \rbrace$</i>
2. <i>$\lbrace \land, \oplus \rbrace$</i>
3. <i>$\lbrace \lnot, \oplus \rbrace$</i>

----

1. * ohranjanje 0 **NE VELJA**
- $0 \land 0 \sim 0$
- $0 \iff 0 \not\sim 0$
* ohranjanje 1 **VELJA**, nabor **ni poln**
- $1 \land 1 \sim 1$
- $1 \iff 1 \sim 1$
* afinost **NE VELJA**
- $0 \sim 0 \land 1 \not\sim 1 \land 1 \sim 1$, $0 \sim 0 \land 0 \sim 1 \land 0 \sim 0$ ni afina
- $p \iff q \sim p \oplus q \oplus 1$ je afina
* monotonost **NE VELJA**
- $\land$ je monotona
- $0 \iff 0 \sim 1 > 0 \sim 0 \iff 1$
* sebi dualnost **NE VELJA**
- $\land$ ni sebi dualna
- $\lnot (p \iff q) \not\sim (\lnot p \iff \lnot q)$ ni sebi dualna

2. * ohranjanje 0 **VELJA**, nabor **ni poln**
- $0 \land 0 \sim 0$
- $0 \oplus 0 \sim 0$

3. * afinost **VELJA**, nabor **ni poln**
- $\lnot p \sim 1 \oplus p$
- $p \oplus q \sim p \oplus q$

---

### Naloga 5

Ali izjavni veznik <i>$\Lambda(p,q,r) \equiv p \Rightarrow (q \lor r)$</i> sestavlja poln nabor?

----

* $\Lambda(0, 0, 0) \sim 0 \Rightarrow (0 \lor 0) \sim 1$
* $\Lambda(1, 1, 1) \sim 1 \Rightarrow (1 \lor 1) \sim 1$, nabor $\lbrace \Lambda \rbrace$ ni poln