88-101 חשיבה מתמטית - לוגיקה פסוקית

זהו החלק הראשון של המבוא לחשיבה מתמטית.

הצרנה

אטומים ופסוקים

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

הצרנת פסוקים

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

השלב הראשון בהצרנה הוא זיהוי האטומים, שהם המרכיבים היסודיים של הפסוק. מסמנים כל אטום באות משלו - כאן בחרנו לסמן את האטומים באותיות לטיניות רישיות - A,B,C וכן הלאה.

דוגמא. "אם לא תגמור מהצלחת, יבוא שוטר".

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

"אם לא נכלכל את צעדינו בתבונה, נמצא את עצמנו מול שוקת שבורה".

(אם לא A אז B, כאשר A="נכלכל את צעדינו בתבונה" ו-B="נמצא את עצמנו מול שוקת שבורה").

הדוגמאות יכולות להיות מסובכות בהרבה:

"כאשר אני עייף ורעב אני נעשה עצבני, או שאני הולך לישון; אבל אם אני עצבני ולא עייף, אז אני רעב". (כלומר, עבור האטומים המתאימים A,B,C,D: (אם (A וגם B) אז (C או D)), וגם (אם (C ולא A) אז לא B)).

חוקי המשחק SET: על השולחן מונחים שנים-עשר קלפים, לכל קלף במשחק יש ארבע תכונות: צורה, צבע, מספר ומילוי. על השחקנים למצוא שלשות חוקיות; שלשה חוקית הינה שלשה של קלפים אשר כל תכונה שלהם בנפרד שווה בכולם או שונה בכולם. לכן שלשה הינה חוקית אם (((הצבע של שלושת הקלפים זהה) או (לכל קלף יש צבע אחר)) וגם ((המילוי של שלושת הקלפים זהה) או (לכל קלף יש מילוי אחר))וגם ((המספר של שלושת הקלפים זהה) או (לכל קלף יש מספר אחר)) וגם ((הצורה של שלושת הקלפים זהה) או (לכל קלף יש צורה אחרת))). (כלומר, עבור האטומים המתאימים A,B,C,D,E,F,H,I: שלשה היא חוקית אם ((A או B) וגם (C או D) וגם (E או F) וגם (H או I))).

תרגיל. כתוב את הפסוק המתאר שלשה לא חוקית במשחק SET.

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

"ירד גשם ובכל זאת היה חם בחוץ" ו-
"ירד גשם והיה חם בחוץ"

באותה צורה ("A וגם B"). המשמעות המרומזת ("בדרך כלל A גורר את השלילה של B") נעלמת.

תרגיל. הצרן: למדתי היטב למבחן, ואף על פי כן נכשלתי בו.

דוגמא נוספת:

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

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

ערך אמת

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

שימו לב שערך האמת עשוי להיות T או F; אומרים "לפסוק יש ערך אמת T" או "לפסוק יש ערך אמת F", ולא "לפסוק יש ערך אמת" או "לפסוק יש ערך שקר". (למתחכמים: כתוב כאן - [אומרים ("לפסוק יש ערך אמת T" או "לפסוק יש ערך אמת F"), ולא ("לפסוק יש ערך אמת" או "לפסוק יש ערך שקר")], ולא - [אומרים "לפסוק יש ערך אמת T" או ("לפסוק יש ערך אמת F", ולא "לפסוק יש ערך אמת") או "לפסוק יש ערך שקר"]; תפקידן החיוני של הסוגריים יודגש בהמשך).

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

דוגמא- (פסוקים שיכולים לקבל ערכי אמת: T או F)

"לעיגול אין פינות" (T)
"במשולש שווה שוקיים, חוצה הזוית מאונך לבסיס" (T)
"רווק הינו גבר שאינו נשוי" (F)
[math]\displaystyle{ 1\lt 2, 2 \times 2=4 }[/math] - פסוקים אמיתיים
[math]\displaystyle{ 1\lt 0 }[/math]- פסוק שקרי
[math]\displaystyle{ x\lt 0 }[/math]- לא פסוק, משום שערכו של x אינו ידוע.

תרגיל. נתונים שלושת הפסוקים הבאים: A- הימים חולפים, B- שנה עוברת, C-המנגינה לעולם נשארת.

א. הצרינו את הפסוקים הבאים:

הימים אינם חולפים
הימים חולפים או המנגינה לעולם נשארת
לא נכון שהימים חולפים וששנה עוברת
הימים חולפים, שנה עוברת, אבל המנגינה לעולם נשארת
הימים חולפים אם ורק אם אין זה נכון שאם שנה עוברת אז המנגינה אינה נשארת לעולם.

ב. נתון ש-A אמיתי, B אמיתי, C שקרי. קבעו את ערכי האמת של הפסוקים בסעיף הקודם.

הקשרים הלוגיים

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

1. וגם. אפשר לומר משפטים כמו "התפוח הזה אדום, וגם הצלחת ירוקה", שההצרנה שלהם היא במבנה "A וגם B". אי אפשר לומר "התפוח הזה אדום וגם", משום ש"וגם" הוא קשר בינארי - הוא מחבר שני אטומים. ערך האמת של הפסוק "A וגם B" הוא T, רק כאשר גם A וגם B הם T. בכל מקרה אחר, ערך האמת הוא F.

P	Q	P [math]\displaystyle{ \and }[/math] Q
T	T	T
T	F	F
F	T	F
F	F	F

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

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

3. קשר נוסף הוא או: גם הוא קשר בינארי, המאפשר לבנות את הפסוק "A או B". פסוק כזה מקבל ערך אמת T אם לפחות אחת ההצהרות קיבלה ערך אמת T.

ה"או" המתמטי הוא "או במובן החלש" - "תפוח או בננה" פירושו תפוח, או בננה, או שניהם. בשפה העברית אומרים "או תפוח או בננה" כדי להדגיש שמדובר באפשרות זו או אחרת, אבל לא בשתיהן יחד - זהו "או מוציא", הקרוי בשפות המחשב xor = exclusive or.

P	Q	P [math]\displaystyle{ \or }[/math] Q
T	T	T
T	F	T
F	T	T
F	F	F

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

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

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

P	Q	[math]\displaystyle{ \,P \rightarrow Q }[/math]
T	T	T
T	F	F
F	T	T
F	F	T

נראה עוד כמה דוגמאות.

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

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

אם n אינו זוגי אז קיימים מספרים עוקבים שסכומם הוא n. הפסוק הזה הוא בעל ערך אמת, למרות שלא קיימים שני מספרים עוקבים שסכומם הוא 4; הרי עבור n=4 גם ההנחה "n אינו זוגי" אינה מתקיימת, וממילא כשלון המסקנה אינו משפיע על ערך האמת.

תרגיל. בדוק שאם ערך האמת של B הוא T, אז ערך האמת של "אם A אז B" הוא תמיד T. קבע מתי ערך האמת של "אם A אז B" הוא T, אם ידוע שערך האמת של B הוא F.

תרגיל. אמא מבטיחה לילד: אם תקבל 100 במבחן, נקנה לך כלבלב. הוא קיבל במבחן 97, ואיננו יודעים האם קיבל כלבלב או לא. האם קיימה האם את ההבטחה?

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

5. אם ורק אם.

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

נסכם: הפסוקים "אם A אז B", "B אם A" ו"A רק אם B" אומרים אותו הדבר.

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

P	Q	P [math]\displaystyle{ \leftrightarrow }[/math] Q
T	T	T
T	F	F
F	T	F
F	F	T

דוגמא. משולש הוא ישר זווית ושווה שוקיים אם ורק אם יש לו שתי זוויות של 45 מעלות.

סימוני הקשרים

לקשרים הסטנדרטיים יש גם סימון סטנדרטי, שיש להכיר ולזכור.

במקום "לא A" כותבים [math]\displaystyle{ \ \sim A }[/math] או [math]\displaystyle{ \neg A }[/math].
במקום "A וגם B" כותבים [math]\displaystyle{ \ A \wedge B }[/math].
במקום "A או B" כותבים [math]\displaystyle{ \ A \vee B }[/math].
במקום "אם A אז B" כותבים [math]\displaystyle{ \ A \rightarrow B }[/math]; מותר גם [math]\displaystyle{ \ B \leftarrow A }[/math].
במקום "A אם ורק אם B" כותבים [math]\displaystyle{ \ A \leftrightarrow B }[/math].

תרגיל. * לוגיקן הלך לאכול במסעדת גורמה. הוא ניגש אל המלצר בתחילת הארוחה ואומר לו:

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

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

פתרון:

P - המלצר קיבל טיפ
H - האוכל הגיע חם
O - האוכל הגיע בזמן
K - האוכל הגיע טעים
B - המזגן פעל
D - המלצר נתן קינוח חינם

התנאי לקבלת טיפ: [math]\displaystyle{ \neg \left[(\neg H\and \neg O)\or (\neg K\and \neg B)\right] \or (\neg H\and K \and \neg O \and D ) \leftrightarrow P }[/math]

פסוקים מורכבים

את הקשרים שפגשנו (לא, וגם, או, אם-אז, אם-ורק-אם) אפשר להפעיל לא רק על אטומים, אלא גם על פסוקים.

דוגמא. אם אדם הוא מאושר אם ורק אם הוא לומד דברים חדשים, אז אדם שאינו לומד דברים חדשים אינו מאושר. (שמצרינים ל"אם (A אם ורק אם B), אז (אם לא B, אז לא A)").

פסוק הוא רצף של תווים, שכל אחד מהם הוא או אחד מסימני האטומים (מקובל להניח שעומדת לרשותנו אספקה אינסופית של סימנים לאטומים), או אחד מסימני הקשרים, או אחד הסימנים המיוחדים "(" ו")" שתפקידם להבטיח קריאה חד-משמעית של הפסוק. לדוגמא, הפסוק [math]\displaystyle{ \ A \wedge B \vee C }[/math] אינו ניתן לקריאה באופן ברור: אין לדעת האם הכוונה היא ל-[math]\displaystyle{ \ (A \wedge B) \vee C }[/math] או ל-[math]\displaystyle{ \ A \wedge (B \vee C) }[/math]. (תרגיל: מצא ערכי אמת של A,B,C שיתנו ערכי אמת שונים לשני הפסוקים האחרונים). הכלל במקרה של ספק הוא פשוט: עדיף לבזבז מאה זוגות סוגריים מיותרים, מאשר להשמיט זוג סוגריים חיוני אחד.

כמובן שלא כל רצף של סימנים הוא פסוק. "[math]\displaystyle{ \ )A\vee\neg\wedge)BA\neg }[/math]" אינו פסוק. אפשר להגדיר מהו פסוק "באינדוקציה על המבנה":

כל פסוק הוא או אטום, או שיש לו הצורה [math]\displaystyle{ \ \neg(x) }[/math] כאשר x הוא פסוק, או הצורה [math]\displaystyle{ \ (x)R(y) }[/math], כאשר R הוא אחד מסימני הקשרים הבינאריים, ו-x,y הם פסוקים.

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

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

טבלאות אמת

טבלת אמת מאפשרת לטפל בפסוק על-ידי בחינת כל האפשרויות לערכי אמת של האטומים המעורבים בו. טכנית, אם בפסוק יש n אטומים, הטבלה מורכבת מ-[math]\displaystyle{ \ 2^n }[/math] שורות, שבכל אחת מהן מקצים אפשרות אחרת לערכי האמת של האטומים. למשל, בטבלת האמת של [math]\displaystyle{ \ \varphi = ((A \vee B) \rightarrow A) \rightarrow (\neg B \vee A) }[/math] יש ארבע שורות, המתאימות לערכי האמת TT, TF, FT, FF עבור האטומים AB. בטבלה יש להוסיף גם את ערך האמת של כל תת-פסוק (במקרה דנן, [math]\displaystyle{ \ A \vee B }[/math] ו- [math]\displaystyle{ \ (A\vee B) \rightarrow A }[/math]), ובסופו של דבר את ערך האמת של הפסוק עצמו.

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

לטאוטולוגיות חשיבות מיוחדת בלוגיקה, משום שהם מבטאות אמת צורנית אוניברסלית, שאינה תלויה בהצבת ערכי האמת. (ראו גם [1]). דוגמא. הפסוק [math]\displaystyle{ \ \varphi }[/math] שהוזכר לעיל הוא טאוטולוגיה. הוא קובע שאם מההנחה "A או B" אפשר להסיק את A, אז A אמיתי או B שקרי.

תרגיל. אם [math]\displaystyle{ \ \psi = \psi(A_1,\dots,A_n) }[/math] הוא פסוק טאוטולוגי התלוי באטומים [math]\displaystyle{ \ A_1,\dots,A_n }[/math], אז כל פסוק המתקבל מהצבה של פסוקים כלשהם [math]\displaystyle{ \ \theta_1,\dots,\theta_n }[/math] במקום האטומים (באופן עקבי), גם הוא טאוטולוגי.

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

[math]\displaystyle{ \ (A \wedge B) \rightarrow A }[/math] (כלומר, אם A וגם B, אז בפרט A);
[math]\displaystyle{ \ A \rightarrow (A \vee B) }[/math] (אם A, אז בוודאי מתקיים A או B);
[math]\displaystyle{ \ A \vee \neg A }[/math] (זהו "כלל השלישי הנמנע": או שהתפוח אדום או שאינו אדום (כמובן, בתנאי שמגדירים היטב מתי תפוח הוא אדום));
[math]\displaystyle{ \ ((A\rightarrow B)\wedge (B\rightarrow C)) \rightarrow (A \rightarrow C) }[/math] (אם מ-A נובע B ומ-B נובע C, אז מ-A נובע C).
[math]\displaystyle{ A\rightarrow (B\rightarrow A) }[/math] (אם התפוח אדום, אזי כל דבר גורר שהוא אדום).
[math]\displaystyle{ \left[ (A\rightarrow B) \and (\neg A \rightarrow B)\right] \leftrightarrow B }[/math] (כדי להוכיח את B, אפשר להוכיח את הפסוק B בהנחה ש-A, ואחר-כך בהנחה של שלילת A: זוהי הוכחה בדרך של חלוקה למקרים, ובלשון התלמוד "ממה נפשך")

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

כדאי להכיר גם כמה סתירות בסיסיות:

[math]\displaystyle{ P\and \neg P }[/math]
[math]\displaystyle{ (A \and B) \and (\neg B) }[/math]
[math]\displaystyle{ (A\rightarrow B)\and A \and \neg B }[/math]
[math]\displaystyle{ (A \leftrightarrow B)\and (A\rightarrow \neg B)\and A }[/math]

הגדרתו של הקשר הלוגי "אם ורק אם" מובילה אותנו להגדרה שימושית:

הגדרה. הפסוקים [math]\displaystyle{ \ \varphi, \varphi' }[/math] הם שקולים אם הפסוק [math]\displaystyle{ \ \varphi \leftrightarrow \varphi' }[/math] הוא טאוטולוגיה. במקרה כזה מסמנים [math]\displaystyle{ \ \varphi \equiv \varphi' }[/math].

אם [math]\displaystyle{ A\rightarrow B }[/math] הינו טאוטולוגיה, אזי מסמנים [math]\displaystyle{ A\Rightarrow B }[/math] ואומרים כי A הינו תנאי מספיק לB ואילו B הינו תנאי הכרחי לA. אם הם שקולים, אזי A תנאי הכרחי ומספיק לB וכמו כן, B תנאי הכרחי ומספיק לA.

דוגמאות.

[math]\displaystyle{ \ \neg\neg A \equiv A }[/math]
[math]\displaystyle{ \ (A\rightarrow B) \equiv ((\neg A) \vee B) }[/math].
[math]\displaystyle{ \ (A \leftrightarrow B) \equiv ((A \wedge B)\vee((\neg A)\wedge (\neg B) }[/math].
[math]\displaystyle{ \ (A \leftrightarrow B) \equiv (A \rightarrow B) \wedge (B \rightarrow A) }[/math].
[math]\displaystyle{ \ (A \rightarrow B) \equiv ((\neg B) \rightarrow (\neg A)) }[/math].

בעזרת הדוגמאות האלו אפשר להוכיח את העובדה הבאה:

משפט. כל פסוק לוגי שקול לפסוק שבו מופיעים רק קשר השלילה והקשרים "או" ו"וגם".

תרגיל. בנה טבלאות אמת לפסוקים הבאים וקבע אילו מהם הם טאוטולוגיה ואילו מהם הם סתירה לוגית (ויתכן שהם לא זה ולא זה...)

א. [math]\displaystyle{ A \rightarrow (A \and \neg B) }[/math]

ב. [math]\displaystyle{ (A \rightarrow B) \rightarrow ((A \vee \neg B) \rightarrow (A \and B)) }[/math]

חוקי דה-מורגן

חשוב לדעת לנסח במדוייק את השלילה של פסוק נתון. הדוגמאות הבסיסיות מסוג זה נקראות כללי דה-מורגן:

[math]\displaystyle{ \ \neg (A \vee B) \equiv (\neg A) \wedge (\neg B) }[/math].
[math]\displaystyle{ \ \neg (A \wedge B) \equiv (\neg A) \vee (\neg B) }[/math].

למשל, כמישהו שואל "האם עבר כאן קו 45 *או* קו 7?", תשובה שלילית פירושה "לא עבר כאן קו 45, *וגם* לא עבר כאן קו 7". אם רוכל מוכר שיקוי פלאים המצמיח שערות *וגם* מרפא שיעול, ורוצים להראות שהוא אינו דובר אמת, מספיק לבדוק שהשיקוי אינו מצמיח שערות, *או* אינו מרפא שיעול.

חוקי דה-מורגן מאפשרים לשפר את המשפט הקודם: משפט. כל פסוק לוגי (באטומים [math]\displaystyle{ \ A_1, \dots,A_n }[/math]) שקול להצבת האטומים [math]\displaystyle{ \ A_i }[/math] ושלילתם [math]\displaystyle{ \ \neg A_i }[/math], בפסוק שבו מופיעים רק הקשרים "או" או "וגם", במבנה כזה: [math]\displaystyle{ \ \psi_1 \vee \cdots \vee \psi_m }[/math], כאשר כל מרכיב הוא מהצורה [math]\displaystyle{ \ \psi_j = B_1 \wedge \cdots \wedge B_n }[/math] וכל אחד מן ה-[math]\displaystyle{ \ B_i }[/math] מייצג את האטום [math]\displaystyle{ \ A_i }[/math] או שלילתו [math]\displaystyle{ \ \neg A_i }[/math].

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

תחשיב פרדקטים

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

לכל מספר יש מספר גדול יותר

או

מישהו כתב את הדפים האלה.

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

פרדיקטים

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

דוגמאות.

כדי לומר "התפוח הזה צהוב", מגדירים פרדיקט [math]\displaystyle{ \ Y(x) }[/math], עם משתנה אחד, המחזיר את הערך T כאשר x צהוב, ואת הערך F בכל מקרה אחר.
כדי לומר "דפנה היא אמא של יובל", אפשר להגדיר פרדיקט [math]\displaystyle{ \ M(x,y) }[/math] המקבל ערך T כאשר x היא אמא של y. יש להציב את דפנה במקום x ואת יובל במקום y.
כדי לומר "2 קטן מ-7", יש להגדיר פרדיקט של סדר, [math]\displaystyle{ \ S(x,y) }[/math], המקבל ערך T כאשר [math]\displaystyle{ \ x\lt y }[/math], ולכתוב [math]\displaystyle{ \ S(2,7) }[/math]. מכיוון שיחס הסדר כבר זכה לשם מוכר, אפשר להשתמש בו ישירות, ולכתוב את הפרדיקט [math]\displaystyle{ \ 2\lt 7 }[/math].

תרגיל. הגדירו פרדיקטים והצבות במשתנים, כך שהפסוק [math]\displaystyle{ \ A(x) \vee (B(x,y) \wedge A(y)) }[/math] יצרין את "אורן או חברתו קארין לומדים לוגיקה".

הפסוקים מהסוג הראשון שפגשנו הורכבו מאטומים המקושרים על-ידי הקשרים הלוגיים. הסוג השני הוא בעל אותו מבנה, אלא שבמקום אטומים מותר להשתמש בפרדיקטים עם משתנים כלשהם. התוצאה, כמו בסוג הראשון, היא פסוק לוגי - אלא שכאן התוצאה תלויה במשתנים. לכן, במקום לסמן את הפסוק באות בודדת, נכתוב [math]\displaystyle{ \ \psi(x) }[/math] או [math]\displaystyle{ \ \varphi(x,y) }[/math].

חשוב להבין שערך האמת של פסוק [math]\displaystyle{ \ \psi(x) }[/math] המערב פרדיקטים, כמו [math]\displaystyle{ \ \psi(x) = Y(x) \rightarrow M(x,x) }[/math] ("אם x צהוב, אז הוא אמא של עצמו") תלוי בערך המשתנה: בדוגמא הזו, אם x הוא אדם צהוב, הפסוק מקבל את הערך F, ואם x הוא אדם שאינו צהוב, ערך האמת הוא T (באופן ריק).

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

לפני שנמשיך לסעיף הבא, שבו נוסיף למבנה הפסוקים סיבוך נוסף, נצטט את המתמטיקאי פול הלמוס ("איך לכתוב מתמטיקה", 1970; מתורגם): "... הסימבוליזם של הלוגיקה הפורמלית חיוני לדיון בלוגיקה של המתמטיקה, אבל בתור אמצעי להעברת רעיונות מאדם לאדם הוא הופך לקוד מסורבל. הכותב נאלץ לקודד בו את המחשבות שלו (אני מסרב להאמין שאדם כלשהו חושב במונחי [math]\displaystyle{ \ \wedge, \vee }[/math] או [math]\displaystyle{ \ \exists }[/math]), והקורא נאלץ לפענח אותו. בשני הכיוונים מדובר בבזבוז זמן. פסוקים פורמליים הם משהו שמכונות יכולות לכתוב, ומעטים מלבד מכונות יכולים לקרוא". איננו לומדים לוגיקה פורמלית כדי שתכתבו בה - השפה הטבעית עדיפה בהרבה, *בתנאי* שמשתמשים בה כראוי, לאור העקרונות של הלוגיקה הפורמלית.

המשיכו לחלק השני.