changed 4 years ago  
Linked with GitHub

Diskretne strukture (FiM) - vaje 11.11.2020

Sklepanje

Naloga 1

Kateri od naslednjih sklepov so veljavni? Dokaži jih ali pa navedi protiprimer.

  1. \((q \vee r) \Rightarrow \lnot p, s \vee p, q \models s\)
  2. \(p \land q,~\lnot p \Rightarrow q \models \lnot q\)
  3. \(p \lor q, p \Rightarrow r, q \Rightarrow s \models r \lor s\)
  4. \((p \Rightarrow q) \Rightarrow (r \Rightarrow s),~\lnot(r \Rightarrow q) \models s\)

Primer 1

  1. \((q \vee r) \Rightarrow \lnot p\) (predp.)
  2. \(s \lor p\) (predp.)
  3. \(q\) (predp.)
  4. \(q \lor r\) (Pr(3))
  5. \(\lnot p\) (MP(4, 1))
  6. \(s\) (DS(2, 5))

Sklep je veljaven.

Primer 2

  • Protiprimer: \(p \sim 1, q \sim 1\)
  • Sklep je neveljaven.

Primer 3

  1. \(p \lor q\) (predp.)
  2. \(p \Rightarrow r\) (predp.)
  3. \(q \Rightarrow s\) (predp.)
    1. \(p\) (predp. AP(1))
    2. \(r\) (MP(4.1, 2))
    3. \(r \lor s\) (Pr(4.2))
    1. \(q\) (predp. AP(1))
    2. \(s\) (MP(5.1, 3))
    3. \(r \lor s\) (Pr(5.2))
  6. \(r \lor s\) (AP(1, 4.1-4.3, 5.1-5.3))

Sklep je veljaven.

Primer 4

  • Protiprimer: \(s \sim 0, r \sim 1, q \sim 0, p \sim 1\)
  • Sklep je neveljaven.

Naloga 2

Preveri pravilnost sklepov s pomočjo pogojnega sklepa.

  1. \(s \land (p \Rightarrow t), t \Rightarrow (q \lor r) \models p \Rightarrow (\lnot q \Rightarrow r)\)
  2. \(p \lor q \Rightarrow r \land s, r \lor t \Rightarrow u \models p \Rightarrow u\)
  3. \(p \Rightarrow q \lor r, q \Rightarrow \lnot p, \lnot (s \land r) \models p \Rightarrow \lnot s\)
  4. \(\models (p \Rightarrow (q \Rightarrow r)) \Rightarrow ((p \Rightarrow q) \Rightarrow (p \Rightarrow r))\)

Primer 1

  1. \(s \land (p \Rightarrow t)\) (predp.)
  2. \(t \Rightarrow (q \lor r)\) (predp.)
  3. \(s\) (Po(1))
  4. \(p \Rightarrow t\) (Po(1))
    1. \(p\) (predp. PS)
    2. \(t\) (MP(5.1, 4))
    3. \(q \lor r \sim \lnot q \Rightarrow r\) (MP(5.2, 2))
      1. \(\lnot q\) (predp. PS)
      2. \(r\) (DS(3, 4.1))
    5. \(\lnot q \Rightarrow r\) (PS(4.1-4.2))
  6. \(p \Rightarrow (\lnot q \Rightarrow r)\) (PS(5.1-5.5 (-5.3)))

Primer 2

  1. \(p \lor q \Rightarrow r \land s\) (predp.)
  2. \(r \lor t \Rightarrow u\) (predp.)
    1. \(p\) (predp. PS)
    2. \(p \lor q\) (Pr(3.1))
    3. \(r \land s\) (MP(3.2, 1))
    4. \(r\) (Po(3.3))
    5. \(r \lor t\) (Pr(3.4))
    6. \(u\) (MP(3.5, 2))
  4. \(p \Rightarrow u\) (PS(3.1-3.6))

Primer 3

  1. \(p \Rightarrow q \lor r\) (predp.)
  2. \(q \Rightarrow \lnot p\) (predp.)
  3. \(\lnot (s \land r) \sim \lnot s \lor \lnot r\) (predp.)
    1. \(p\) (predp. PS)
    2. \(q \lor r\) (MP(4.1, 1))
    3. \(\lnot q\) (MT(2, 4.1))
    4. \(r\) (DS(4.2, 4.3))
      1. \(s\) (predp. RA)
      2. \(s \land r\) (Zd(5.1, 4))
      3. \(0\) (Zd(3, 5.2))
    6. \(\lnot s\) (RA(5.1-5.3))
  5. \(p \Rightarrow \lnot s\) (PS(4.1-4.6))

Primer 4

  • Dokazujemo tavtologijo
  • \(\models (p \Rightarrow (q \Rightarrow r)) \Rightarrow ((p \Rightarrow q) \Rightarrow (p \Rightarrow r))\)
    1. \(p \Rightarrow (q \Rightarrow r)\) (predp. PS)
      1. \(p \Rightarrow q\) (predp. PS)
        1. \(p\) (predp. PS)
        2. \(q\) (MP(1.2.2.1, 1.2.1))
        3. \(q \Rightarrow r\) (MP(1.2.2.1, 1.1))
        4. \(r\) (MP(1.2.2.2, 1.2.2.3))
      3. \(p \Rightarrow r\) (PS(1.2.2.1-1.2.2.4))
    3. \((p \Rightarrow q) \Rightarrow (p \Rightarrow r)\) (PS(1.2.1-1.2.3))
  2. \((p \Rightarrow (q \Rightarrow r)) \Rightarrow ((p \Rightarrow q) \Rightarrow (p \Rightarrow r))\) (PS(1.1-1.3))

Naloga 3

Preveri pravilnost sklepov s pomočjo dokaza s protislovjem (reductio ad absurdum).

  1. \((p \Rightarrow q) \land (r \Rightarrow s), s \land q \Rightarrow t, \lnot t \models \lnot (p \land r)\)
  2. \(p \lor q, p \Rightarrow r, q \Rightarrow s \models r \lor s\)
  3. \(p \Rightarrow r \land t, t \lor s \Rightarrow \lnot q \models \lnot (p \land q)\)
  4. \(p \Rightarrow q, r \lor s \Rightarrow p, s \lor t, \lnot t \lor r \models q\)

Primer 1

  1. \((p \Rightarrow q) \land (r \Rightarrow s)\) (predp.)
  2. \(s \land q \Rightarrow t\) (predp.)
  3. \(\lnot t\) (predp.)
  4. \(\lnot (s \land q)\) (MT(2, 3))
  5. \(p \Rightarrow q\) (Po(1))
  6. \(r \Rightarrow s\) (Po(1))
    1. \(p \land r\) (predp. RA)
    2. \(p\) (Po(7.1))
    3. \(r\) (Po(7.2))
    4. \(q\) (MP(7.2, 5))
    5. \(s\) (MP(7.3, 6))
    6. \(s \land q\) (Zd(7.5, 7.4))
    7. \(0\) (Zd(4, 7.6))
  8. \(\lnot (p \land r)\) (RA(7.1-7.7))

Primer 2

  1. \(p \lor q\) (predp.)
  2. \(p \Rightarrow r\) (predp.)
  3. \(q \Rightarrow s\) (predp.)
    1. \(\lnot (r \lor s) \sim \lnot r \land \lnot s\) (predp. RA)
    2. \(\lnot r\) (Po(4.1))
    3. \(\lnot s\) (Po(4.1))
    4. \(\lnot p\) (MT(2, 4.2))
    5. \(\lnot q\) (MT(3, 4.3))
    6. \(q\) (DS(1, 4.4))
    7. \(0\) (Zd(4.5, 4.6))
  5. \(r \lor s\) (RA(4.1-4.7))

Primer 3

  1. \(p \Rightarrow r \land t\) (predp.)
  2. \(t \lor s \Rightarrow \lnot q\) (predp.)
    1. \(p \land q\) (predp. RA)
    2. \(p\) (Po(3.1))
    3. \(q\) (Po(3.1))
    4. \(r \land t\) (MP(3.2, 1))
    5. \(t\) (Po(3.4))
    6. \(t \lor s\) (Pr(3.5))
    7. \(\lnot q\) (MP(3.6, 2))
    8. \(0\) (Zd(3.3, 3.7))
  4. \(\lnot (p \land q)\) (RA(3.1-3.8))

Primer 4

  1. \(p \Rightarrow q\) (predp.)
  2. \(r \lor s \Rightarrow p\) (predp.)
  3. \(s \lor t\) (predp.)
  4. \(\lnot t \lor r\) (predp.)
  5. \(r \lor s \Rightarrow q\) (HS(2, 1))
    1. \(\lnot q\) (predp. RA)
    2. \(\lnot (r \lor s) \sim \lnot r \land \lnot s\) (MT(5, 6.1))
    3. \(\lnot r\) (Po(6.2))
    4. \(\lnot s\) (Po(6.2))
    5. \(\lnot t\) (DS(4, 6.3))
    6. \(t\) (DS(3, 6.4))
    7. \(0\) (Zd(6.5, 6.6))
  7. \(q\) (RA(6.1-6.7))
Select a repo