לדלג לתוכן

תרגילים פרק 6🏋️

[[6 - דדוקציה טבעית]] [[עזרים לדדוקציה טבעית]]

תרגיל א

א. 

1. רכיבת אופניים היא פעילות ספורט ממושכת
2. אם פעילות היא מהנה, אז היא גם בריאה
3. כל פעילות ספורט שהיא ממושכת היא גם מהנה
4. אדי מרקס עוסק ברכיבת אופניים
לכן אדי מרקס עוסק בפעילות בריאה.
  1. רכיבת אופניים היא פעילות ספורט ממושכת
  2. אם פעילות היא מהנה, אז היא גם בריאה
  3. כל פעילות ספורט שהיא ממושכת היא גם מהנה
  4. אדי מרקס עוסק ברכיבת אופניים
  5. רכיבת אופניים היא פעילות ספורט מהנה (1,3)
  6. רכיבת אפניים היא פעילות בריאה (2,5)
  7. אדי מרקס עוסק בפעילות בריאה (4,6)

ב. 

1. אם הפועל באר־שבע תנצח בשבת, הפועל תל־אביב תזכה באליפות
2. אם הפועל תל־אביב תזכה באליפות, מכבי חיפה תסיים במקום השני
3. אם מכבי חיפה תסיים במקום השני, יעקב שחר יפרוש
4. הפועל באר־שבע תנצח בשבת
לכן יעקב שחר יפרוש.
  1. אם הפועל באר־שבע תנצח בשבת, הפועל תל־אביב תזכה באליפות
  2. אם הפועל תל־אביב תזכה באליפות, מכבי חיפה תסיים במקום השני
  3. אם מכבי חיפה תסיים במקום השני, יעקב שחר יפרוש
  4. הפועל באר־שבע תנצח בשבת
  5. הפועל תל אביב תזכה באליפות (1,4)
  6. מכבי חיפה תסיים במקום השני (2,5)
  7. יעקב שחר יפרוש (6,3)

ג. 

1. אם מכבי תל־אביב לא תזכה באליפות אירופה, מזרחי יתפטר
2. אם מכבי תל־אביב תזכה באליפות אירופה, מוני יתעשר
3. או שמוני לא יתעשר או שבלאט ישמח
4. בלאט לא ישמח
לכן מזרחי יתפטר.
  1. אם מכבי תל־אביב לא תזכה באליפות אירופה, מזרחי יתפטר
  2. אם מכבי תל־אביב תזכה באליפות אירופה, מוני יתעשר
  3. או שמוני לא יתעשר או שבלאט ישמח
  4. בלאט לא ישמח
  5. מוני לא יתעשר (3,4)
  6. מכבי תל אביב לא תזכה באליפות אירופה (2,5)
  7. מזרחי יתפטר (1,6)

ד. 

1. אם ארגנטינה או ברזיל יזכו באליפות, מלכת אנגליה תתאכזב
2. אם מלכת אנגליה תתאכזב, הפרלמנט האנגלי יסער
3. אם הפרלמנט האנגלי יסער, יש חשש שתפרוץ מלחמה
4. אין חשש שתפרוץ מלחמה
לכן ברזיל לא תזכה באליפות.
  1. אם ארגנטינה או ברזיל יזכו באליפות, מלכת אנגליה תתאכזב
  2. אם מלכת אנגליה תתאכזב, הפרלמנט האנגלי יסער
  3. אם הפרלמנט האנגלי יסער, יש חשש שתפרוץ מלחמה
  4. אין חשש שתפרוץ מלחמה
  5. הפרלמנט האנגלית לא יסער (3,4)
  6. מלכת אנגליה לא תתאכזב (2,5)
  7. ארגנטינה או ברזיל לא יזכו באליפות (1,6)

בדיקה: הכל נכון, החוברת ביקשה עוד צעד בד', לכתוב סעיף 8: ברזיל לא תזכה (כי ארגנטינה סלש ברזיל לא יזכו...)

תרגיל ב

א. לפניכם שישה טיעונים. בכל אחד מהם ניתן לגזור את המסקנה מן ההנחות בצעד אחד בלבד. ציינו מהו הכלל שבו יש להשתמש על־מנת שניתן יהיה לגזור את המסקנה מן ההנחות.

1)
1. (p→q)∧(r→¬t) ∴ (p→q) 1 Simp.

2)
1. t→¬q ∴ (t→¬q)∨(p∧r) 1 Add. 3)
1. p→(q↔¬r) 2. (q↔¬r)→¬s ∴ p→¬s 1, 2 H.S. 4)
1. (t∧¬p)∨(q↔r) 2. ¬(t∧¬p) ∴ q↔r 1, 2 D.S. 5)
1. (p→¬r)∧(s→(q→¬t) 2. ¬¬r∨¬(q→¬t) ∴ ¬p∨¬s 1,2, D.D. 6)
1. (p→(¬q∧¬s))→((t∧¬r)∨¬(p→t)) 2. ¬((t∧¬r)∨¬(p→t)) ∴ ¬(p→(¬q∧¬s)) 1,2 M.T.

ב. לפניכם ארבע הוכחות של תקפות טיעונים, ללא הצידוקים. השלימו את ההוכחות על־ידי ציון הצידוק עבור כל שלב בהוכחה.

1)
1. (p∧t)→(p→(r∧s)) 2. (p∧t)∧s 3. p∧t 2 Simp. 4. p→(r∧s) 1, 3 M.P. 5. p 3 Simp. 6. r∧s 4, 5 M.P. 7. r 6 Simp. 8. r∨s 6, Add.**

בדיקה: בסוף זה 7 ADD, לשים לב למספור! 2)
1. q→(r∧s) 2. (r∧s)→t 3. (s∧p)→¬q 4. ¬q→(r↔¬s) 5. ¬t∨¬(r↔¬s) 6. q→t 1,2 H.S. 7. (s∧p)→(r↔¬s) 3,4 H.S. 8. (q→t)∧((s∧p)→(r↔¬s)) 6,7 Con¬. 9. ¬q∨¬(s∧p) 5,8 D.D. בדיקה: החוברת כתבה 8,5 DD, לא יודע אם זה משמעותי, לחשוב על זה (כי יש הבדל בין אלפה לבטא בצורות הכלליות של הכללים) 3)
1. p→q 2. r→s 3. ¬q∨¬s 4. ¬¬p 5. (t∧p1)→r 6. (p→q)∧(r→s) 1,2 Con¬. 7. ¬p∨¬r 3,6 D.D. 8. ¬r 4,7 D.S. 9. ¬(t∧p1) 5,8 M.T. 4)
1. ((p∨¬q)∨r)→(s→(t↔r1)) 2. (p∨¬q)→((r1↔p1)→q1) 3. p→((t↔r1)→(r1↔p1)) 4. p 5. p∨¬q 4, Add. 6. (p∨¬q)∨r 5, Add. 7. s→(t↔r1) 1,6 M.P. 8. (t↔r1)→(r1↔p1) 3,4 M.P. 9. s→(r1↔p1) 1,3 H.S. 1∨. (r1↔p1)→q1 2, 5 M.P. 11. s→q1 9,1∨ H.S. בדיקה: זה 78 HS ב-9, לא יודע למה כתבתי 1,3, כנראה סתם התבלבלתי. לשיםלב.

ג. גזרו את מסקנות הטיעונים הבאים, תוך שימוש בכללי ההיסק בלבד

1)
1. p→q 2. r→s 3. (¬q∨¬s)∧(¬p∨¬q) ∴ ¬p∨¬r

  1. p→q
  2. r→s
  3. (¬q∨¬s)∧(¬p∨¬q)
  4. (p→q)∧(r→s) 1,2 Con¬.
  5. ¬q∨¬s 3 Simp.
  6. ¬p∨¬r 4,5 D.D.

2)
1. p→q 2. p∨(q∨¬r) 3. ¬q ∴ ¬r∧¬q

  1. p→q
  2. p∨(q∨¬r)
  3. ¬q
  4. ¬p 1,3 M.T.
  5. q∨¬r 2,4 D.S.
  6. ¬r 3,5 D.S.
  7. ¬r∧¬q 3,6 Con¬.

3)
1. (r→¬s)∧(t→¬p) 2. (q→¬r1)∧(p1→¬q1) 3. (t→r1)∧(p→s) 4. q∨r ∴ ¬t∨¬p

  1. (r→¬s)∧(t→¬p)
  2. (q→¬r1)∧(p1→¬q1)
  3. (t→r1)∧(p→s)
  4. q∨r
  5. r→¬s 1, Simp.
  6. q→¬r1 2, Simp.
  7. (r→¬s)∧(q→¬r1) 5,6 Con¬.
  8. ¬r1∨¬s 4,7 C.D.
  9. ¬t∨¬p 3,8 D.D.

תרגיל ג

א . לפניכם טיעונים אחדים, שבכל אחד מהם ניתן לגזור את המסקנה מההנחה בצעד אחד בלבד. ציינו מהו כלל החילוף שיש להשתמש בו על־מנת שניתן יהיה לגזור את המסקנה מההנחה.

1)
1. (p→q)∧(r∨¬t) ∴(p→q)∧(¬t∨r) 1 Com. 2)
1. (p→q)∧(r∨¬t) ∴(¬q→¬p)∧(r∨¬t) 1 Trans. 3)
1. (p∧(q↔r))∨(p∧(q↔r)) ∴ (p∧(q↔r)) 1 Taut. 4)
1. (p∧(q∨¬r))→(s→t) ∴ p→((q∨¬r)→(s→t)) 1 Exp. 5)
1. (p→q)∨(r∧s) ∴ ((p→q)∨r)∧((p→q)∨s) 1 Dist.

ב . לפניכם כמה הוכחות של תקפות טיעונים החסרים צידוקים. השלימו את ההוכחות על־ידי ציון הצידוק עבור כל שלב בהוכחה.

1)
1. (p∨q)→(r∧s) 2. ¬r 3. ¬r∨¬s 2 Add. 4. ¬(r∧s) 3 De Morgan. 5. ¬(p∨q) 1,4 M.T. 6. ¬p∧¬q 5 De Morgan. 7. ¬q∧¬p 6 Com.
8. ¬q 7 Simp.

2)
1. (p∧q)→r 2. (p→r)→s 3. ¬q∨t 4. (q∧p)→r 1 Com. 5. q→(p→r) 4 Exp. 6. q→s 2,5 HS. 7. ¬q∨s 6 Impl. 8. (¬q∨s)∧(¬q∨t) 3,7 Con¬. 9. ¬q∨(s∧t) 8 Dist. 1∨. q→(s∧t) 9 Impl.

3)
1. s→(t→p) 2. p→¬p 3. (q→s)∧(r→t) 4. (s∧t)→p 1 Exp. 5. ¬p∨¬p 2 Impl. 6. ¬p 5 Taut. 7. ¬(s∧t) 4,6 M.T. 8. ¬s∨¬t 7 De Morgan. 9. ¬q∨¬r 3,8 D.D. 1∨. q→¬r 9 Impl.

4)
1. p→(q→¬p) 2. p↔q 3. p→(¬¬p→¬q) 1 Trans. 4. p→(p→¬q) 3 D.N. 5. (p∧p)→¬q 4 Exp. 6. p→¬q 5 Taut. 7. ¬p∨¬q 6 Impl. 8. ¬(p∧q) 7 De Morgan. 9. (p∧q)∨(¬p∧¬q) 2 Equiv. 1∨. ¬p∧¬q 7,9 D.S.

5)
1. p∨(¬q∨p) 2. q∨(¬p∨q) 3. (¬q∨p)∨p 1 Com. 4. ¬q∨(p∨p) 3 Assoc. 5. ¬q∨p 4 Taut. 6. q→p 5 Impl. 7. (¬p∨q)∨q 2 Com. 8. ¬p∨(q∨q) 7 Assoc. 9. ¬p∨q 8 Taut. 1∨. p→q 9 Impl. 11. (p→q)∧(q→p) 6,1∨ Con¬. 12. p↔q 11 Equiv. 13. (p∧q)∨(¬p∧¬q) 12 Equiv.

לא לשכוח שאפשר להחליף רישה וסיפה באימפליקציה... זה מוסיף שלילות, זה Trans.

ג. גזרו את המסקנות של הטיעונים הבאים תוך שימוש בכל כללי הדדוקציה הטבעית שלמדנו עד כה

1)
1. ¬p ∴ p→q 1. ¬p 2. ¬p∨q 1 Add. 3. p→q 2 Impl.

2)
1. p→(q∧r( ∴ p→q

  1. p→(q∧r)
  2. p→q 1 Simp.

זו גרסה לא נכונה. מגדירים את מה שאפשר לעשות לפי הקשר הראשי. אני יכול להפוך את Q-AND-R כשלעצמו ל-Q או ל-R, אבל כשהוא חלק מהתניה, אי אפשר.

  1. p→(q∧r)
  2. ¬p∨(q∧r) 1 Impl.
  3. (¬p∨q)∧(¬p∨r) 2 Dist.
  4. ¬p∨q 3 Simp.
  5. p→q 4 Impl.

לזכור, כשיש אימפליקציה ננסה לעשות או Impl. כדי לעבור לדיסיונקציה, או Trans. כדי לשלול את הרישה והסיפה, ברוב המקרים.

3)
1. (p∨q)→r ∴ p→r 1. (p∨q)→r 2. ¬(p∨q)∨r 1 Impl. 3. (¬p∧¬q)∨r 2 De Morgan. 4. r∨(¬p∧¬q) 3 Com. 5. (r∨¬p)∧(r∨¬q) 4 Dist. 6. r∨¬p 5 Simp. 7. ¬p∨r 6 Com. 8. p→r 7 Impl.

אם יש לי פסוקים שצריך "להיפטר" מהם, הרבה פעמים הכיוון יהיה ליצור Dist. ולהעיף את אחד הקוניונקטים בעזרת Simp. 4) 

1. p→¬(q→r)
2. (s∧q)→r
3. s
∴ ¬p
  1. p→¬(q→r)
  2. (s∧q)→r
  3. s
  4. ¬p∨¬(q→r) 1 Impl.
  5. s→(q→r) 2 Exp.
  6. q→r 3,5 M.P.
  7. ¬p 4,6 M.T.

זה היה די קשה. אבל לחשוב טוב על הדברים ב"סדר הפוך". להשיג את הרכיבים שצריך כדי להוכיח. הרבה פעמים זה פשוט להפעיל את מה שמתבקש על הפסוקים.

5)
1. (p∨q)→¬(r∧s) 2. (¬r∨¬s)→(t↔p1) 3. (t↔p1)→(q1∧r1) ∴ (q∨p)→(r1∧q1)

  1. (p∨q)→¬(r∧s)
  2. (¬r∨¬s)→(t↔p1)
  3. (t↔p1)→(q1∧r1)
  4. (q∨p)→¬(r∧s) 1 Com.
  5. (t↔p1)→(r1∧q1) 2 Com.
  6. (q∨p)→(¬r∨¬s) 4 De Morgan.
  7. (q∨p)→(t↔p1) 2,6 H.S.
  8. (q∨p)→(q1∧r1) 3,7 H.S.

פה פעלתי חכם. סידרתי את הפסוקים שאני צריך והדרך די חשפה את עצמה.

6)
1. p→(q→r) 2. r→(s∧t) ∴ p→(q→t)

  1. p→(q→r)
  2. r→(s∧t)
  3. ¬r∨(s∧t) 2 Impl.
  4. (¬r∨s)∧(¬r∨t) 3 Dist.
  5. (r→s)∧(r→t) 4 Impl.
  6. (r→t)∧(r→s) 5 Com.
  7. r→t 6 Simp..
  8. (p∧q)→r 1 Exp.
  9. (p∧q)→t 7,8 H.S. 1∨. p→(q→t) 8 Exp.

זה היה אחד קשה... למדנו: 1. להתחיל מלהבין איך נוצרה המסקנה, מה היה השלב לפני-אחרון 2. כדי להעיף אות פסוקית מהנחה יש מהלך נחמד: א. הופכים התניה לדיסיונקציה שלולה ב. הופכים דיסיונקציה שלולה לקוניונקציה של שתי דיסיונקציות ג. מסדרים את הקונוינקציה איך שצריך ד. משתמשים בסימפ כדי לפרק אותה
ה. משתמשים בסילוגיזם היפתותטי כדי לערבב את הלוח :) 7)
1. (p∧(q∨r))→(q∧r) ∴ p→(q→r) 1. (p∧(q∨r))→(q∧r) 2. ((p∧q)∨(p∧r))→(q∧r) 1 Dist. 3. ¬((p∧q)∨(p∧r))∨(q∧r) 2 Impl. 4. ¬(p∧q)∧¬(p∧r))∨(q∧r) 3 De Morg. 5. (q∧r)∨(¬(p∧q)∧¬(p∧r)) 4 Com. 6. (q∧r)∨(¬(p∧q))∧(q∧r)∨(¬(p∧r)) 5 Dist. 7. (q∧r)∨(¬(p∧q)) 6 Simp. 8. (¬(p∧q))∨(q∧r) 7 Com. 9. (¬(p∧q))∨(r∧q) 8 Com. 1∨. (¬(p∧q))∨r)∧(¬(p∧q))∨q) 9 Dist. 11. (¬(p∧q))∨r) 1∨ Simp. 12. (p∧q)→r 11 Impl. 13. p→(q→r) 12 Exp.

טוב... זה הרגיל בלתי אפשרי. סימנתי נכון את האחד-לפני-אחרון, אבל לא יצא מזה כלום. בגדול למדתי שצריך לשחק עם Dist - לפתוח סוגריים בין אם הן שלולות או לא. ואז לשחק עם Com כדי לסדר את הדברים ועם Simp כדי לחצות אותם... ** לזכור** - Dist זה מול פסוק שיש לו קוניונקציה∧דיסיונקציה בסוגריים מורגן זה מול סוגריים שלולות אחרי שעושים IMPL. ומגיעים לסוגריים שלולות, להשתמש ב-DE MORGAN כדי לפתוח אותן... ואז אפשר לשחק עם COM, DIST וכו' כדי לסדר את הפסוקים... חוץ מלירות באפלה לאלף כיוונים, לא הבנתי מה יכולתי לעשות יותר טוב, האמת.

8)
1. s→(t∧p) 2. (t∨p)→q ∴ s→q 1. s→(t∧p) 2. (t∨p)→q 3. ¬(t∨p)∨q 2 Impl. 4. (¬t∧¬p)∨q 3 De Morgan. 5. ¬t∨(¬p∨q) 4 Assoc. 6. ¬t∨(p→q) 5 Impl. 7. (t→(p→q) 6 Impl. 8. (t∧p)→q 7 Exp. 9. s→q 1,8 H.S.

זה היה מאוד קשה אבל למדתי דברים: 1. לשחק עם דה מורגן זה אומר להפוך כל הזמן את הסימן של V ובהתאם את השלילות 2. יש דרך יותר טובה מלירות באפלה או להנדס אחורנית: לעשות את שניהם עד שהם משתלבים...

9)
1. (p∨q)→(r∧s) 2. p→(t→t) 3. r ∴ t

כל הזמן הזה עבדתי כאילו 3 היה r, אבל הוא צריך להיות r¬... אני אנסה שוב בהמשך.

  1. (p∨q)→(r∧s)
  2. p→(t→t)
  3. ¬r

1∨) 1. q∨(r∧s) 2. (q→t)∧(t→s) ∴ s

  1. q∨(r∧s)
  2. (q→t)∧(t→s)
  3. q→t 2 Simp.
  4. (t→s)∧(q→t) 2 Com.
  5. t→s 4 Simp.
  6. q→s 3,5 H.S.
  7. (q∨r)∧(q∨s) 1 Dist.
  8. (q∨s)∧(q∨r) 7 Com.
  9. q∨s 8 Simp. 1∨. ¬¬q∨s 9 D.N.
  10. ¬q→s 1∨ Impl.
  11. ¬s→¬q 6 Trans.
  12. ¬s→s 11,12 H.S.
  13. ¬¬s∨s 13 Impl
  14. s∨s 14 D.N.
  15. s 15 Taut.

את האחד הזה לא הצלחתי ולא השארתי לסוף. זה כדי ללמוד. בוא ננסה לשחזר מה קורה כאן. 3. מתחילים מעבודה על הפסוק השני, זה שרירותי. לקחנו מהקוניונקציה את q→t. אנחנו צריכים להוכיח בסוף אות פסוקית, אז כל מה שקשור להיסק כזה (ההיסקים שאפשר להסיק מהם פסוקית, טאוטולוגיה וכו') שווה לבודד. 4-5: החלפנו את הסדר של הקוניונקציה כדי לקחת את ההתניה השניה מהקוניונקציה, מאותן סיבות 6: זה כבר מספיק כדי ליצור עוד אימפליקציה שיכולה לשמש אותנו 7: עבודה על הפסוק הראשון: פותחים סוגריים באמצעות dist כדי לראות מה יוצא 8: זיהינו סוגריים עם פסוקים רלוונטיים למה שמצאנו קודם, אז נשים אותם ראשונים עם com 9: ניקח את הסוגריים הראשונות עם simp 1∨-11: מהלך שחשוב לזכור!!! זה בעצם הגרסה המלאה של לעשות את הצעד ההפוך מimpl רגיל. (הופכים את החיובי לדאבל נגטיב ואז אפשר לעשות) - אני מדלג על השלב הזה ועושה בראש, אבל אסור. 12: רוב הפעמים שעשיתי trans, טעיתי, צריך להפוך את הרישה והסיפה!!! בעצם ניגשנו להיסק החדש שלנו ממקודם והפכנו אותו כך שיתכתב עם התוצאה של הimpl ב-1∨-11 13: מצאנו עוד היסק טוב עם HS 14-15: רואים טאוטולוגיה ממרחק, אז עושים IMPL ואז D.N כדי להגיע אליה...

היה לי יום קשה היום עם התרגילים... זה בסדר להודות בזה... האחרונים, שהיו קשים, פשוט בהיתי בהם בלי כיוון... אבל למדתי לשלוט בכל הכללים החדשים ממש יפה. אני אמשיך ללמוד מחר, אסיים תכף את הפרק ואתחיל להתקדם. צריך להתאמן בפיתרון ולזכור שכנראה לא יזיינו לי את האמ-אמא בממן. איזה לקחים למדתי? 1. לפתוח סוגריים עם Dist 2. להעיף שלילה מסוגריים עם Morgan 3. לשחק עם סדר של דברים עם Com 4. לבודד פסוקים שימושיים עם Simp 5. להפוך התניות באמצעות Trans 6. לשחק עם Impl. כשיש לי דיסיונקציות עם רישה שלולה∧אימפליקציות שצריך לפתוח 7. לזהות מקרים שרלוונטי להחיל בהם Exp ולבצע את זה 8. לא ממש שיחקנו עם assoc (הזזת סוגריים) או עם equiv (שקילות), אבל אני מבין את הקונספט. מה למדנו מבחינת אסטרטגיה בתכלס? (חוץ מ"לנחש" או "לנחש הפוך"?) 1. לנסות להגיע למושג כללי - איך הגיעו למסקנה? אפילו לכתוב כמה ניחושים לצעד האחד-לפני-אחרון 2. לבודד מההנחות פסוקים שנראים שימושיים להמשך (כאלה שאפשר להחיל עליהם כללים שיחברו שורות, כמו H.S. 3. להפוך את הסדר עם com כמה שצריך כדי שדברים יתחברו 4. שימוש חכם ב-add! אם נתונה אות פסוקית, ויש איפשהו את אותה אות עם OR, הופכים את הפסוקית ל-OR כדי להפעיל HS וכו' 5. הפסוקים לרוב ירמזו מה לעשות להם: קוניונקציה של התניות תדרוש או שנבודד או שנהפוך אותן לדיסיונקציות עם רישה שלולה; מה שמתאים לdist ידרוש dist, וכו'. 6. שדדוקציה טבעית זה מפגר! עקרונית האדם הכי חכם בעולם יכל לשבת על הוכחה אינסוף זמן ולא להגיע אליה, ואני יכולתי להגיע אליה. סתם במקרה. זה לא מתודי והזוי לבחון על זה, אבל שיהיה, זה כן מאפשר לפתח מחשבה באופן מסוים. (היו היום מקרים שכבר ראיתי את ההוכחה, אבל בתנאים שעומדים לרשותי לא יכולתי להוכיח. זה בסדר, זה הכל מחדד את המחשבה ואת השליטה בחוקים.) מחר אני ממשיך ללמוד, לפתור תרגילים, ונראה לאן זה יקח אותנו... מתישהו השבוע אשב עוד פעם על תרגיל 9.

תרגיל ד

גזרו את מסקנותיהם של הטיעונים הבאים, תוך שימוש בכל הכללים שלמדנו עד כה. שימו לב לכך שלעיתים יהיה צורך להפעיל את כלל ההוכחה המותנית, ולעיתים לא יהיה בכך צורך. אתם אלה שתקבעו בכל פעם.

1) 1. p ∴ q→p

  1. p
  2. q C.P.
    1. q∧p 1,2 Con¬.
    2. p∧q 3 Com.
    3. p 4 Simp.
  3. q→p

2) 1. p→(r∧s) ∴ p→s

  1. p→(r∧s)
  2. p C.P.
    1. (r∧s) 1,2 M.P.
    2. (s∧r) 3 Com.
    3. s 4 Simp.
  3. p→s

3) 1. p→q ∴ (p∧r)→q

  1. p→q
  2. p∧r C.P.
    1. p 2 Simp.
    2. q 1,3 M.P.
  3. (p∧r)→q

4) 1. p→¬(q→r) ∴ p→q

  1. p→¬(q→r)
  2. p C.P.
    1. ¬(q→r) 1,2 M.P.
    2. ¬(¬q∨r) 3 Impl.
    3. ¬¬q∧¬r 4 De Morgan.
    4. q∧¬r 5 D.N.
    5. q 6 Simp.
  3. p→q

5) 1. p→(q∨r) 2. ¬q ∴ p→r

  1. p→(q∨r)
  2. ¬q
  3. p C.P.
    1. q∨r 1,2 M.P.
    2. r 2,4 D.S.
  4. p→r

6) 1. p→q 2. p∨q ∴ q

  1. p→q
  2. p∨q
  3. ¬¬p∨q 2 D.N.
  4. ¬¬¬p→q **3 Impl.
  5. ¬p→q 4 D.N.
  6. (p→q)∧(¬p→q) 1,5 Con¬.
  7. (¬p∨q)∧(¬¬p∨q) 6 Impl.
  8. (¬p∨q)∧(p∨q) 7 D.N.
  9. (q∨¬p)∧(q∨p) 8 Com. 1∨. q∨(¬p∧p) 9 Dist.
  10. ¬q C.P.
    1. (¬p∧p) 1∨,11 D.S.
    2. ¬p 12 Simp.
    3. ¬p∨p 13 Add.
    4. q∨q 8,14 C.D.
    5. q 15 Simp.
  11. ¬q→q
  12. ¬¬q∨q 17 Impl.
  13. q∨q 18 D.N. 2∨. q 19 Taut.

7) 1. (p∨q)→((r∨s)→t) ∴ p→((r∧s)→t)

  1. (p∨q)→((r∨s)→t)
  2. p C.P.
    1. p∨q 2 Add.
    2. ((r∨s)→t) 1,3 M.P.
  3. p→((r∧s)→t) 2-4 C.P.

8) 1. (p∨q)→(r→s) 2. (r→(r∧s))→t 3. t→((p∨¬p)→p) ∴ p↔t

  1. (p∨q)→(r→s)
  2. (r→(r∧s))→t
  3. t→((p∨¬p)→p)
  4. t C.P.
    1. ((p∨¬p)→p) 3,5 M.P.
    2. ((¬p∨p)→p) 6 Impl.
    3. ¬(¬p∨p)∨p) 7 Impl. 1∨. (¬¬p∧¬p)∨p 8 Da Morgan.
    4. (p∧¬p)∨p 1∨ D.N.
    5. p∨(p∧¬p) 11 Com.
    6. (p∨p)∧(p∨¬p) 12 Dist.
    7. p∨p 13 Simp.
    8. p 14 Taut.
    9. t→p 4-15 C.P.
  5. ¬t∨((p∨¬p)→p) 3 Impl.
  6. ((p∨¬p)→p)∨¬t 17 Com.
  7. ¬¬((p∨¬p)→p)∨¬t 18 D.N. 2∨. ¬((p∨¬p)→p)→¬t 19 Impl.
  8. (¬p∧¬¬p)→p)→¬t 2∨ Da Morgan.
  9. (¬p∧p)→p)→¬t 21 D.N.
  10. ¬(¬p∧p)∨p)→¬t 22 Impl.
  11. (¬¬p∨¬p)∨p)→¬t 23 Da Morgan.
  12. (p∨¬p)∨p)→¬t 24 D.N.
    1. (p∨(¬p∨p))→¬t 25 Assoc.
  14. (p∨(p∨¬p))→¬t 26 Com.
  15. ((pvp)∨¬p)→¬t 27 Assoc.
  16. (p∨¬p)→¬t 28 Taut. 3∨. ¬¬t→¬(p∨¬p) 29 Trans.
  17. ¬¬t→(¬p∧¬¬p) 3∨ Da Morgan.
  18. t→(¬p∧p) 31 D.N,
  19. ¬(¬p∧p)→¬t 32 Trans.
  20. (¬¬p∨¬p)→¬t 33 Da Morgan.
  21. (p∨¬p)→¬t 34 D.N,
  22. ¬(p∨¬p)∨¬t 35 Impl.
  23. (¬p∧¬¬p)∨¬t 36 Da Morgan.
  24. (¬p∧p)∨¬t 37 D.N.
  25. ¬t C.P.
    1. (¬p∧¬¬p)
    2. ¬p 4∨. ¬t→¬p
  26. ¬¬p→¬¬t
  27. p→t

צריך לסדר את זה כשיהיה לי קצת זמן אבל הצלחתי. א. מציבים t כדי להגיע לאם t אז p ב. מפתחים את האמאמא של פסוק 3 עד שמגיעים ל(p∨¬p)→t ג. מציבים p ומגיעים ל-p→t

עריכה: לא מצליח להגיע ל p→t, צריך להתקדם הלאה. פעם הבאה לנסות להוכיח שקילות עם דיסיונקציה כי Add. עושה חיים קלים.

9) 1. (p→(¬q∧¬r))∧(s→¬(q∨r)) 2. (¬t→p)∧(¬t→s) 3. (t→q)∧(t→r) ∴ q↔r

  1. (p→(¬q∧¬r))∧(s→¬(q∨r))
  2. (¬t→p)∧(¬t→s)
  3. (t→q)∧(t→r)
  4. (t→q) 3 Simp.
  5. (t→r)∧(t→q) 3 Com.
  6. (t→r) 5 Simp.
  7. (¬¬t∨p)∧(¬¬t∨s) 2 Impl.
  8. (t∨p)∧(t∨s) 6 D.N.
  9. (p∨t)∧(s∨t) 7 Com. 1∨. (¬p→t)∧(¬s→t) 8 Impl.
  10. (¬p→t) 9 Simp.
  11. t C.P.
    1. q 4 M.P.
    2. r 6 M.P.
    3. q∧r 13,14 Con¬.
  12. t→(q∧r) 12-16 C.P.
  13. ¬t C.P.
    1. p 2 M.P.
    2. p∨s 18 Add. 2∨. t∨t 9 C.D.
    3. t 2∨ taut
  14. ¬t→t C.P.
  15. t∨t 22 Impl.
  16. t 23 Taut
  17. q∧r 16 M.P.
  18. (q∧r)∨(¬q∧¬r) 25 Add.
  19. q↔r

(p→(¬q∧¬r))∧(s→¬(q∨r)) ¬p∨(¬q∧¬r) (¬s∨¬(q∨r)) ¬s∨(¬q∧¬r) (¬p∨(¬q∧¬r))∧(¬s∨(¬q∧¬r) ((¬q∧¬r)∨¬p)∧((¬q∧¬r)∨¬s) ((¬q∧¬r)∨(¬p∧¬s))

(p→(¬q∧¬r)) (¬(¬q∧¬r)→¬p) (¬¬q∨¬¬r)→¬p (q∨r)→¬p

(s→¬(q∨r)) (s→(¬q∧¬r) ¬(¬q∧¬r)→¬s (¬¬q∨¬¬r)→¬s (q∨r)→¬s

נראה לי שהצלחתי. מציבים t כדי להגיע לאם טי אז קיו אנר אר מציבים נוט טי כדי להגיע לאם נוט טי, אז טי יוצרים את השיט לסדר אח"כ

עריכה: הצלחתייייי

תרגיל ה

_לפניכם שלושה טיעונים. גזרו את המסקנה של כל אחד מהטיעונים הללו על־ידי שימוש בטקטיקת ההוכחה העקיפה:

1) 1. (p∨q)→(r→s) 2. (¬s∨t)→(p∧r) ∴ s

  1. (p∨q)→(r→s)
  2. (¬s∨t)→(p∧r)
  3. ¬s C.P.
    1. ¬s∨t 3 Add.
    2. p∧r 2 M.P.
    3. p 5 simp.
    4. r∧p 5 Com.
    5. r 7 Simp.
    6. p∨q 6 Add. 1∨. r→s 1 M.P.
    7. s 8 M.P.
  4. ¬s→s 3-11 C.P.
  5. ¬¬s∨s 12 Impl.
  6. s∨s 13 D.N.
  7. s 14 Taut.

2) 1. (p→q)∧(r→s) 2. (q∨s)→t 3. ¬t ∴ ¬(p∨r)

  1. (p→q)∧(r→s)
  2. (q∨s)→t
  3. ¬t
  4. ¬¬(p∨r) C.P.
    1. (p∨r) 4 D.N.
    2. q∨s 1,5 C.D.
    3. (¬p∨q)∧(¬r∨s) 1 Impl.
    4. ¬(q∨s) 3 M.T.
    5. ¬q∧¬s 9 Da Morgan 1∨. ¬q 1∨ Simp.
    6. ¬s∧¬q 1∨ Com.
    7. ¬s 12 Simp
    8. (q∨¬p)∧(s∨¬r) 8 Com.
    9. q∨¬p 14 simp
    10. (s∨¬r)∧(q∨¬p) 14 Com.
    11. s∨¬r 15 Simp.
    12. ¬p 1∨,14 D.S.
    13. ¬r 12,16 D.S.
    14. ¬p∧¬r 17,18 Con¬. 2∨. ¬(¬¬p∨¬¬r) 19 Da Morgan
    15. ¬(p∨r) 2∨ D.N.
  5. (p∨r)→¬(p∨r) 4-22 C.P.
  6. ¬(p∨r)∨¬(p∨r) 22 Impl.
  7. ¬(p∨r) 23 Taut.

3) 1. (p∨q)→(r∧s) 2. (r∨t)→(¬p1∧q1) 3. (p1∨r1)→(p∧s1) ∴ ¬p1

  1. (p∨q)→(r∧s)
  2. (r∨t)→(¬p1∧q1)
  3. (p1∨r1)→(p∧s1)
  4. p1 C.P.
    1. p1∨r1 4 Add.
    2. p∧s1 3 3,5 M.P.
    3. p 6 Simp.
    4. p∨q 7 Add.
    5. r∧s 1,8 M.P. 1∨. r 9 Simp.
    6. r∨t 1∨ Add.
    7. ¬p1∧q1 2,11 M.P.
    8. ¬p1 12 Simp.
  5. p1→¬p1 4-13 C.P.
  6. ¬p1∨¬p1 14 Impl.
  7. ¬p1 15 Taut.

למדתי שיעור ממש חשוב על דיסיונקציות! אם השגתי אות פסוקית היא יכולה להפוך לכל דיסיונקציה שבונה אותה. ככה אפשר להתחיל להשיג אותיות בעזרת IFF, להוסיף גם להן דיסיונקציות, וככה עד להצלחה!

תרגיל ו

הוכיחו כי כל אחד מהפסוקים הבאים הוא טאוטולוגיה.

  1. ¬¬(q∧r)→(q∧r)
  2. (p→(¬q∨r))→((p∧q)→r)
  3. (p→q)∨(p∧¬q)
  4. (p→q)↔(¬p∨q)
  5. (p∨¬p)∧¬(p∧¬p)
  6. p→p
  7. (p→q)→(p→(p∧q))
  8. ((p→q)→p)→p
  9. ((p∨q)→r)→(((r∨s)→t)→(p→t)) 1∨. (p→q)→((r∨p)→(q∨r))

1) 1. ¬¬(q∧r) C.P. 2. (q∧r) 1 D.N. 3. ¬¬(q∧r)→(q∧r)

2) 1. (p→(¬q∨r)) C.P. 2. ¬p∨(¬q∨r) 1 Impl. 3. (¬p∨¬q)∨r 2 Assoc. 4. ¬(p∧q)∨r 3 Da Morgan 5. (p∧q)→r 4 Impl. 6. (p→(¬q∨r))→((p∧q)→r)

3) 1. ¬(p→q) C.P. 2. ¬(¬p∨q) 1 Impl. 3. ¬¬p∧¬q 2 Da Morgan 4. p∧¬q 3 D.N. 5. ¬(p→q)→(p∧¬q) 1-4 C.P. 6. ¬¬(p→q)∨(p∧¬q) 5 Impl. 7. (p→q)∨(p∧¬q) 6 D.N.

4) 1. (p→q) C.P. 2. ¬p∨q 1 Impl. 3. (p→q)→(¬p∨q) 1-2 C.P. 4. ¬p∨q C.P. 5. p→q 4 Impl. 6. (¬p∨q)→(p→q) 3-4 C.P. 7. (p→q)↔(¬p∨q) 3,6 Equiv.

5) 1. ¬(p∧¬p) c.p. 2. ¬p∨¬¬p 1 Da Morgan. 3. ¬p∨p 2 D.N. 4. p∨¬p 3 Com. 5. ¬(p∧¬p)→(p∨¬p) 1-4 C.P. 6. ¬¬(p∧¬p)∨(p∨¬p) 7. ¬¬(p∧¬p)∨¬¬(p∨¬p) 6 D.N. 8. ¬(¬(p∧¬p))∧¬(¬(p∨¬p)) 7 DA Morgan 9. ¬(¬p∨¬¬p))∧¬(¬p∧¬¬p)) 8 Da Morgan 10. (¬¬p∧¬¬¬p))∧(¬¬p∨¬¬¬p)) 9 Da Morgan 11. (p∧¬p)∧(p∨¬p) 10 D.N. 12. (p∨¬p) ∧(p∧¬p) 11 Com. 13. (p∨¬p) 12 Simp. 14. ¬(¬p∧p) 13 Da Morgan (+ D.N.) 15. ¬(p∧¬p) 14 Com. 16. ¬(p∧¬p) ∧(p∨¬p) 13,15 Conj, 17. (p∨¬p)∧¬(p∧¬p) 16 Com.

6) 1. p C.P. 2. p∨p 1 Add. 3. p 2 Taut. 4. p→p

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

8)

  1. ¬p C.P.
    1. ¬p∨q 1 Add.
    2. p→q 2 Impl.
    3. ¬p∧(p→q) 1,3 Conj.
    4. ¬(p∨¬(p→q)) 4 De Morgan.
    5. ¬(¬p→¬(p→q)) 5 Impl.
    6. ¬(¬¬(p→q)→¬¬p) 6 Trans.
    7. ¬((p→q)→p) 7 D.N.
  2. ¬p→¬((p→q)→p) 1-8 C.P.
  3. ¬¬((p→q)→p)→¬¬p 9 Trans.
  4. ((p→q)→p)→p 10 D.N.

פה היה צריך להיות די סניקי... לזכור שאפשר להגיע להתניה הפוכה ושלולה שתתוקן עם Trans.

2) ((p∨q)→r)→(((r∨s)→t)→(p→t)) ((p∨q)→r)→(((¬r→s)→t)→(p→t))

  1. ((p∨q)→r) C.P.
    1. (((r∨s)→t) C.P.
      1. p C.P.
        1. p∨q 3 add
        2. r 1,4 M.P.
        3. r∨s 5 add
        4. t 2,6 M.P.
      2. (p→t)
    2. (((r∨s)→t)→(p→t))
  2. ((p∨q)→r)→(((r∨s)→t)→(p→t))

לזכור, כשצריך להוכיח טאוטולוגיה ויש מלא התניות, הכי קל זה להציב את הרישות אחת אחרי השניה ולמצוא דרך להסיק "אחורה" ("קופסה" אחת אחורה) את הסיפה האחרונה. משם הכל מתחבר.

10) 1. (¬q→¬p) C.P. 2. (¬p→r) C.P. 3. ¬q C.P. 4. ¬p 5. r 6. ¬q→r C.P. 7. (¬p→r)→(¬q→r) 8. (¬q→¬p)→((¬p→r)→(¬q→r)) 9. (¬q→¬p)→((¬r→¬¬p)→(¬q→r)) 10. (¬q→¬p)→((¬r→p)→(¬q→r)) 11. (¬q→¬p)→((r∨p)→(¬q→r)) 12. (p→q)→((r∨p)→(q∨r))

טוב, לטאוטולוגיות יש מתודה והיא דווקא די קלה: 1. כותבים בצד את הפסוק 2. פותחים C.P. לכל רישה בפסוק, מהקשר הגדול לקטן (נפספס את כל התת-רישות ברישה המקורית כמובן) 3. בודקים מה אפשר להסיק - אם אי אפשר, בצד, נתחיל להחיל כללים על הפסוק המבוקש 4. נעדכן את ההצבות בהתאם, כדי שנוכל להסיק את מה שצריך 5. זה בעצם תהליך עם שני מוקדים: אנחנו מפתחים את הפסוק כדי לראות לאיזו צורה שלו אפשר להגיע כדי להסיק אותו ממנה - ומעדכנים את ההצבות כדי לקרב את עצמנו לאפשרות לגזור את אחת הצורות. 6. הכל בתרגיל 10 האחרון, לזכור אותו