מתמטיקה בדידה - מבוא מהיר ללוגיקה - 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‬‬