מבוא ללוגיקה - תחשיב הפסוקים
מבוא ללוגיקה - תחשיב הפסוקים¶
שיעור 2¶
## תקפות היא פונקציה של מבנה בגדול: תקפות היא פונקציה של מבנה
שיעור 3 - דוגמא נגדית¶
שיעור 4¶
קשרים פסוקיים¶
טענות מורכבות לעיתים קרובות מהמבנה האריסטוטלי, שלפיה ישנם קשרים פסוקיים.
טענות עם קשרים פסוקיים יוצרות פסוקים מורכבים, שמורכבים מפסוקים אטומיים ומקשרים.
אותנו מטרידים במיוחד קשרי 'פונקציית אמת' - ערך האמת של הטענה המתקבלת תלוי בערך האמת של הפסוק(ים) האטומי(ם).
הקשרים הם מבנים עם 'חללים', שאם ממלאים אותם בפסוק תתקבל טענה שלמה. למשל:
"רחל מאמינה ש_"
ישנם חמישה סוגים של קשרים פסוקיים:
- קוניונקציה (Conjunction) - & - יורד גשם ויש עננים (R&C)
- דיסיונקציה (Disjunction) - v - יורד גשם או שיש עננים (RvC)
לשים לב להבדל בין 'או' כולל (vel) ל- 'או' מוציא (aut)
בדיסיונקציה (v) הכוונה היא ל- או כולל.
- שלילה - ~ - זה לא נכון שיורד גשם (R~)
ערך האמת של השלילה הופכי לערך האמת של הטענה (הגיוני)
- גרירה - <-|-> - אם יורד גשם אז יש עננים (R->C)
R הוא הרישא (precedent?) וC הוא הסיפא (?antecedent)
בקשרי גרירה, אנחנו מניחים אמת כברירת מחדל (F וT הם T - אם ירד גשם אז אסגור את החלון, לא ירד גשם, סגרתי את החלון - אמת).
כלומר, הגרירה שקרית אם ורק אם הרישא אמיתית והסיפא שקרית.
- גרירה דו כיוונית - <-> - יש לי לב אם ורק אם יש לי כליות (H<->K)
כלומר, הגרירה אמיתית רק אם לשני הפסוקים יש את אותו ערך האמת.
אנחנו לא נשתמש לרוב בקשר זה.
נוסחה בנויה כהלכה¶
ניתן לחשוב על שפת תחשיב הפסוקים כמו שפת תכנות - יש לה דקדוק (syntax) מדויק וברור.
1. כל אות אנגלית גדולה היא נב"כ
2. אם **נ** היא נב"כ, אז גם **נ~** היא נב"כ
3. אם **נ1** ו**נ2** שתיהן נב"כ, אז גם (**נ1** & **נ2**) היא נב"כ
4. אם **נ1** ו**נ2** שתיהן נב"כ, אז גם (**נ1** v **נ2**) היא נב"כ
5. אם **נ1** ו**נ2** שתיהן נב"כ, אז גם (**נ1** -> **נ2**) היא נב"כ
6. אם **נ1** ו**נ2** שתיהן נב"כ, אז גם (**נ1** <-> **נ2**) היא נב"כ
7. ***שום דבר אחר אינו נב"כ***
שיעור 5¶
מהי אפשרות¶
אפשרות היא מקרה, כלומר צירופים אפשריים של ערכי אמת לפסוקים אטומיים.
למשל, אם ברשותי 2 פסוקים אטומיים, אז ישנם 4 מקרים - אמת ושקר לכל פסוק. אם ברשותי 3 פסוקים, ישנם 8 מקרים.
אם בטיעון יש n פסוקים אטומיים, אז ישנם 2^n^ מקרים.
עברנו על 3 מודולים (מבני טיעון):
- מודוס טולנס - תקף
- מודוס פוננס(?) - לא תקף
- מודוס מורונס - לא תקף
- מודוס טולנדו פוננס (סילוגיזם דיסיונקטיבי)
שווין לוגי (אקווילנטיות לוגית)¶
ניתן להגיד על שתי נוסחאות שהן שוות אם ורק אם ערך האמת של שתיהן שווה (בכל המקרים).
ר' דוגמאות במצגת.
סוגי נוסחאות¶
- טאוטולוגית (תמיד אמת)
P v ~P - סתירה (תמיד שקר)
P & ~P - קונטינגנטית (מלשון Contingent) - לפעמים אמיתית ולפעמים שקרית.
P > ~P
שיעור 6 - תרגומים משפה טבעית¶
השאיפה בתרגום משפה טבעית היא כזו:
ביטויים בשפה טבעיות -> ביטויים בשפה פורמאלית -> ביצוע פעולות בשפה פורמאלית (הוכחות תקיפות וכו') -> ביטויים בשפה פורמאלית -> ביטויים בשפה טבעית
בגדול, לקחת לרלורים בעברית, להצרין להם את הצורה, לעבד אותם ולירוק אותם חריפים בהרבה, ובעברית.
כפל משמעות¶
כדאי להיזהר ממכשולים כמו משפטים דו משמעיים (שחר ותומר נשואים - אחד לשני\ה? לשני אנשים שונים?), או מוציא (הילארי או דונאלד ת\ינצח בבחירות - ניתן לפרק ללפחות אחד\ת ת\ינצח ולא שניהם ינצחו).
רק אם¶
צריך לשים לב גם לרק אם - שאינו שקול לאם:
יש לי חיית מחמד אם יש לי חתול (T)
יש לי חיית מחמד רק אם יש לי חתול (F)
רק¶
רק מתפקד כשלילה כפולה. למשל:
רק עובדים מורשים
משמעותו
אם אתה לא עובד
אז אסור לך להיכנס
אם ורק אם¶
יש שתי דרכים להתמודד עם אם ורק אם: - גרירה דו כיוונית (<->) - פירוק מורכב:
יש לי לב אם ורק אם יש לי כליות
(K>H) & (K>~H~)
אלא אם¶
את אלא אם אפשר להפוך לאם לא:
אני לא אקבל ציון עובר אלא אם אלמד
אם לא אלמד אז לא אקבל ציון עובר
שיעור 7 - תרגומים משפה טבעית (המשך)¶
תנאי הכרחי¶
אם לא אגש לכל הבחנים
אז
לא אעבור את הקורס
A > ~E~
תנאי מספיק¶
כדי לעבור את הקורס
מספיק
לקבל 60
A > E
שלילה של תנאי הכרחי¶
לגשת לשני הבחנים
זה לא הכרחי
בשביל לעבור את הקורס
(A > ~E~)~
שלילה של תנאי מספיק¶
לגשת לשני הבחנים
זה לא מספיק
לקבל 100 בקורס
(A > E)~
שילובים¶
תנאי הכרחי ומספיק¶
A > ~E~
&
A > E
תנאי הכרחי אבל לא מספיק¶
A > ~E~
&
(A > E)~
תנאי מספיק אבל לא הכרחי¶
A > E
&
(A > ~E~)~
תנאי לא הכרחי ולא מספיק¶
(A > ~E~)~
&
(A > E)~
ש"ב - לבדוק את ערך האמת של החבר הזה, ומה זה אומר
פסוקים מורכבים¶
- נזהה את הפסוקים הפשוטים ונסמן באותיות גדולות.
- נזהה את כל הקשרים. אילו מהם הם קשרים סטנרטיים? אילו מהם אינם?
- נשכתב את המשפט כאשר הפסוקים הפשוטים יוחלפו ע"י הקישורים שלהם. נשמור על המבנה התחבירי.
- נזהה את הקשר הראשי.
- אם הקשר הראשי סטנדרטי, נחליף אותו בלוגוגרמה מתאימה; אם לא, נמצא פרפרזה ונחזור ל4.
- נעבוד על הנוסחאות המרכיבות כתוצאה מ5 (עבור 4)
- נחליף את הנוסחאות המרכיבות בחזרה לתוך הנוסחה הכוללת.
- נתרגם את הנוסחה הכוללת בחזרה לשפה טבעית, ונשווה אותה עם המשפט המקורי.
שיעור 8¶
רענון¶
אנחנו יודעים מהם: - משפט - יחידה בשפה - פסוק - משפט בעל ערך אמת - טענה - ערך אמת - אמת\שקר - טיעון - אוסף של פסוקים שאחד המסקנה והשאר ההנחות - טיעון נכון עובדתית - טיעון שכל הנחותיו אמיתיות - תקף - טיעון שאם כל הנחותיו אמיתיות אז בהכרח מסקנתו אמיתית - נאות - טיעון תקף ונכות עובדתית - קשר פסוקי - ביטוי המחבר בין מספר פסוקים אטומיים - קשר ערך אמת - קשרים שערכיהם תלויים בערך הפסוקים האטומיים
וגם: - הכלל היסודי של הלוגיקה - תקפות היא פונקציה של מבנה - שיטת הדוגמא הנגדית להוכחת אי תקפות - תרגום משפה טבעית לתחשיב הפסוקים - להוכיח תקפות או אי תקפות באמצעות טבלאות אמת
המלצה: שאלת ההיבטים הנשגבים של האלוהים (ר' מצגת)
טיפ ^מההמלצה^: היצמד לשיטה הפילוסופית - Present, Explain, Evaluate (PEE arguments). הצג, הסבר והערך^?^ טיעון.
שיעור 9 - הוכחות בתחשיב הפסוקים¶
נפטרים מטבלאות האמת¶
טבלאות אמת זה לא כיף. במקום לבדוק את כל המקרים, כדאי לבדוק רק את המקרים בהם כל ההנחות האמיתיות (שכן אם המסקנה שקרית, הטיעון אינו תקף).
נתחיל במבנים (מודוס-ים) שאנחנו יודעים שהם תקפים - ונשליך אותם על הטיעון שלנו.
P
P>Q
Q>R
R>S
/S
למשל - נניח שP אמיתי ונפעיל מבנה תקף:
P
P>Q
/Q
משמע, אם P אמיתי, Q אמיתי. נמשיך באותה הצורה:
Q>R
Q (סעיף קודם)
R
משמע, אפ Q אמיתי, אז R אמיתי. וככה הלאה.
המהלך הזה הוא הוכחה שהטיעון הזה תקף - במקום ללכת על דרך השלילה (אין מצב שבו ההנחות אמיתיות והמסקנה שקרית), הולכים על החיוב.
ר' את דרך הרישום (נוטציה) בספר של Hardegree
בגדול, המבנה הוא כזה:
1. P Pr(emise)
2. P > Q Pr
3. Q > R Pr
4. R > S Pr
5. SHOW: S
-^-^נקודות חינם עד כאן^-^-
6. Q 1,2,MP
7. R 3,6,MP
8. S 4,7,MP
(בסוף: Box & Cancel)
מומלץ:
- מיד לאחר העתק ההנחות, לוודא שהעתקנו נכון ולא פספסנו שלילה נבזית כזו או אחרת
- לכתוב את הSHOW
הישמר: המודוסים צורניים לחלוטין. גם אם יש להם אותו ערך אמת, ביטויים תקפים אחרים אינם מופעים של המודוסים
למשל:
~P > ~Q
Q
/P
אינו מופע של מודוס תולנס.
חוקי ההיקש¶
כאן מתחילים לבהות בדף הנוסחאות. הידד!
בשפה יש (בערך) חמישה קשרים. ל(כמעט) כל קשר יש - חוק OUT איך לפרק נוסחה עם הקשר הזה - חוק IN איך לבנות נוסחה עם הקשר הזה
&O¶
אם הקוניוקציה אמיתית, מותר להסיק את הפסוק הראשון:
A & B
/A
או את הפסוק השני:
A & B
/B
הרישום נראה ככה:
A & B Pr
SHOW: A
A &O
הכלל הזה חל רק על שורה שלמה:
A > (B & C)
לא ניתן להחיל על ביטוי זה את הכלל!
(A > B) & (C & D)
ניתן להחיל על ביטוי זה את הכלל.
&I¶
אם יש לך נוסחא, ויש לך נוסחא, מותר לך להקיש את הקוניוקנציה הראשונה שלהם
A
B
/A & B
ואת השנייה שלהם
A
B
/B & A
Ov¶
אם יש לך דיסיונקציה ויש לך את השלילה של הדיסיונקט הראשון, מותר לך להקיש את הדיסיונקט השני:
A v B
~A
/B
ואם יש שלילה של הדיסיונקט השני, מותר לך להקיש את הדיסיונקט הראשון:
A v B
~B
/A
Iv¶
אם יש לנו נוסחה, אז מותר לנו להקיש את הדיסיונקציה עם כל נוסחא לימינה:
A
/ A v B
או לשמאלה:
A
/ B v A
>O¶
אם יש לך תנאי ויש לך את השלילה שלו, מותר לך להסיק את ההשלכה ^?^
A > C
A
/C
אם יש לך תנאי ויש לך את השלילה של ההשלכה, מוצתר לך להקיש את השלילה של התנאי:
A > C
~C
/A
>I¶
אין. במקומו יש כלל אחר שנדוש בו בהמשך.
שלילה כפולה (DN)¶
אם יש לך נוסחה מותר לך להקיש את שלילתה הכפולה
A
/~~A
ואם יש לך שלילה כפולה, מותר לך להסיק את הנוסחה
~~A
/A
ושוב - הכללים פועלים רק על שורות שלמות
הוכחה ישירה (DD)¶
SHOW: A DD
...
...
...
A
אם הוכחתי פסוק על ידי כך שהגעתי עליו בדיוק כפי שהוא, הרי שהוכחתי הוכחה ישירה. לא את כל הטיעונים ניתן להוכיח בהוכחה ישירה, אך כשכן, דרך זו נוטה להיות הקלה והמהירה ביותר.
שיעור 10¶
גזירה מותנית (CD)¶
SHOW: A>C CD
A As
SHOW: C DD
במשפטי תנאי, יש לנו הזכות להניח באמצעות גזירה מותנית שהרישא אמיתית (Assumption - As). באמצעות הנחה זו ניתן להוכיח את הסיפא בגזירה ישירה. כמו הדוגמא של גרי: אם יש לי חור במיכל הדלק, לא יהיה לי דלק. אם לא יהיה לי דלק, הרכב לא יזוז. לכן, אם נניח שיש לי חור במיכל הדלק, ניתן להוכיח שהרכב לא יזוז.
P > Q Pr
Q > R Pr
SHOW: P > R CD
P As
SHOW: R DD
Q 1,4,>O
R 2,6,>O
בדוגמא הזו, על מנת להוכיח את R (בתנאי P>R), הנחנו (As) שP אמיתי, ומשם הוכחנו הוכחה ישירה שR אמיתי. כלומר, אם P אמיתי, R אמיתי - הטיעון תקף.
גזירה בשלילה (~D)¶
SHOW: ~A ~D
A As
SHOW: X DD
.
.
.
X XI
לשיטה זו קוראים רדוקציה לאבסורד (Reductio ad absurdum). השיטה היא להוכיח שאם מניחים את השלילה של ההוכחה, מתקבלת סתירה (X) - משהו שלא יכול להיות לוגית (למשל: P&~P).
סתירה מראים תמיד בגזירה ישירה (DD)!
שיעור 12¶
גזירה עקיפה (ID)¶
SHOW: A ID
A~ As
SHOW: X DD
.
.
.
X
בשיטה זו, נניח את היפוכה של ההוכחה ונראה קיומה של סתירה.
ההבדל לעומת גזירה בשלילה (~D) היא שבגזירה עקיפה מוסיפים שלילה, ובגזירה בשלילה מסירים שלילה. בנוסף, בגזירה עקיפה ניתן להוכיח כל פסוק - בגזירה שבשלילה רק פסוקים המתחילים בשלילה.
כל דוגמא שניתן להראות בגזירה ישירה, ניתן להראות גם בגזירה עקיפה - אך לא להיפך!
כשID מופעלת על דיסיונקציה, ניתן לכנותה vD. מדובר באותה אסטרטגיה בדיוק - מטרת השם הוא להזכיר.