הדפסות 6 דדוקציה טבעית

לא להפעיל כללים סתם בחיים. לחשוב מה אני עושה ואז לעשות.

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

קומבואים: דה מורגן ואז impl -- אם שללנו דיסיונקציה ברישה, זה יתן לנו קוניונקציה של פסוקים שלולים בידוד פסוקים: אם יש משהו כמו r→(p∧q) וצריך r→p, אנחנו מגיעים למצב שאפשר להפעיל עליו Dist. לא-a אז a: אם אפשר להגיע ל-NOT-A THEN A אז אפשר להגיע ל-NOTNOT A OR A, שזה בעצם טאוטולוגיה. אם יש הרבה THEN בהוכחה, לעתים קרובות יהיה צריך לשחק עם הסדרים (לשחק עם H.S, IMPL, Trans) ולהגיע לטאוטולוגיה. לא לשכוח D.N כשעוברים מדיסיונקציה להתניה (D.N. לפני IMPL בכיוון ההפוך) לא לשכוח ש-M.T. מאפשר להגיד "אם אלפה אז בטא, ולא-בטא, אז לא אלפה! לא לשכוח כשמוכיחים שקילות: אם צריך להראות ש-a שקול ל-b. אפשר להראות ש: ¬a→¬b ∧ ¬b→¬a זה שקול לצורה הנורמלית של הכלל -- בזכות כלל ה-Trans!!! (באופן כללי, התניה של שלילות שקולה להתניה ההפוכה בחיובי)

אם הוכחנו קוניונקציה, אפשר להוכיח כל דיסיונקציה עם כל אחד מהמרכיבים של הקוניונקציה: אם היה לנו a and b וצריך a or c, פשוט עושים סימפ בשביל לקבל a, ואז עושים add בשביל לקבל a or c

לזכור את השיטה להיפטר מהתניה עם דיסיונקציה או קוניונקציה באחד הצדדים: מסדרים את ההתניה כך ש-Impl ישאיר את הדיסיונקציה/קוניונקציה כולה שלולה, מכניסים את השלילה לתוך הסוגריים של הדיסיונקציה/קוניונקציה עם דה מורגן, מסדרים כך שהדיסיונקציה/קוניונקציה תהיה הסיפה של הדיסיונקציה הגדולה (שקיבלנו מ-Imp), מפעילים Dist כדי להפריד את איברי הדיסיונקציה/קוניונקציה, מוציאים עם Simp את חלק הקוניונקציה הגדולה שהתקבלה שצריכים כדי לחזור להתניה הדרושה עם Impl הפוך.

תמיד לחפש חלקי התניות!!! ו-'בעיקר ב-CP!!! אם מסתובבים לנו "חצים בתוך חצים" - צריך לזכור שהתוצאה של C.P. היא גם חץ. אז תמיד לבדוק אם יש התאמות של חלקי דיסיונקציות - אבל בעיקר לזכור שאם הן אחת בתוך השניה, יש סיכוי טוב שתוצאה של C.P. אחד (התניה) תתן לנו את התוצאה של המשך ההתניה (החץ שבתוך החץ.)

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

תרגילים שלא הצלחתי/דילוג לסוף - 1. פרק 6, תרגיל ג, סעיף ג-7 2. פרק 6, תרגיל ג, סעיף ג-10 3. פרק 6, תרגיל ד, סעיף 8

כללי ההיסק

• נלמד 9 כללים, ועוד 1 בהמשך. בסה"כ 10 כללים.

מודוס פוננס (Modus Ponens) - אבריבציה M.P.

• בהינתן פסוק תנאי בשורה מסוימת, ובהינתן הרישה של אותו פסוק תנאי בשורה אחרת, אפשר לגזור את הסיפה של פסוק התנאי ולכתוב אותה בשורה חדשה. α→β α ∴β

מודוס טולנס (Modus Tollens) אבריבציה M.T.

• ההיפוך של מודוס פוננס: בהינתן פסוק תנאי בשורה מסוימת, ובהינתן שלילת הסיפה של אותו פסוק תנאי בשורה אחרת, אפשר לגזור את שלילת הרישה. α→β ¬β ∴¬α

סילוגיזם היפותטי (Hypothetical Syllogism) אבירבציה H.S.

• בגדול, קובע שאם "אם A אז B", ואם "אם B אז C", אפשר לקבוע ש-"אם A אז C"
• "מאפשר לנו לגזור פסוק תנאי כמסקנה משני פסוקי תנאי המופיעים בשורות קודמות במהלך ההיסק, ובתנאי שהסיפה של הראשון זהה לרישה של השני. פסוק התנאי החדש שנגזור יורכב מהרישה של פסוק התנאי הראשון ומהסיפה של פסוק התנאי השני." α→β β→γ ∴α→γ

סילוגיזם דיסיונקטיבי (Disjunctive Syllogism) אבריבציה D.S.

• בהינתן פסוק דיסיונקטיבי בשורה מסוימת, ושלילת הדיסיונקט הראשון בדיסיונקציה בשורה אחרת, אפשר לגזור את הדיסיונקט השני בשורה חדשה. α∨β ¬α ∴β

דילמה בונה (Constructive Dilemma) אבריבציה C.D.

• בהינתן קוניונקציה של פסוקי תנאי בשורה מסוימת, ודיסיונקציה המורכבת מהרישות של פסוקי התנאי הללו בשורה אחרת, אפשר לגזור דיסיונקציה המורכבת מהסיפות של אותם פסוקי תנאי. (α→β)∧(γ→δ) α∨γ ∴β∨δ

דילמה הורסת (Destructive Dilemma) אבריבציה D.D.

• זה בעצם הפוך מהדילמה הבונה...
• בהינתן קוניונקציה של פסוקי תנאי בשורה מסוימת, ובהינתן דיסיונקציה של שלילת הסיפות של אותם פסוקי תנאי, אפשר לגזור דיסיונקציה המורכבת משלילת הרישות של פסוקי התנאי. (α→β)∧(γ→δ) ¬β∨¬δ ∴¬α∨¬γ

סימפליפיקציה (Simplification) אבריבציה Simp.

• בפשטות: קובע שאפשר להפריד קוניונקציות לשתי שורות נפרדות
• הכלל קובע כי בהינתן קוניונקציה בשורה מסוימת, אפשר לגזור את הקוניונקט הראשון בשורה חדשה. α∧β ∴α
• החוברת מדגישה שאי אפשר לגזור כך את הקוניונקט השני - למה??? (כל קוניונקציה ניתן להפוך...)

קוניונקציה (Conjunction) אבירבציה Conj.

• היפוך של הסימפליפיקציה, קובע שאפשר לצרף שורות לכדי קוניונקציה α β ∴α∧β

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

הוספה (Addition) אבריבציה Add.

• זה כלל כלבבי - הוא קובע שאם נתון פסוק, בשורה חדשה ניתן לכתוב את הפסוק בקשר של דיסיונקציה, עם כל פסוק שהוא (זה הגיוני... "אני בן אדם" הופך ל-"או שאני בן אדם או שהירח עשוי מגבינה".) α ∴α∨β

![[Pasted image 20241210184042.png]] (אם ההוכחה דורשת פסוק שלא קיים בהנחות - יש לשקול את כלל ההוספה... )

מתודות לבניית ההוכחה:

• החוברת מציינת שזה הרבה עניין של ניסיון, תמיד אפשר להפעיל את כל הכללים האפשריים עד שנגיע לכיוון הנכון. הגישה מכונה 'ירי באפלה'
• עם זאת, כמו בגאומטריה, חבל להוכיח את כל הדברים, יש להוכיח את הנחוצים למסקנה בלבד.
• גישה נוספת שכבר הבנתי לבד: 'הליכה לאחור'. דגש חשוב להליכה לאחור כשהטיעון הוא צורני: צריך לחפש את חלקי הטיעון שמשרתים את המהלך הסופי (זה שיביא אותנו למסקנה), ואז להפעיל כללים שיעזרו בחילוץ שלהם

כללי חילוף

• עובדים דומה לכללי ההיסק, אבל גם קצת שונה...
• כללי היסק ניתן להחיל רק על הנוסחה בשלמותה (באמת תהיתי אם אפשר להחיל אותם על חלק מהשורה...)
• כללי חילוף ניתן להחיל גם על חלק מהנוסחה/שורה, כל עוד מדובר בנב"ך!
• כללי החילוף הם גם דו-כיווניים, לעומת כללי ההיסק
• ההחלפות מתבצעות בין חלקי פסוקים שהם שקולים מבחינה לוגית, ולכן נסמן אותם באותו אופן שלמדנו לסמן שקילות: ≡

11. שלילה כפולה (Double Negation) אבריבציה: D.N.

• קובע שניתן להחליף בין α ל-ᬬ, ולהיפך α ≡ ¬¬α

12. קומוטטיביות (Commutation) אבריבציה: Com.

• קובע שאפשר להחליף את סדר הקוניונקטים או הדיסיונקטים בקוניוקציה/דיסיונקציה (למדנו את זה כבר בהקשר של פונקציות אמת) α∨β ≡ β∨α α∧β ≡ β∧α

13. אסוציואטיביות (Association) אבריבציה: Assoc.

• מן הרחבה של הקומוטטיביות, קובע שאפשר להזיז את המיקום של הסוגריים בפסוקים עם שני מופעים של קוניונקציה או של דיסיונקציה.
• לשים לב שזה רק אם גם בתוך הסוגריים, יש לנו קוניונקציה או דיסיונקציה!
  • p∧(p∧p) יכול להשתנות ככה ש-P הבודדה מגיעה עם קוניונקציה לאחר הסוגריים, אבל אי אפשר לעשות אותו דבר עם (p→p)∧p, לצורך העניין.

• אפשר גם לשחק עם הסוגרים באופן כזה:

  • ![[Pasted image 20241212194756.png]]
  • (כלומר, בעצם, אפשר גם לנתק קוניונקטים מהסוגריים שלהם ולהעביר לסוגריים אחרות... כל עוד משני הצדדים יש קוניונקציה )

  α∨(β∨γ) ≡ (α∨β)∨γ α∧(β∧γ) ≡ (α∧β)∧γ

• דרך קלה לזכור את החוקים של זה: אם הקשר הראשי והמשני, שניהם דיסיונקציה/קוניונקציה - אפשר; אם זה אחרת - אי-אפשר

14. תיאורמות דה-מורגן (De Morgan's Theorems) - אבריבציה?

• נוסח 1 קובע שאפשר להחליף בין קוניונקציה שלולה לדיסיונקציה ששני הדיסיונקטים שלה שלולים, ולהיפך
• זה בעצם אומר: "לא (a ו-b)" שקול ל-"או (לא-a) או (לא-b)" (זה הגיוני...)
• נוסח 2 קובע שאפשר להחליף בין דיסיונקציה שלולה לקוניונקציה ששני הקוניונקטים שלה שלולים ולהפך (כמו מראה של נוסח 1)
• זה בעצם אומר: "לא (או (a) או (b))" שקול -"לא-a ולא-b", גם מסתדר... ¬(α∧β) ≡ ¬α∨¬β ¬(α∨β) ≡ ¬α∧¬β

15. חלוקה (Distribution) אבריבציה: Dist.

• זה הכי מבלבל עד עכשיו: עוסק במקרים שיש לנו קשר ראשי דיסיונקציה וקשר משני קוניונקציה, או להפך (ראשי קוניונקציה משני דיסיונקציה)
• קובע שאפשר "להכפיל בסוגריים" - אם יש לנו "a ו- (b או c)" אפשר להפוך את זה ל-"(a ו-b) או (a ו-c)".
• הצורה ההופכית יותר מבלבלת: אם יש לנו "a או (b ו-c)" - אפשר להפוך את זה ל-"(a או b) ו- (a או c)"
  • בהתחלה לא הבנתי איך זה יכול להיות נכון... זה הרי או a, או גם b וגם c. אבל זה הגיוני: שתי הסוגריים חייבות להתקיים, וה-a היא אותה a... אז אם היא מתקיימת פעם אחת: שלננו גם את b וגם את c. ואם היא לא מתקיימת: (b ו-c) יהיה אמת.

α∧(β∨γ) ≡ (α∧β)∨(α∧γ) α∨(β∧γ) ≡ (α∨β)∧(α∨γ)

• סופר חשוב: הפסוקים שהמשתנים מייצגים בצורה הכללית, לא חייבים להיות שונים! ![[Pasted image 20241212200933.png]] (בתמונה: אפשר ליישם את הכלל עם שתיים או אפילו שלוש הופעות של p)
• באופן כללי, כאשר יש שתי אותיות לטיניות שונות, הכוונה היא שאלה יכולים להיות פסוקים שונים, או אותו הפסוק. כשיש את אותה האות - הכוונה היא שזה אותו הפסוק בהכרח.

16. טרנספוזיציה (Transposition) אבריבציה: Trans.

• קובע שאפשר להחליף אימפליקציה מטריאלית באימפליקציה מטריאלית נוספת, שבה הרישה והסיפה מחליפות מקום, ונוספת להן שלילה. α→β ≡ ¬β→¬α

• כמו כל כללי החילוף - זה עובד לשני הכיוונים

17. אימפליקציה מטריאלית (Material Implication) אבריבציה: Impl.

• קובע שאפשר להפוך כל אימפליקציה לדיסיונקציה ע"י החלפת האופרטור והוספת שלילה לרישה α→β ≡ ¬α∨β
• זה בסה"כ הגיוני מאוד... המשמעות של אימפליקציה לפי הטבלאות היא אכן שאו שהרישה שקרית, או שהסיפה חיובית.

18. שקילות מטיריאלית (Material Equivalence) אבריבציה: Equiv.

• קובע שאפשר להחליף שקילות מטריאלית עם אחת משתי אפשרויות:
• ראשונה: עם קוניונקציה של שני פסוקי התניה בין השקולים, כל אחד בסדר הפוך
  • הכוונה היא: "a שקול ל-b" הופך ל"אם a אז b" וגם "אם b אז a"

• שניה: בדיסיונקציה של שתי קוניונקציות: באחת שני השקולים, ובאחת השלילות של שני השקולים.

  • הכוונה היא: "a שקול ל-b" הופך ל-"a ו-b" או "לא a ולא b".

  α↔β ≡ (α→β)∧(β→α) α↔β ≡ (α∧β)∨(¬α∧¬β)

19. אקספורטציה (Exportation) אבריבציה Exp.

• זה אחד קצת מורכב: קובע שאפשר להחליף פסוק תנאי שהרישה שלו היא קוניונקציה, בפסוק תנאי שהרישה שלו היא הקוניונקט הראשון, והסיפה שלו היא פסוק תנאי של הקוניונקט השני ושל הסיפה המקורית (נשארת אחרונה).
• זה בעצם אומר: "אם (a וגם b) אז c" שקול ל-"אם a אז (אם b אז c)"
• בתכלס הגיוני... במקום ש ההתניה תפעל "באחת" כשגם a וגם b מתקיימים, הבדיקה נעשית בשלבים... אם a, אז נמשיך לאם b, ואם אכן - אז c.

![[Pasted image 20241212202632.png]]

20. טאוטולוגיה (Tautology) אבריבציה: Taut.

• יוצר טאוטולוגיות... קובע שאפשר להחליף פסוק בקוניונקציה שהפסוק הוא שני הקוניונקטים שלה, ואותו כנ"ל עם דיסיונקציה α ≡ α∨α α ≡ α∧α

עוד שני כללים

הוכחה מותנית C.P.

• בטיעונים בשפה הפורמלית, המשמעות היא לעשות דבר כזה:
• בשורה m, נציב הנחה מותנית α
• נפתח את ההנחה, עד שנגיע למסקנה המבוקשת, נקרא לה שורה n ופסוק ꞵ
• בשורה n+1 (לאחר המסקנה המבוקשת), נכתוב α→ꞵ
• נתחום את השורות m-n ב-"קופסה" - המשמעות היא שאנחנו לא יכולים להשתמש בהן להמשך ההוכחה (כי הן הנחות לצורך הטיעון ולאו דווקא אמתיות)

![[Pasted image 20241215124256.png]]

• ברמה הכי בסיסית אנחנו משתמשים ב-C.P. כדי להוכיח פסוק תנאי. אם המסקנה שיש להגיע אליה היא אימפליקציה מטריאלית, זו הרי התוצאה של הפעולה לבסוף, כשסוגרים את "הקופסה".
• איך נגיע באופן הזה להוכחה של דיסיונקציה, קוניונקציה וכו'?
  • התשובה שלי: נגיע להתניה שבאפשרותה להצדיק את הדיסיונקציה. אם למשל צריך להוכיח a∨b, ונתון כבר p. מספיק להשיג מההנחה לצורך הטיעון משהו כמו p→(a∨b)

הנחה בתוך הנחה:

• אפשר להוסיף הנחה מותנית חדשה לפני שנפטרנו מהקודמת
• נשתמש בדוגמה: ![[Pasted image 20241215130203.png]]
• כדי להגיע להתניה במסקנה, באפשרותנו להניח p ולפתח את ההנחה עד שנגיע ל q→s
• גם q→s היא התניה, אז נוכל להניח את q בתוך הקופסה של ההנחה p על מנת להגיע לפסוק s ![[Pasted image 20241215130404.png]]
• החוק להיפטרות מהנחות מרובות הוא "נכנס אחרון - יוצא ראשון", כלומר שניפטר מההנחה q לפני שניפטר מההנחה p, וההנחה q היא למעשה קופסה שמתקיימת בתוך הקופסה של p (ולכן לא יכולה להתקיים מחוץ לה, וחייבת להיסגר לפחות שורה אחת לפניה.)

הוכחה עקיפה (הוכחה על דרך השלילה)

• זה משהו שעשיתי כבר בתרגילים... זה שימוש "מיוחד" בהוכחה המותנית
• מניחים את שלילת המסקנה ומפעילים את הכללים עד שמתקבלת מסקנת הטיעון
• סוגרים את "הקופסה" ומקבלים התניה שהיא בעצם α→α¬ (אם α היא המסקנה המבוקשת)
• משם הדרך להוכחת המסקנה פשוטה: הופכים את ההתניה ל-α∨ᬬ ולאחר מכן ל-α∨α. הופכים את הטאוטולוגיה ל-α וסיימנו.

• התוצאה שהיא מתקבלת שקולה להיגד "אם המסקנה שקרית, אז המסקנה אמתית" בשפה הטבעית

  • המשמעות היא שהפסוק הוא טאוטולוגיה? נראה לי, זה בעצם אומר שהוא נכון בכל מצב.
  • או לא טאוטולוגיה: אבל שגם במצב עניינים שבו הוא F, הוא למעשה T?

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

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

רדוקציה לאבסורד (Redaction ad Absurdum) אבריבציה: R.A.

• הכלל קובע שמפסוק ושלילתו (הקשורים בקוניונקציה) ניתן לגזור כל פסוק. α∧¬α ∴ β

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

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

(תרגיל ה)

הוכחת טאוטולוגיות

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

• טיעון שמסקנתו היא טאוטולוגיה הוא טיעון תקף, ללא קשר להנחות

  • (למעשה, טאוטולוגיות הן סוג מיוחד של טיעונים תקפים: טיעונים חסרי הנחות, או ליתר דיוק שאינם תלויים בהנחות שעשויות להתלוות אליהם.)

• בגלל שאין הנחות, אנחנו נצטרך להשתמש ב-add או בהוכחה מותנית כדי שיהיה עם מה לעבוד.

• נניח שרוצים להוכיח את הטאוטולוגיה (p→(q→p
  1. p (C.P.)
     1. p∨¬q 1 Add.
     2. ¬q∨p 2 Com.
     3. q→p 3 Imp.
  2. p→(q→p) (בעצם בנינו טיעון שמתחיל מהנחה מותנית אחת: p; הראנו שאם p נתונה, הסיפה נובעת בהכרח; סיימנו עם פסוק שהוא נכון ללא תלות בהנחות: p→(q→p))