Discrete Mathematics: A Quick Introduction to Logic - PDF

‫מתמטיקה בדידה‬ ‫מבוא מהיר ללוגיקה‬ ‫איתי הראבן‬ ‫מהדורה פנימית‬ ‫לא להפצה ולא למכירה‬ ‫מק”ט ‪20476-5051‬‬ ‫‪Nir‬‬ ‫‪Yakuti‬‬...

‫מתמטיקה בדידה‬ ‫מבוא מהיר ללוגיקה‬ ‫איתי הראבן‬ ‫מהדורה פנימית‬ ‫לא להפצה ולא למכירה‬ ‫מק”ט ‪20476-5051‬‬ ‫‪Nir‬‬ ‫‪Yakuti‬‬ ‫‪DAFFAEAFC‬‬ ‫‪File #0004773 belongs to Nir Yakuti- do not distribute‬‬ ‫ת נ א י ש י מ ו ש ב ק וב ץ ה ד י גי ט ל י ‪:‬‬ ‫‪1.‬הקובץ הוא לשימושך האישי בלבד‪.‬פרטים מזהים שלך מוטבעים‬ ‫בקובץ בצורה גלויה ובצורה סמויה‪.‬‬ ‫‪2.‬השימוש בקובץ הוא אך ורק למטרות לימוד‪ ,‬עיון ומחקר אישי‪.‬‬ ‫‪3.‬העתקה או שימוש בתכנים נבחרים מותרת בהיקף העומד בכללי‬ ‫השימוש ההוגן‪ ,‬המפורטים בסעיף ‪ 19‬לחוק זכות יוצרים ‪.2007‬‬ ‫במקרה של שימוש כאמור חלה חובה לציין את מקור הפרסום‪.‬‬ ‫‪___--_____-_____--____--_____-__-‬‬ ‫‪1‬‬ ‫מבוא מהיר ללוגיקה‬ ‫מתמטיקה בדידה‬ ‫מבוא מהיר ללוגיקה‬ ‫איתי הראבן‬ ‫מהדורה פ‪‬ימית‬ ‫לא למכירה ולא להפצה‬ ‫‪20476-5051‬‬ ‫‪Nir‬‬ ‫‪Yakuti‬‬ ‫‪___--_____-_____--____--_____-__-‬‬ ‫‪File #0004773 belongs to Nir Yakuti- do not distribute‬‬ ‫מתמטיקה בדידה‬ ‫‪2‬‬ ‫כותבים‪:‬‬ ‫איתי הראבן‬ ‫אילון בן שמואל )תשובות לשאלות(‬ ‫יועצים‪:‬‬ ‫פרופ' ד‪‬יאלה ליבוביץ‪ ,‬האו‪‬יברסיטה הפתוחה‬ ‫ד"ר שמואל ברגר‪ ,‬האו‪‬יברסיטה הפתוחה‬ ‫ד"ר מ‪‬ור מ‪‬דל‪ ,‬האו‪‬יברסיטה הפתוחה‬ ‫ד"ר גיל אלון‪ ,‬האו‪‬יברסיטה הפתוחה‬ ‫עורכת לשון‪:‬‬ ‫חוה ‪‬יומן‬ ‫הדפסה דיגיטלית מתוק‪‬ת – ‪‬ובמבר ‪2021‬‬ ‫‪ ‬תשפ"ב – ‪.2021‬כל הזכויות שמורות לאו‪‬יברסיטה הפתוחה‪.‬‬ ‫ההוצאה לאור של האו‪‬יברסיטה הפתוחה‪ ,‬הקריה ע"ש דורותי דה רוטשילד‪ ,‬דרך האו‪‬יברסיטה ‪ ,1‬ת"ד ‪ ,808‬רע‪‬ה‬ ‫‪.4353701‬‬ ‫‪Academic Development and Publishing, The Open University of Israel, The Dorothy de Rothschild Campus, 1‬‬ ‫‪University Road, P.O.Box 808, Raanana 4353701.‬‬ ‫‪Printed in Israel.‬‬ ‫אין לשכפל‪ ,‬להעתיק‪ ,‬לצלם‪ ,‬להקליט‪ ,‬לתרגם‪ ,‬לאחסן במאגר מידע‪ ,‬לשדר או לקלוט בכל דרך או בכל אמצעי אלקטרו‪‬י‪,‬‬ ‫אופטי‪ ,‬מכ‪‬י או אחר כל חלק שהוא מהחומר שבספר זה‪.‬שימוש מסחרי בחומר הכלול בספר זה אסור בהחלט‪ ,‬אלא‬ ‫ברשות מפורשת ובכתב ממדור זכויות יוצרים של האו‪‬יברסיטה הפתוחה‪.‬‬ ‫‪___--_____-_____--____--_____-__-‬‬ ‫‪3‬‬ ‫מבוא מהיר ללוגיקה‬ ‫תוכן העניינים‬ ‫‪5‬‬ ‫הקדמה‬ ‫‪7‬‬ ‫‪ 1‬פסוקים וערכי אמת‪.‬משת‪‬ים פסוקיים‬ ‫‪9‬‬ ‫ַקשָּ ר השלילה‬ ‫‪2‬‬ ‫‪9‬‬ ‫הקשָּ רים "וגם"‪" ,‬או"‬ ‫ַ‬ ‫‪3‬‬ ‫‪12‬‬ ‫‪ 4‬מהו ַקשָּ ר לוגי‬ ‫‪13‬‬ ‫והקשָּ ר "‪‬אם ורק אם‪"‬‬ ‫ַ‬ ‫הקשָּ ר "אם‪‬אז‪"‬‬ ‫ַ‬ ‫‪5‬‬ ‫‪16‬‬ ‫‪ 6‬הַ צְ ָר‪ָ‬ה‪.‬פסוקים פורמליים ולוחות האמת שלהם‬ ‫‪19‬‬ ‫‪ 7‬טאוטולוגיה וסתירה‪.‬שקילוּת בין פסוקים‬ ‫‪24‬‬ ‫‪ 8‬טע‪‬ות שימושיות‬ ‫‪27‬‬ ‫ַקשָּ רים ‪‬וספים‪.‬הבעת ַקשָּ ר לוגי בעזרת ַקשָּ רים לוגיים אחרים‬ ‫‪9‬‬ ‫‪29‬‬ ‫‪ 10‬גרירה ‪ /‬ביעה‬ ‫‪33‬‬ ‫‪ 11‬משת‪‬ים וכַמָּ תים‬ ‫‪37‬‬ ‫‪ 12‬תשובות לשאלות‬ ‫‪52‬‬ ‫‪ 13‬הערות‬ ‫‪Nir‬‬ ‫‪Yakuti‬‬ ‫‪250405503 yakuti1atgmail.com‬‬ ‫‪___--_____-_____--____--_____-__-‬‬ File #0004773 belongs to Nir Yakuti- do not distribute ‫מתמטיקה בדידה‬ 4 ___--_____-_____--____--_____-__- ‫‪5‬‬ ‫מבוא מהיר ללוגיקה‬ ‫הקדמה‬ ‫בפרק זה ‪‬סקור בקצרה כמה מושגים בלוגיקה‪ ,‬אשר ישמשו ליצירת שפה משותפת בקורס זה‬ ‫ובקורסים הבאים‪.‬למעו‪‬יי‪‬ים‪ ,‬ושאי הפרק הזה מוצגים בהרחבה בקורסים ‪‬ושאים‬ ‫במתמטיקה למדעי החברה ‪ ,10444‬לוגיקה מתמטית ‪ ,20327‬לוגיקה למדעי המחשב ‪,20466‬‬ ‫וכן בקורס מבוא ללוגיקה ‪ 10703‬השייך למחלקה למדעי הרוח‪.‬‬ ‫‪Nir‬‬ ‫‪Yakuti‬‬ ‫‪___--_____-_____--____--_____-__-‬‬ File #0004773 belongs to Nir Yakuti- do not distribute ‫מתמטיקה בדידה‬ 6 ___--_____-_____--____--_____-__- ‫‪7‬‬ ‫מבוא מהיר ללוגיקה‬ ‫פסוקים וערכי אמת‪.‬משתנים פסוקיים‬ ‫‪1‬‬ ‫פסוק )‪ (proposition‬הוא משפט בשפת הדיבור או בשפה מתמטית‪ ,‬המביע טע‪‬ה‪ ,‬שהיא‬ ‫אמת או שקר‪.‬ה‪‬ה כמה דוגמאות‪:‬‬ ‫א‪.‬ביולי ‪ 2011‬היה ברק אובאמה נשיא ארצות‪-‬הברית‪.‬‬ ‫ב‪10 + 18 = 4.‬‬ ‫ג‪3  4 > 10.‬‬ ‫ד‪.‬חצוצרה היא כלי נשיפה וגיטרה היא כלי מיתר‪.‬‬ ‫ה‪.‬בפיתוח העשרוני של ‪ ,‬הספרה שנמצאת בַּ ָמּקום המאה‪-‬טריליון היא ‪.4‬‬ ‫הפסוקים א'‪ ,‬ג' ו‪-‬ד' הם אמת‪.‬פסוק ב' הוא שקר‪.‬גם טע‪‬ה ה' היא פסוק‪ :‬הקביעה שמוצגת‬ ‫בסעיף ה' היא אמת או שקר‪ ,‬גם אם אי‪‬ו יודעים כרגע מהי הספרה שבה מדובר‪.‬‬ ‫למושגים אמת ושקר אין כאן משמעות ערכית‪ :‬במילה "שקר" כוו‪‬ת‪‬ו פשוט לטע‪‬ה שאי‪‬ה‬ ‫‪‬כו‪‬ה‪ ,‬שאי‪‬ה תואמת את המציאות‪.‬בשפות רבות יש מילה ‪‬יטרלית עבור טע‪‬ה כזו‪ :‬בא‪‬גלית‬ ‫משמשת המילה ‪ ,False‬בערבית– ﺑﺎﻁﻞ‪.‬אם בשבת בבוקר שמעון קם מבולבל ואמר למשפחתו‬ ‫"היום יום ראשון"‪ ,‬האמירה שלו היא ‪) False‬היא אי‪‬ה משקפת את המציאות(‪ ,‬אך אי‪‬ה ‪Lie‬‬ ‫)הוא לא מסר מידע שגוי בכוו‪‬ה(‪.‬בהיעדר כי‪‬וי פשוט וקצר בעברית לטע‪‬ה שאי‪‬ה ‪‬כו‪‬ה‪,‬‬ ‫‪‬הוג‪ ,‬בדיון בלוגיקה בעברית‪ ,‬לתרגם את המילה ‪ False‬ל"שקר"‪.‬אי‪‬ו מתייחסים בכך‬ ‫לכוו‪‬ה של הדובר או למצב הידע שלו על העולם‪ ,‬אלא פשוט לכך שהאמירה אי‪‬ה ‪‬כו‪‬ה‪.‬‬ ‫את המושגים אמת ושקר ‪‬ייצג בעזרת האותיות ‪ T‬ו‪ F -‬בהתאמה )‪.(False ,True‬‬ ‫ייצוג מקובל אחר הוא‪ :‬הספרה ‪ 1‬עבור אמת‪ ,‬והספרה ‪ 0‬עבור שקר‪.‬‬ ‫על פסוק שהוא אמת אומרים שערך האמת )‪ (Truth value‬שלו הוא ‪ T‬או ‪.1‬‬ ‫על פסוק שהוא שקר אומרים שערך האמת שלו הוא ‪ F‬או ‪.0‬‬ ‫לכל פסוק יש ערך אמת יחיד‪ :‬אחד מש‪‬י הערכים ‪ T‬או ‪.F‬‬ ‫למשל‪ ,‬ערך האמת של הפסוק ‪ 3  4 > 10‬הוא ‪.T‬‬ ‫ערך האמת של הפסוק ‪ 10 + 18 = 4‬הוא ‪.F‬‬ ‫המושג "פסוק" חופף במידה רבה )אך לא מלאה( למושג "משפט חיווי" בלשון‪.‬‬ ‫חלקי משפטים שאי‪‬ם פסוקים‪:‬‬ ‫ה‪‬ה דוגמאות למשפטים ול ֵ‬ ‫מה השעה?‬ ‫)‪(i‬‬ ‫)‪ (ii‬לך הבייתה מוטי‪ ,‬שלום ותודה!‬ ‫)‪x  2  5 (iii‬‬ ‫)‪3  2  4 (iv‬‬ ‫)‪ (v‬שכונת תלפיות‬ ‫)‪ (vi‬החשבון ברח יבֵ ש‪.‬‬ ‫‪Nir‬‬ ‫‪Yakuti‬‬ ‫‪___--_____-_____--____--_____-__-‬‬  ‫‪File #0004773 belongs to Nir Yakuti- do not distribute‬‬ ‫מתמטיקה בדידה‬ ‫‪8‬‬ ‫אף אחת מן הדוגמאות האלה אי‪‬ה פסוק‪ ,‬כי עבור אף אחת מהן לא ‪‬יתן לומר שהיא אמת או‬ ‫שקר‪ :‬דוגמה )‪ (i‬היא שאלה‪.‬דוגמה )‪ (ii‬היא שילוב של ציווי וברכה‪ ,‬ואף אחת מהן אי‪‬ה‬ ‫טע‪‬ה‪.‬‬ ‫לגבי דוגמה )‪ ,(iii‬לפ‪‬י ש‪‬וכל לשאול אם היא אמת או שקר‪ ,‬עלי‪‬ו להציב ערך מספרי במקום‬ ‫‪.x‬‬ ‫גם הדוגמאות )‪ (iv‬ו‪ (v)-‬אי‪‬ן טע‪‬ות‪ :‬לא ‪‬יתן לשאול אם ‪‬כון ש‪. 3  2  4 -‬במילים אחרות‪,‬‬ ‫אין משמעות לשאלה "האם ‪‬כון ש‪."?10-‬בדומה‪ ,‬לא ‪‬יתן לשאול אם ‪‬כון ששכו‪‬ת תלפיות*‪.‬‬ ‫דוגמה )‪ (vi‬היא משפט חיווי בעברית‪ ,‬תקין מבחי‪‬ה תחבירית‪ ,‬אבל הוא חסר משמעות‪ ,‬ולא‬ ‫‪‬יתן לייחס לו ערך אמת‪(1).‬‬ ‫לגבי טע‪‬ות מסוימות‪ ,‬חוץ לדעת את ההֶ קשר שבו הן ‪‬אמרו כדי לייחס להן ערך אמת‪.‬‬ ‫למשל‪:‬‬ ‫א‪.‬אני נפוליאון‪.‬‬ ‫ב‪.‬היום יום ראשון‪.‬‬ ‫ג‪.‬קיים מספר שאם נכפול אותו ב‪ 2-‬נקבל ‪.5‬‬ ‫טע‪‬ה א' היא אמת אם ‪‬אמרה על‪-‬ידי ‪‬פוליאון‪ ,‬אך היא שקר אם ‪‬אמרה על‪-‬ידי אדם אחר‪.‬‬ ‫טע‪‬ה ב' היא אמת אם ‪‬אמרה ביום ראשון‪ ,‬אך היא שקר אם ‪‬אמרה ביום אחר‪.‬‬ ‫טע‪‬ה ג' היא אמת אם מפרשים את המילה "מספר" כמספר ממשי או כמספר רציו‪‬לי‪.‬היא‬ ‫שקר אם מפרשים את המילה "מספר" כ"מספר שלם"‪.‬‬ ‫לגבי טע‪‬ות כאלה‪ ,‬יח ש‪‬תון ההֶ קשר שבו הן ‪‬אמרו‪ ,‬ואז ‪‬וכל להתייחס אליהן כאל פסוק‪.‬‬ ‫למעשה‪ ,‬גם עבור חלק מהפסוקים שהבא‪‬ו לדוגמה בתחילת הסעיף‪ ,‬ה‪‬ח‪‬ו שא‪‬ו מדברים על‬ ‫הֶ קשר מסוים‪.‬אמר‪‬ו שהפסוק ‪ 10  18  4‬הוא שקר‪.‬הוא אכן שקר כאשר מתייחסים‬ ‫לפירוש המקובל שלו‪ ,‬אבל הוא אמת אם הוא ‪‬ועד להביע את העובדה ש‪ 18-‬שעות אחרי‬ ‫השעה ‪ 10‬מגיעה השעה ‪.4‬‬ ‫צייַ‪‬ו שהפסוק ‪ 3  4 > 10‬הוא אמת‪.‬פסוק זה הוא שקר אם ‪‬יח שהמספרים כתובים‬ ‫בבסיס הקסָ דֶ צימלי )‪ ,(Hexadecimal‬שבו הסימן "‪ "10‬מייצג את המספר העשרו‪‬י ‪.16‬‬ ‫כדי לא להזדקק לייעוץ של עורך‪-‬דין בכל פעם שא‪‬ו מציי‪‬ים שפסוק מסוים הוא אמת‬ ‫ושפסוק אחר הוא שקר‪ ,‬סכים שבכל מקרה שבו יש למושגים פירוש או הֶ קשר מקובל‪ ,‬יח‬ ‫)בלי לציין זאת( שמדובר על הפירוש או על ההֶ קשר הזה‪ ,‬בדיוק כפי שעשי‪‬ו בתחילת הסעיף‪.‬‬ ‫כאשר ‪‬רצה לדבר על פסוק כלשהו‪ ,‬בלי להתחייב מהו‪ ,‬שתמש לרוב באחת האותיות ‪.p,q,r,s‬‬ ‫אותיות אלה ייצגו פסוקים‪ ,‬בדומה לאופן שבו השתמש‪‬ו בבית‪-‬הספר ב‪ x,y,z-‬לייצוג מספרים‪.‬‬ ‫לאותיות המסמ‪‬ות פסוקים ‪‬קרא משת‪‬ים פסוקיים‪.‬‬ ‫* בשפות תכ‪‬וּת מסוימות‪ ,‬כל ערך שאי‪‬ו ‪ 0‬או ‪ null‬חשב "אמת"‪.‬בלוגיקה מתמטית אין מוסכמה כזאת‪.‬‬ ‫‪250405503 yakuti1atgmail.com‬‬ ‫‪DAFFAEAFC‬‬ ‫‪9‬‬ ‫מבוא מהיר ללוגיקה‬ ‫האות ‪ p‬יכולה‪ ,‬למשל‪ ,‬לייצג את הפסוק ‪ , 10 + 18 = 4‬היא יכולה לייצג את הפסוק‬ ‫חצוצרה היא כלי נשיפה וגיטרה היא כלי מיתר‪ ,‬והיא יכולה גם לייצג את הפסוק‬ ‫היום בבוקר שמעון אמר ש‪ 511-‬הוא מספר ראשוני‪ ,‬אבל אני חושב שהוא טועה‪.‬‬ ‫במקרים רבים ‪‬רצה ל‪‬תח אמירות מורכבות למרכיבים הלוגיים שלהן‪.‬‬ ‫בסעיפים הבאים ‪‬ב‪‬ה כלים שיאפשרו ל‪‬ו לעשות זאת‪.‬‬ ‫קַ שָּר השלילה‬ ‫‪2‬‬ ‫שלילת הפסוק ‪ 10 + 18 = 4‬היא הפסוק ‪. 10 + 18  4‬‬ ‫שלילת הפסוק ‪ 2 < 5‬היא הפסוק ‪ 2‬אינו קטן מ‪.5-‬‬ ‫שלילת הפסוק חצוצרה היא כלי נשיפה היא הפסוק חצוצרה אינה כלי נשיפה‪.‬‬ ‫שלילתו של פסוק ‪ p‬פירושה‪ :‬לא ‪.p‬שלילת ‪ p‬מסומ‪‬ת‪.  p :‬בא‪‬גלית‪.Negation :‬יש‬ ‫ספרים שבהם שלילה מסומ‪‬ת על‪-‬ידי ~‪).‬בשפות תכ‪‬ות שו‪‬ות‪ ,‬שלילה מסומ‪‬ת על‪-‬ידי המילה‬ ‫‪ NOT‬או על‪-‬ידי סימן קריאה‪(.‬‬ ‫שימו לב ששלילה של פסוק אי‪‬ה "ההיפך" מהפסוק‪.‬למשל‪ ,‬שלילת הפסוק שמעון הוא‬ ‫הסטודנט הגבוה ביותר בכיתה אי‪‬ה הפסוק שמעון הוא הסטודנט הנמוך ביותר בכיתה אלא‬ ‫הפסוק שמעון אינו הסטודנט הגבוה ביותר בכיתה‪.‬לע‪‬יין זה ‪‬חזור לקראת סוף הפרק‪.‬‬ ‫אם ‪ p‬הוא אמת‪  p ,‬הוא שקר‪ ,‬ולהיפך‪:‬‬ ‫‪p‬‬ ‫‪p‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫לוח ‪ :1‬לוח האמת של ‪‬‬ ‫סימן השלילה הוא ַקשָּ ר חד‪-‬מקומי‪ ,‬כלומר ַקשָּ ר הפועל על פסוק בודד‪.‬‬ ‫בסעיף הבא ‪‬ציג ש‪‬י ַקשָּ רים דו‪-‬מקומיים‪.‬‬ ‫הקַ שָּרים "וגם"‪" ,‬או"‬ ‫‪3‬‬ ‫מיליות קישור מסוימות בעברית מאפשרות ל‪‬ו לשלב ש‪‬י פסוקים וליצור מהם פסוק אחד‪.‬‬ ‫למשל‪ ,‬הפסוק חצוצרה היא כלי נשיפה וגיטרה היא כלי מיתר ב‪‬וי מש‪‬י פסוקים‪:‬‬ ‫מן הפסוק חצוצרה היא כלי נשיפה ומן הפסוק גיטרה היא כלי מיתר‪.‬‬ ‫‪Nir‬‬ ‫‪Yakuti‬‬ ‫‪___--_____-_____--____--_____-__-‬‬  ‫‪File #0004773 belongs to Nir Yakuti- do not distribute‬‬ ‫מתמטיקה בדידה‬ ‫‪10‬‬ ‫מילית הקישור "ו‪ "-‬משלבת את ש‪‬י הפסוקים לפסוק אחד‪:‬‬ ‫חצוצרה היא כלי נשיפה וגיטרה היא כלי מיתר‪.‬‬ ‫בלוגיקה ובמתמטיקה בכלל‪ ,‬פעולת השילוב הזו מיוצגת על‪-‬ידי הסימן ‪. ‬‬ ‫אם ‪ p‬מייצג את הפסוק חצוצרה היא כלי נשיפה ו‪ q-‬מייצג את הפסוק גיטרה היא כלי מיתר‪,‬‬ ‫אזי את הפסוק חצוצרה היא כלי נשיפה וגיטרה היא כלי מיתר ‪‬וכל לייצג כך‪. p  q :‬‬ ‫למילית "ו‪ "-‬יש בעברית משמעויות שו‪‬ות‪.‬תבו‪‬ן למשל במשפט‪:‬‬ ‫רון והרמיוני נפגשו לראשונה ברכבת‪.‬‬ ‫המשפט הזה כמובן אי‪‬ו שילוב של שתי האמירות המוזרות‪:‬‬ ‫רון נפגש לראשונה ברכבת ו‪ -‬הרמיוני נפגשה לראשונה ברכבת‪.‬‬ ‫השימוש במילית "ו‪ "-‬בפסוק רון והרמיוני נפגשו לראשונה ברכבת אי‪‬ו יכול להיות מיוצג על‪-‬‬ ‫ידי הסימן ‪. ‬לעומת זאת‪ ,‬האמירה‪ ,‬ש‪‬שמעת דומה מבחי‪‬ה תחבירית‪:‬‬ ‫רון והרמיוני נמצאו מתאימים לגריפינדור‪ ,‬פירושה בדיוק‪:‬‬ ‫רון נמצא מתאים לגריפינדור ‪ ‬הרמיוני נמצאה מתאימה לגריפינדור‪.‬‬ ‫בשפה המדוברת‪ ,‬המילית "ו‪ "-‬עשויה גם לתאר סדר התרחשויות‪.‬למשל‪:‬‬ ‫באמצע הספר השביעי נמאס לי והלכתי לישון פירושו בדרך‪-‬כלל שהלכתי לישון אחרי ש‪‬מאס‬ ‫לי ולא להיפך‪.‬‬ ‫לסימן ‪ ‬אין משמעות כזו‪:‬‬ ‫לקשֶ ר סיבתי או ל ֶקשֶ ר בזמ‪‬ים בין חלקי הפסוק‪.‬‬ ‫הוא אי‪‬ו מתייחס ֶ‬ ‫כדי להבהיר את המשמעות של הסימן ‪ ‬בצורה שאי‪‬ה תלויה במוסכמות לשו‪‬יות כאלו או‬ ‫אחרות‪ ,‬גדיר אותה בצורה מפורשת‪:‬‬ ‫כאשר הפסוקים ‪ q, p‬ש‪‬יהם אמת‪ ,‬הפסוק ‪ p  q‬הוא אמת‪.‬‬ ‫כאשר לפחות אחד מבין הפסוקים ‪ q, p‬הוא שקר‪ ,‬הפסוק ‪ p  q‬הוא שקר‪.‬‬ ‫זו ההגדרה של משמעות הסימן ‪. ‬סכם אותה בטבלה‪:‬‬ ‫‪p‬‬ ‫‪q‬‬ ‫‪pq‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫לוח ‪ :2‬לוח האמת של ‪‬‬ ‫‪___--_____-_____--____--_____-__-‬‬ ‫‪11‬‬ ‫מבוא מהיר ללוגיקה‬ ‫הקשָּ ר ‪. ‬את הסימן ‪ ‬קוראים "וגם" או בקיצור "ו‪."-‬‬ ‫טבלה זו ‪‬קראת לוח האמת של ַ‬ ‫"קוֹ‪‬יוּ‪‬קציה" )‪*.(Conjunction‬‬ ‫ְ‬ ‫בלוגיקה כי‪‬ויו הרשמי הוא‬ ‫הקשָּ ר ‪ ‬הוא דו‪-‬מקומי‪ ,‬כלומר זהו ַקשָּ ר הפועל על זוג פסוקים‪.‬‬ ‫ַ‬ ‫ַקשָּ ר דו‪-‬מקומי אחר הוא הסימן ‪ , ‬המוגדר כך‪:‬‬ ‫כאשר לפחות אחד מהפסוקים ‪ q, p‬הוא אמת‪ p  q ,‬הוא אמת‪.‬‬ ‫כאשר ש‪‬י הפסוקים ‪ q, p‬הם שקר‪ p  q ,‬הוא שקר‪.‬‬ ‫‪p‬‬ ‫‪q‬‬ ‫‪pq‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫לוח ‪ :3‬לוח האמת של ‪‬‬ ‫את הסימן ‪ ‬קוראים "או"‪.‬‬ ‫לדוגמה‪ ,‬אהד‪ ,‬ב‪‬ו של שמעון‪ ,‬חזר הביתה ביום גשום‪.‬שמעון הביט בו ואמר לעצמו‪:‬‬ ‫אהד נפל לתוך שלולית או מישהו השליך על אהד בוץ‪.‬‬ ‫שימו לב שאם אהד ‪‬פל לתוך שלולית וב‪‬וסף לכך מישהו השליך עליו בוץ‪ ,‬לא ‪‬גיד ששמעון‬ ‫טעה באבח‪‬תו‪.‬פירוש זה של "או" בא לידי ביטוי בשורה הראשו‪‬ה בלוח האמת של "או"‬ ‫המוצג למעלה‪.‬‬ ‫בשפה המדוברת‪ ,‬הביטוי "או" משמש לעתים במשמעות של "או‪-‬או"‪ ,‬כלומר ‪‬ועד לציין שבדיוק‬ ‫אחת משתי האפשרויות ‪‬כו‪‬ה‪".‬או" כזה ‪‬קרא "או מוציא" )‪ :(Exclusive OR‬כו‪‬ות אחד‬ ‫הרכיבים מוציאה מכלל אפשרות את ‪‬כו‪‬ות הרכיב האחר‪.‬ה"או" המתמטי‪ ,  ,‬אי‪‬ו כזה‪.‬‬ ‫ה‪"-‬או" המתמטי הוא "או כולל" )‪ :(Inclusive OR‬ב‪"-‬או" המתמטי‪ ,‬כאשר ש‪‬י הרכיבים יחד‬ ‫הם אמת‪ ,‬הפסוק כולו הוא אמת‪.‬‬ ‫"דיסיוּ‪‬קציה" )‪†.(Disjunction‬‬ ‫ְ‬ ‫בקרב לוגיקאים‪ ,‬שמו הרשמי של ה"או" המתמטי הוא‬ ‫ֶ‬ ‫הסימן ‪ ‬לקוח מהאות הראשו‪‬ה של המילה הלטי‪‬ית ‪ ,Vel‬שפירושה "או" במובן המתמטי‪,‬‬ ‫הכולל‪).‬אגב‪ ,‬בלטי‪‬ית יש מילה ‪‬פרדת לציון "או מוציא"‪ :‬המילה ‪.(Aut‬‬ ‫* בשפות תכ‪‬ות מסוימות סימ‪‬וֹ הוא ‪ ,AND‬ובאחרות סימ‪‬וֹ הוא &&‪.‬‬ ‫† בכמה שפות תכ‪‬ות סימ‪‬ו הוא ‪ ,OR‬בשפות אחרות הוא מסומן על‪-‬ידי ש‪‬י קווים א‪‬כיים‪|| :‬‬ ‫‪Nir‬‬ ‫‪Yakuti‬‬ ‫‪___--_____-_____--____--_____-__-‬‬  ‫‪File #0004773 belongs to Nir Yakuti- do not distribute‬‬ ‫מתמטיקה בדידה‬ ‫‪12‬‬ ‫מהו קַ שָּר לוגי‬ ‫‪4‬‬ ‫בשיר "פטעו‪‬י" )‪ ,(Jabberwocky‬מתוך "מבעד למראה ומה שעליסה מצאה שם" של לואיס‬ ‫ומ ֵתי ﬠָ ָרן כֵּרדוּ‪.‬‬ ‫קרול‪ ,‬בתרגומו של אהרן אמיר‪ ,‬מוזכר כי בזמן מסוים ִחילכֵּן היה נִ ְמזַר ְ‬ ‫אי‪‬ו מבי‪‬ים את רוב המילים באמירה זו‪ ,‬אבל א‪‬ו רואים שהיא מורכבת משתי טע‪‬ות‪:‬‬ ‫)‪ִ (i‬חיל ֵכּן היה נִ ְמ ַזר‪ְ (ii).‬מ ֵתי ﬠַ ָרן ֵכּרדוּ‪.‬‬ ‫השימוש במילית "ו‪ "-‬באמירה ה‪‬תו‪‬ה ‪‬ראה מתאים לייצוג על‪-‬ידי ‪. ‬‬ ‫כעת ‪‬יח שמישהו אמין מדווח ל‪‬ו שבדק את ה‪‬ושא וגילה שחילכן אכן היה ‪‬מזר‪ ,‬אבל מתי‬ ‫ומ ֵתי ﬠָ ָרן ֵכּרדוּ הוא שקר‪.‬‬ ‫ערן לא כרדו כלל וכלל‪.‬במצב זה ברור שהפסוק ִחיל ֵכּן היה נִ ְמ ַזר ְ‬ ‫הסק‪‬ו זאת מתוך ערכי האמת של ש‪‬י הרכיבים‪ ,‬בלי להבין כלל את משמעותם של הרכיבים‪.‬‬ ‫זה התאפשר בזכות העובדה שלמילית "ו‪ ,"-‬כלומר ל ַקשָּ ר ‪ , ‬יש לוח אמת‪.‬‬ ‫בשפה המדוברת קיימות דרכים רבות לצרף זוג פסוקים ולקבל מהם פסוק חדש‪.‬בלוגיקה‬ ‫מע‪‬יי‪‬ות אות‪‬ו רק חלק מהדרכים האלה‪ :‬ביטוי המייצר מתוך כל ש‪‬י פסוקים פסוק חדש‬ ‫‪‬קרא ַקשָּ ר לוגי דו‪-‬מקומי‪ ,‬אם ורק אם ערך האמת של כל פסוק מורכב ש‪‬קבל בעזרתו תלוי‬ ‫רק בערכי האמת של הפסוקים המרכיבים‪.‬‬ ‫במילים אחרות‪ ,‬ביטוי המייצר מתוך כל ש‪‬י פסוקים פסוק חדש הוא ַק ָשּר לוגי דו‪-‬מקומי‬ ‫אם ורק אם יש לו לוח אמת‪.‬‬ ‫בדומה‪ ,‬ביטוי המייצר פסוק מתוך פסוק בודד‪ ,‬ויש לו לוח אמת‪ ,‬הוא ַקשָּ ר לוגי חד‪-‬מקומי‪.‬‬ ‫כדי להבהיר את הדרישה מ ַקשָּ ר לוגי‪ ,‬ה‪‬ה דוגמה לביטוי שאי‪‬ו ַקשָּ ר לוגי‪:‬‬ ‫לכל פסוק אפשר להוסיף את הפתיח "שמעון אמר ש‪."‬למשל‪:‬‬ ‫שמעון אמר שחצוצרה היא כלי נשיפה‪.‬‬ ‫שמעון אמר ש‪. 3  4 > 10 -‬‬ ‫הוספת הפתיח "שמעון אמר ש‪ "‬לפסוק – ‪‬ות‪‬ת ל‪‬ו פסוק חדש‪.‬למרות זאת‪ ,‬הפתיח הזה‬ ‫אי‪‬ו קשר לוגי‪:‬‬ ‫אם ‪ p‬הוא אמת‪ ,‬הטע‪‬ה "שמעון אמר ש‪ "p-‬יכולה להיות אמת או שקר‪.‬‬ ‫בדומה‪ ,‬אם ‪ p‬הוא שקר‪ ,‬הטע‪‬ה "שמעון אמר ש‪ "p-‬יכולה להיות אמת או שקר‪.‬‬ ‫מובן אפוא שלא ‪‬יתן לכתוב לוח אמת עבור "שמעון אמר ש‪."‬לפיכך ביטוי זה אי‪‬ו ַקשָּ ר‬ ‫לוגי‪.‬‬ ‫ל ַקשָּ ר השלילה יש לוח אמת‪ ,‬לכן הוא קשר לוגי חד‪-‬מקומי‪.‬בדומה‪ ,‬ה ַקשָּ רים ‪  , ‬הם‬ ‫ַקשָּ רים לוגיים דו‪-‬מקומיים‪.‬בלוח האמת של ַקשָּ ר לוגי חד‪-‬מקומי יש שתי שורות‪ ,‬ואילו בלוח‬ ‫‪___--_____-_____--____--_____-__-‬‬ ‫‪13‬‬ ‫מבוא מהיר ללוגיקה‬ ‫האמת של ַקשָּ ר לוגי דוּ‪-‬מקומי יש ארבע שורות‪.‬בהמשך הפרק ‪‬זכיר בחטף גם ַקשָּ רים לוגיים‬ ‫תלת‪-‬מקומיים וכן הלאה‪.‬‬ ‫‪ ‬שאלה ‪1‬‬ ‫הביטוי "לפ‪ֵ‬י ש‪ "‬יכול לשלב זוג פסוקים לפסוק אחד‪.‬למשל‪:‬‬ ‫סיימתי לכתוב את המטלה לפ‪ֵ‬י ששוחחתי בצ'אט עם שמעון‪.‬‬ ‫ִחיל ֵכּן היה נִ ְמ ַזר לפ ֵ‪‬י ש ְמ ֵתי ﬠַ ָרן ֵכּרדוּ‪.‬‬ ‫‪‬תחו דוגמאות אלה או דוגמאות אחרות פרי דמיו‪‬כם‪ ,‬והראו שהביטוי "לפ‪ֵ‬י ש‪ "‬אי‪‬ו )!(‬ ‫ַקשָּ ר לוגי‪(2).‬‬ ‫התשובה בעמ' ‪37‬‬ ‫הקַ שָּר "אם‪‬אז‪ "‬והקַ שָּר "‪‬אם ורק אם‪"‬‬ ‫‪5‬‬ ‫הצירוף "אם‪ ‬אז‪ "‬פוץ מאוד הן במתמטיקה והן בשפה המדוברת‪.‬‬ ‫האם הוא ַקשָּ ר לוגי‪ ,‬ואם כן‪ ,‬מהו לוח האמת שלו? ‪‬תבו‪‬ן למשל באמירות שלהלן‪:‬‬ ‫)*( אם חצוצרה היא כלי נשיפה‪ ,‬אז ‪. 10 + 18 = 4‬‬ ‫)**( אם לסבתא יש גלגלים‪ ,‬אז היא אוטובוס‪.‬‬ ‫)***( אם לסבתא יש גלגלים‪ ,‬אז היא סבתא‪.‬‬ ‫האם אלה בכלל פסוקים? אם הם פסוקים‪ ,‬מהם ערכי האמת שלהם? גם אם ‪‬סכים על ערכי‬ ‫אמת עבורם‪ ,‬לא ברור איך ‪‬יתן לכתוב לוח אמת לביטוי "אם‪ ‬אז‪ ,"‬שיביע את המשמעות‬ ‫שלו בצורה שתלויה רק בערכי האמת של הרכיבים‪.‬‬ ‫האם הקושי ‪‬ובע מה‪‬יסיון של‪‬ו לשלב אמירות שאי‪‬ן קשורות זו לזו לפסוק אחד‪ ,‬או שהוא‬ ‫קשור ספציפית לביטוי "אם‪ ‬אז‪ ?"‬בשאלה הבאה ‪‬סה לברר זאת‪.‬‬ ‫‪ ‬שאלה ‪2‬‬ ‫א‪.‬בכל אחת מהאמירות )*(‪ (***) ,(**) ,‬שלמעלה‪ ,‬החליפו את הביטוי "אם‪ ‬אז‪ "‬ב ַקשָּ ר‬ ‫הלוגי "‪‬וגם‪."‬קבעו אם הפסוק שקיבלתם הוא אמת או שקר‪.‬‬ ‫ב‪.‬חזרו על סעיף א'‪ ,‬אלא שהפעם במקום "וגם" השתמשו ב ַקשָּ ר הלוגי "או"‪.‬‬ ‫התשובה בעמ' ‪38‬‬ ‫כפי שראי‪‬ו בשאלה ‪ ,2‬לוחות האמת של ה ַקשָּ רים ‪  , ‬מגדירים את ערכי האמת של‬ ‫הפסוקים המורכבים המתאימים‪ ,‬והתוצאה מתקבלת על הדעת‪ ,‬גם אם הפסוקים ‪‬שמעים‬ ‫קצת מוזרים‪.‬שורש הבעיה באמירות )*(‪ (***) ,(**) ,‬הוא הביטוי "אם‪ ‬אז‪."‬המשמעות‬ ‫המקובלת של ביטוי זה בעברית )ובשפות אחרות שאי‪‬ן שפות פורמאליות( אי‪‬ה מאפשרת‬ ‫‪Nir‬‬ ‫‪Yakuti‬‬ ‫‪___--_____-_____--____--_____-__-‬‬  ‫‪File #0004773 belongs to Nir Yakuti- do not distribute‬‬ ‫מתמטיקה בדידה‬ ‫‪14‬‬ ‫לראותו כ ַקשָּ ר לוגי‪ :‬א‪‬ו מתקשים לייחס ערך אמת לרבים מהפסוקים ש‪‬יתן לב‪‬ות בעזרתו‪,‬‬ ‫קל וחומר – לב‪‬ות לוח אמת עבורו‪.‬‬ ‫בשפת הדיבור הביטוי "אם‪ ‬אז‪ "‬אי‪‬ו ַקשָּ ר לוגי‪.‬‬ ‫למרות זאת‪ ,‬במתמטיקה ובהֶ ְקשֵ רים פורמאליים אחרים ‪‬ית‪‬ת לו משמעות של ַקשָּ ר לוגי‪.‬‬ ‫משמעותו מוגדרת בלוח האמת הזה‪:‬‬ ‫‪p‬‬ ‫‪q‬‬ ‫‪p q‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫לוח ‪ :4‬לוח האמת של ‪‬‬ ‫כדי להבין את התפקיד של לוח האמת הזה ואת משמעותו‪ ,‬חשוב על התסריט הבא‪:‬‬ ‫תכ‪‬תם ללמוד עם שמעון לבחי‪‬ה‪.‬מזג האוויר קצת סוער‪ ,‬ושמעון לא ממש רוצה לצאת‬ ‫מהבית‪.‬התקשרתם אליו‪ ,‬ואחרי דברי שכ‪‬וע הוא אמר‪ :‬אם ייפסק הגשם‪) ,‬אז( אבוא אליכם‪.‬‬ ‫‪‬יח שהגשם פסק ושמעון לא בא‪.‬במצב זה ברור ששמעון לא עמד בדיבורו‪.‬ההבטחה שלו‬ ‫התגלתה כשקר‪.‬זה מביא אות‪‬ו לקבוע שכאשר ‪ p‬אמת ו‪ q-‬שקר‪ ,‬הפסוק ‪ p q‬הוא שקר‪.‬‬ ‫‪‬יח שהגשם פסק וששמעון התייצב אצלכם‪.‬במצב זה שמעון עמד בדיבורו‪.‬‬ ‫זה מביא אות‪‬ו לקבוע שכאשר ‪ p‬אמת ו‪ q-‬אמת‪ ,‬הפסוק ‪ p q‬הוא אמת‪.‬‬ ‫כעת ‪‬יח שהגשם לא פסק‪.‬במצב זה שמעון משוחרר מהתחייבות‪.‬משמע‪ ,‬במצב שבו הגשם‬ ‫לא פסק‪ ,‬שמעון יעמוד בדיבורו בין שיגיע אליכם ובין שלא יגיע‪.‬‬ ‫זה מביא אות‪‬ו לקבוע שכאשר ‪ p‬הוא שקר‪ ,‬הפסוק ‪ p q‬הוא אמת‪ ,‬בלי תלות בערך‬ ‫האמת של ‪.q‬‬ ‫ייתכן שחלקכם אי‪‬ו מסכים לכמה מן הקביעות של‪‬ו כאן‪ ,‬ובפרט לקביעה שבשורה השלישית‬ ‫בלוח‪ :‬שמעון אמר "אם ייפסק הגשם‪ ,‬אבוא אליכם"‪.‬יח שהגשם לא פסק וששמעון בכל זאת‬ ‫הגיע‪.‬האם סביר לומר שהוא עמד בדיבורו? מה עם הת‪‬אי שהתייחס להפסקת הגשם? א‪‬ו‬ ‫טוע‪‬ים ששמעון דיבר אמת‪ ,‬וכדי להבהיר זאת ‪‬זכיר שיש בעברית אפשרות להת‪ַ‬יה אחרת‪,‬‬ ‫שבה הפסקת הגשם היא ת‪‬אי הכרחי לבואו של שמעון‪:‬‬ ‫אילו שמעון היה אומר‪ :‬רק אם ייפסק הגשם‪ ,‬אבוא אליכם‪ ,‬פירושו שהתחייב שלא יבוא כל‬ ‫עוד יורד גשם‪.‬‬ ‫אבל שמעון לא אמר זאת‪.‬הוא אמר‪ :‬אם ייפסק הגשם‪ ,‬אבוא אליכם‪.‬‬ ‫‪___--_____-_____--____--_____-__-‬‬ ‫‪15‬‬ ‫מבוא מהיר ללוגיקה‬ ‫אמירה זו‪ ,‬שאין בה "רק אם"‪ ,‬משאירה אותו חופשי מהתחייבות במקרה שהגשם לא פסק‪.‬‬ ‫לסיכום‪:‬‬ ‫הפסוק ‪ p q‬הוא שקר כאשר ‪ p‬הוא אמת ו‪ q-‬הוא שקר‪.‬בכל מקרה אחר‪ p q ,‬הוא‬ ‫אמת‪.‬‬ ‫זהו הפירוש המקובל של "אם‪‬אז‪ "‬בלוגיקה ובמתמטיקה בכלל‪ *.‬כאשר א‪‬ו מדברים‬ ‫וחושבים מתמטיקה‪ ,‬א‪‬ו מחילים פירוש זה גם על מקרים שבהם בשפה המדוברת לא ברור‬ ‫ל‪‬ו מהו ערך האמת של הפסוק‪.‬הסיבה שחשוב ל‪‬ו להפוך את "אם‪ ‬אז‪ַ "‬‬ ‫לקשָּ ר לוגי‬ ‫תתברר יותר בסוף הפרק‪ ,‬בסעיף ‪.11‬‬ ‫‪ ‬שאלה ‪3‬‬ ‫חשבו את ערכי האמת של הפסוקים )*(‪ (***) ,(**) ,‬שבתחילת הסעיף‪.‬‬ ‫התשובה בעמ' ‪38‬‬ ‫ַקשָּ ר לוגי דו‪-‬מקומי ‪‬וסף‪ ,‬שבו מרבים להשתמש במתמטיקה‪ ,‬הוא "אם ורק אם"‪.‬ה‪‬ה לוח‬ ‫האמת שלו‪:‬‬ ‫‪p‬‬ ‫‪q‬‬ ‫‪p  q‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫לוח ‪ :5‬לוח האמת של ‪‬‬ ‫הפסוק ‪ p  q‬הוא אמת כאשר לפסוקים ‪ p,q‬יש אותו ערך אמת‪ ,‬והוא שקר כאשר ערכי‬ ‫האמת של ‪ p,q‬שו‪‬ים זה מזה‪.‬את הביטוי "אם ורק אם" כותבים לעתים בקיצור "אםם"‪.‬‬ ‫בא‪‬גלית מתמטית‪ ,‬הביטוי המקביל הוא ‪ ,if and only if‬והקיצור המקביל לאםם הוא ‪.iff‬‬ ‫בשפת הדיבור‪ ,‬השימוש ב‪"-‬אם ורק אם" אי‪‬ו ‪‬פוץ‪.‬בכל זאת ‪‬דגים‪:‬‬ ‫בשיחה אחרת שמעון הודיע‪ :‬אבוא אליכם אם ורק אם ייפסק הגשם‪.‬‬ ‫* "אם‪ ‬אז‪ "‬שהגדר‪‬ו כאן אי‪‬ו מקביל למב‪‬ה ‪ if then‬המוכר בתכ‪‬וּת‪.‬בתכ‪‬וּת א‪‬ו משתמשים במב‪‬ה‬ ‫כזה‪ :‬אם )ביטוי בוליא‪‬י( אז }בצע סדרת פעולות{‪.‬לעומת זאת‪ ,‬בלוגיקה מדובר בביטוי מהצורה‪ :‬אם ‪ A‬אז‬ ‫‪ ,B‬כאשר הן ‪ A‬והן ‪ B‬הם פסוקים )ביטויים בוליא‪‬יים(‪ ,‬והביטוי כולו מקבל ערך "אמת" או "שקר"‪ ,‬בדומה‬ ‫לכל ביטוי בוליא‪‬י מורכב אחר!‬ ‫בלוגיקה‪ ,‬הביטוי "אם‪ ‬אז‪ "‬הוא ַקשָּ ר לוגי בדיוק כמו ‪.OR , AND‬‬ ‫‪Nir‬‬ ‫‪Yakuti‬‬ ‫‪___--_____-_____--____--_____-__-‬‬  ‫‪File #0004773 belongs to Nir Yakuti- do not distribute‬‬ ‫מתמטיקה בדידה‬ ‫‪16‬‬ ‫יש ש‪‬י מצבים שבהם הוא עומד בדיבורו‪ :‬המצב שבו הגשם פסק ושמעון הגיע‪ ,‬והמצב שבו‬ ‫הגשם לא פסק ושמעון לא הגיע‪.‬בש‪‬י המקרים האחרים שמעון אי‪‬ו עומד בדיבורו‪ ,‬כלומר‬ ‫הפסוק שלו הוא שקר‪.‬‬ ‫הצְָרנ ָה‪.‬פסוקים פורמאליים ולוחות האמת שלהם‬ ‫ַ‬ ‫‪6‬‬ ‫ייצוג טע‪‬ות משפת הדיבור בשפה פורמאלית ‪‬קרא הַ צְ ָר‪ָ‬ה )‪.(Formalization‬‬ ‫עסק‪‬ו בּהַ צְ ָר‪ָ‬ה‪ ,‬בלי לקרוא לה בשם‪ ,‬בפסקאות האחרו‪‬ות של סעיף ‪ 1‬ואילך‪.‬‬ ‫‪ ‬שאלה ‪4‬‬ ‫‪‬סמן‪:‬‬ ‫‪ :q‬הקרנף עף לשמים‪.‬‬ ‫‪ :p‬הקרנף פרש כנפיים‪.‬‬ ‫‪ :s‬העורב עף לשמים‪.‬‬ ‫‪ :r‬העורב פרש כנפיים‪.‬‬ ‫הפסוקים א'‪-‬ו' שלהלן כתובים בשפה מדוברת‪.‬הַ צְ ִרי‪‬וּ אותם‪:‬‬ ‫הקשָּ רים הלוגיים ‪.  ,  , ,  , ‬‬ ‫הביעו אותם בעזרת הסימ‪‬ים ‪ p,q,r,s‬ובעזרת ַ‬ ‫א‪.‬הקרנף פרש כנפיים ועף לשמים‪.‬‬ ‫לשמים‪(3).‬‬ ‫ב‪.‬הקרנף פרש כנפיים אבל לא עף‬ ‫ג‪.‬אם הקרנף עף לשמים‪ ,‬אז הוא פרש כנפיים‪.‬‬ ‫ד‪.‬לפחות אחד משני בעלי‪-‬החיים – הקרנף והעורב – פרש כנפיים‪.‬‬ ‫ה‪.‬אם העורב עף לשמים והקרנף לא‪ ,‬אז העורב פרש כנפיים והקרנף לא‪.‬‬ ‫ו‪.‬לא נכון ש)הקרנף עף לשמים אם ורק אם העורב לא פרש כנפיים ולא עף לשמים(‪.‬‬ ‫הביעו בעברית את הפסוקים הפורמאליים ז'‪ ,‬ח' שלהלן‪:‬‬ ‫ז‪( r  s ) ( p  q ).‬‬ ‫ח‪( p  r )  ( q  s ).‬‬ ‫התשובה בעמ' ‪38‬‬ ‫כדאי לשים לב‪ ,‬שבמקרים רבים דרך ההַ צְ ָר‪ָ‬ה של פסוק ה‪‬תון בשפה מדוברת או בשפה‬ ‫מתמטית אי‪‬ה מוכתבת מראש‪ :‬זכות‪‬ו לייצג בעזרת משת‪‬ה פסוקי בודד כל פסוק‪ ,‬גם אם‬ ‫הוא ‪‬ראה מורכב‪.‬למשל‪ ,‬את הפסוק אכלתי ושתיתי א‪‬ו יכולים לייצג כ‪ , p  q -‬אבל זכות‪‬ו‬ ‫גם לייצג אותו בעזרת משת‪‬ה פסוקי בודד‪ ,‬כגון ‪.r‬הבחירה בדרך הייצוג תלויה בהֶ קשר שבו‬ ‫א‪‬ו פועלים‪.‬אם בדיון שעל הפרק לא ייתכן שעשיתי רק אחת משתי הפעולות ולא את‬ ‫האחרת‪ ,‬יהיה זה סביר בהחלט‪ ,‬עבור אותו דיון‪ ,‬לייצג את הפסוק אכלתי ושתיתי בעזרת‬ ‫משת‪‬ה פסוקי בודד‪.‬‬ ‫לביטוי שמתקבל מהַ צְ ָר‪ָ‬ה של פסוק ‪‬קרא פסוק פוֹרמָ אלי‪.‬למשל‪ ,‬הביטוי ‪ p  q‬הוא פסוק‬ ‫פורמאלי‪(4).‬‬ ‫גם משת‪‬ה פסוקי בודד‪ ,‬כגון הסימן ‪ ,p‬הוא פסוק פורמאלי‪.‬‬ ‫‪___--_____-_____--____--_____-__-‬‬ ‫‪17‬‬ ‫מבוא מהיר ללוגיקה‬ ‫לפסוק פורמאלי המכיל לפחות ַקשָּ ר לוגי אחד ‪‬קרא פסוק פורמאלי מורכב‪.‬‬ ‫ה‪‬ה פסוק פורמאלי מורכב‪:‬‬ ‫)*(‬ ‫) ‪(( p  q )   r ) ( q  r‬‬ ‫בדומה לדיון שבתחילת סעיף ‪) 4‬מהו ַקשָּ ר לוגי(‪ ,‬יח שלא ידועים או לא מוב‪‬ים ל‪‬ו הפסוקים‬ ‫שאותם מייצגים המשת‪‬ים ‪ ,p,q,r‬אבל ידועים ל‪‬ו ערכי האמת שלהם‪.‬מתוך מידע זה ‪‬וכל‬ ‫בקלות לקבוע את ערך האמת של )*(‪ :‬עשה זאת על‪-‬ידי שימוש חוזר בלוחות האמת של‬ ‫הקשָּ רים הלוגיים‪.‬למשל‪ ,‬אם ‪ p‬הוא אמת‪ q ,‬הוא אמת ו‪ r -‬הוא שקר‪ ,‬אז הפסוק )*( הוא אמת‪.‬‬‫ַ‬ ‫לצורך חישוב ערך האמת של )*(‪ ,‬אין זה מש‪‬ה אם ‪‬ציב‪:‬‬ ‫‪2 + 2 = 5 :r‬‬ ‫‪ :q‬גיטרה היא כלי מיתר‪.‬‬ ‫‪ :p‬חצוצרה היא כלי נשיפה‪.‬‬ ‫או אם ‪‬ציב‪:‬‬ ‫‪2 + 2 = 4 :q‬‬ ‫‪ :p‬גיטרה היא כלי מיתר‪.‬‬ ‫‪ :r‬השוער של מכבי חיפה – גובהו חמישה מטרים ועשרים סנטימטרים‪.‬‬ ‫באופן כללי‪ ,‬ערך האמת של פסוק פורמאלי אי‪‬ו תלוי בפירוש של המשת‪‬ים הפסוקיים‬ ‫המופיעים בו אלא רק בערכי האמת שלהם‪ :‬ערך האמת של הפסוק הפורמאלי ‪‬קבע מתוך‬ ‫הקשָּ רים‬ ‫ערכי האמת של המשת‪‬ים הפסוקיים‪ ,‬על‪-‬ידי שימוש חוזר בלוחות האמת של ַ‬ ‫הלוגיים‪.‬‬ ‫ְלפסוּק פורמאלי ‪‬יתן אפוא לב‪‬ות לוח אמת‪.‬לוח האמת של פסוק פורמאלי מפרט את כל‬ ‫הדרכים להקצות ערכי אמת למשת‪‬ים הפסוקיים המופיעים בו; עבור כל דרך כזו‪ ,‬העמודה‬ ‫הימ‪‬ית ביותר בלוח מציגה את ערך האמת שמקבל הפסוק המורכב‪.‬‬ ‫ה‪‬ה לוח האמת של הפסוק הפורמאלי )*(‪:‬‬ ‫‪p‬‬ ‫‪q‬‬ ‫‪r‬‬ ‫‪pq‬‬ ‫‪r‬‬ ‫‪( p  q)   r‬‬ ‫‪qr‬‬ ‫) ‪(( p  q )   r ) ( q  r‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫לוח ‪ :6‬דוגמה ללוח אמת של פסוק מורכב‬ ‫למעשה‪ ,‬לוח האמת של הפסוק הפורמאלי )*( מורכב משלוש העמודות השמאליות והעמודה‬ ‫הימ‪‬ית‪.‬‬ ‫‪Nir‬‬ ‫‪Yakuti‬‬ ‫‪___--_____-_____--____--_____-__-‬‬  ‫‪File #0004773 belongs to Nir Yakuti- do not distribute‬‬ ‫מתמטיקה בדידה‬ ‫‪18‬‬ ‫בשלוש העמודות השמאליות הקצֵ י‪‬ו ערכי אמת למשת‪‬ים‪ ,‬בכל דרך אפשרית‪.‬בעמודה‬ ‫הימ‪‬ית פירט‪‬ו את ערכי האמת המתאימים של הפסוק הפורמאלי )*(‪.‬העמודות שבי‪‬יהן‬ ‫מפרטות כיצד קיבל‪‬ו את העמודה הימ‪‬ית; הן אי‪‬ן ‪‬חשבות חלק מלוח האמת‪ :‬הן החישוב‬ ‫של לוח האמת‪ ,‬ההוכחה של ‪‬כו‪‬ותו‪.‬‬ ‫ללוח המלא‪ ,‬הכולל את עמודות החישוב שבדרך‪ ,‬קרא לוח אמת מורחב‪.‬‬ ‫‪ ‬שאלה ‪5‬‬ ‫א‪.‬רשמו לוח אמת מורחב עבור הפסוק הפורמאלי )) ‪(( p q ) r )  ( r ( q  p‬‬ ‫ב‪.‬כמה שורות יש בלוח האמת של פסוק מורכב הב‪‬וי בעזרת ארבעת המשת‪‬ים הפסוקיים‬ ‫‪?p,q,r,s‬‬ ‫התשובה בעמ' ‪39‬‬ ‫‪ ‬שאלה ‪6‬‬ ‫א‪.‬הראו שבלוח האמת של ) ‪ , ( p q )  ( q p‬העמודה הימ‪‬ית מכילה רק ‪.T‬‬ ‫ב‪.‬הראו שבלוח האמת של ) ‪ , ( p  q )  ( p  q‬העמודה הימ‪‬ית מכילה רק ‪.F‬‬ ‫ג‪.‬הראו שלש‪‬י הפסוקים הפורמאליים ) ‪ ( p  q ) r , p ( q r‬יש אותו לוח אמת‪.‬‬ ‫התשובה בעמ' ‪39‬‬ ‫בסעיף זה הגדר‪‬ו לוח אמת של פסוק פורמאלי‪.‬בסעיפים הקודמים הגדר‪‬ו לוחות אמת של‬ ‫ַקשָּ רים לוגיים‪.‬‬ ‫הקשֶ ר בין ש‪‬י המושגים? למעשה‪ ,‬יתן לחשוב על לוח אמת בשתי דרכים‪ ,‬שו‪‬ות מעט זו‬ ‫מה ֶ‬ ‫מזו‪.‬‬ ‫‪‬תבו‪‬ן למשל בלוח האמת הבא‪:‬‬ ‫‪p‬‬ ‫‪q‬‬ ‫‪q‬‬ ‫‪p q‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫לוח ‪ :7‬לוח אמת של פסוק או של פעולה?‬ ‫זהו לוח אמת של פסוק פורמאלי‪ ,‬אבל אפשר לחשוב עליו גם אחרת‪ :‬הלוח מגדיר פעולה לוגית‬ ‫)אפשר לקרוא לפעולה זו "אם‪ ‬אז לא‪.("‬אילו היה ל‪‬ו ע‪‬יין בכך‪ ,‬יכול‪‬ו לייצג פעולה זו‬ ‫על‪-‬ידי סימן חדש ולצרף אותה לקבוצת ה ַקשָּ רים הלוגיים שבהם א‪‬ו ‪‬עזרים באופן שוטף‪.‬‬ ‫מ‪‬קודת מבט זו‪ ,‬הסימ‪‬ים ‪ q, p‬הם רק "מציי‪‬י מקום" שבהם א‪‬ו ‪‬עזרים כדי לרשום לוח‬ ‫הקשָּ ר הלוגי "אם‪ ‬אז לא‪."‬‬ ‫אמת עבור ַ‬ ‫בדומה‪ ,‬חזור ללוח האמת שבעמוד ‪) 17‬לוח ‪.(6‬הצג‪‬ו אותו כלוח אמת של הפסוק הפורמאלי‬ ‫‪250405503 yakuti1atgmail.com‬‬ ‫‪DAFFAEAFC‬‬ ‫‪19‬‬ ‫מבוא מהיר ללוגיקה‬ ‫)*(‬ ‫) ‪(( p  q )   r ) ( q  r‬‬ ‫באותה מידה א‪‬ו יכולים לחשוב עליו כעל לוח אמת של ַקשָּ ר לוגי תלת‪-‬מקומי‪.‬‬ ‫מובן שזהו המצב לגבי כל פסוק פורמאלי ולגבי כל לוח אמת‪:‬‬ ‫אבחנה‬ ‫פסוק פורמאלי שמופיעים בו בדיוק ‪ n‬משת‪‬ים פסוקיים – אפשר לראות אותו כ ַקשָּ ר לוגי‬ ‫‪-n‬מקומי‪).‬ולוח אמת של פסוק כזה אפשר לראות כלוח אמת של ַקשָּ ר לוגי‬ ‫‪-n‬מקומי‪(5) (.‬‬ ‫לסיום הסעיף – הבהרה קצרה‪:‬‬ ‫לוחות אמת ‪‬כתבים עבור פסוקים פורמאליים‪ ,‬הכתובים בעזרת משת‪‬ים פסוקיים‪.‬‬ ‫לא ‪‬כתוב לוחות אמת עבור פסוקים ש‪‬תו‪‬ים במפורש‪.‬‬ ‫למשל‪ ,‬אין טעם בלוח אמת עבור הפסוק ‪ 1 + 1 = 2‬או ‪. 4 < 6‬‬ ‫זה מובן ובכל זאת ‪‬סביר‪ ,‬כי לחוסר הטעם יש שתי סיבות‪:‬‬ ‫ראשית‪ ,‬במקרה שלפ‪‬י‪‬ו ערכי האמת של ש‪‬י הרכיבים ידועים‪ ,‬כך שאין תועלת בלוח‬ ‫שמתייחס לאפשרויות אחרות‪.‬ש‪‬ית‪ ,‬אף שא‪‬ו ‪‬וטים להתייחס אל הפסוק ‪ 1 + 1 = 2‬או‬ ‫‪ 4 < 6‬כמורכב מש‪‬י פסוקים )א‪‬ו ‪‬וטים להצרין אותו כ‪ ,( p  q -‬באותה מידה זכות‪‬ו‪ ,‬אם‬ ‫ההֶ קשר שבו א‪‬ו עוסקים מתאים לכך‪ ,‬להתייחס אל הפסוק כולו כאל טע‪‬ה אחת )זכות‪‬ו‬ ‫להצרין אותו באות בודדת‪ ,‬למשל ‪.(p‬‬ ‫ההחלטה על דרך הפירוק של פסוק למרכיביו היא חיו‪‬ית‪ ,‬לצורך קביעת לוח אמת‪.‬בפסוק‬ ‫פורמאלי‪ ,‬קיימת חלוקה למרכיבים‪ ,‬ואין צורך במידע ‪‬וסף‪ :‬מרכיביו של פסוק פורמאלי הם‬ ‫המשת‪‬ים הפסוקיים‪.‬לעומת זאת‪ ,‬בפסוק מפורש‪ ,‬חלוקה למרכיבים היא בגדר מידע ‪‬וסף‪,‬‬ ‫שאי‪‬ו גלום בתוך הפסוק עצמו‪.‬‬ ‫טאוטולוגיה וסתירה‪.‬שקילוּת בין פסוקים‬ ‫‪7‬‬ ‫הגדרה ‪ :1‬טאוטולוגיה וסתירה‬ ‫א‪.‬פסוק פורמאלי שהעמודה הימ‪‬ית בלוח האמת שלו מכילה רק ‪ T‬קרא טאוטולוגיה‬ ‫)‪.(Tautology‬‬ ‫ב‪.‬פסוק פורמאלי שהעמודה הימ‪‬ית בלוח האמת שלו מכילה רק ‪ F‬קרא סתירה‬ ‫)‪.(Contradiction‬‬ ‫טאוטולוגיה היא אפוא פסוק פורמאלי‪ ,‬שהצבה של פסוקים כלשהם‪ ,‬בשפה המדוברת או‬ ‫המתמטית‪ ,‬במקום המשת‪‬ים הפסוקיים שבו‪ ,‬תיתן תמיד פסוק אמת‪.‬סתירה היא פסוק‬ ‫פורמאלי‪ ,‬שהצבה של פסוקים כלשהם‪ ,‬בשפה המדוברת או המתמטית‪ ,‬במקום המשת‪‬ים‬ ‫הפסוקיים שבו‪ ,‬תיתן תמיד פסוק שקר‪.‬‬ ‫‪Nir‬‬ ‫‪Yakuti‬‬ ‫‪___--_____-_____--____--_____-__-‬‬  ‫‪File #0004773 belongs to Nir Yakuti- do not distribute‬‬ ‫מתמטיקה בדידה‬ ‫‪20‬‬ ‫דוגמאות‬ ‫בשאלה ‪ ,6‬טע‪‬ת סעיף א' היא שהפסוק הפורמאלי ) ‪ ( p q )  ( q p‬הוא טאוטולוגיה‪.‬‬ ‫טע‪‬ת סעיף ב' של אותה שאלה היא שהפסוק הפורמאלי )) ‪ ( p  q )  ( p ( q‬הוא‬ ‫סתירה‪.‬‬ ‫‪ ‬שאלה ‪7‬‬ ‫הוכיחו‪ p  (  p ) :‬הוא טאוטולוגיה‪.‬‬ ‫א‪.‬‬ ‫הוכיחו‪ p  (  p ) :‬הוא סתירה‪.‬‬ ‫ב‪.‬‬ ‫הוכיחו‪ p p :‬הוא טאוטולוגיה‪.‬‬ ‫ג‪.‬‬ ‫האם ) ‪ p (  p‬הוא טאוטולוגיה? האם הוא סתירה?‬ ‫ד‪.‬‬ ‫התשובה בעמ' ‪40‬‬ ‫‪‬ציג מושג ‪‬וסף‪:‬‬ ‫שקילוּת טַ אוּטוֹלוֹגִ ית )ההגדרה הבאה היא הגדרה זמ‪‬ית‪.‬וסח סופי של ההגדרה – בהמשך(‪:‬‬ ‫ש‪‬י פסוקים פורמאליים ‪‬קראים שקולים טַ אוּטוֹלוֹגִ ית‪ ,‬ובקיצור– שקולים‪ ,‬אם יש להם אותו‬ ‫לוח אמת‪.‬‬ ‫דוגמאות‬ ‫בשאלה ‪6‬ג ראי‪‬ו שהפסוק הפורמאלי ) ‪ p ( q r‬שקול לפסוק הפורמאלי ‪. ( p  q ) r‬‬ ‫בעמודים האחרו‪‬ים הקפד‪‬ו להשתמש בביטוי "פסוק פורמאלי"‪ ,‬כדי להדגיש את ההבדל‬ ‫בי‪‬ו לבין פירושיו האפשריים‪ ,‬שהם פסוקים בשפה טבעית או במתמטיקה‪.‬מכאן ואילך‬ ‫‪‬רשה לעצמ‪‬ו לעתים לקצר ולכתוב "פסוק" גם כאשר מדובר בפסוק פורמאלי כגון‬ ‫‪. p  q‬עשה זאת רק כאשר יהיה ברור מתוך ההֶ קשר שמדובר בפסוק פורמאלי‪.‬‬ ‫‪ ‬שאלה ‪8‬‬ ‫‪‬‬ ‫א‪.‬הוכיחו שהפסוק ‪  p‬שקול לפסוק ‪.p‬‬ ‫ב‪.‬הוכיחו שהפסוק ‪ p q‬שקול לפסוק ) ‪ , ( p   q‬ושש‪‬יהם שקולים לפסוק ‪( p )  q‬‬ ‫ג‪.‬הוכיחו שהפסוק ) ‪ ( p q‬אי‪‬ו שקול לפסוק ‪) p  q‬המחשבה המוטעית שש‪‬י‬ ‫פסוקים אלה שקולים זה לזה היא מקור ידוע לבלבול אצל סטוד‪‬טים בראשית דרכם(‪.‬‬ ‫התשובה בעמ' ‪40‬‬ ‫אף שההגדרה הזמ‪‬ית ש‪‬ת‪‬ו לשקילוּת היא הגדרה טבעית מאוד‪ ,‬עדיף להרחיב אותה מעט‪.‬‬ ‫כדי להבין מדוע‪ ,‬תבו‪‬ן בפסוק ‪. q   p  ( p ) ‬‬ ‫‪___--_____-_____--____--_____-__-‬‬ ‫‪21‬‬ ‫מבוא מהיר ללוגיקה‬ ‫כידוע ל‪‬ו משאלה ‪7‬א‪ p  (  p ) ,‬הוא טאוטולוגיה‪.‬מכאן לא קשה לראות‬ ‫ש‪ q   p  ( p )  -‬הוא אמת אם ‪ q‬אמת‪ ,‬ושקר – אם ‪ q‬שקר‪.‬במילים אחרות‪ ,‬ערך האמת‬ ‫של ‪ q   p  ( p ) ‬שווה תמיד לערך האמת של ‪.q‬היי‪‬ו רוצים לומר ש‪q   p  ( p )  -‬‬ ‫שקול ל‪.q-‬ההגדרה הזמ‪‬ית של שקילוּת אי‪‬ה מאפשרת ל‪‬ו לומר זאת‪ ,‬כי‬ ‫ל‪ q   p  ( p )  -‬לוח אמת של ארבע שורות‪ ,‬ולפסוק ‪ q‬לוח אמת של שתי שורות בלבד‪.‬כדי‬ ‫לאפשר השוואה בין פסוקים אף‪-‬על‪-‬פי שהמשת‪‬ים הפסוקיים המופיעים בהם שו‪‬ים‪ ,‬שפר‬ ‫את ההגדרה של שקילות‪.‬‬ ‫הגדרה ‪ :2‬שקילוּת טַאוּטוֹלוֹג ִית‬ ‫בהי‪‬תן ש‪‬י פסוקים פורמאליים‪ ,‬ב‪‬ה לוח אמת מאוחד‪ ,‬המכיל את כל המשת‪‬ים הפסוקיים‬ ‫המופיעים לפחות באחד מש‪‬י הפסוקים‪.‬זוג פסוקים פורמאליים שיש להם אותו לוח אמת‬ ‫מאוחד ‪‬קראים שקולים טאוטולוגית‪ ,‬ובקיצור – שקולים‪.‬‬ ‫דוגמאות‬ ‫השוואת העמודה הש‪‬ייה משמאל לעמודה הימ‪‬ית בלוח שלהלן מראה כי ‪q   p  ( p ) ‬‬ ‫שקול ל‪:q-‬‬ ‫‪p‬‬ ‫‪q‬‬ ‫) ‪p  ( p‬‬ ‫‪q   p  ( p ) ‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫לוח ‪8‬‬ ‫בלוח האמת הבא‪ ,‬השוואה של עמודה ‪ 6‬לעמודה ‪ 8‬מראה כי הפסוק ‪p   q ( r  ( r )) ‬‬ ‫שקול לפסוק ) ‪: p  (  q‬‬ ‫‪1‬‬ ‫‪2‬‬ ‫‪3‬‬ ‫‪4‬‬ ‫‪5‬‬ ‫‪6‬‬ ‫‪7‬‬ ‫‪8‬‬ ‫‪p‬‬ ‫‪q‬‬ ‫‪r‬‬ ‫) ‪r  ( r‬‬ ‫)) ‪q ( r  ( r‬‬ ‫‪p   q ( r  (  r )) ‬‬ ‫‪q‬‬ ‫) ‪p  ( q‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫‪T‬‬ ‫‪F‬‬ ‫לוח ‪9‬‬ ‫‪Nir‬‬ ‫‪Yakuti‬‬ ‫‪___--_____-_____--____--_____-__-‬‬  ‫‪File #0004773 belongs to Nir Yakuti- do not distribute‬‬ ‫מתמטיקה בדידה‬ ‫‪22‬‬ ‫‪ ‬שאלה ‪9‬‬ ‫א‪.‬הוכיחו שכל שתי טאוטולוגיות שקולות זו לזו‪.‬‬ ‫ב‪.‬הוכיחו שכל שתי סתירות שקולות זו לזו‪.‬‬ ‫התשובה בעמ' ‪40‬‬ ‫להבדיל מלוחות אמת )ראו הדיון בסוף סעיף ‪ ,(5‬את המושגים טאוטולוגיה‪ ,‬סתירה ושקילוּת‬ ‫טאוטולוגית ‪‬יתן ליישם גם עבור פסוקים ה‪‬תו‪‬ים במפורש‪ ,‬בשפה טבעית או בשפה‬ ‫מתמטית‪:‬‬ ‫פסוק בשפה טבעית או מתמטית ‪‬קרא טאוטולוגיה‪ ,‬אם ‪‬יתן להצרין אותו לפסוק פורמאלי‬ ‫שהוא טאוטולוגיה‪.‬כך גם לגבי סתירה‪.‬למשל‪,‬‬ ‫הוא טאוטולוגיה‪ :‬ראו שאלה ‪7‬א‪.‬‬ ‫הפסוק ניצחנו במשחק או לא ניצחנו במשחק‬ ‫הפסוק ניצחנו במשחק וגם לא ניצחנו במשחק הוא סתירה‪ :‬ראו שאלה ‪7‬ב‪.‬‬ ‫לעומת זאת‪ ,‬הפסוק ניצחנו במשחק וגם הירח עשוי גבינה צהובה הוא שקר אבל אי‪‬ו סתירה‪.‬‬ ‫על זוג פסוקים בשפה טבעית או בשפה מתמטית ‪‬אמר שהם שקולים טאוטולוגית )בקיצור–‬ ‫שקולים(‪ ,‬אם ‪‬יתן להצרין את ש‪‬יהם יחד לזוג פסוקים פורמאליים השקולים טאוטולוגית‪.‬‬ ‫למשל‪,‬‬ ‫הפסוק‪ :‬אם הכלב נובח – החתול בורח‬ ‫והפסוק‪ :‬לא ייתכן ש‪)-‬הכלב נובח והחתול אינו בורח(‬ ‫שקולים טאוטולוגית‪ :‬ראו שאלה ‪8‬ב )א‪‬ו מפרשים את "לא ייתכן ש‪ "-‬כשלילה(‪.‬‬ ‫‪ ‬שאלה ‪ :10‬כללי דה–מורגן‬ ‫בשאלה זו ‪‬כיר שתי שקילויות שימושיות‪.‬‬ ‫א‪.‬תבו‪‬ן בטע‪‬ות שלהלן‪:‬‬ ‫)‪ (i‬סנונית אפריקאית מסוגלת לסחוב במעופה אגוז קוקוס‪ ,‬וגם סנונית אירופית מסוגלת‬ ‫לעשות זאת‪.‬‬ ‫)‪ (ii‬טענה )‪ (i‬אינה נכונה!‬ ‫)‪ (iii‬לפחות אחת משתי הסנוניות – האפריקאית או האירופית – אינה מסוגלת לסחוב‬ ‫במעופה אגוז קוקוס‪.‬‬ ‫הַ צרי‪‬ו את שלוש הטע‪‬ות תוך שימוש בש‪‬י משת‪‬ים פסוקיים בלבד‪.‬‬ ‫הראו בעזרת לוחות אמת שטע‪‬ה )‪ (ii‬שקולה לטע‪‬ה )‪.(iii‬‬ ‫ב‪.‬תבו‪‬ן בטע‪‬ות שלהלן‪:‬‬ ‫)‪ (iv‬מהירות התעופה של סנונית אפריקאית היא ‪ 20‬קשר או ‪ 30‬קשר‪.‬‬ ‫)‪ (v‬טענה )‪ (iv‬אינה נכונה!‬ ‫)‪ (vi‬מהירות התעופה של סנונית אפריקאית אינה ‪ 20‬קשר ואינה ‪ 30‬קשר‪.‬‬ ‫הַ צרי‪‬ו את שלוש הטע‪‬ות תוך שימוש בש‪‬י משת‪‬ים פסוקיים בלבד‪.‬‬ ‫הראו בעזרת לוחות אמת שטע‪‬ה )‪ (v‬שקולה לטע‪‬ה )‪.(vi‬‬ ‫‪___--_____-_____--____--_____-__-‬‬ ‫‪23‬‬ ‫מבוא מהיר ללוגיקה‬ ‫תשובה ‪) 10‬פתרון חלקי(‬ ‫א‪.‬בהתאם לדיון שלפ‪‬י השאלה‪ ,‬כדי להראות שהטע‪‬ות )‪ (iii) ,(ii‬שקולות זו לזו‪ ,‬צרין אותן‬ ‫ו‪‬וכיח שהפסוקים הפורמאליים המתקבלים שקולים זה לזה‪.‬סמן אפוא‪:‬‬ ‫‪ :p‬סנונית אפריקאית מסוגלת לסחוב במעופה אגוז קוקוס‪.‬‬ ‫‪ :q‬סנונית אירופית מסוגלת לסחוב במעופה אגוז קוקוס‪.‬‬ ‫‪‬צרין את הטע‪‬ות המילוליות שבשאלה‪:‬‬ ‫)‪. (  p )  (  q ) (iii‬‬ ‫)‪( p  q ) (ii‬‬ ‫) ‪p  q (i‬‬ ‫פתרון יתר הסעיפים מופיע בסעיף ‪.12‬‬ ‫תשובה בעמ' ‪41‬‬ ‫הדיון מכאן עד לסוף סעיף ‪ 7‬עוסק בהצבה של פסוקים פורמאליים מורכבים במקום משת‪‬ים‬ ‫פסוקיים‪ ,‬בתוך פסוק פורמאלי‪.‬יישום מעשי של כללי הלוגיקה‪ ,‬שהוא היעד של‪‬ו במבוא זה‪,‬‬ ‫אי‪‬ו דורש הצבות כאלו )‪ ,(6‬ולכן דיון זה הוא בגדר חומר רשות‪.‬ה‪‬ושא יידון שוב בקצרה‪,‬‬ ‫כחומר רשות‪ ,‬גם בהמשך הפרק‪.‬‬ ‫דיון קצר על הצבה‬ ‫‪‬תבו‪‬ן בטאוטולוגיה כלשהי‪ ,‬כגון ) ‪. p  (  p‬כזכור‪ p ,‬מייצג פסוק כלשהו בשפה המדוברת‬ ‫או בשפה המתמטית‪.‬פרש את ‪ p‬כפסוק היום חם ולח‪.‬הטאוטולוגיה ) ‪ p  (  p‬הופכת בכך‬ ‫לאמירה חסרת תועלת על מזג האוויר‪.‬צרין את האמירה על מזג האוויר מחדש‪ ,‬כאשר הפעם‬ ‫‪‬פרק את היום חם ולח למרכיביו‪ :‬היום חם‪ ,‬היום לח‪.‬ייצג אפוא את היום חם ולח כ‪. q  r -‬‬ ‫במקום ) ‪ p  (  p‬קבל את הפסוק הפורמאלי ) ‪. ( q  r )  ( q  r‬‬ ‫את התהליך הזה ‪‬יתן לעשות גם בלי לעבור דרך השפה המדוברת‪:‬‬ ‫בפסוק הפורמאלי ) ‪ p  (  p‬ציב במקום המשת‪‬ה הפסוקי ‪ p‬את ‪ , q  r‬ו‪‬קבל את הפסוק‬ ‫הפורמאלי ) ‪. ( q  r )  ( q  r‬‬ ‫טע‪‬ה‪ :‬הצבה בטאוטולוגיה ‪‬ות‪‬ת טאוטולוגיה‪.‬הצבה בסתירה ‪‬ות‪‬ת סתירה‪.‬‬ ‫הוכחה מלאה של טע‪‬ה זו דורשת עיסוק מפורט במושג "הצבה" )המוכר היטב בצורה‬ ‫אי‪‬טואיטיבית מימי בית‪-‬הספר(‪.‬לא ‪‬וכיח אותה‪ ,‬כי כאמור ה‪‬ושא אי‪‬ו ‪‬כלל בחומר הלימוד‬ ‫של הקורס‪.‬בכל זאת‪ ,‬יתן ‪‬ימוק קצר‪ ,‬ש‪‬יתן להרחיב אותו להוכחה מלאה‪:‬‬ ‫בהי‪‬תן טאוטולוגיה כלשהי‪ ,‬ש‪‬ה את ‪‬קודת המבט ו‪‬חשוב עליה כעל ַקשָּ ר לוגי )ראו‬ ‫"אבח‪‬ה" בסעיף ‪.(6‬לפ‪‬י‪‬ו ַקשָּ ר לוגי המחזיר תמיד ערך ‪ ,T‬בלי תלות בערכים ש‪‬מסרים לו‪.‬‬ ‫‪‬וכל להפעיל את ה ַקשָּ ר הלוגי הזה על פסוקים פורמאליים כלשהם‪ ,‬מורכבים ככל ש‪‬רצה –‬ ‫הוא מחזיר תמיד ‪.T‬הפעלה של ה ַקשָּ ר הזה על פסוקים פורמאליים כלשהם מתבצעת על‪-‬ידי‬ ‫הצבה שלהם בטאוטולוגיה ה‪‬תו‪‬ה‪.‬מכיוון שערך האמת המתקבל הוא תמיד ‪ ,T‬הרי כל פסוק‬ ‫המתקבל מהטאוטולוגיה ה‪‬תו‪‬ה על‪-‬ידי הצבה הוא טאוטולוגיה‪.‬‬ ‫ההוכחה לגבי סתירה מקבילה לגמרי‪ ,‬כאשר במקום ‪ T‬מופיע בכל מקום ‪.F‬‬ ‫‪Nir‬‬ ‫‪Yakuti‬‬ ‫‪___--_____-_____--____--_____-__-‬‬  ‫‪File #0004773 belongs to Nir Yakuti- do not distribute‬‬ ‫מתמטיקה בדידה‬ ‫‪24‬‬ ‫טענות שימושיות‬ ‫‪8‬‬ ‫משפט ‪ 1‬טאוטולוגיות וסתירות שימושיות‬ ‫תהי ‪ t‬טאוטולוגיה כלשהי ותהי ‪ f‬סתירה כלשהי‪.‬‬ ‫א‪.‬הפסוקים שלהלן הם טאוטולוגיות‪:‬‬ ‫‪. p t , f p , p  ( p ) , p  p , p p‬‬ ‫ב‪.‬הפסוקים שלהלן הם סתירות‪:‬‬ ‫) ‪. t f , p  ( p ) , p  ( p‬‬ ‫ג‪.‬שלילת טאוטולוגיה היא סתירה‪ ,‬שלילת סתירה היא טאוטולוגיה‪.‬‬ ‫‪ ‬שאלה ‪11‬‬ ‫הוכיחו את משפט ‪.1‬‬ ‫תשובה ‪11‬‬ ‫א‪.‬לפי לוח האמת של חץ‪ ,‬בין שערך האמת של ‪ p‬הוא ‪ T‬ובין שערך האמת שלו הוא ‪ ,F‬ערך‬ ‫האמת של ‪ p p‬הוא ‪.T‬לכן ‪ p p‬הוא טאוטולוגיה‪.‬‬ ‫כך גם לגבי ‪. p  p‬‬ ‫לגבי ‪ : f p‬מכיוון ש‪ f -‬הוא סתירה‪ ,‬ערך האמת שלו בכל מצב הוא ‪.F‬לפי לוח האמת‬ ‫של חץ‪ ,‬יוצא מכך שערך האמת של ‪ f p‬הוא ‪ ,T‬ללא תלות בערך האמת של ‪.p‬‬ ‫ההוכחה לגבי ‪ p t‬דומה‪.‬‬ ‫ב‪.‬ההוכחה קלה ודומה להוכחת סעיף א'‪.‬‬ ‫‪‬‬ ‫ג‪.‬ובע מיידית מהגדרת טאוטולוגיה‪ ,‬מהגדרת סתירה ומלוח האמת של ‪. ‬‬ ‫משפט ‪ 2‬שקילויות שימושיות‬ ‫הסימן ‪ ‬מציין שהפסוקים שמש‪‬י צדיו שקולים זה לזה‪.‬‬ ‫א‪.‬שלילה כפולה‪ p  p :‬‬ ‫‪pq  q p‬‬ ‫ב‪.‬חילוף‪:‬‬ ‫‪pq  q p‬‬ ‫) ‪( p  q )  r  p  (q  r‬‬ ‫ג‪.‬קיבוץ‪:‬‬ ‫) ‪( p  q )  r  p  (q  r‬‬ ‫) ‪p  (q  r )  ( p  q )  ( p  r‬‬ ‫ד‪.‬פילוג‪:‬‬ ‫) ‪p  (q  r )  ( p  q )  ( p  r‬‬ ‫ה‪.‬כללי דה‪-‬מורגן‪( p  q )  ( p )  (  q ) :‬‬ ‫) ‪( p  q )  ( p )  (  q‬‬ ‫) ‪p q  ( q ) ( p‬‬ ‫ו‪.‬עקרון ה‪:contrapositive-‬‬ ‫ז‪.‬הבעת חץ בעזרת ַקשָּ רים אחרים‪p q  ( p  (  q ))  (  p )  q :‬‬ ‫‪___--_____-_____--____--_____-__-‬‬ ‫‪25‬‬ ‫מבוא מהיר ללוגיקה‬ ‫ח‪.‬שקילויות עבור חץ כפול‪:‬‬ ‫)) ‪p  q  q  p  ( p q )  ( q p )  ( p  q )  (( p )  ( q‬‬ ‫‪p f  f‬‬ ‫‪pt  p‬‬ ‫ט‪p  p  p.‬‬ ‫‪p f  p‬‬ ‫‪pt  t‬‬ ‫‪p p  p‬‬ ‫י‪p ( q r )  ( p  q ) r.‬‬ ‫‪ ‬שאלה ‪12‬‬ ‫הוכיחו את משפט ‪.2‬‬ ‫תשובה ‪) 12‬פתרון חלקי(‬ ‫א‪.‬הוכח‪‬ו זאת בשאלה ‪8‬א‪.‬‬ ‫ב‪.‬ובע מיידית מלוחות האמת של ‪.  , ‬‬ ‫ג‪ (i).‬ל‪ ( p  q )  r -‬ול‪ p  ( q  r ) -‬יש אותו לוח אמת‪ :‬ש‪‬יהם מקבלים ערך ‪ T‬כאשר‬ ‫‪ – p,q,r‬שלושתם אמת‪ ,‬וש‪‬יהם מקבלים ‪ F‬בכל שאר השורות בלוח‪.‬‬ ‫)‪ (ii‬ל‪ ( p  q )  r -‬ול‪ p  ( q  r ) -‬יש אותו לוח אמת‪ :‬ש‪‬יהם מקבלים ערך ‪ F‬כאשר‬ ‫‪ – p,q,r‬שלושתם שקר‪ ,‬וש‪‬יהם מקבלים ‪ T‬בכל שאר השורות בלוח‪.‬‬ ‫ד‪.‬בעזרת לוח אמת של ‪ 8‬שורות )פירוט בסעיף ‪.(12‬‬ ‫ה‪.‬הוכח‪‬ו זאת במהלך פתרון שאלה ‪.10‬‬ ‫ו‪.‬בעזרת לוח אמת של ‪ 4‬שורות )פירוט בסעיף ‪.(12‬‬ ‫ז‪.‬הוכח‪‬ו זאת בשאלה ‪8‬ב‪.‬‬ ‫ח‪.‬בעזרת לוח אמת של ‪ 4‬שורות )פירוט בסעיף ‪.(12‬‬ ‫ט‪.‬ובע מיידית בעזרת שיקול מילולי פשוט )פירוט בסעיף ‪.(12‬‬ ‫י‪.‬הוכח‪‬ו זאת בשאלה ‪6‬ג‪.‬‬ ‫התשובה בעמ' ‪41‬‬ ‫‪‬‬ ‫‪ ‬שאלה ‪13‬‬ ‫מיי‪‬ו את הפסוקים הבאים לקבוצות‪ ,‬כך שבכל קבוצה יהיו רק פסוקים השקולים זה לזה‪,‬‬ ‫וכך שפסוקים מקבוצות שו‪‬ות לא יהיו שקולים זה לזה‪.‬‬ ‫א‪.‬אם תרצי תפוח זהב – בפרדס אשב עד הסתיו‪.‬‬ ‫ב‪.‬אם לא תרצי תפוח זהב – לא אשב בפרדס עד הסתיו‪.‬‬ ‫ג‪.‬אם לא אשב בפרדס עד הסתיו‪ ,‬זה אומר שלא תרצי )לא רצית( תפוח זהב‪.‬‬ ‫ד‪.‬אם אשב בפרדס עד הסתיו – ודאי תרצי תפוח זהב‪.‬‬ ‫ה‪.‬בפרדס אשב עד הסתיו או שלא תרצי תפוח זהב‪.‬‬ ‫ו‪.‬לא ייתכן ש‪) -‬תרצי תפוח זהב ואני לא אשב בפרדס עד הסתיו(‪.‬‬ ‫ז‪.‬לא ייתכן ש‪) -‬אשב בפרדס עד הסתיו ואת לא תרצי תפוח זהב(‪.‬‬ ‫ח‪.‬ודאי תרצי תפוח זהב‪ ,‬אבל אני לא אשב בפרדס עד הסתיו‪.‬‬ ‫‪Nir‬‬ ‫‪Yakuti‬‬ ‫‪___--_____-_____--____--_____-__-‬‬  ‫‪File #0004773 belongs to Nir Yakuti- do not distribute‬‬ ‫מתמטיקה בדידה‬ ‫‪26‬‬ ‫ט‪.‬אשב בפרדס עד הסתיו או לא אשב בפרדס עד הסתיו‪.‬‬ ‫י‪.‬בין שתרצי תפוח זהב ובין שלא‪ ,‬אשב בפרדס עד הסתיו‪.‬‬ ‫י"א‪.‬אשב בפרדס עד הסתיו !‬ ‫התשובה בעמ' ‪43‬‬ ‫משפט ‪3‬‬ ‫‪ , ‬שקולים טאוטולוגית זה לזה אם ורק אם ‪   ‬הוא‬ ‫הפסוקים הפורמאליים‬ ‫טאוטולוגיה‪.‬‬ ‫הוכחה‬ ‫כמות הביטויים ממשפחת "אם ורק אם" בטע‪‬ה זו )"שקולים"‪" ,‬אם ורק אם"‪ ( "  " ,‬עשויה‬ ‫לבלבל‪.‬ביטויים אלה שייכים לרמות דיון שו‪‬ות‪.‬כדי להבהיר את משפט ‪ 3‬וכדי לגשת להוכחה‬ ‫שלו‪ ,‬סח אותו ביתר פירוט בעזרת ההגדרה של שקילוּת טאוטולוג?