לדלג לתוכן
שינוי מצב סרגל צד
Math-Wiki
חיפוש
יצירת חשבון
כלים אישיים
יצירת חשבון
כניסה לחשבון
דפים לעורכים שלא נכנסו לחשבון
מידע נוסף
שיחה
תרומות
ניווט
עמוד ראשי
שינויים אחרונים
העלאת קובץ
כלים
דפים המקושרים לכאן
שינויים בדפים המקושרים
דפים מיוחדים
מידע על הדף
עריכת הדף "
88-101 חשיבה מתמטית - לוגיקה פסוקית
" (פסקה)
דף
שיחה
עברית
קריאה
עריכה
גרסאות קודמות
עוד
קריאה
עריכה
גרסאות קודמות
אזהרה:
אינכם מחוברים לחשבון. כתובת ה־IP שלכם תוצג בפומבי אם תבצעו עריכות כלשהן. אם
תיכנסו לחשבון
או
תיצרו חשבון
, העריכות שלכם תיוחסנה לשם המשתמש שלכם ותקבלו גם יתרונות אחרים.
בדיקת אנטי־ספאם.
אין
למלא שדה זה!
== הקשרים הלוגיים == '''קשר''' הוא פונקציה לוגית המחברת כמה אטומים. יש כמה קשרים חשובים. הדרך הפשוטה ביותר לתאור של קשר היא באמצעות '''טבלת האמת''' שלו, המציינת את ערך האמת של הקשר, לפי ערכי האמת של האטומים המרכיבים אותו. בהמשך נדון בטבלאות אמת של פסוקים מורכבים יותר. 1. '''וגם'''. אפשר לומר משפטים כמו "התפוח הזה אדום, וגם הצלחת ירוקה", שההצרנה שלהם היא במבנה "A וגם B". אי אפשר לומר "התפוח הזה אדום וגם", משום ש"וגם" הוא '''קשר בינארי''' - הוא מחבר שני אטומים. ערך האמת של הפסוק "A וגם B" הוא T, רק כאשר גם A וגם B הם T. בכל מקרה אחר, ערך האמת הוא F. {| border="1" align="center" style="text-align:center;" |P |Q |P <math>\and</math> Q |- |T |T |T |- |T |F |F |- |F |T |F |- |F |F |F |} '''דוגמא'''. כשפוליטיקאי מבטיח "לא נעלה מסים וגם נגדיל את ההוצאה לחינוך" (שצורתו "(לא A) וגם B"), הוא יצטרך לקיים שתי הבטחות: גם לא A, וגם B. 2. '''לא'''. כבר פגשנו את קשר השלילה, '''לא''', שהוא ה'''קשר האונארי''' היחיד (קשר אונארי הוא קשר המטפל באטום אחד). הפסוק המתקבל משלילת A הוא, כמובן, "לא A"; ערך האמת שלו הפוך לזה של A: אם "יבוא שוטר" הוא פסוק אמיתי, אז "לא יבוא שוטר" הוא פסוק שקרי, ולהיפך. 3. קשר נוסף הוא '''או''': גם הוא קשר בינארי, המאפשר לבנות את הפסוק "A או B". פסוק כזה מקבל ערך אמת T אם לפחות אחת ההצהרות קיבלה ערך אמת T. ה"או" המתמטי הוא "או במובן החלש" - "תפוח או בננה" פירושו תפוח, או בננה, או שניהם. בשפה העברית אומרים "או תפוח או בננה" כדי להדגיש שמדובר באפשרות זו או אחרת, אבל לא בשתיהן יחד - זהו "או מוציא", הקרוי בשפות המחשב xor = exclusive or. {| border="1" align="center" style="text-align:center;" |P |Q |P <math>\or</math> Q |- |T |T |T |- |T |F |T |- |F |T |T |- |F |F |F |} '''דוגמא'''. כשפוליטיקאי מבטיח "לא נעלה מסים, או שנגדיל את ההוצאה לחינוך" (שצורתו "(לא A) או B"), הוא יוכל להסתפק בקיום אחת ההבטחות. '''תרגיל'''. בפעם הבאה שמלצר שואל "מה תרצה, אדוני, שניצל או עוף", השיבו "כן, בדיוק, תודה רבה", והסבירו את ההבדל בין או במובן החלש לאו מוציא. אירזו את חפציכם במהירות והמתינו בסבלנות לאנשי הבטחון. 4. הקשר '''אם-אז''' בונה משפטים כמו "אם נגדיל את ההוצאה לחינוך, נעלה מסים": "אם A אז B". אם ערך האמת של A הוא T, אז ערך האמת של "אם A אז B" שווה לערך האמת של B: אם מבטיחים, ההצהרה "אם הבטחתי אז אקיים" נכונה אם אקיים, ולא נכונה אם לא אקיים. לעומת זאת, אם לא הבטחתי, ההצהרה נכונה בכל מקרה: כשערך האמת של A הוא F, ערך האמת של "אם A אז B" הוא T בלי קשר לערך האמת של B. במקרה זה אומרים שהפסוק "אם A אז B" '''נכון באופן ריק''' (כלומר, הוא נכון, אבל אינו נושא שום אינפורמציה על המסקנה, משום שההנחה אינה נכונה). זהו הסכם חשוב, גם אם קצת קשה לקבל אותו בתחילה. {| border="1" align="center" style="text-align:center;" |P |Q |<math>\,P \rightarrow Q</math> |- |T |T |T |- |T |F |F |- |F |T |T |- |F |F |T |} נראה עוד כמה דוגמאות. * "אם מחיר החיטה עולה, אנשים אוכלים פחות לחם". אם מחיר החיטה אינו עולה, הטענה הזו נכונה באופן ריק: יתכן למשל שאנשים אוכלים פחות לחם משום שהם מעדיפים עוגות. הטענה נכונה בוודאות אם אנשים אוכלים פחות לחם - בין אם מחיר החיטה עולה ובין אם לא. כדי לבדוק את הטענה, יש לחכות שמחיר החיטה יעלה, ורק אז לבדוק האם אנשים באמת אוכלים פחות לחם. * '''שלילת הטענה''': נניח, לשם הפשטות, שמחיר החיטה וכמות הלחם שאנשים אוכלים משתנים כל הזמן. בתנאים אלה, הפסוק "אם אנשים אוכלים יותר לחם אז מחיר החיטה יורד" שקול לגמרי לפסוק הקודם (הפסוקים נקראים "קונטראפוזיטיביים" זה לזה; את המונח הזה אין צורך לזכור). * אם n אינו זוגי אז קיימים מספרים עוקבים שסכומם הוא n. הפסוק הזה הוא בעל ערך אמת, למרות שלא קיימים שני מספרים עוקבים שסכומם הוא 4; הרי עבור n=4 גם ההנחה "n אינו זוגי" אינה מתקיימת, וממילא כשלון המסקנה אינו משפיע על ערך האמת. '''תרגיל'''. בדוק שאם ערך האמת של B הוא T, אז ערך האמת של "אם A אז B" הוא תמיד T. קבע מתי ערך האמת של "אם A אז B" הוא T, אם ידוע שערך האמת של B הוא F. '''תרגיל'''. אמא מבטיחה לילד: אם תקבל 100 במבחן, נקנה לך כלבלב. הוא קיבל במבחן 97, ואיננו יודעים האם קיבל כלבלב או לא. האם קיימה האם את ההבטחה? '''תרגיל'''. ניסוי מפורסם בפסיכולוגיה של החשיבה עוסק בקלפים שעל כל אחד מהם שני סימנים, משני העברים - אות ומספר. מניחים על השולחן ארבעה קלפים, שצידם החשוף מראה את הסימנים A, P, 2, 3. אילו כרטיסים יש להפוך על-מנת לבדוק את הטענה "אם בצד אחד של הכרטיס יש אות ניקוד (AEIOU) אז בצידו האחר יש מספר זוגי?" רוב גדול של האנשים משיב שיש להפוך את הכרטיס הראשון והשלישי. מדוע, לדעתך? ומה התשובה הנכונה? 5. '''אם ורק אם'''. '''דוגמא'''. הפסוק "אם יש עננים אז יורד גשם" אינו אמיתי, משום שיתכן שיהיו עננים בלי שירד גשם. לעומת זאת הפסוק "אם יורד גשם אז יש עננים" הוא אמיתי. את הפסוק השני, האמיתי, אפשר לנסח בצורות נוספות: "יש עננים אם יורד גשם" (מוכרחים להיות עננים אם יורד גשם), וגם "יורד גשם רק אם יש עננים" (כל אימת שיורד גשם, מוכרחים להיות עננים). נסכם: הפסוקים "אם A אז B", "B אם A" ו"A רק אם B" אומרים אותו הדבר. לכן, במקום להגיד "(אם B אז A), וגם (אם A אז B)", אפשר לומר "(A אם B), ו-(A רק אם B)", ובקיצור "A אם ורק אם B". זהו הקשר הבינארי האחרון שנציג בשם: '''אם ורק אם'''. ערך האמת של "A אם ורק אם B" הוא T בדיוק כאשר ערכי האמת של A ושל B שווים. {| border="1" align="center" style="text-align:center;" |P |Q |P <math>\leftrightarrow</math> Q |- |T |T |T |- |T |F |F |- |F |T |F |- |F |F |T |} '''דוגמא'''. משולש הוא ישר זווית ושווה שוקיים אם ורק אם יש לו שתי זוויות של 45 מעלות. === סימוני הקשרים === לקשרים הסטנדרטיים יש גם סימון סטנדרטי, שיש להכיר ולזכור. * במקום "לא A" כותבים <math>\ \sim A</math> או <math> \neg A</math>. * במקום "A וגם B" כותבים <math>\ A \wedge B</math>. * במקום "A או B" כותבים <math>\ A \vee B</math>. * במקום "אם A אז B" כותבים <math>\ A \rightarrow B</math>; מותר גם <math>\ B \leftarrow A</math>. * במקום "A אם ורק אם B" כותבים <math>\ A \leftrightarrow B</math>. '''תרגיל'''. * לוגיקן הלך לאכול במסעדת גורמה. הוא ניגש אל המלצר בתחילת הארוחה ואומר לו: "תקבל טיפ, אלא אם תגיש את האוכל קר ובאיחור, או שהאוכל לא טעים והמזגן לא פעל. למרות זאת, אם האוכל יהיה קר וטעים ויגיע באיחור, תקבל את הטיפ אם תגיש קינוח חינם". הצרן את התנאי לקבלת טיפ, וחשב מה קרה בארוחה אם ידוע שהמלצר לא קיבל טיפ. פתרון: * P - המלצר קיבל טיפ * H - האוכל הגיע חם * O - האוכל הגיע בזמן * K - האוכל הגיע טעים * B - המזגן פעל * D - המלצר נתן קינוח חינם התנאי לקבלת טיפ: <math>\neg \left[(\neg H\and \neg O)\or (\neg K\and \neg B)\right] \or (\neg H\and K \and \neg O \and D ) \leftrightarrow P </math> === פסוקים מורכבים === את הקשרים שפגשנו (לא, וגם, או, אם-אז, אם-ורק-אם) אפשר להפעיל לא רק על אטומים, אלא גם על פסוקים. '''דוגמא'''. אם אדם הוא מאושר אם ורק אם הוא לומד דברים חדשים, אז אדם שאינו לומד דברים חדשים אינו מאושר. (שמצרינים ל"אם (A אם ורק אם B), אז (אם לא B, אז לא A)"). פסוק הוא רצף של תווים, שכל אחד מהם הוא או אחד מסימני האטומים (מקובל להניח שעומדת לרשותנו אספקה אינסופית של סימנים לאטומים), או אחד מסימני הקשרים, או אחד הסימנים המיוחדים "(" ו")" שתפקידם להבטיח קריאה חד-משמעית של הפסוק. לדוגמא, הפסוק <math>\ A \wedge B \vee C</math> אינו ניתן לקריאה באופן ברור: אין לדעת האם הכוונה היא ל-<math>\ (A \wedge B) \vee C</math> או ל-<math>\ A \wedge (B \vee C)</math>. ('''תרגיל''': מצא ערכי אמת של A,B,C שיתנו ערכי אמת שונים לשני הפסוקים האחרונים). הכלל במקרה של ספק הוא פשוט: עדיף לבזבז מאה זוגות סוגריים מיותרים, מאשר להשמיט זוג סוגריים חיוני אחד. כמובן שלא כל רצף של סימנים הוא פסוק. "<math>\ )A\vee\neg\wedge)BA\neg</math>" אינו פסוק. אפשר '''להגדיר''' מהו פסוק "באינדוקציה על המבנה": * כל פסוק הוא או אטום, או שיש לו הצורה <math>\ \neg(x)</math> כאשר x הוא פסוק, או הצורה <math>\ (x)R(y)</math>, כאשר R הוא אחד מסימני הקשרים הבינאריים, ו-x,y הם פסוקים. הגדרה זו היא אחת מאבני היסוד של '''הלוגיקה הפסוקית''', המטפלת בפסוקים באופן פורמלי. זהו רק '''הסוג הראשון''' של פסוקים שאנו פוגשים - בהמשך נכיר שני סוגים מתוחכמים יותר. '''תרגיל'''. תאר מכונה המשתמשת באינדוקציה על אורך הפסוק כדי לזהות האם רצף של תווים הוא פסוק של הלוגיקה הפסוקית (הנח שהמכונה יודעת לזהות אטומים).
תקציר:
לתשומת לבך: תורמים אחרים עשויים לערוך או אף להסיר את תרומתך ל־Math-Wiki. אם אינך רוצה שעבודתך תהיה זמינה לעריכה על־ידי אחרים, אין לפרסם אותה פה.
כמו־כן, שמירת העריכה משמעה הבטחה שכתבת את הטקסט הזה בעצמך, או העתקת אותו ממקור שאינו מוגן בזכויות יוצרים (אפשר לעיין בדף
Math-Wiki:זכויות יוצרים
לפרטים נוספים).
אין לעשות שימוש בחומר המוגן בזכויות יוצרים ללא רשות!
ביטול
עזרה בעריכה
(נפתח בחלון חדש)