changed 4 years ago  
Linked with GitHub jaanos/diskretne-strukture-fim/zapiski/2020-21/2020-11-06.md

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:

  • 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))
    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. …
Select a repo