שינויים
/* משתנים ותחולתם */
זהו '''החלק השני''' של [[88-101 חשיבה מתמטית|המבוא לחשיבה מתמטית]].
== כמתים ==
=== פסוקים עם כמתים ===
ה'''כמתים''', המציינים תחולה של משתנה, הם תוספת חיונית למערך הקשרים שלנו. יש שני כמתים: "לכל", המסומן באות <math>\ \forall</math> (זוהי A הפוכה, קיצור של המלה All); ו"קיים", המסומן באות <math>\ \exists</math> (E הפוכה, קיצור של Exists). כשבונים פסוק עם כמתים, מותר לקחת פסוק קיים (הכולל פרדיקטים, שבהם x הוא משתנה), ולבנות:* <math>\ \forall x : P(x)</math> - מקבל ערך אמת T אם הפסוק <math>\ P(x)</math> מקבל ערך אמת T לכל הצבה של x.* <math>\ \exists x: P(x)</math> - מקבל ערך אמת T אם יש הצבה של x כך שהפסוק <math>\ P(x)</math> מקבל ערך אמת T.
'''הערה'''. יש דרכים רבות לכתוב פסוקים כגון אלו. מקובל למשל <math>\ \forall x P(x)</math> או <math>\ (\forall x) P(x)</math>. כל הסגנונות חוקיים, בתנאי שהפסוק ניתן לקריאה באופן חד-משמעי.
'''דוגמא'''. את הפסוק "אין מספר גדול ביותר" אפשר להצרין באופן פשטני, כך: <math>\ \neg \exists x: L(x)</math>, כאשר <math>\ L(x)</math> הוא הפרדיקט "x הוא מספר גדול ביותר". הצרנה מעט יותר מתוחכמת תגדיר את הפרדיקט <math>\ P(x,y)</math> שפירושו "x<y", ותצרין ל-<math>\ \forall x: \exists y: P(x,y)</math>, כלומר, לכל מספר יש מספר הגדול ממנו.
זהו הסוג השלישי (והאחרון עבורנו) של פסוקים לוגיים. נסכם: פסוק הוא או פרדיקט (לרבות אטומים, שהם פרדיקטים ללא משתנים), או חיבור של פסוקים קצרים יותר באמצעות קשרים לוגיים, או החלה של כמת על פסוק קצר יותר.
'''דוגמא'''. נצרין את הטענה הבאה:
לכל משוואה ריבועית <math>ax^2+bx+c=0</math> כך ש-<math>b^2-4ac \geq 0ge0</math> יש לפחות פתרון אחד.
<math>\forall a \forall b \forall c \Big[(b^2-4ac \geq 0ge0)\rightarrow to\big(\exists x (ax^2+bx+c=0)\big)\Big]</math>
'''תרגיל'''. הצרינו את הטענה הבאה:
לכל משוואה ריבועית <math>ax^2+bx+c=0</math> כך ש-<math>b^2-4ac = 0</math> קיים בדיוק פתרון אחד.
'''תרגיל'''
*למספר שלילי אין שורש ריבועי
תשובה: <math>\forall x (x<0 \rightarrow to\forall y(y^2 \neq ne x))</math>
*למספר חיובי יש שורש חיובי ושורש זה אינו יחיד
תשובה: <math>\forall x (x>0 \rightarrow to(\exists y(y^2=x) \and \exists z((z \neq ne y)\and (z^2=x)))</math>
=== פסוקים אמיתיים === לפסוקים שיש בהם כמתים אי אפשר לבנות טבלאות אמת, משום שלצד האטומים המקבלים רק שני ערכי אמת אפשריים, יש בהם משתנים העשויים לעבור על-פני מספר אינסופי של אפשרויות. לכן הלוגיקה המטפלת בפסוקים עם כמתים (הנקראת "לוגיקה מסדר ראשון") מורכבת יותר מן הלוגיקה הפסוקית, ויש לה יכולת ביטוי רחבה יותר. גם בלוגיקה זו אומרים ששני פסוקים <math>\ \varphi, \psi</math> הם שקולים אם <math>\ \varphi \leftrightarrow \psi</math> מקבל ערך אמת לכל הצבה של המשתנים המעורבים.
'''פסוק אמיתי''' הוא כזה שמתקיים לכל בחירה של הפרדיקטים ולכל הצבה במשתנים. כל הטאוטולוגיות הן פסוקים אמיתיים, אבל ההיפך אינו נכון. לא נכנס כאן לפרטים, שמהם מתפרנסים חוקרי הלוגיקה המתמטית.
'''כיצד מוכיחים'''. זוהי דרך המלך להוכחה או סתירה של טענות:
* כדי להוכיח שהפסוק <math>\ \forall x : P(x)</math> אמיתי, יש להראות שהטענה P נכונה לכל ערך אפשרי של x.* כדי להוכיח שהפסוק <math>\ \exists x : P(x)</math> אמיתי, יש למצוא ערך של x שעבורו הטענה נכונה ("דוגמא").* כדי להוכיח שהפסוק <math>\ \forall x : P(x)</math> שקרי, יש למצוא ערך של x שעבורו הטענה אינה נכונה ("דוגמא נגדית").* כדי להוכיח שהפסוק <math>\ \exists x : P(x)</math> שקרי, יש להראות שהטענה P אינה נכונה לכל ערך אפשרי של x.
בפרק האחרון נחזור להוכחות ונעסוק בהן בהרחבה. למרות שרוב ההוכחות הולכות בדרך המלך, לפעמים יש דרכים קצרות ומתוחכמות יותר.
'''תרגיל'''. קבע אלו מהפסוקים הבאים הם אמיתיים, כאשר הסימנים "לכל" ו"קיים" פירושם "לכל מספר שלם" ו"קיים מספר שלם". אם הפסוק אינו אמיתי, בחר פרדיקטים ומשתנים המדגימים זאת. * <math>\ \forall x P(x) \implies \exists x P(x)</math>.* <math>\ \forall z: P(z) \rightarrow to\forall x,y: P(x^2+y^2)</math>.* <math>\ \exists z: P(z) \rightarrow to\exists x,y: P(x^2+y^2)</math>.* <math>\ (\forall x: P(x) \wedge and\forall x: Q(x)) \rightarrow to\forall x: (P(x) \wedge and Q(x))</math>.* <math>\ \forall x: (P(x) \wedge and Q(x)) \rightarrow to(\forall x: P(x) \wedge and\forall x: Q(x))</math>.* <math>\ (\exists x: P(x) \wedge and\exists x: Q(x)) \rightarrow to\exists x: (P(x) \wedge and Q(x))</math>.**'''פתרון''': יש מספר שלם ריבועי ויש מספר שלם בין 70 ל-80; אבל אין מספר שלם ריבועי שהוא בין 70 ל-80.* <math>\ \exists x: (P(x) \wedge and Q(x)) \rightarrow to(\exists x: P(x) \wedge and\exists x: Q(x))</math> .*<math>(\exists x:P(x)\or\exists x:Q(x))\to\exists x:(P(x)\or Q(x))</math>.
'''תרגיל'''. שכנע את עצמך באמיתיות הפסוק הבא:
* <math>\ (\forall x: P(x) \rightarrow to Q(x)) \rightarrow to(\forall x: P(x) \rightarrow to\forall x: Q(x))</math>.
'''תרגיל'''. נניח ש-c הוא קבוע, A תכונה אטומית, ו-P פרידקט עם משתנה אחד. הוכח את השקילות של הפסוקים הבאים:
נתבונן בפרדיקט בן שני משתנים, <math>\ P(x,y)</math> (למשל x אוהב את y). ערך האמת שלו תלוי בהצבה של x ו-y.
נשווה זאת לפסוק <math>\ \forall x : P(x,y)</math> (כל x אוהב את y). בפסוק זה אי אפשר להציב את x: הפסוק למעשה אומר "כולם אוהבים את y", והתפקיד של x הוא פורמלי לחלוטין - לסמן את המשתנה העובר על כל האפשרויות. הפסוק <math>\ \forall z : P(z,y)</math> שקול לגמרי לקודם. כדי להדגיש זאת, אפשר לכתוב <math>\ \phi(y) = \forall x: P(x,y)</math>, עם המשתנה היחיד שבו יש משתנה חופשי יחיד, y.
שימו לב לתפקיד הרגיש של x בפסוק כזה. אם נכתוב למשל <math>\ \forall x : P(x,x)</math> ("כל אחד אוהב את עצמו"), נקבל פסוק בעל משמעות שונה לחלוטין. אם רוצים להציב ב-<math>\ \phi</math> את x דווקא, מוכרחים להחליף לפני כן את המשתנה. לא נכתוב <math>\ \phi(x) = \forall x: P(x,x)</math>, אלא <math>\ \phi(x) = \forall z: P(z,x)</math>.
קל לטעות, ולעבור מ"קיים חתול שאוהב שניצלים" ל"הנה חתול; מכאן שהוא אוהב שניצלים". להלן דוגמא מבחינה של סטודנט. כידוע, מספר טבעי 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", הלקוחה גם היא מבחינה של סטודנט?(תשובה: טענה זו שקולה לטענה "אם יש n כך ש-n|a,b אז יש m כך ש-m|d"; ומה זה אומר בכלל על d).
דוגמא נוספת: הפתרון הכללי למשוואה דיפרנציאלית מסויימת הוא הפונקציה <math>\ y(x) = e^x+C</math> כאשר C הוא קבוע (אין צורך לדעת מהי משוואה דיפרנציאלית כדי להצרין את הטענה הזו: קיים, מן הסתם, פרדיקט P המקבל ערך אמת T רק על פונקציות הפותרות את המשוואה, ואם כך הפסוק קובע ש"לכל y, אם <math>\ P(y)</math> אז קיים C כך ש- <math>\ y = e^x + C</math>"). קושיה שהעלה סטודנט: האם נכון לומר שהפתרון הכללי לאותה משוואה הוא <math>\ y(x) = e^x+2C</math>? ומה אם התהיה היתה לגבי הפתרון <math>\ y(x) = e^x+1/C</math>?
'''משפט ואן-דר-ורדן''' הוא אחד המשפטים היסודיים בקומבינטוריקה אינסופית. הוא קובע שבכל חלוקה של המספרים השלמים למספר סופי של קבוצות, ולכל k, אחד החלקים כולל סדרות חשבוניות (<math>\ a, a+d, a+2d, \dots,a+(k-1)d</math>) מכל אורך סופי מאורך k. (1א) הסבירו את ההבדל בין טענה זו לטענה "בכל חלוקה של השלמים למספר סופי של קבוצות, לכל k, אחד החלקים מכיל סדרה חשבונית באורך k", והראו שהן שקולות זו לזו למרות ההבדל. (2ב) הראו שאפשר לחלק את השלמים לשתי קבוצות שאף אחת מהן אינה כוללת סדרה חשבונית אינסופית.
=== וריאציות וכימות יחסי ===
* <math>\ \forall n : \exists x : ((x>n) \wedge P(x))</math>: "לכל n יש x גדול ממנו המקיים את התכונה". אם היה רק מספר סופי של מספרים המקיימים את התכונה המדוברת, אז הפסוק היה שקרי משום שאפשר היה לבחור בתור n את המספר הגדול ביותר.
מאחורי כל כמת מסתתרת "קבוצה אוניברסלית", שהיא קבוצת הערכים המותרים עבור המשתנה הצמוד לכמת (מספרים ממשיים, מספרים טבעיים, פירות, אנשים). בדרך כלל הקבוצה הזו מובנת מההקשר; אם לא, יש לציין במפורש מהו טווח הערכים המתאים. לצרכי נוחות, מרשים גמישות במבנה הצורני של הפסוקים, כך שאפשר יהיה לכמת "כימות יחסי". לדוגמא, מותר לכתוב
* <math>\ \forall x>0: \exists y>0: y<x</math> - "לכל מספר חיובי x יש מספר חיובי y הקטן ממנו", כלומר "אין מספר חיובי קטן ביותר", בתור קיצור לכתיבה המלאה <math>\ \forall x: ((x>0) \rightarrow (\exists y: ((y>0) \wedge (y<x))))</math> - "לכל מספר x, אם הוא חיובי, אז קיים מספר y שהוא חיובי וקטן מ-x".
יש טענות שאפשר לנסח באופן ישיר, אבל קל יותר לנסח באופן יחסי:
'''תרגיל'''. נניח שהיכרות היא פרדיקט סימטרי P בשני משתנים (כלומר, <math>\ \forall x,y: P(x,y) \leftrightarrow P(y,x)</math>).
* נסח את הפסוק: מבין כל ששה אנשים, או שיש שלושה המכירים זה את זה, או שיש שלושה שאף אחד מהם אינו מכיר אף אחד אחר.
* <math>\ \neg \exists x: P(x) \equiv \forall x: \neg P(x)</math>.
זו הזדמנות לשוב ולעיין בדרכים להוכיח ולהפריך טענות מכומתות שהובאו בראש [[#טענות אמיתיות|אחד הסעיפים הקודמים]]. שימו לב שאת הטענות <math>\ \neg \exists forall x: \neg P(x)</math> ו-<math>\ \neg \exists x: P(x)</math> מוכיחים למעשה באותה דרך (מראים ש*לכל* x, הטענה P אינה מתקיימת), וגם את <math>\ \neg \forall x: P(x)</math>, ו-<math>\ \exists x: \neg P(x)</math> מוכיחים באותה דרך (מראים ש*קיים* x שעבורו P אינה נכונה).
אפשר "לחסוך" ולכתוב כל פסוק רק באמצעות אחד משני הכמתים:
פתרון: קיים <math>a\in A</math> כך שלכל <math>b \in B</math> מתקיים <math>b\in A \setminus \{a\}</math> או <math>(A\setminus\{a\})\cup \{b\}</math> תלויה לינארית.
* '''המשיכו ל[[88-101 חשיבה מתמטית - הגדרות והוכחות|חלק השלישי]]'''.
