שינויים
/* משתנים ותחולתם */
זהו '''החלק השני''' של [[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) \vee or\exists x: Q(x)) \rightarrow to\exists x: (P(x) \vee 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 פרידקט עם משתנה אחד. הוכח את השקילות של הפסוקים הבאים:
קל לטעות, ולעבור מ"קיים חתול שאוהב שניצלים" ל"הנה חתול; מכאן שהוא אוהב שניצלים". להלן דוגמא מבחינה של סטודנט. כידוע, מספר טבעי 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>?
יש טענות שאפשר לנסח באופן ישיר, אבל קל יותר לנסח באופן יחסי:
'''תרגיל'''. נניח שהיכרות היא פרדיקט סימטרי 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 אינה נכונה).
אפשר "לחסוך" ולכתוב כל פסוק רק באמצעות אחד משני הכמתים:
