---
tags: vaje, ds, izjavni
hackmd: https://hackmd.io/L59-6yBaQMGgjVKbdicrVQ
plugins: mathjax
---
# Diskretne strukture (FiM) - vaje 28.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 (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 \lor \lnot q) \lor r \\
&\sim (\lnot p \land q) \lor r
\end{aligned}
$$

---

## Polni nabori

* Nabor izjavnih veznikov je **poln**, če lahko z njim izrazimo poljuben izjavni izraz.
* Primeri polnih naborov: $\lbrace \land, \lor, \lnot \rbrace$, $\lbrace \land, \lnot \rbrace$, $\lbrace \lor, \lnot \rbrace$
* Nabor $N$ je poln, če lahko vsak veznik znanega polnega nabora $Z$ izrazimo samo z vezniki nabora $N$.
- Primer: $N = \lbrace \uparrow \rbrace$
- Vzamemo npr. $Z = \lbrace \lor, \lnot \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 naslednjih lastnosti velja za vse veznike $\Delta \in N$:
1. ohranjanje 0: $\Delta(0, 0, \dots, 0) \sim 0$
2. ohranjanje 1: $\Delta(1, 1, \dots, 1) \sim 1$
3. afinost:
- $\Delta$ lahko izrazimo z naborom $\lbrace \oplus, 1 \rbrace$
- vsak vhod bodisi vedno vpliva na rezultat ali pa nikoli ne vpliva
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>
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>

### 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 p \oplus 1$
* $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 p \oplus 1 \oplus 0 \sim \Delta(p, 1, 0)$
* $p \land q \sim q \land p$

---

### 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**
- $1 \land 0 \sim 0 \not\sim 1 \land 1 \sim 1$, $0 \land 0 \sim 0 \sim 0 \land 1 \sim 0$, veznik ni afin
- $p \iff q \sim p \oplus q \oplus 1$, veznik je afin
* monotonost **NE VELJA**
- $p \land q \sim 1$, samo če $p \sim q \sim 1$, veznik je monoton
- $0 \iff 0 \sim 1 > 0 \iff 1 \sim 0$, veznik ni monoton
* sebi dualnost **NE VELJA**
- $\lnot (p \land q) \not\sim (\lnot p \land \lnot q)$, veznik ni sebi dualen
- $\lnot (p \iff q) \not\sim (\lnot p \iff \lnot q)$, veznik ni sebi dualen

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

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