הבדלים בין גרסאות בדף "88-101 חשיבה מתמטית"

גרסה מ־10:05, 9 במאי 2012

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

אם יש לכם שאלות, הצעות, השגות והערות אחרות, אתם מוזמנים לכתוב אותם בדף השיחה.

תוכן עניינים

1 הצרנה
2 הקשרים הלוגיים
- 2.1 סימוני הקשרים
- 2.2 פסוקים מורכבים
3 טבלאות אמת
- 3.1 חוקי דה-מורגן
4 תחשיב פרדקטים
- 4.1 פרדיקטים
5 כמתים
6 הגדרות
7 הוכחות

הצרנה

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

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

הצרנת פסוקים

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

השלב הראשון בהצרנה הוא זיהוי האטומים, שהם המרכיבים היסודיים של הפסוק. מסמנים כל אטום באות משלו - כאן בחרנו לסמן את האטומים באותיות לטיניות רישיות - 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)
$1<2, 2 * 2=4$ - פסוקים אמיתיים
$1<0$ - פסוק שקרי
$x<0$ - לא פסוק, משום שערכו של x אינו ידוע.

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

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

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

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

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

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

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

P	Q	P $\and$ 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 $\or$ 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	$\,P \rightarrow Q$
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 $\leftrightarrow$ Q
T	T	T
T	F	F
F	T	F
F	F	T

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

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

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

במקום "לא A" כותבים $\ \sim A$ או $\neg A$ .
במקום "A וגם B" כותבים $\ A \wedge B$ .
במקום "A או B" כותבים $\ A \vee B$ .
במקום "אם A אז B" כותבים $\ A \rightarrow B$ ; מותר גם $\ B \leftarrow A$ .
במקום "A אם ורק אם B" כותבים $\ A \leftrightarrow B$ .

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

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

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

פתרון:

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

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

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

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

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

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

כמובן שלא כל רצף של סימנים הוא פסוק. " $\ )A\vee\neg\wedge)BA\neg$ " אינו פסוק. אפשר להגדיר מהו פסוק "באינדוקציה על המבנה":

כל פסוק הוא או אטום, או שיש לו הצורה $\ \neg(x)$ כאשר x הוא פסוק, או הצורה $\ (x)R(y)$ , כאשר R הוא אחד מסימני הקשרים הבינאריים, ו-x,y הם פסוקים.

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

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

טבלאות אמת

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

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

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

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

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

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

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

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

$P\and \neg P$
$(A \and B) \and (\neg B)$
$(A\rightarrow B)\and A \and \neg B$
$(A \leftrightarrow B)\and (A\rightarrow \neg B)\and A$

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

הגדרה. הפסוקים $\ \varphi, \varphi'$ הם שקולים אם הפסוק $\ \varphi \leftrightarrow \varphi'$ הוא טאוטולוגיה. במקרה כזה מסמנים $\ \varphi \equiv \varphi'$ .

אם $A\rightarrow B$ הינו טאוטולוגיה, אזי מסמנים $A\Rightarrow B$ ואומרים כי A הינו תנאי מספיק לB ואילו B הינו תנאי הכרחי לA. אם הם שקולים, אזי A תנאי הכרחי ומספיק לB וכמו כן, B תנאי הכרחי ומספיק לA.

דוגמאות.

$\ \neg\neg A \equiv A$
$\ (A\rightarrow B) \equiv ((\neg A) \vee B)$ .
$\ (A \leftrightarrow B) \equiv ((A \wedge B)\vee((\neg A)\wedge (\neg B)$ .
$\ (A \leftrightarrow B) \equiv (A \rightarrow B) \wedge (B \rightarrow A)$ .
$\ (A \rightarrow B) \equiv ((\neg B) \rightarrow (\neg A))$ .

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

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

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

א. $A \rightarrow (A \and \neg B)$

ב. $(A \rightarrow B) \rightarrow ((A \vee \neg B) \rightarrow (A \and B))$

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

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

$\ \neg (A \vee B) \equiv (\neg A) \wedge (\neg B)$ .
$\ \neg (A \wedge B) \equiv (\neg A) \vee (\neg B)$ .

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

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

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

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

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

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

או

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

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

פרדיקטים

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

דוגמאות.

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

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

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

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

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

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

כמתים

פסוקים עם כמתים

הכמתים, המציינים תחולה של משתנה, הם תוספת חיונית למערך הקשרים שלנו. יש שני כמתים: "לכל", המסומן באות $\ \forall$ (זוהי A הפוכה, קיצור של המלה All); ו"קיים", המסומן באות $\ \exists$ (E הפוכה, קיצור של Exists). כשבונים פסוק עם כמתים, מותר לקחת פסוק קיים (הכולל פרדיקטים, שבהם x הוא משתנה), ולבנות:

$\ \forall x : P(x)$ - מקבל ערך אמת T אם הפסוק $\ P(x)$ מקבל ערך אמת T לכל הצבה של x.
$\ \exists x: P(x)$ - מקבל ערך אמת T אם יש הצבה של x כך שהפסוק $\ P(x)$ מקבל ערך אמת T.

הערה. יש דרכים רבות לכתוב פסוקים כגון אלו. מקובל למשל $\ \forall x P(x)$ או $\ (\forall x) P(x)$ . כל הסגנונות חוקיים, בתנאי שהפסוק ניתן לקריאה באופן חד-משמעי.

דוגמא. את הפסוק "אין מספר גדול ביותר" אפשר להצרין באופן פשטני, כך: $\ \neg \exists x: L(x)$ , כאשר $\ L(x)$ הוא הפרדיקט "x הוא מספר גדול ביותר". הצרנה מעט יותר מתוחכמת תגדיר את הפרדיקט $\ P(x,y)$ שפירושו "x<y", ותצרין ל- $\ \forall x: \exists y: P(x,y)$ , כלומר, לכל מספר יש מספר הגדול ממנו.

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

דוגמא. נצרין את הטענה הבאה:

לכל משוואה ריבועית $ax^2+bx+c=0$ כך ש- $b^2-4ac \geq 0$ יש לפחות פתרון אחד.

$\forall a \forall b \forall c [(b^2-4ac \geq 0)\rightarrow (\exists x (ax^2+bx+c=0))]$

תרגיל. הצרינו את הטענה הבאה:

לכל משוואה ריבועית $ax^2+bx+c=0$ כך ש- $b^2-4ac = 0$ קיים בדיוק פתרון אחד.

תרגיל

הצרינו את הטענות הבאות:

למספר שלילי אין שורש ריבועי

תשובה: $\forall x (x<0 \rightarrow \forall y(y^2 \neq x))$

למספר חיובי יש שורש חיובי ושורש זה אינו יחיד

תשובה: $\forall x (x>0 \rightarrow (\exists y(y^2=x) \and \exists z((z \neq y)\and (z^2=x)))$

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

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

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

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

כדי להוכיח שהפסוק $\ \forall x : P(x)$ אמיתי, יש להראות שהטענה P נכונה לכל ערך אפשרי של x.
כדי להוכיח שהפסוק $\ \exists x : P(x)$ אמיתי, יש למצוא ערך של x שעבורו הטענה נכונה ("דוגמא").
כדי להוכיח שהפסוק $\ \forall x : P(x)$ שקרי, יש למצוא ערך של x שעבורו הטענה אינה נכונה ("דוגמא נגדית").
כדי להוכיח שהפסוק $\ \exists x : P(x)$ שקרי, יש להראות שהטענה P אינה נכונה לכל ערך אפשרי של x.

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

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

$\ \forall x P(x) \implies \exists x P(x)$ .
$\ \forall z: P(z) \rightarrow \forall x,y: P(x^2+y^2)$ .
$\ \exists z: P(z) \rightarrow \exists x,y: P(x^2+y^2)$ .
$\ (\forall x: P(x) \wedge \forall x: Q(x)) \rightarrow \forall x: (P(x) \wedge Q(x))$ .
$\ \forall x: (P(x) \wedge Q(x)) \rightarrow (\forall x: P(x) \wedge \forall x: Q(x))$ .
$\ (\exists x: P(x) \wedge \exists x: Q(x)) \rightarrow \exists x: (P(x) \wedge Q(x))$ .
$\ \exists x: (P(x) \wedge Q(x)) \rightarrow (\exists x: P(x) \wedge \exists x: Q(x))$ .

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

$\ (\forall x: P(x) \rightarrow Q(x)) \rightarrow (\forall x: P(x) \rightarrow \forall x: Q(x))$ .

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

$\ (\forall x: P(x)) \leftrightarrow A$ (השמש זורחת אם ורק אם כל התרנגולים קוראים),
$\ (P(c) \rightarrow A) \wedge (A \rightarrow \forall x: P(x))$ (כשהתרנגול קוקי קורא השמש זורחת, וכשהשמש זורחת כל התרנגולים קוראים).
האם הפסוק $\ (\forall x: P(x)) \leftrightarrow A$ שקול לפסוק $\ \forall x: (P(x) \leftrightarrow A)$ (כל תרנגול, בנפרד, קורא אם ורק אם השמש זורחת)?

משתנים ותחולתם

אנו מגיעים לנקודה חשובה ביותר הנוגעת לשמות המשתנים. לכל כמת יש אזור תחולה. אם נכתוב למשל $\ \forall x : (P(x) \rightarrow Q(x)) \rightarrow \exists y : P(y)$ , אזור התחולה של הכמת הראשון הוא תת-הפסוק $\ P(x) \rightarrow Q(x)$ , ואזור התחולה של הכמת השני הוא ההופעה השניה. בתוך אזור התחולה הזה, אין כל חשיבות לשם המשתנה - אין שום הבדל בין "לכל נורה x יש מתג y כך ש-y מפעיל את x" (הצרן את הפסוק הזה), לבין "לכל נורה z יש מתג y כך ש-y מפעיל את z": השני מתקבל מהחלפת המשתנה x במשתנה z. לעומת זאת, הפסוק "לכל נורה x יש מתג y כך ש-y מפעיל את z" הוא בעל משמעות שונה (יש לו "משתנה חופשי", z, שההצבה בו תקבע את ערך האמת); הצבה לא זהירה ושגויה משנה את משמעות הפסוק.

נתבונן בפרדיקט בן שני משתנים, $\ P(x,y)$ (למשל x אוהב את y). ערך האמת שלו תלוי בהצבה של x ו-y. נשווה זאת לפסוק $\ \forall x : P(x,y)$ (כל x אוהב את y). בפסוק זה אי אפשר להציב את x: הפסוק למעשה אומר "כולם אוהבים את y", והתפקיד של x הוא פורמלי לחלוטין - לסמן את המשתנה העובר על כל האפשרויות. הפסוק $\ \forall z : P(z,y)$ שקול לגמרי לקודם. כדי להדגיש זאת, אפשר לכתוב $\ \phi(y) = \forall x: P(x,y)$ , עם המשתנה היחיד y.

שימו לב לתפקיד הרגיש של x בפסוק כזה. אם נכתוב למשל $\ \forall x : P(x,x)$ ("כל אחד אוהב את עצמו"), נקבל פסוק בעל משמעות שונה לחלוטין. אם רוצים להציב ב- $\ \phi$ את x דווקא, מוכרחים להחליף לפני כן את המשתנה. לא נכתוב $\ \phi(x) = \forall x: P(x,x)$ , אלא $\ \phi(x) = \forall z: P(z,x)$ .

נתבונן בדוגמא נוספת. אם ידועה תכונה Q הנכונה לכל x ולכל y, כותבים $\ \forall x : \forall y : Q(x,y)$ (ולפעמים, בקיצור, $\ \forall x,y: Q(x,y)$ ). מכיוון שהטענה נכונה לכל x ולכל y, אפשר להציב בה ערכים בכל דרך שנרצה - כמובן שלכל x ו-y מתקיים $\ Q(x,y)$ , אבל גם $\ Q(y,x)$ או $\ Q(x,x)$ .

לעומת זאת, הטענה $\ \exists x,y: Q(x,y)$ אומרת שקיימים x,y המקיימים את התכונה (מישהו נשך מישהו אחר במרפק). אנחנו לא יכולים לבחור את x,y - וגם לא להניח שיש קשר מסויים ביניהם. בפרט, לא נובע מההנחה ש- $\ \exists x: Q(x,x)$ (מישהו נשך את עצמו במרפק).

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

להלן דוגמא נוספת. נניח ש-a,b מספרים שלמים. אומרים ש-d הוא מחלק משותף מקסימלי אם הוא מחלק את a ו-b, ומתחלק בכל מחלק משותף שלהם. כלומר, אם d מחלק משותף מקסימלי, אז לכל n כך ש-n|a,b, מתקיים n|d. מה שגוי בגרסה "מכיוון ש-d מחלק משותף מקסימלי של a,b, אם יש n כך ש-n|a,b אז יש n כך ש-n|d", הלקוחה גם היא מבחינה של סטודנט?

דוגמא נוספת: הפתרון הכללי למשוואה דיפרנציאלית מסויימת הוא הפונקציה $\ y(x) = e^x+C$ כאשר C הוא קבוע (אין צורך לדעת מהי משוואה דיפרנציאלית כדי להצרין את הטענה הזו: קיים, מן הסתם, פרדיקט P המקבל ערך אמת T רק על פונקציות הפותרות את המשוואה, ואם כך הפסוק קובע ש"לכל y, אם $\ P(y)$ אז קיים C כך ש- $\ y = e^x + C$ "). קושיה שהעלה סטודנט: האם נכון לומר שהפתרון הכללי לאותה משוואה הוא $\ y(x) = e^x+2C$ ? ומה אם התהיה היתה לגבי הפתרון $\ y(x) = e^x+1/C$ ?

וריאציות וכימות יחסי

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

$\exists x : (P(x) \wedge \forall y : (P(y) \rightarrow x=y))$ -- "קיים x המקיים את התכונה P, ובנוסף, כל y המקיים את התכונה P שווה ל-x". כלומר: "קיים x יחיד המקיים את התכונה P". לפעמים מקצרים את הפסוק הזה וכותבים $\ \exists! x: P(x)$ . אפשר לראות בצירוף " $\ \exists !$ " כמת שלישי, למרות שכאמור לעיל ניתן להגדיר אותו באמצעות שני הכמתים האחרים (בנוכחות פרדיקט השוויון).

לפעמים רוצים לומר שיש אינסוף מספרים המקיימים תכונה מסויימת. אפשר לעשות זאת כך:

$\ \forall n : \exists x : ((x>n) \wedge P(x))$ : "לכל n יש x גדול ממנו המקיים את התכונה". אם היה רק מספר סופי של מספרים המקיימים את התכונה המדוברת, אז הפסוק היה שקרי משום שאפשר היה לבחור בתור n את המספר הגדול ביותר.

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

$\ \forall x>0: \exists y>0: y<x$ - "לכל מספר חיובי x יש מספר חיובי y הקטן ממנו", כלומר "אין מספר חיובי קטן ביותר", בתור קיצור לכתיבה המלאה $\ \forall x: ((x>0) \rightarrow (\exists y: ((y>0) \wedge (y<x))))$ - "לכל מספר x, אם הוא חיובי, אז קיים מספר y שהוא חיובי וקטן מ-x".

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

הצרן את הטענה "a הוא חסם מלעיל של A" (אם ברצונך להתייחס לאיברים מהקבוצה A, אפשר להשתמש בכמתים באופן $\forall a\in A, \exists a\in A$ )

הגדרה: חסם עליון הוא חסם מלעיל, הקטן מכל חסם מלעיל אחר.

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

a הוא חסם עליון של הקבוצה A אם מתקיים: $(\forall b \in A : b<a)\and (\forall c: \forall b \in A: (b<c)\rightarrow c<a)$

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

תרגיל.

באחד התרגילים הקודמים היית אמור לאשר שהפסוק $\ \forall x P(x) \implies \exists x P(x)$ הוא אמיתי, אם הכמתים מתייחסים לקבוצת המספרים השלמים. מצא מרחב אוניברסלי לכמתים שעבורו הפסוק אינו אמיתי (חשוב על הפסוק "כל פיל מעופף יודע קרוא וכתוב; מכאן שיש פיל מעופף היודע קרוא וכתוב").

יש טענות שאפשר לנסח באופן ישיר, אבל קל יותר לנסח באופן יחסי: תרגיל. נניח שהיכרות היא פרדיקט סימטרי P בשני משתנים (כלומר, $\ \forall x,y: P(x,y) \leftrightarrow P(y,x)$ ).

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

פתרון חלקי. הפתרון הישיר הוא מהצורה $\ \forall x_1,x_2,x_3,x_4,x_5,x_6: P(x_1,x_2,x_3,x_4,x_5,x_6)$ כאשר P הוא פסוק ארוך מאד בן ששה משתנים, שאין בו כמתים. יעיל יותר לפתור כך: $\ x_1,\dots,x_6$ שונים, וקיימים y,z,u מתוך הערכים $\ x_1,\dots,x_6$ , המקיימים תנאי מסויים.

בשלב זה קשה לכתוב "קיימים y,z,u מתוך" קבוצה מסויימת; כדי לעשות זאת היטב יש ללמוד מעט תורת הקבוצות.

שלילת כמתים

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

הפעולה האחרונה ב- $\ \forall x: ((x<y) \rightarrow (x<0))$ ("לכל x, אם x קטן מ-y אז x שלילי") היא הכמת הכולל על x; לעומת זאת הפעולה האחרונה ב- $\ (\forall x: (x<y)) \rightarrow (y<0))$ ("אם כל x הוא קטן מ-y, אז y שלילי") היא הקשר "אם-אז".

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

"לא כל תפוח הוא צהוב" שקול לכך ש"קיים תפוח שאינו צהוב".
"לא קיים תפוח צהוב" שקול לכך ש"כל תפוח אינו צהוב".

אכן, לכל פרדיקט P,

$\ \neg \forall x: P(x) \equiv \exists x: \neg P(x)$ , וכך גם
$\ \neg \exists x: P(x) \equiv \forall x: \neg P(x)$ .

זו הזדמנות לשוב ולעיין בדרכים להוכיח ולהפריך טענות מכומתות שהובאו בראש אחד הסעיפים הקודמים. שימו לב שאת הטענות $\ \neg \exists x: P(x)$ ו- $\ \neg \exists x: P(x)$ מוכיחים למעשה באותה דרך (מראים ש*לכל* x, הטענה P אינה מתקיימת), וגם את $\ \neg \forall x: P(x)$ , ו- $\ \exists x: \neg P(x)$ מוכיחים באותה דרך (מראים ש*קיים* x שעבורו P אינה נכונה).

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

$\ \exists x: P(x) \equiv \neg \forall x: \neg P(x)$ ("קיים סוס שחור" = "אין זה נכון שכל הסוסים אינם שחורים").

באופן הזה אפשר להחליף כל מופע של הכמת "קיים" במופע אחד של הכמת "לכל"; כמובן, גם ההיפך אפשרי:

$\ \forall x: P(x) \equiv \neg \exists x: \neg P(x)$ ("כל הסוסים שחורים" = "אין אף סוס שאינו שחור").

בפועל, שני הכמתים נמצאים בשימוש מתמטי תמידי.

תרגיל.

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

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

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

על מה מכמתים

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

דוגמא. הפסוק $\ (\exists x: x=x) \wedge (\forall x,y: x=y)$ מקבל ערך אמת אם במרחב הכימות יש בדיוק ערך אחד. תרגיל. כתוב פסוק שיקבל ערך אמת רק אם מרחב הכימות הוא בן שני ערכים. תרגיל. כתוב פסוק שיקבל ערך אמת רק אם מרחב הכימות הוא בן שלושה ערכים.

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

הבעיה היא שעד כה הרשינו לכתוב $\ \forall x_1,x_2,x_3$ בתור קיצור ל- $\ \forall x_1 \forall x_2 \forall x_3$ , ובקלות אפשר לנחש למה הכוונה גם בביטוי כמו $\ \forall x_1,\dots,x_{100}$ (למרות שלא נעים לכתוב אותו במפורש). אבל איננו יכולים לכתוב $\ \exists n: \forall x_1,\dots,x_n: Q(x_1,\dots,x_n)$ (זה אינו קיצור של שום דבר). כשנרכוש נסיון מסויים בתורת הקבוצות נראה שאפשר לעקוף את הבעיה הזו די בקלות (הרעיון הוא שאפשר לכמת על אובייקט אחד - פונקציה המוגדרת על המספרים הטבעיים - במקום על מספר לא ידוע של אובייקטים). מאידך, כימות של פונקציה (או אובייקטים דומים לזה) הוא דבר מסובך בפני עצמו: הוא גורם שהפסוק כבר לא יהיה שייך ל"שפה מסדר ראשון". על כך - בקורס בלוגיקה מתמטית, ולא כאן.

ניתן דוגמא נוספת שבה נחוץ לכמת על משתנים שמספרם אינו ידוע מראש. תרגיל. אחת הדרכים להגדיר את המבנה הקומבינטורי החשוב גרף היא לחשוב עליו כעל פרדיקט סימטרי P בשני משתנים (את הסימטריה הגדרנו קודם לכן). גרפים אפשר לצייר, על-ידי מתיחת קשת בין שני קודקודים x,y בדיוק כאשר הפרדיקט $\ P(x,y)$ מקבל ערך אמת T.

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

תרגיל. אומרים שקבוצת וקטורים A היא תלויה לינארית אם יש בה אברים $\ v_1,...,v_n$ , כך שקיימים קבועים $\,a_1,...,a_n$ שלא כולם אפס, כך ש- $a_1v_1+...+a_nv_n=0$ .

תרגיל. כתובת את שלילת הטענה הבאה: לכל $a\in A$ קיים $b \in B$ כך ש $b\notin A \setminus \{a\}$ וגם הקבוצה $(A\setminus\{a\})\cup \{b\}$ בלתי תלויה לינארית.

פתרון: קיים $a\in A$ כך שלכל $b \in B$ מתקיים $b\in A \setminus \{a\}$ או $(A\setminus\{a\})\cup \{b\}$ תלויה לינארית.

הגדרות

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

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

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

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

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

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

המבנה של הגדרות

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

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

מתאים/לא-מתאים

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

משולש הוא מצולע שיש לו שלושה קודקודים; או

מצולע יקרא משולש אם יש לו שלושה קודקודים.

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

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

הגדרה מאפיינת

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

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

המספר היחיד a שעבורו הנגזרת של הפונקציה

\ a^x

שווה לעצמה, נקרא בסיס הלוגריתמים הטבעי.

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

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

יהי a משולש. המעגל החוסם של a הוא המעגל היחיד העובר דרך שלושת הקודקודים של a.

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

\ B(x,y)

- שמקבל ערך אמת T אם ורק אם y מהווה מעגל חוסם של x. מכיוון ש-

\ \forall x \exists ! y: B(x,y)

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

תרגיל. החליטו לאיזה סוג שייכות ההגדרות הבאות:

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

המושג המוגדר

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

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

משתנים המופיעים בהגדרה

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

תרגיל: מספר x הוא דו-ריבועי אם קיימים y,z כך ש- $\ x=y^2+z^2$ . נניח ש-x,y הם מספרים דו-ריבועיים. נסה להוכיח שהמכפלה xy היא דו-ריבועית. זהירות עם שמות המשתנים!

הוכחות

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

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

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

מודוס פוננס

הוכחה פורמלית של פסוק P היא רצף של פסוקים $\ P_1,\dots,P_n$ שכל אחד מהם הוא או אקסיומה, או שאפשר לגזור אותו באופן פורמלי מפסוקים קודמים: אם $\ P_k$ אינו אקסיומה, צריכים להיות קיימים $\ i,j<k$ כך ש- $\ P_k = P_i \rightarrow P_j$ .

הגזירה מתבססת כאן על הכלל הלוגי היסודי הנקרא מודוס פוננס: מ- $\ P\rightarrow Q$ ו- $P$ אפשר לגזור (כלומר להסיק את) $Q$ .

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

שימו לב. מהטענה $\ P \rightarrow Q$ לא נובע P, ולא נובע Q, אלא רק שאם P אז Q. תנו דוגמא מפורשת לכך.

תרגיל. נניח שהמשפט הבא הוא אמיתי: "כאשר אני בכושר אני מסוגל לרוץ 10 קילומטר".

נניח עוד כי "כעת איני בכושר" האם אני מסוגל לרוץ 10 קילומטר? אם לא, הוכח (באמצעות הצרנה).
נניח שאיני מסוגל לרוץ 10 קילומטר, האם אני בכושר? הוכח.
נניח שאני מסוגל לרוץ 10 קילומטר, האם אני בכושר? הוכח.

הוכחה בדרך השלילה

הוכחה בדרך השלילה נבנית על הטאוטולוגיה הפשוטה $A \equiv (\neg A \rightarrow F)$ . לכן, כאשר אנו מעוניינים להוכיח בדרך השלילה, אנו מניחים את השלילה של הטענה שלנו וגוזרים ממנה סתירה.

דוגמא:

רוצים להוכיח שיש אינסוף מספרים ראשוניים. נניח בשלילה שיש רק מספר סופי של ראשוניים $p_1,...,p_n$ ; אז המספר $p_1\cdot p_2 \cdots p_n + 1$ אינו מתחלק באף מספר ראשוני, ולכן הוא מוכרח להיות ראשוני; אבל הוא גדול מכל מספר ראשוני, וזו סתירה. (הוכחה זו נמצאת בספרו בן ה-2300 שנה של אוקלידס, "יסודות").
רוצים להוכיח ששורש 2 אינו מספר רציונלי (כלומר שבר בעל מונה ומכנה שלמים). נניח בשלילה ששורש שתיים הוא רציונלי. אז קיים שבר מצומצם $\frac{p}{q}$ כך ש $\frac{p^2}{q^2}=2$ . לכן $p^2=2q^2$ לכן $p$ זוגי ולכן הוא מהצורה $2p'$ ולכן מתקיים $2p'^2=q^2$ ולכן $q$ זוגי בסתירה לכך שהשבר היה מצומצם.
נוכיח שאין מספר רציונלי חיובי מינימלי. נניח בשלילה ש $q$ הינו המספר הרציונאלי הקטן ביותר הגדול מאפס. אזי $0<\frac{q}{2}<q$ הוא מספר רציונאלי, בסתירה להנחת המינימליות.

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

"בלי הגבלת הכלליות"

דוגמא. בין המספרים השלמים מוגדרת פעולת כפל, ומוגדר יחס של חלוקה: $\ a|b \leftrightarrow \exists x: b=ax$ . מספר p, שאינו אפס ואינו מחלק את 1, הוא ראשוני אם $\ \forall a,b: p | ab \rightarrow (p|a \vee p|b)$ . מספר p, שאינו אפס ואינו מחלק את 1, הוא אי-פריק אם $\ p=ab \implies (a|1 \wedge b|1)$ . נוכיח שכל מספר ראשוני הוא אי-פריק: יהי p מספר ראשוני. כדי להוכיח שהוא אי-פריק, עלינו להראות שאם p=ab אז a|1 או b|1. נניח, אם כך, ש- p=ab. מכיוון ש- ab=p*1, p|ab ומכיוון ש-p ראשוני, בלי הגבלת הכלליות, אפשר להניח ש- p|a. אבל אז קיים x כך ש- a=px=abx, ומכיוון ש- $\ a\neq 0$ (אחרת p=0), אפשר לצמצם ולקבל bx=1, ומכאן b|1.

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

הוכחת טענות מכומתות

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

כדי להוכיח טענה מהסוג $\ \forall x: P(x)$ , על המוכיח להראות את אמיתות הטענה $\ P(x)$ , וזאת לכל x *שבחר היריב*. היריב עשוי לבחור x שעבורו הוכחת הטענה קשה יותר. למוכיח אסור לבחור את x בעצמו, משום שהוא צריך להוכיח את הטענה לכל x.
כדי להוכיח טענה מהסוג $\ \exists x: P(x)$ , המוכיח צריך להראות את אמיתות הטענה $\ P(x)$ עבור x כלשהו. הדרך הקלה והבטוחה ביותר לעשות זאת היא *להצביע* על x שעבורו הטענה נכונה; זוהי הוכחה קונסטרוקטיבית. יש גם הוכחות לא קונסטרוקטיביות, אבל בשלבי הלימודים הראשונים תתקלו בהן רק לעתים רחוקות.

בדרך כלל המשחק כולל יותר משלב אחד. למשל, כדי להוכיח "לכל x חיובי קיים y חיובי הקטן ממנו", עלינו לאפשר ליריב לבחור x כרצונו; אחר-כך עלינו להראות שקיים y הקטן מן ה-x הזה, וזאת נעשה על-ידי בחירת y מתאים (למשל: $\ y = x/2$ ). אפשר לכתוב זאת כך:

עלינו להוכיח שלכל $\ 0<x$ יש $\ 0<y<x$ . יהי $\ x>0$ (היריב בוחר x *כרצונו*). נבחר $\ y = x/2$ , ואז $\ 0<y=x/2<x$ (כאן אנו בודקים שעבור y שבחרנו, הטענה אכן מתקיימת).

להלן דוגמא דומה, ושגויה בתכלית:

רוצים להוכיח שלכל n שלם קיים m (שלם) כך ש- $\ n^3-n=3m$ . יהי n מספר שלם. נבחר m כך שמתקיים $\ n^3-n=3m$ -- מה שהיה להוכיח.

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

נזכיר שהספריה L מוצלחת אם יש בה אגף S כך שלכל נושא t יש באגף מדף s, כך שכל ספר x ב-s עוסק בנושא t; הגדרה זו כוללת ארבעה כמתים - ובמתמטיקה יש לא מעט מושגים יסודיים שהגדרתם היא ברמת המורכבות הזו לפחות. כדי להוכיח שספריה נתונה היא מוצלחת, עלינו להצביע על האגף המוצלח; לתת ליריב לבחור נושא; לבחור את המדף, ולהראות שכל ספר על המדף הזה אכן עוסק בנושא הדרוש. תרגיל. תאר את מהלך המשחק המוכיח שספריה מסויימת אינה מוצלחת.

סדר הפעולות במשחק חשוב ביותר. לאחר שבחרנו את האגף S, היריב עשוי לבחור $\ t$ התלוי ב-S; ואז נוכל בתורנו לבחור את המדף כפונקציה של t ושל $\ S$ (אבל לא של x, שאינו מוגדר בכלל בשלב הזה!).

להלן כמה טכניקות הוכחה שכיחות.

"מספיק להוכיח ש-": לפעמים הדרך הקצרה ביותר להוכיח טענה מסויימת היא הוכחת טענה חזקה יותר. זהו שימוש ישיר במודוס פוננס: במקום להוכיח את Q, אנו מוכיחים את P, כאשר הטענה $\ P\rightarrow Q$ ידועה מראש. למשל, כדי להוכיח "קיים מספר ראשוני הגדול מ- $\ 10^{4300}$ ", מספיק להוכיח שקיימים אינסוף ראשוניים.

תרגילים.

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

דוגמא. לפני המאפיה עומדים בתור אינסוף אנשים - ראשון, שני, שלישי וכן הלאה. האם אפשר לסמן אינסוף אנשים, שגובהם אינו עולה, או אינסוף אנשים שגובהם אינו יורד?

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

הפרכה

הפרכה של טענה אינה אלא הוכחה שהטענה אינה נכונה.

הפרכה על-ידי דוגמא נגדית: כדי להפריך את הטענה $\ \forall x: P(x)$ , יש להראות שקיים x שעבורו הטענה $\ P(x)$ אינה נכונה. גם כאן, הדרך השכיחה ביותר היא להצביע על ערך מסויים של x שעבורו הטענה אינה נכונה.
מאידך, כדי להפריך את הטענה $\ \exists x: P(x)$ , יש *להוכיח* שלכל x, הטענה $\ P(x)$ אינה נכונה.

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

הוכח או הפרך: שאלה כמו "הוכח או הפרך - אם p ראשוני אז הוא אי-זוגי" שואלת למעשה "נכון לא נכון - אם p ראשוני אז הוא אי-זוגי", וגם רומזת מה יש לעשות בשני המקרים: אם הטענה נכונה, יש לספק לה הוכחה, ואם היא לא נכונה, יש להפריך אותה, כמעט תמיד באמצעות דוגמא נגדית ("טענה זו אינה נכונה משום ש-p=2 הוא ראשוני אבל אינו אי-זוגי"). פעמים רבות הטענה היא מהצורה "לכל a, מתקיים $\ Q(a)$ ". דוגמא שבה הטענה מתקיימת אינה יכולה לבוא במקום הוכחה, משום שהטענה היא ש- $\ Q(a)$ לכל a ולא רק עבור a נחמדים במיוחד; מצד שני, כדי להפריך טענה כזו, אין שום צורך להראות שהיא נכשלת לכל a; מספיק למצוא a מסויים שעבורו היא נכשלת. כמובן, אם $\ Q(a)$ נכונה לפעמים ושגויה לפעמים, אז הטענה "לכל a מתקיים $\ Q(a)$ " שגויה (ולא "שגויה לפעמים!").

שגיאות נפוצות

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

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

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

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

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

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

@@ שורה 651: / שורה 651: @@
 * הפעלת תנאי מספיק כאילו היה הכרחי: אם הוא יודע אלגברה לינארית, סימן שהוא חכם. הוא אינו יודע אלגברה לינארית, ומכאן שאינו חכם.
 * רוצים להוכיח שכל הסוסים שחורים. רוזיננטה הוא סוס. הבה נוכיח שהוא שחור.
-* קריאה סלקטיבית: כשהפסוק הלוגי נעשה ארוך ומסובך (אם לכל x קיים y כך ש..., אז ...), יש נטיה לשלוף קטע ממנו ולהתייחס אליו בלבד. זיכרו שמספריים אינם אופרטור חוקי בלוגיקה.
+* קריאה סלקטיבית: כשהפסוק הלוגי נעשה ארוך ומסובך (אם לכל x קיים y כך ש..., אז ...), יש נטיה לשלוף קטע ממנו ולהתייחס אליו בלבד. זיכרו שגזירה במספריים אינה אופרטור חוקי בלוגיקה.