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

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

הצרנה

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

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

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

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

דוגמא נוספת:

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

תרגיל.

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

ערך אמת

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

טבלאות אמת

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

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

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

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

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

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

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

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

דוגמאות.

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

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

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

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

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

משפט. כל פסוק לוגי שקול להצבת האטומים [math]\displaystyle{ \ A_i }[/math] ושלילתם [math]\displaystyle{ \ \neg A_i }[/math], בפסוק שבו מופיעים רק הקשרים "או" ו"וגם".

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

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

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

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

או

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

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

פרדיקטים

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

דוגמאות.

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

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

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

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

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

חידודים לוגיים

((???))

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

כמתים

פסוקים מסדר ראשון

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

• [math]\displaystyle{ \ \forall x : P(x) }[/math] - מקבל ערך אמת T אם הפסוק [math]\displaystyle{ \ P(x) }[/math] מקבל ערך אמת לכל הצבה של x.
• [math]\displaystyle{ \ \exists x: P(x) }[/math] - מקבל ערך אמת T אם יש הצבה של x כך שהפסוק [math]\displaystyle{ \ P(x) }[/math] מקבל ערך אמת.

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

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

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

• הפעולה האחרונה ב- [math]\displaystyle{ \ \forall x: ((x\lt y) \rightarrow (x\lt 0)) }[/math] ("לכל x, אם x קטן מ-y אז x שלילי") היא הכמת הכולל על x; לעומת זאת הפעולה האחרונה ב- [math]\displaystyle{ \ (\forall x: (x\lt y)) \rightarrow (y\lt 0)) }[/math] ("אם כל x הוא קטן מ-y, אז y שלילי") היא הקשר "אם-אז".

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

שקילות

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

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

אנו מגיעים לנקודה חשובה ביותר הנוגעת לשמות המשתנים. לכל כמת יש אזור תחולה. אם נכתוב למשל [math]\displaystyle{ \ \forall x : P(x) \rightarrow \exists y : P(y) }[/math], אזור התחולה של הכמת הראשון הוא ההופעה הראשונה של P, ואזור התחולה של הכמת השני הוא ההופעה השניה. בתוך אזור התחולה הזה, אין כל חשיבות לשם המשתנה - אין שום הבדל בין "לכל נורה x יש מתג y כך ש-y מפעיל את x" (הצרן את הפסוק הזה), לבין "לכל נורה z יש מתג y כך ש-y מפעיל את z". לעומת זאת, הפסוק "לכל נורה x יש מתג y כך ש-y מפעיל את z".

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

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

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

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

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

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

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

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

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

• [math]\displaystyle{ \ \forall n : \exists x : ((x\gt n) \wedge P(x)) }[/math]: "לכל n יש x גדול ממנו המקיים את התכונה". אם היה רק מספר סופי של מספרים המקיימים את התכונה המדוברת, אז הפסוק היה שקרי משום שאפשר היה לבחור בתור n את המספר הגדול ביותר.

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

• [math]\displaystyle{ \ \forall x\gt 0: \exists y\gt 0: y\lt x }[/math] - "לכל מספר חיובי x יש מספר חיובי y הקטן ממנו", כלומר "אין מספר חיובי קטן ביותר", בתור קיצור לכתיבה המלאה [math]\displaystyle{ \ \forall x: ((x\gt 0) \rightarrow (\exists y: ((y\gt 0) \wedge (y\lt x)))) }[/math] - "לכל מספר x, אם הוא חיובי, אז קיים מספר y שהוא חיובי וקטן מ-x".

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

שלילת כמתים

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

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

כלומר, לכל פרדיקט P,

• [math]\displaystyle{ \ \neg \forall x: P(x) \equiv \exists x: \neg P(x) }[/math], וכך גם
• [math]\displaystyle{ \ \neg \exists x: P(x) \equiv \forall x: \neg P(x) }[/math].

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

• [math]\displaystyle{ \ \exists x: P(x) \equiv \neg \forall x: \neg P(x) }[/math] ("קיים סוס שחור" = "אין זה נכון שכל הסוסים אינם שחורים").

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

• [math]\displaystyle{ \ \forall x: P(x) \equiv \neg \exists x: \neg P(x) }[/math] ("כל הסוסים שחורים" = "אין אף סוס שאינו שחור").

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

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

• "0 הוא הגבול של הסדרה [math]\displaystyle{ \ 1, 1/2, 1/3, 1/4, \cdots }[/math]".
• "לסדרה [math]\displaystyle{ \ 1, 1/2, 1/3, 1/4, \cdots }[/math] קיים גבול".
• "L איננו הגבול של הסדרה [math]\displaystyle{ \ a_1,a_2,\dots }[/math]".
• "לסדרה [math]\displaystyle{ \ a_1,a_2,\dots }[/math] לא קיים גבול".
• "אם יש לסדרה [math]\displaystyle{ \ a_1,a_2,\dots }[/math] גבול, אז הוא יחיד".

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

• הפונקציה [math]\displaystyle{ \ f(x) = x^5 }[/math] רציפה בקטע [0,1].
• הפונקציה [math]\displaystyle{ \ f(x) = x^5 }[/math] אינה רציפה בנקודה x=0.
• הפונקציה f רציפה בנקודה x אם ורק אם לכל סדרה [math]\displaystyle{ \ a_1,a_2,\dots }[/math] המתכנסת ל-x, הסדרה [math]\displaystyle{ \ f(a_1),f(a_2),\dots }[/math] מתכנסת לערך [math]\displaystyle{ \ f(x) }[/math].

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

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

הוכחה

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

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

מודוס פוננס

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

הגזירה מתבססת כאן על הכלל הלוגי היסודי הנקרא מודוס פוננס: מ- [math]\displaystyle{ \ P\rightarrow Q }[/math] ו- [math]\displaystyle{ P }[/math] אפשר לגזור (כלומר להסיק את) [math]\displaystyle{ Q }[/math].

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

שימו לב. מהטענה [math]\displaystyle{ \ P \rightarrow Q }[/math] לא נובע P, ולא נובע Q, אלא רק שאם P אז Q. תנו דוגמא מפורשת לכך.

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

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

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

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

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

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

• יהי [math]\displaystyle{ \ x\gt 0 }[/math] (היריב בוחר x כרצונו). נבחר [math]\displaystyle{ \ y = x/2 }[/math], ואז [math]\displaystyle{ \ 0\lt y\lt x }[/math] (כאן אנו מראים שעבור y שבחרנו, הטענה אכן מתקיימת).

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

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

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

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

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

תרגילים.

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

חומר נוסף

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

שלילה

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

הצרנה

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

אמביוולנטיות בין עברית לבין מתמטיקה

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

ההבדל בין 'אם' לבין 'אם ורק אם'

ראו הערה בדף השיחה לגבי השימוש ב"אם" במתמטיקה. בועז

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

דוגמא

מילולית

נביט בשלושה משפטים:

1. השמש זורחת אם ורק אם כל התרנגולים קוראים
2. כאשר השמש זורחת, כל התרנגולים קוראים
3. כאשר התרנגול קוקי קורא, השמש זורחת

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

מתמטית

1. הטור [math]\displaystyle{ \sum a_n }[/math] מתכנס בהחלט אם"ם לכל סדרה חסומה [math]\displaystyle{ b_n }[/math] מתקיים ש [math]\displaystyle{ \sum a_n\cdot b_n }[/math] מתכנס
2. אם הטור [math]\displaystyle{ \sum a_n }[/math] מתכנס בהחלט אזי לכל סדרה חסומה [math]\displaystyle{ b_n }[/math] מתקיים ש [math]\displaystyle{ \sum a_n \cdot b_n }[/math] מתכנס
3. קיימת סדרה חסומה [math]\displaystyle{ b_n }[/math] כך שהעובדה ש[math]\displaystyle{ \sum a_n\cdot b_n }[/math] מתכנס גוררת שהטור [math]\displaystyle{ \sum a_n }[/math] מתכנס בהחלט

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

• "השמש זורחת" = "הטור [math]\displaystyle{ \sum a_n }[/math] מתכנס בהחלט"
• "תרנול" = "סדרה חסומה"
• "תרנגול קורא" = "סדרה חסומה [math]\displaystyle{ b_n }[/math] כך ש [math]\displaystyle{ \sum a_n\cdot b_n }[/math] מתכנס"

כתיבת הוכחה

הגדרות

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

• מתורת הקבוצות: הכלה, חיתוך, איחוד,משלים, קבוצת החזקה. כתוב תנאים השקולים לכך שאיבר שייך/אינו שייך לחיתוך/איחוד.
• נגדיר קבוצה פתוחה בתור קבוצה שהמשלימה שלה סגורה. נניח וכל תתי הקבוצות פתוחות, כמה תתי קבוצות סגורות יש?
• נניח וfg חח"ע/על, האם בהכרח f,g חח"ע/על? כתוב הוכחה מדויקת.

דוגמאות

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

(אני אישית משתדל להמנע מטיעון זה בשנה א', כי באמת תלמידים לא מבינים מתי הוא מותר. אבל כדאי שיכירו אותו, ואת מכשלותיו. בועז)

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

מציאת שגיאות

אינדוקציה שגוייה

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