Diskretne strukture (FiM)

« nazaj

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.)
4. 1. $p$ (predp. AP(1))
   2. $r$ (MP(4.1, 2))
   3. $r \lor s$ (Pr(4.2))
5. 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))
5. 1. $p$ (predp. PS)
   2. $t$ (MP(5.1, 4))
   3. $q \lor r \sim \lnot q \Rightarrow r$ (MP(5.2, 2))
   4. 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.)
3. 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.)
4. 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))
   5. 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. 1. $p \Rightarrow (q \Rightarrow r)$ (predp. PS)
   2. 1. $p \Rightarrow q$ (predp. PS)
      2. 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))
7. 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.)
4. 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.)
3. 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))
6. 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))

Ta stran je odprtokodna. Izboljšaj to stran.

Ta zapisek je dostopen tudi na HackMD.