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

[[לוגיקה]]

מה היא דדוקציה טבעית

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

מודוס פוננס (Modus Ponens)

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

סילוגיזם דיסיונקטיבי (Disjunctive Syllogism)

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

אופן הכתיבה:

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

• לצד כל הנחה שנוסיף, נכתוב "הצדקה": באילו הנחות ובאיזה כלל השתמשנו ![[Pasted image 20241210173946.png]] (1-3 הם הטיעון המקורי, 5 המסקנה המקורית)

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

• השיטה שאנחנו נלמד מתבססת ברובה על העבודה של Irving M. Copi, אמורה להיות די מאוזנת (בין בזבזנות לחסכנות)

(תרגיל א)

כללי ההיסק

• נלמד 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.)

• לפעמים יש טיעונים תקפים שאי אפשר להוכיח באמצעות 19 הכללים שלמדנו
  • למשל:
  • p→q ∴ p→(p∧q)
• בשביל להוכיח פסוק זה, אנחנו נדרשים לכלל נוסף: כלל ההוכחה המותנית

• באמצעות הכלל, אנחנו יכולים להוסיף הנחות לטיעון ולפתח אותן, כל עוד "ניפטר" מההנחות טרם הטיעון יגיע לסופו

• בטיעונים בשפה הטבעית, המשמעות היא לעשות דבר כזה:

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

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

• בטיעונים בשפה הפורמלית, המשמעות היא לעשות דבר כזה:

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

![[Pasted image 20241215124256.png]]

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

דוגמה על שקילות מטריאלית:

![[Pasted image 20241215125050.png]]

![[Pasted image 20241215125025.png]]

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

דוגמה על דיסיונקציה:

![[Pasted image 20241215125621.png]]

![[Pasted image 20241215125908.png]]

• אופן המחשבה:
• כדי להגיע מהתניה לדיסיונקציה הדרושה, נצטרך להגיע ל- p→r¬ ואז להפעיל Impl.
• תמיד מניחים את הרישה של ההתניה הדרושה, ואז מפתחים עד שמגיעים לסיפה הדרושה. (נציב NOT-P וננסה להגיע ל"אם NOT-P אז R")
• נשתמש בהנחה לצורך הטיעון כדי לגזור את הסיפה של (1) (ספציפי להוכחה זו)
• נגזור מהפסוק שהתקבל את הפסוק שדרוש כדי ליצור את ההתניה...
• נשתמש בImpl. ואז ב-D.N. כדי להגיע למסקנה המבוקשת

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

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

(תרגיל ד)

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

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

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

  • המשמעות היא שהפסוק הוא טאוטולוגיה? נראה לי, זה בעצם אומר שהוא נכון בכל מצב.
  • או לא טאוטולוגיה: אבל שגם במצב עניינים שבו הוא 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))

• עוד דוגמה עבור p∨¬p: ![[Pasted image 20241215165225.png]]

• שוב, כרגיל, מניחים את הרישה של ההתניה הדרושה (המסקנה בבירור נובעת מהחלה של הכללים על התניה)

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

• מפה זה רק לסדר קצת

• טאוטולוגיה כמו (p∧¬p)¬, שפחות ברור איך להוכיח, אפשר על דרך ההוכחה העקיפה:

![[Pasted image 20241215165656.png]]

• זה מסובך להוכיח שיט, אבל לזכור את האסטרטגיה: אם יש לנו פסוק תנאי, נניח את הרישה שלו, ונפתח את ההנחה עד שנגיע לסיפה שלו.
• אם מדובר בפסוק אחר, נחשוב איך ניתן להגיע אליו מפסוק התניה...
• גם אם מדובר באוסף של מלא פסוקי תנאי, כמו בדוגמה: ![[Pasted image 20241215165844.png]]

(תרגיל ו)

נספח 1: שלמות ונאותות

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

• אז העלנו טיעון, לפיו שיטת הדדוקציה הטבעית היא שיטה נאותה

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

  • (בעצם, אם עבור קבוצת פסוקים שניתן בשיטה הנידונה להוכיח באמצעותה את α, הפסוקים שכלולים בקבוצה הם הנחות מספיקות להוכחה של α - ללא תוספות חיצוניות)

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

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

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

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