88-101 חשיבה מתמטית

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

הכרת טיעונים

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

טיעון לוגי אינו תקף אם ורק אם כל ההנחות אמיתיות אולם המסקנה שקרית.

דוגמא:

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

תרגיל

פרק את הטקסט הבא לטיעונים; טענות, ומסקנות:

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

פתרון

טיעון 1:

1. עונש הבא בסוף לא יכול להיות למטרת תיקון.

מסקנה:

• עונש מהאל הוא למטרת נקמה בלבד.

טיעון 2:

1. עונש הבא מהאל הוא למטרת נקמה בלבד.

• המסקנה - האל לא סולח.

ערך אמת

ערך אמת הוא אחת משתי האפשרויות - אמת או שקר, שמסמנים לשם הקיצור 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$- לא פסוק

פסוקים וקשרים

וגם

וגם הוא קשר לוגי: אפשר לומר משפטים כמו "התפוח הזה אדום, וגם הצלחת ירוקה", שההצרנה שלהם היא במבנה "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.

לא

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

או

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

P	Q	P $\or$ Q
T	T	T
T	F	T
F	T	T
F	F	F

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

אם-אז

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

P	Q	P $\rightarrow$ Q
T	T	T
T	F	F
F	T	T
F	F	T

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

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

• אם n מספר זוגי אזי קיים k כך ש 2k=n. עבור 3 הטענה השנייה אינה נכונה, אבל הטענה הכללית עדיין נכונה מכיוון שהטענה "3 הינו מספר זוגי" הינה שקרית.

תרגיל.

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

על טענה מהצורה "אם P אז Q" שבה ערך האמת של P הוא F, אומרים שהיא נכונה באופן ריק.

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

אם ורק אם

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

נסכם: הפסוקים "אם 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$.

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

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

דוגמא. אם אדם הוא מאושר אם ורק אם הוא לומד דברים חדשים, אז אדם שאינו לומד דברים חדשים אינו מאושר. (שמצרינים ל"אם (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$ (זוהי בדיוק הטענה לפי מותר לחלק למקרים)

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

חשוב גם להכיר סתירות בסיסיות:

• $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)$.

משפט

כל פסוק לוגי שקול להצבת האטומים $\ A_i$ ושלילתם $\ \neg A_i$, בפסוק שבו מופיעים רק הקשרים "או" או "וגם" (מספיק אחד מהם).

• $A \rightarrow B\equiv \neg A \or B$
• $A\or B \equiv \neg (\neg A \and \neg B)$

הצרנה

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

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

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

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

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

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

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

דוגמא נוספת:

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

תרגיל

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

תרגיל

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

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

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

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

תרגיל

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

תרגיל

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

"תקבל טיפ אלא אם: 1.תגיש את האוכל קר ובאיחור. 2. האוכל לא טעים ולא בררת איתי לגבי טעמו

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

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

פתרון:

P - המלצר קיבל טיפ

H - האוכל הגיע חם

O - האוכל הגיע בזמן

K - האוכל הגיע טעים

B - המלצר בירר לגבי טעם האוכל

D - המלצר נתן קינוח חינם

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

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

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

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

או

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

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

פרדיקטים

בלוגיקה מתמטית, פרדיקט הוא פונקציה המקבלת משתנה או כמה משתנים, ומחזירה ערך אמת (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) = Y(x) \rightarrow M(x,x)$ ("אם x צהוב, אז הוא אמא של עצמו") תלוי בערך המשתנה: בדוגמא הזו, אם x הוא אדם צהוב, הפסוק מקבל את הערך F, ואם x הוא אדם שאינו צהוב, ערך האמת הוא T.

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

כמתים

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

הכמתים, המציינים תחולה של משתנה, הם תוספת חיונית למערך הקשרים שלנו. יש שני כמתים: "לכל", המסומן באות $\ \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.

דוגמא. את הפסוק "אין מספר גדול ביותר" אפשר להצרין באופן פשטני, כך: $\ \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) \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)$ (מישהו נשך את עצמו במרפק).

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

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

• $\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".

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

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

הגדרה: חסם עליון הינו חסם המלעיל הקטן ביותר מבין חסמי המלעיל.

• הצרן את המושג חסם עליון

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

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

תרגיל.

• באחד התרגילים הקודמים היית אמור לאשר שהפסוק $\ \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)$.

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

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

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

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

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

תרגיל. סדרה היא התאמה של מספר ממשי לכל מספר טבעי: $\ a_1,a_2,a_3,\cdots$. מספר ממשי L הוא גבול של הסדרה, אם לכל מספר חיובי שנבחר, יש מקום בסדרה שממנו והלאה מרחק האברים בסדרה מ-L קטן מן המספר האמור. הצרן את הטענות הבאות:

• L הוא גבול של הסדרה $\ a_1,a_2,a_3,\cdots$

$\forall \epsilon >0 : \exists n_{\epsilon}: \forall n> n_{\epsilon}: (|a_n-L|<\epsilon)$

• "0 הוא הגבול של הסדרה $\ 1, 1/2, 1/3, 1/4, \cdots$".

$\forall \epsilon >0 : \exists n_{\epsilon}: \forall n> n_{\epsilon}: (\frac{1}{n}<\epsilon)$

• "לסדרה $\ 1, 1/2, 1/3, 1/4, \cdots$ קיים גבול".

$\exists L: \forall \epsilon >0 : \exists n_{\epsilon}: \forall n> n_{\epsilon}: (|\frac{1}{n}-L|<\epsilon)$

• "L איננו הגבול של הסדרה $\ a_1,a_2,\dots$".

$\exists \epsilon >0: \forall n_{\epsilon}: \exists n>n_{\epsilon}: (|a_n-L|>\epsilon)$

• "לסדרה $\ a_1,a_2,\dots$ לא קיים גבול".

$\forall L: \exists \epsilon >0 :\forall n_{\epsilon} : \exists n> n_{\epsilon}: (|a_n-L| >\epsilon)$

• "אם יש לסדרה $\ a_1,a_2,\dots$ גבול, אז הוא יחיד".

הגדרה: אומרים שקיימים אינסוף מספרים כך שפרדיקט כלשהו מתקיים עליהם אם לכל n כמות המספרים המקיימים את הפרדיקט גדולה מ-n.

תרגיל. הוכח שהטענות הבאות שקולות:

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

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

פתרון

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

• $\forall n\in\mathbb{N}:(\exists m\in\mathbb{N}:2m=n)\rightarrow \exists k\in\mathbb{N}:(k>n \and P(k))$
• $\neg[\exists n\in\mathbb{N}:\forall k\in\mathbb{N}:(k>n \rightarrow \neg P(k))]$
• $\forall n\in\mathbb{N}:\exists k\in\mathbb{N}:(k>n \and P(k))$

הוכחה:

• נוכיח שהטענה השנייה נגררת מהראשונה. נניח בשלילה את שלילת הטענה השנייה. כלומר, נניח ש $\exists n\in\mathbb{N}:\forall k\in\mathbb{N}:(k>n \rightarrow \neg P(k))$

נקצר ברישום, ונוסיף את הפרדיקט $C(n)=\exists m\in\mathbb{N}:2m=n$. נוסיף את העובדה $C(n)\or C(n+1)$ ונקבל

$\exists n\in\mathbb{N}:(C(n)\or C(n+1))\and [\forall k\in\mathbb{N}:(k>n \rightarrow \neg P(k))]$

נשתמש בטאוטולוגיה $(A \or B) \and C \equiv (A \and C) \or (B \and C)$ ונקבל

$\exists n\in\mathbb{N}:(C(n) \and [\forall k\in\mathbb{N}:(k>n \rightarrow \neg P(k))]) \or (C(n+1) \and [\forall k\in\mathbb{N}:(k>n \rightarrow \neg P(k))])$

אבל יחד עם הטענה הראשונה, אנחנו יכולים לגרור את הטענה הבאה:

$\exists n\in\mathbb{N}:(\exists k\in\mathbb{N}:(k>n \and P(k)) \and [\forall k\in\mathbb{N}:(k>n \rightarrow \neg P(k))]) \or \exists k\in\mathbb{N}:(k>n+1 \and P(k)) \and [\forall k\in\mathbb{N}:(k>n \rightarrow \neg P(k))])$

וקל לראות (-: שזו סתירה.

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

(שימו לב לשימוש בטאוטולוגיה $\neg (A\rightarrow B) \Leftrightarrow (A \and \neg B)$)

• הטענה השלישית גוררת את הראשונה בקלות מתוך הטאוטולוגיה $(n \in\mathbb{N} \and C(n))\rightarrow n \in\mathbb{N}$

תרגיל. הפונקציה $\ f : C \rightarrow \mathbb{R}$ רציפה בנקודה x אם לכל $\ \epsilon>0$, קיים $\ \delta>0$ כך שאם $\ |x-y|<\delta$ (עבור y בקטע) אז $\ |f(x)-f(y)|<\epsilon$. הפונקציה רציפה בקטע C אם היא רציפה בכל הנקודות x הנמצאות בקטע. הצרן את הטענות הבאות:

• הפונקציה $\ f(x) = x^5$ רציפה בקטע [0,1].

$\forall x \in [0,1] : \forall \epsilon >0: \exists \delta >0: (|x-y|<\delta \rightarrow |x^5-y^5|<\epsilon)$

• הפונקציה $\ f(x) = x^5$ אינה רציפה בנקודה x=0.

$\exists \epsilon >0: \forall \delta >0: (|y|<\delta \and |f(y)|> \epsilon)$

• הפונקציה f רציפה בנקודה x אם ורק אם לכל סדרה $\ a_1,a_2,\dots$ המתכנסת ל-x, הערך $\ f(x)$ הוא גבול של הסדרה $\ f(a_1),f(a_2),\dots$.

תרגיל. הפונקציה $\ f : C \rightarrow \mathbb{R}$ רציפה במידה שווה בקטע C אם לכל $\ \epsilon>0$, קיים $\ \delta>0$ כך שלכל x,y בקטע, אם $\ |x-y|<\delta$ אז $\ |f(x)-f(y)|<\epsilon$. הצרן את הטענות הבאות:

• הפונקציה $\ f(x) = x^5$ רציפה במידה שווה בקטע [0,1].
• הפונקציה $\ f(x) = x^5$ אינה רציפה במידה שווה בקטע [0,1].
• אם הפונקציה f רציפה במידה שווה בקטע C, אז היא רציפה בכל נקודה שלו.

תרגיל.

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

על מה מכמתים

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

דוגמא. הפסוק $\ (\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.

תרגיל

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

(דוגמא: (0,1), (1,0) אינם תלויים לינארית.)

הוכח ש$v_1,..,v_n$ תלויים לינארית אם"ם $v_1+v_2,v_1-v_2,v_3,...,v_n$ תלויים לינארית.

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

תרגיל

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

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

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

הוכחות

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

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

מודוס פוננס

הוכחה פורמלית של פסוק 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)$. לכן, כאשר אנו מעוניינים להוכיח בשלילה, אנו מניחים את השלילה של הטענה שלנו וגוזרים ממנה סתירה. מקרה פרטי הוא גזירה של A ואז מקבלים את הביטוי $A \and \neg A \equiv F$.

דוגמא:

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

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

דוגמא. בין המספרים השלמים מוגדרת פעולת כפל, ומוגדר יחס של חלוקה: $\ 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$). אפשר לכתוב זאת כך:

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

נזכיר שהסדרה $\ a_1,a_2,\dots$ מתכנסת לגבול L אם $\ \forall \epsilon >0 \exists N \forall n >N : |a_n-L|<\epsilon$; אכן, ההגדרה של מושג יסודי זה באנליזה כוללת שלושה כמתים. כדי לומר "הסדרה מתכנסת" (=יש מספר L שהוא הגבול שלה) נחוצים ארבעה כמתים. כדי להוכיח שסדרה נתונה מתכנסת, עלינו להצביע על ערכו הנכון של L; לתת ליריב לבחור את $\epsilon$; לבחור N, ולהראות שלכל n>N שיבחר היריב, מתקיים $\ |a_n-L|<\epsilon$. תרגיל. תאר את מהלך המשחק המוכיח שסדרה מסויימת אינה מתכנסת.

סדר הפעולות במשחק חשוב ביותר. לאחר שבחרנו את L, היריב עשוי לבחור $\ \epsilon$ התלוי ב-L; ואז נוכל בתורנו לבחור את N כפונקציה של L ושל $\ \epsilon$ (אבל לא של n, שאינו מוגדר בכלל בשלב הזה!).

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

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

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

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

תרגילים.

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

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

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

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

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

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

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

דוגמאות נוספות

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

פתרון

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

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