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

---

## Polni nabori

### Naloga 1

Kateri izmed naslednjih izjavnih veznikov sestavlja poln nabor?

1. <i>$\Lambda(p,q,r) \equiv p \Rightarrow (q \lor r)$</i>
2. <i>$\Lambda(p,q,r) \equiv (p \uparrow q) \downarrow r$</i>
3. <i>$\Lambda(p,q,r) \equiv (\lnot p \land \lnot r) \Rightarrow q$</i>
4. <i>$\Lambda(p,q,r) \equiv p \Rightarrow (q \Rightarrow \lnot r) \sim \lnot p \lor \lnot q \lor \lnot r$</i>

----

1. * ohranjanje 1: $\Lambda(1, 1, 1) \sim 1 \Rightarrow (1 \lor 1) \sim 1$ velja
* nabor $\lbrace \Lambda \rbrace$ **ni poln**

2. * ohranjanje 0: $\Lambda(0, 0, 0) \sim (0 \uparrow 0) \downarrow 0 \sim 1 \downarrow 0 \sim 0$ velja
* nabor $\lbrace \Lambda \rbrace$ **ni poln**

3. * ohranjanje 0: $\Lambda(0, 0, 0) \sim (\lnot 0 \land \lnot 0) \Rightarrow 0 \sim 0$ velja
* nabor $\lbrace \Lambda \rbrace$ **ni poln**

4. * ohranjanje 0: $\Lambda(0, 0, 0) \sim 0 \Rightarrow (0 \Rightarrow \lnot 0) \sim 1$
* ohranjanje 1: $\Lambda(1, 1, 1) \sim 1 \Rightarrow (1 \Rightarrow \lnot 1) \sim 0$
* afinost: $\Lambda(0, 0, 1) \sim 0 \Rightarrow (0 \Rightarrow \lnot 1) \sim 1$, $\Lambda(1, 1, 0) \sim 1 \Rightarrow (1 \Rightarrow \lnot 0) \sim 1$
* monotonost: ne velja zaradi neohranjanja 0, 1
* sebi dualnost: protiprimer podan pri afinosti
- $\lnot \Lambda(\lnot p, \lnot q, \lnot r) \sim \lnot (p \lor q \lor r) \sim \lnot p \land \lnot q \land \lnot r$
* $\Lambda(p, p, p) \sim \lnot p \lor \lnot p \lor \lnot p \sim \lnot p$
* $p \lor q \sim \Lambda(\lnot p, \lnot q, \lnot q) \sim \Lambda(\Lambda(p, p, p), \Lambda(q, q, q), \Lambda(q, q, q))$
* nabor $\lbrace \Lambda \rbrace$ **je poln**

---

## Sklepanje

<i>$p_1, p_2, \dots p_n \models q$</i> velja natanko tedaj, ko velja <i>$p_1 \land p_2 \land \dots \land p_n \Rightarrow q$</i>

1. modus ponens (MP): $p, p \Rightarrow q \models q$
2. modul tollens (MT): $p \Rightarrow q, \lnot q \models \lnot p$
3. disjunktivni silogizem (DS): $p \lor q, \lnot p \models q$
4. hipotetični silogizem (HS): $p \Rightarrow q, q \Rightarrow r \models p \Rightarrow r$
5. poenostavitev (Po): $p \land q \models p$
6. pridružitev (Pr): $p \models p \lor q$
7. združitev (Zd): $p, q \models p \land q$
8. pogojni sklep (PS): $[p \models q] \models p \Rightarrow q$
9. dokaz s protislovjem (*reductio ad absurdum*, RA): $[\lnot p \models 0] \models p$
10. analiza primerov (AP): $p \lor q, [p \models r], [q \models r] \models r$

---

### Naloga 2

Preveri veljavnost naslednjih sklepov.

1. Študent se je s trolejbusom peljal na izpit. Rekel si je: "Če bo semafor pri Drami zelen, bom naredil izpit." No, ko je avtobus pripeljal na križišče, je semafor svetil rdečo, študent pa si je dejal: "Presneto, spet bom padel."

2. Če nočem jutri zamuditi pouka, moram zgodaj vstati; če pa grem nocoj na žur, se bom vrnil pozno. Če se bom pozno vrnil in zgodaj vstal, bom spal le <i>$5$</i> ur. Ne morem si privoščiti samo <i>$5$</i> ur spanja. Potemtakem bom moral zamuditi pouk ali pa se odpovedati žuru.

----

1. * $p$ ... semafor sveti zeleno
* $q$ ... naredil bom izpit
* $p \Rightarrow q, \lnot p \models \lnot q$
* protiprimer: $p \sim 0, q \sim 1$
* sklep **ni veljaven**

2. * $p$ ... zamudim pouk
* $q$ ... zgodaj vstanem
* $r$ ... grem na žur
* $s$ ... vrnil se bom pozno
* $t$ ... spal bom le $5$ ur
* $\lnot p \Rightarrow q, r \Rightarrow s, s \land q \Rightarrow t, \lnot t \models p \lor \lnot r$

----

1. $\lnot p \Rightarrow q$ (predp.)
2. $r \Rightarrow s$ (predp.)
3. $s \land q \Rightarrow t$ (predp.)
4. $\lnot t$ (predp.)
5. $\lnot (s \land q) \sim \lnot s \lor \lnot q \sim s \Rightarrow \lnot q$ (MT(3, 4))
6. $r \Rightarrow \lnot q$ (HS(2, 5))
7. 1. $\lnot s$ (predp. AP(5))
2. $\lnot r$ (MT(2, 7.1))
3. $p \lor \lnot r$ (Pr(7.2))
8. 1. $\lnot q$ (predp. AP(5))
2. $p$ (MT(1, 8.1))
3. $p \lor \lnot r$ (Pr(8.2))
9. $p \lor \lnot r$ (AP(5, 7.1-7.3, 8.1-8.3))

---

### Naloga 3

Na oglasno desko Ekonomske fakultete je nekdo nabil sledeči tezi:

* Genialni ekonomisti so tudi matematiki.
* Če je nekdo genialen, iz tega, da ni ekonomist, sledi, da tudi matematik ni.

Na oglasni deski FMF pa sta se pojavili taki tezi:

* Genialni matematiki so vsi po vrsti nori ali pa niso ekonomisti.
* Če ni res, da iz dejstva, da je nekdo matematik, sledi, da ni ekonomist, potem je ta oseba nora ali genialna.

Kaj more študent Finančne matematike od tod sklepati?

----

* $p$ ... je genialen
* $q$ ... je ekonomist
* $r$ ... je matematik
* $s$ ... je nor

1. $p \land q \Rightarrow r$ (predp.)
2. $p \Rightarrow (\lnot q \Rightarrow \lnot r)$ (predp.)
3. $p \land r \Rightarrow s \lor \lnot q$ (predp.)
4. $\lnot (r \Rightarrow \lnot q) \Rightarrow s \lor p$ (predp.)
5. $q \land r$ (predp.)
6. $q$ (Po(5))
7. $r$ (Po(5))
8. 1. $r \Rightarrow \lnot q$ (predp. RA)
2. $\lnot q$ (MP(7, 8.1))
3. $q \land \lnot q \sim 0$ (Zd(6, 8.2))
9. $\lnot (r \Rightarrow \lnot q)$ (RA(8.1-8.3))
10. $s \lor p$ (MP(9, 4))
11. ...