---
tags: vaje, ds, sklepanje
hackmd: https://hackmd.io/jWlDRSOcSiShtKMtRncF1Q
plugins: mathjax
---
# Diskretne strukture (FiM) - vaje 11.11.2020

---

## Sklepanje

### Naloga 1

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

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

----

#### 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. <i>$s \land (p \Rightarrow t), t \Rightarrow (q \lor r) \models p \Rightarrow (\lnot q \Rightarrow r)$</i>
2. <i>$p \lor q \Rightarrow r \land s, r \lor t \Rightarrow u \models p \Rightarrow u$</i>
3. <i>$p \Rightarrow q \lor r, q \Rightarrow \lnot p, \lnot (s \land r) \models p \Rightarrow \lnot s$</i>
4. <i>$\models (p \Rightarrow (q \Rightarrow r)) \Rightarrow ((p \Rightarrow q) \Rightarrow (p \Rightarrow r))$</i>

----

#### 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
* <i>$\models (p \Rightarrow (q \Rightarrow r)) \Rightarrow ((p \Rightarrow q) \Rightarrow (p \Rightarrow r))$</i>

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. <i>$(p \Rightarrow q) \land (r \Rightarrow s), s \land q \Rightarrow t, \lnot t \models \lnot (p \land r)$</i>
2. <i>$p \lor q, p \Rightarrow r, q \Rightarrow s \models r \lor s$</i>
3. <i>$p \Rightarrow r \land t, t \lor s \Rightarrow \lnot q \models \lnot (p \land q)$</i>
4. <i>$p \Rightarrow q, r \lor s \Rightarrow p, s \lor t, \lnot t \lor r \models q$</i>

----

#### 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))