---
tags: vaje, ds, izjavni, sklepanje
hackmd: https://hackmd.io/9JsyGFhrTw-arbQY16Ak6w
plugins: mathjax
---
# Diskretne strukture (FiM) - vaje 5.11.2020

---

## Polni nabori

### Naloga 1

Kateri izmed naslednjih izjavnih veznikov sestavlja poln nabor?

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

----

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

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

3. * ohranjanje 0: $\Lambda(0, 0, 0) \sim 0 \Rightarrow (0 \Rightarrow \lnot 0) \sim 1$ ne velja
* ohranjanje 1: $\Lambda(1, 1, 1) \sim 1 \Rightarrow (1 \Rightarrow \lnot 1) \sim 0$ ne velja
* afinost: $\Lambda(1, 1, 0) \sim 1 \Rightarrow (1 \Rightarrow \lnot 0) \sim 1$, $\Lambda(0, 0, 1) \sim 0 \Rightarrow (0 \Rightarrow \lnot 1) \sim 1$ ne velja
* monotonost: ne velja (glej ohranjanje 0, 1)
* sebi dualnost: $\lnot \Lambda(\lnot p, \lnot q, \lnot r) \sim \lnot (\lnot p \Rightarrow (\lnot q \Rightarrow r)) \sim \lnot (p \lor q \lor r) \sim \lnot p \land \lnot q \land \lnot r$ ne velja
* $\Lambda(p, p, p) \sim p \Rightarrow (p \Rightarrow \lnot p) \sim \lnot p$
* $\Lambda(p, q, q) \sim p \Rightarrow (q \Rightarrow \lnot q) \sim p \Rightarrow \lnot q \sim \lnot p \lor \lnot q \sim \lnot (p \land q)$
* $p \land q \sim \lnot \Lambda(p, q, q) \sim \Lambda(\Lambda(p, q, q), \Lambda(p, q, q), \Lambda(p, q, q))$
* $p \lor q \sim \Lambda(\Lambda(p, p, p), \Lambda(q, q, q), \Lambda(q, q, q))$
* $\lbrace \Lambda \rbrace$ **je** poln nabor

---

## Sklepanje

* <i>$p_1, p_2, \dots, p_n \models q$</i> pomeni
* <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. modus tollens (MT): $p \Rightarrow q, \lnot q \models \lnot p$
3. disjunktivni silogizem (DS): $p \lor q, \lnot q \models p$
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. sklep s protislovjem (RA - *reductio ad absurdum*): $[\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 bo izpit
* $p \Rightarrow q, \lnot p \models \lnot q$
* protiprimer: $p \sim 0$, $q \sim 1$
* sklep je **neveljaven**

2. * $p$ ... zamudil bom na pouk
* $q$ ... zgodaj bom vstal
* $r$ ... nocoj grem na žur
* $s$ ... pozno se bom vrnil
* $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$ (MT(3, 4))
6. 1. $\lnot s$ (predp. AP(5))
2. $\lnot r$ (MT(2, 6.1))
3. $p \lor \lnot r$ (Pr(6.2))
7. 1. $\lnot q$ (predp. AP(5))
2. $p$ (MT(1, 7.1))
3. $p \lor \lnot r$ (Pr(7.2))
8. $p \lor \lnot r$ (AP(5, 6.1-6.3, 7.1-7.3))

Sklep je **veljaven**.

---

### 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 ekonomist
* $q$ ... je matematik
* $r$ ... je genialen
* $s$ ... je nor

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