Diskretne strukture (FiM)

« nazaj

Diskretne strukture (FiM) - vaje 5.11.2020

---

Polni nabori

Naloga 1

Kateri izmed naslednjih izjavnih veznikov sestavlja poln nabor?

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

---

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

• $p_1, p_2, \dots, p_n \models q$ pomeni
• $p_1 \land p_2 \land \dots \land p_n \Rightarrow q$

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 $5$ ur. Ne morem si privoščiti samo $5$ 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. …

Ta stran je odprtokodna. Izboljšaj to stran.

Ta zapisek je dostopen tudi na HackMD.