Diskretne strukture (FiM)

« nazaj

Diskretne strukture (FiM) - vaje 13.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 \vee 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

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(5))
    2. $s$ (MP(5.1, 3))
    3. $r \lor s$ (Pr(5.2))
  4. $r \lor s$ (AP(1, 4.1-4.3, 5.1-5.3))

Sklep je veljaven.

Primer 4


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))
  5. $p \Rightarrow q \lor r$ (HS(4, 2))
    1. $p$ (predp. PS)
    2. $q \lor r \sim \lnot q \Rightarrow r$ (MP(6.1, 5))
      1. $\lnot q$ (predp. PS)
      2. $r$ (DS(6.2, 6.3.1))
    3. $\lnot q \Rightarrow r$ (PS(6.3.1-6.3.2))
  6. $p \Rightarrow (\lnot q \Rightarrow r)$ (PS(6.1-6.4 (-6.2)))

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))
  3. $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)$ (predp.)
    1. $p$ (predp. PS)
    2. $q \lor r$ (MP(4.1, 1))
    3. $\lnot q$ (MT(2., 4.2))
    4. $r$ (DS(4.2, 4.3))
      1. $s$ (predp. RA)
      2. $s \land r$ (Zd(4.5.1, 4.4))
      3. $0$ (Zd(3, 4.5.2))
    5. $\lnot s$ (RA(5.1-5.3))
  4. $p \Rightarrow \lnot s$ (PS(4.1-4.6))

Primer 4

    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))
      2. $p \Rightarrow r$ (PS(1.2.2.1-1.2.2.4))
    2. $(p \Rightarrow q) \Rightarrow (p \Rightarrow r)$ (PS(1.2.1-1.2.3))
  1. $(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.1))
    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))
  7. $\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.5))
    7. $0$ (Zd(4.5, 4.6))
  4. $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. $r \land t$ (MP(3.2, 1))
    4. $t$ (Po(3.3))
    5. $t \lor s$ (Pr(3.4))
    6. $\lnot q$ (MP(3.5, 2))
    7. $q$ (Po(3.1))
    8. $0$ (Zd(3.6, 3.7))
  3. $\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.)
    1. $\lnot q$ (predp. RA)
    2. $\lnot p$ (MT(1, 5.1))
    3. $\lnot (r \lor s) \sim \lnot r \land \lnot s$ (MT(2, 5.2))
    4. $\lnot s$ (Po(5.3))
    5. $t$ (DS(3, 5.4))
    6. $r$ (DS(4, 5.5))
    7. $\lnot r$ (Po(5.3))
    8. $0$ (Zd(5.6, 5.7))
  5. $q$ (RA(5.1-5.8))