Diskretne strukture (FiM)

« nazaj

Diskretne strukture (FiM) - vaje 6.11.2020

Polni nabori

Naloga 1

Kateri izmed naslednjih izjavnih veznikov sestavlja poln nabor?

  1. $\Lambda(p,q,r) \equiv p \Rightarrow (q \lor r)$
  2. $\Lambda(p,q,r) \equiv (p \uparrow q) \downarrow r$
  3. $\Lambda(p,q,r) \equiv (\lnot p \land \lnot r) \Rightarrow q$
  4. $\Lambda(p,q,r) \equiv p \Rightarrow (q \Rightarrow \lnot r) \sim \lnot p \lor \lnot q \lor \lnot r$
    • ohranjanje 1: $\Lambda(1, 1, 1) \sim 1 \Rightarrow (1 \lor 1) \sim 1$ velja
    • nabor $\lbrace \Lambda \rbrace$ ni poln
    • 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
    • ohranjanje 0: $\Lambda(0, 0, 0) \sim (\lnot 0 \land \lnot 0) \Rightarrow 0 \sim 0$ velja
    • nabor $\lbrace \Lambda \rbrace$ ni poln
    • 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

$p_1, p_2, \dots p_n \models q$ velja natanko tedaj, ko velja $p_1 \land p_2 \land \dots \land p_n \Rightarrow q$

  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 $5$ ur. Ne morem si privoščiti samo $5$ ur spanja. Potemtakem bom moral zamuditi pouk ali pa se odpovedati žuru.

    • $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
    • $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))
    1. $\lnot s$ (predp. AP(5))
    2. $\lnot r$ (MT(2, 7.1))
    3. $p \lor \lnot r$ (Pr(7.2))
    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:

Na oglasni deski FMF pa sta se pojavili taki tezi:

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

  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))
    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. …
Ta stran je odprtokodna. Izboljšaj to stran.
Ta zapisek je dostopen tudi na HackMD.