מבוא מהיר ללוגיקה PDF
Document Details
Uploaded by CelebratoryHill
האוניברסיטה הפתוחה
2021
איתי הראבן
Tags
Summary
This document, a chapter on discrete mathematics, provides a brief introduction to logic. It covers propositions, truth values, and logical operators. The document is a textbook, focused on mathematical logic for undergraduate-level students at a specific university.
Full Transcript
מתמטיקה בדידה מבוא מהיר ללוגיקה איתי הראבן מהדורה פנימית לא להפצה ולא למכירה מק”ט 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 pq 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 pq 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 pq r ( p q) r qr ) (( 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 : pq q p ב.חילוף: pq 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 pt p טp p p. p f p pt 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וכדי לגשת להוכחה שלו ,סח אותו ביתר פירוט בעזרת ההגדרה של שקילוּת טאוטולוג?