מטלת מנחה 14 לקורס 'מבוא ללוגיקה' (10703)

מגיש: אנטוניו דורון (ת.ז 318155272)
למנחה: ענבל קולינר
סמסטר 2025א
שאלה 1: הוכיחו בשיטת הדדוקציה הטבעית כי הפסוקים הבאים הם טאוטולוגיות

א)
(p∧q)→q
1. p∧q C.P 2. q∧p 1 Com. 3. q 2 Simp. 4. (p∧q)→q 1-3 C.P

ב)
(p→q)→(p→(p∧q))
1. p→q C.P 2. p C.P 3. q 1,2 M.P. 4. p∧q 2,3 Conj. 5. p→(p∧q) 2-4 C.P 6. (p→q)→(p→(p∧q)) 1-5 C.P

ג)
(p→q)→(¬(q∧r)→¬(r∧p))
1. ¬q→¬p C.P 2. r→¬q C.P 3. r C.P 4. ¬q 2,3 M.P 5. ¬p 1,4 M.P 6. r→¬p 3-5 C.P 7. (r→¬q)→(r→¬p) 2-6 C.P 8. (¬q→¬p)→((r→¬q)→(r→¬p)) 1-7 C.P. 9. (¬¬p→¬¬q)→((r→¬q)→(r→¬p)) 8 Trans. 10. (p→q)→((r→¬q)→(r→¬p)) 9 D.N 11. (p→q)→((¬¬q→¬r)→(r→¬p)) 10 Trans. 12. (p→q)→((q→¬r)→(r→¬p)) 11 D.N 13. (p→q)→((¬q∨¬r)→(¬r∨¬p)) 12 Impl. 14. (p→q)→(¬(q∧r)→¬(r∧p)) 13 De Morgan

ד)
p↔(p∧(p∨q))
1. p C.P. 2. p∨q 1 Add. 3. p∧(p∨q) 1,2 Conj. 4. p→(p∧(p∨q)) 1-3 C.P 5. p∧(p∨q) C.P 6. p 5 Simp. 7. p∧(p∨q)→p 5-6 C.P 8. (p∧(p∨q)→p)∧(p→(p∧(p∨q))) 4,7 Conj. 9. p↔(p∧(p∨q)) 8 Equiv.

ה)
p∨(p→p)
1. ¬p C.P 2. p C.P 3. ¬p∧p 1,2 Conj. 4. p 3 R.A 5. p→p 2-4 C.P 6. ¬p→(p→p) 1-5 C.P 7. ¬¬p∨(p→p) 6 Impl. 8. p∨(p→p) 7 D.N.

שאלה 2: הוכיחו בשיטת הדדוקציה הטבעית את מסקנות הטיעונים התקפים שלהלן
א)
1. (p∨q)⟶r 2. ¬r ∴¬p
1. (p∨q)⟶r 2. ¬r 3. ¬(p∨q) 1,2 M.T 4. ¬p∧¬q 3 De Morgan 5. ¬p 4 Simp.

ב)
1. ((p⟶q)∨t)⟶¬r 2. r ∴p∨s
1. ((p⟶q)∨t)⟶¬r 2. r 3. ((¬p∨q)∨t)⟶¬r 1 Impl. 4. ¬¬r 2 D.N 5. ¬((¬p∨q)∨t) 3,4 M.T 6. (¬(¬p∨q)∧¬t) 5 De Morgan 7. ((¬¬p∧q)∧¬t) 6 De Morgan 8. ((p∧q)∧¬t) 7 D.N 9. (p∧(q∧¬t)) 8 Assoc. 10. p 9 Simp. 11. p∨s 10 Add.

ג)
1. (p∨q)⟶r 2. s⟶(t∧p1) 3. (p∨q)∨s ∴r∨t
1. (p∨q)⟶r 2. s⟶(t∧p1) 3. (p∨q)∨s 4. ¬r C.P 5. ¬(p∨q) 1,4 M.T 6. s 3,5 D.S 7. t∧p1 2,6 M.P 8. t 7 Simp. 9. ¬r→t 4-8 C.P 10. ¬¬r∨t 9 Impl 11. r∨t 10 Simp

ד)
1. (p⟷q)⟶¬r 2. r∧¬q ∴p
1. (p⟷q)⟶¬r 2. r∧¬q 3. ((p∧q)∨(¬q∧¬p))→¬r 1 Equiv. 4. r 2 Simp. 5. ¬¬r 4 D.N 6. ¬((p∧q)∨(¬q∧¬p)) 3,5 M.T 7. ¬(p∧q)∧¬(¬q∧¬p) 6 De Morgan 8. ¬(¬q∧¬p)∧ ¬(p∧q) 7 Com. 9. ¬(¬q∧¬p) 8 Simp. 10. ¬¬q∨¬¬p 9 De Morgan 11. ¬¬q∨p 10 D.N 12. ¬q→p 11 Impl. 13. ¬q∧r 2 Com. 14. ¬q 13 Simp. 15. p 12,14 M.P

ה)
1. (p∨q)⟶r 2. (r∨s)⟶(t∧p1) 3. ¬t ∴¬p
1. (p∨q)⟶r 2. (r∨s)⟶(t∧p1) 3. ¬t 4. ¬(t∧p1)→¬(r∨s) 2 Trans. 5. (¬t∨p1)→¬(r∨s) 4 De Morgan 6. (¬t∨p1)→(¬r∧¬s) 5 De Morgan 7. ¬t∨p1 3 Add. 8. ¬r∧¬s 6,7 M.P 9. ¬r 8 Simp. 10. ¬(p∨q) 1,9 M.T 11. ¬p∧¬q 10 De Morgan 12. ¬p 11 Simp,