הבדלים בין גרסאות בדף "88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 0"

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(הייתה טעות בדוגמה של CNF בC_2. התייחסות ל1 כמו שהוא ו0 כשלילה, כשזה צריך להיות הפוך.)
 
(52 גרסאות ביניים של 5 משתמשים אינן מוצגות)
שורה 1: שורה 1:
 
[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]
 
[[מתמטיקה בדידה - מערך תרגול|חזרה למערכי התרגול]]
−
 
  
 
סיכום הנושא המלא נמצא בדף [[88-101 חשיבה מתמטית]].
 
סיכום הנושא המלא נמצא בדף [[88-101 חשיבה מתמטית]].
  
−
==פסוקים וקַשָּרִים, פרדיקטים וכַּמָּתִים, הצרנה וטבלאות אמת==
+
אזהרה: דף זה נועד להכיר ללומד המתחיל את החשיבה הלוגיקית הקשיחה. כיוון שמדובר בלומד המתחיל ואיננו רוצים להבריח אותו, הדוגמאות וההסברים לעיתים "מעגלים פינות" (מבחינת דיוק קשיח ופורמלי) לטובת הסבר ברור ומסביר פנים.
 +
 
 +
==פסוקים וקַשָּרִים, הצרנה וטבלאות אמת==
  
 
=== אטומים, פסוקים וקשרים===
 
=== אטומים, פסוקים וקשרים===
שורה 11: שורה 12:
 
לדוגמא: הפסוק "שנת הלימודים החלה ויש 5 קורסים בשנה א'"  מורכב משני אטומים- "שנת הלימודים החלה" ו"יש 5 קורסים בשנה א'" (שני האטומים מקשורים ע"י וו החיבור)
 
לדוגמא: הפסוק "שנת הלימודים החלה ויש 5 קורסים בשנה א'"  מורכב משני אטומים- "שנת הלימודים החלה" ו"יש 5 קורסים בשנה א'" (שני האטומים מקשורים ע"י וו החיבור)
  
−
בצורה אחרת: אטומים הם יחידה תוכן בסיסית. פסוקים הם יחידות יותר מורכבות המורכבות מאטומים וקשרים. אטום מקבל ערך אמת TRUE ׁויסומן ב T או 1 (כלומר הוא אמיתי) או ערך עמת FULSE ויסומן ב F או 0 ׁ(כלומר הוא שקרי). פסוקים יקבלו ערך אמת לפי ערכי האמת של האטומים והקשרים המעורבים בפסוק.   
+
בצורה אחרת: אטומים הם יחידה תוכן בסיסית. פסוקים הם יחידות יותר מורכבות המורכבות מאטומים וקשרים. אטום מקבל ערך אמת TRUE ויסומן ב T או 1 (כלומר הוא אמיתי) או ערך אמת FALSE ויסומן ב F או 0 (כלומר הוא שקרי). פסוקים יקבלו ערך אמת לפי ערכי האמת של האטומים והקשרים המעורבים בפסוק.   
  
 
כפי שציינו פסוקים הם יחידות תוכן יותר מורכבות בשל השימוש בקשרים.
 
כפי שציינו פסוקים הם יחידות תוכן יותר מורכבות בשל השימוש בקשרים.
 
==== קשרים ====
 
==== קשרים ====
  
−
הגדרה: יהיו A,B אטומים (או פסןקים) היכולים להיות אמת (1) או שקר (0) אזי הקשרים  
+
הגדרה: יהיו A,B אטומים (או פסוקים) היכולים להיות אמת (1) או שקר (0) אזי הקשרים  
 
* <math>A\to  B</math>  - "גרירה" (חד כיוונית)
 
* <math>A\to  B</math>  - "גרירה" (חד כיוונית)
 
* <math>A \or B</math> "או"  
 
* <math>A \or B</math> "או"  
שורה 64: שורה 65:
 
הערה: קשר נוסף שהינו נפוץ בתחום המתמטקיה והוא גרירה דו-כיוונית (ידוע בכינויו אם ורק אם, אמ"מ).
 
הערה: קשר נוסף שהינו נפוץ בתחום המתמטקיה והוא גרירה דו-כיוונית (ידוע בכינויו אם ורק אם, אמ"מ).
 
הגדרתו פשוטה (נובעת משמו..) והיא מוגדרת ע"י קשר הגרירה החד כיווני.  
 
הגדרתו פשוטה (נובעת משמו..) והיא מוגדרת ע"י קשר הגרירה החד כיווני.  
−
<math>A\iff B := (A\Rightarrow B)\and(B\Rightarrow A)</math>
+
<math>A\leftrightarrow B</math> שטבלת האמת שלו זהה לטבלת האמת של <math>(A\to B)\and(B\to A)</math>
  
 
דוגמאות מילוליות:
 
דוגמאות מילוליות:
שורה 70: שורה 71:
 
* אינדוקציה לומדים בתיכון '''וגם''' זה קל. הפסוק יקבל ערך T רק אם האטומים המרכיבים אותו יקבלו ערך T (כלומר שניהם יתקיימו)
 
* אינדוקציה לומדים בתיכון '''וגם''' זה קל. הפסוק יקבל ערך T רק אם האטומים המרכיבים אותו יקבלו ערך T (כלומר שניהם יתקיימו)
 
* 3 הוא מספר ראשוני '''או''' 5 הוא מספר ראשוני. הפסוק הזה מקבל ערך T כיוון ש 3/5 מספר ראשוני. גם הפסוק  "3 הוא מספר ראשוני '''או''' 4 הוא מספר ראשוני" הוא בעל ערך T.
 
* 3 הוא מספר ראשוני '''או''' 5 הוא מספר ראשוני. הפסוק הזה מקבל ערך T כיוון ש 3/5 מספר ראשוני. גם הפסוק  "3 הוא מספר ראשוני '''או''' 4 הוא מספר ראשוני" הוא בעל ערך T.
−
* מספר (טבעי) מסוים n ניתן להצגה בעזרת 2 ספרות (בבסיס עשרוני) <math>\iff</math> המספר n קטן מ 100. הפסוק יקבל ערך T רק אם שני התנאים יתקיימו ביחד. במילים אחרות, אם אחד מתקיים גם השני. במילים אחרות, אם אחד לא מתקיים והשני אז השני גם לא מתקיים.
+
* מספר (טבעי) מסוים n ניתן להצגה בעזרת 2 ספרות (בבסיס עשרוני) <math>\iff</math> המספר n קטן מ 100. הפסוק יקבל ערך T רק אם שני התנאים יתקיימו ביחד. במילים אחרות, אם אחד מתקיים גם השני. במילים אחרות, אם אחד לא מתקיים אז השני גם לא מתקיים.
  
  
−
 
+
==== פסוקים מורכבים ====
−
תכונות הקשרים:
+
פסוקים יכולים להיות מורכבים יותר מאשר האטומים או חיבור של אטומים ע"י קשרים. המורכבות נוצרת ע"י הפעלה חוזרת של קשרים. במילים אחרות, נתייחס לכל אחד מהבאים כפסוק: א. אטומים ב. אם <math>p,q</math> פסוקים אזי <math>(p)\land (q),(p)\lor (q), (p)\to (q)</math> פסוקים. ג. אם <math>p</math> פסוק אזי <math>\lnot (p)</math> פסוק.
−
* קיבוציות <math>(A\land B) \land C =A\land (B \land C), (A\lor B) \lor C =A\lor (B \lor C)  </math>
+
−
* חילופיות <math>A\land B =B\land A, A\lor B = B\lor A</math>  
+
−
* פילוג <math>A\lor (B\land C)= (A\lor B)\land (A\lor C), A\land (B\lor C)= (A\land B)\lor (A\land C)</math>  
+
−
* כללי דה מורגן  <math>\neg (A \lor B) = \neg A \land \neg B, \neg (A \land B) = \neg A \lor \neg B</math>. תוכיחו אחד מהם בתרגיל הבית
+
−
 
+
  
 
==== הצרנה ====
 
==== הצרנה ====
שורה 101: שורה 97:
 
ההצרנה <math>[(A\land B)\to (C\lor D)]\and[(C \land \lnot A)\to  B]</math>
 
ההצרנה <math>[(A\land B)\to (C\lor D)]\and[(C \land \lnot A)\to  B]</math>
  
−
===פרדיקטים וכמתים===
+
==טאוטולוגיות==
−
בניגוד לאטומים שהם ללא משתנים ה'''פרדיקטים''' הינם פונקציות התלויות במשתנים. לדוגמא ניתן להגדיר את הפרדיקט <math>S(x)</math> להיות x הינו סטודנט באוניברסיטה.
+
הגדרה : טאוטולוגיה הינה ביטוי שנכון תמיד ללא תלות בערכים שמציבים בו.
 +
למשל <math>A \or \neg A</math>
 +
 
 +
הגדרה: נאמר שביטוי <math>A</math> שקול טאוטולוגית לביטוי <math>B</math> (ונסמן <math>A \equiv B</math>)
 +
אם הביטוי <math>A \leftrightarrow B</math> הינו טאוטולוגיה (במילים: A קורה אמ"מ B קורה)
 +
 
 +
====תרגיל====
 +
הוכח באמצעות טבלאות אמת שניתן להציג את הקשרים 'גרירה' ו'וגם' באמצעות 'או' ושלילה בלבד
 +
 
 +
פתרון:
 +
מתקיים <math>A\to B \equiv \neg A \or B</math>
 +
ומתקיים <math>A \and B \equiv \neg(\neg A \or \neg B)</math>
 +
 
 +
====תכונות הקשרים====
 +
כעת נוכל לנסח את הטענה בצורה מדויקת, תכונות הקשרים: לכל שלוש פסוקים <math>A,B,C</math> מתקיים כי:
 +
* קיבוציות <math>(A\land B) \land C \equiv A\land (B \land C), (A\lor B) \lor C \equiv A\lor (B \lor C)  </math>
 +
* חילופיות <math>A\land B\equiv B\land A, A\lor B \equiv B\lor A</math>
 +
* פילוג <math>A\lor (B\land C)\equiv (A\lor B)\land (A\lor C), A\land (B\lor C)\equiv (A\land B)\lor (A\land C)</math>
 +
* כללי דה מורגן  <math>\neg (A \lor B) \equiv \neg A \land \neg B, \neg (A \land B) \equiv \neg A \lor \neg B</math>. תוכיחו אחד מהם בתרגיל הבית
 +
 
 +
ועוד כמה תרגילים למי שיש זמן - הוכח
 +
* <math>\ (A \leftrightarrow B) \equiv (A \wedge B)\vee((\neg A)\wedge (\neg B))</math>.
 +
* <math>\ (A \leftrightarrow B) \equiv (A \rightarrow B) \wedge (B \rightarrow A)</math>.
 +
 
 +
====תרגיל====
 +
האם המשפטים הבאים שקולים:
 +
 
 +
א. אם אייל שמח אז ענת גבוהה, ואם ענת לא גבוהה אז אייל לא שמח.
 +
 
 +
ב. אייל שמח אם ורק אם ענת גבוהה.
 +
 
 +
פיתרון: לא. בא' יש פעמיים את אותו דבר, בגלל השקילות <math>p\to q\equiv \lnot q\to \lnot p</math>. עבור: אייל לא שמח וענת גבוהה, נקבל בא' אמת ובב' שקר.
 +
 
 +
===טענת גרירה===
 +
"טענות גרירה" הם טענות נפוצות במתמטיקה. טענות אלו פשוט טוענות שמתקיים כי: אם (משהו) אז (משהו). בשביל לרמוז על נכונות הטענה מסמנים <math>A\Rightarrow B</math> להדגיש כי הפסוק <math>A\rightarrow B</math> הינו אמת. במידה ולא מגלים לכם אם טענה הגרירה נכונה או לא (או שאתם לא מאמינים למרצה) אזי עומדות בפניכם שתי אופציות:
 +
 
 +
1. אם הטענה נכונה אזי כדאי להוכיח אותה ע"י כך שתראו שאם A נכון אז גם B נכון. או בצורה פרקטית יותר: נניח שA נכון ונוכיח שגם B נכון.
 +
 
 +
2. אם הטענה אינה נכונה אזי כדאי למצוא דוגמא שתפריך אותה. דוגמא מפריכה היא דוגמא עבורה A נכון וB לא נכון.
 +
 
 +
====תרגיל====
 +
האם משני הנתונים:
 +
 
 +
א. אם אני מנגן בחצוצרה אז אני לא מנגן בתופים ובפסנתר יחד.
 +
 
 +
ב. אם אני לא מנגן בחצוצרה אז אני לא מנגן בפסנתר.
 +
 
 +
ניתן להסיק: אני לא מנגן בפסנתר אז אני מנגן בתופים.
 +
 
 +
פתרון: לא, זה תלוי מי זה "אני": במידה ו"אני"  לא מנגן על אף כלי (מתאים לשורה F,F,F בטבלת האמת שאטומיה הן: "מנגן בחצוצרה", "מנגן בתופים", "מנגן בפנתר") נקבל כי הנתונים (א+ב) מקבלים ערך <math>T</math> והמסקנה <math>F</math>. ולכן הפסוק "(מסקנה)<math>\to</math>(נתונים)" אינו נכון.
 +
 
 +
====תרגיל====
 +
האם משני הנתונים:
 +
 
 +
א. אם אני מנגן בחצוצרה אז אני לא מנגן בתופים ובפסנתר יחד.
 +
 
 +
ב. אם אני לא מנגן בחצוצרה אז אני לא מנגן בפסנתר.
 +
 
 +
ניתן להסיק: אם אני מנגן בפסנתר אני לא מנגן בתופים.
 +
 
 +
פתרון: נכון, זה לא תלוי במי זה "אני" (במילים אחרות הפסוק "(מסקנה)<math>\to</math>(נתונים)" הוא טאוטולוגיה ולא מושפע מערכי האמת של האטומים שלו). בהינתן א+ב אנו רוצים להוכיח את המסקנה, שהיא בעצמה טענת גרירה. לכן: נניח שמנגן בפסנתר, לכן לפי ב מנגן בחצוצרה. ואז לפי א יוצא שלא מנגן בתופים או לא מנגן בפסנתר (דה-מורגן). כיון שנתון שמנגן בפסנתר מתחייב שלא בתופים.
 +
 
 +
===הכרחי ומספיק ===
 +
הערה (טרמינולוגיה):
 +
*כאשר אומרים ש B הוא תנאי הכרחי ל A פירושו הוא שהפסוק <math>A \to B</math> נכון. לעיתים, לצורך הדגשה מסמנים <math>A \Rightarrow B</math>
 +
*כאשר אומרים ש B הוא תנאי מספיק ל A פירושו הוא שהפסוק <math>B \to A</math> נכון. לעיתים, לצורך הדגשה מסמנים <math>B \Rightarrow A</math>
 +
*כאשר אומרים ש B הוא תנאי הכרחי ומספיק ל A פירושו הוא שהפסוק <math>B \rightarrow A</math> נכון. לעיתים, לצורך הדגשה מסמנים <math>A \iff B</math>
 +
====תרגיל====
 +
השלם את המשפט הבא: כדי שירד גשם _____ שיהיו עננים בשמים. לכן אם נסמן ע"י "יש עננים בשמים = A", "יורד גשם = B" נקבל "A____B".
 +
 
 +
פיתרון: הכרחי, <math>\Leftarrow </math>
 +
 
 +
====תרגיל====
 +
השלם את המשפט הבא: כניסת המורה לכיתה הוא תנאי _____ שיהיה שקט בכיתה. לכן אם נסמן ע"י "כניסת המורה= A", "שקט בכיתה = B" נקבל "A____B".
 +
 
 +
פיתרון: מספיק, <math>\Rightarrow </math>
 +
 
 +
===תרגיל===
 +
(a) כדי שלזכות בלוטו _____ למלא כרטיס לוטו.
 +
 
 +
(b) כדי שהיה שקט בכיתה _____ ללחוץ mute all
 +
 
 +
(c) לקבל ציון עם 3ספרות בקורס _____ לקבל 100 בקורס.
 +
 
 +
==דרכי הוכחה==
 +
כאשר רוצים להוכיח טענה, לפעמים יותר נח להוכיח ניסוח שקול (לוגית) אליה. דוגמאות נפוצות מוצגים בטענה הבאה:
 +
 
 +
הוכח:
 +
*<math>(A\rightarrow B) \equiv (\neg B \rightarrow \neg A)\equiv ((\neg A) \vee B)</math>
 +
*(הנחה בשלילה) <math>A \equiv (\neg A \rightarrow F)</math>
 +
*<math>(A\lor B) \equiv (\neg A \rightarrow B)</math>
 +
 
 +
 
 +
דוגמאות מילוליות:
 +
* בשביל להוכיח את הטענה ש "אם מישהו יכתוב בדיחה במבחן במקום תשובה אז הוא יקבל ניקוד חלקי" ניתן להוכיח באופן שקול כי " אם מישהו לא קיבל ניקוד חלקי במבחן אז זה אומר שהוא לא כתב בדיחה במבחן במקום תשובה"
 +
* בשביל להוכיח את הטענה ש "הגובה שלי נמוך מ- 3 מטר" אפשר להוכיח באופן שקול כי הגובה שלי לפחות 3 מטר ולהגיע לסתירה. למשל הטיעון הבא: "אם הגובה שלי לפחות 3 מטר, אז הראש שלי היה נוגע בתקרה. כיוון שהוא לא נוגע בתקרה, זו סתירה ולכן איני בגובה 3 מטר"
  
−
כיוון שאטומים הם ללא משתנים הם יכולים להיות T או F אבל לא שניהם. לעומתם פרדיקטים הם תלויים במשתנים ולכן ערך האמת שלהם יקבע לפי ההצבה במשתנים. למשל הפרדיקט <math>S(x,y)=x<y</math> יהיה נכון במקרה ש <math>S(2,3)</math> ולא נכון במקרה ש <math>S(3,2)</math>. כלומר לכל הצבה במשתני הפרדיקטים נקבל פסוק. הערה: משמשים בקשרים גם בפרדיקטים למשל <math>S(x,y)</math> הפרדיקט המוגדר <math>x>0 \land x<y</math>
+
==פרדיקטים וכמתים==
 +
בניגוד לאטומים שהם ללא משתנים ה'''פרדיקטים''' הינם פונקציות התלויות במשתנים. לדוגמא ניתן להגדיר את הפרדיקט <math>S(x)</math> להיות פרדיקט שמביע כי x הינו סטודנט באוניברסיטה ("מביע" פירושו שאם x הוא סטודנט אזי <math>S(x)</math> הוא T ואם x אינו סטודנט <math>S(x)</math> הוא F).
  
 +
כיוון שאטומים הם ללא משתנים הם יכולים להיות T או F אבל לא שניהם. לעומתם פרדיקטים הם תלויים במשתנים ולכן ערך האמת שלהם יקבע לפי ההצבה במשתנים. למשל הפרדיקט <math>S(x,y)</math>שמביע כי <math>x<y</math> יהיה נכון במקרה ש <math>S(2,3)</math> ולא נכון במקרה ש <math>S(3,2)</math>. כלומר לכל הצבה במשתני הפרדיקטים נקבל פסוק. הערה: משמשים בקשרים גם בפרדיקטים למשל <math>S(x,y)</math>  הפרדיקט המוגדר <math>(x>0) \land (x<y)</math>
  
 
בנוסף, ניתן להוסיף כמתים.
 
בנוסף, ניתן להוסיף כמתים.
שורה 116: שורה 209:
  
 
לעומתה הטענה השניה טוענת שניתן למצוא סטודנט אחד (לפחות) שהוא חרוץ (אם רוצים להוכיח את הטענה צריך למצוא סטודנט שהוא חרוץ ואם רוצים להוכיח כי הטענה לא נכונה צריך לעבור בין כל הסטודנטים ולוודא שהם אינם חרוצים
 
לעומתה הטענה השניה טוענת שניתן למצוא סטודנט אחד (לפחות) שהוא חרוץ (אם רוצים להוכיח את הטענה צריך למצוא סטודנט שהוא חרוץ ואם רוצים להוכיח כי הטענה לא נכונה צריך לעבור בין כל הסטודנטים ולוודא שהם אינם חרוצים
−
 
  
 
הצרן: לכל מספר p גדול מ-1:  (p ראשוני) אמ"מ (אם הוא מחלק מכפלת מספרים אז הוא מחלק את אחד המספרים).
 
הצרן: לכל מספר p גדול מ-1:  (p ראשוני) אמ"מ (אם הוא מחלק מכפלת מספרים אז הוא מחלק את אחד המספרים).
שורה 122: שורה 214:
 
פתרון:   
 
פתרון:   
 
ההצרנה <math>\forall p >1 : (P(p)\iff Q(p))</math> כאשר
 
ההצרנה <math>\forall p >1 : (P(p)\iff Q(p))</math> כאשר
−
*  <math>P(x)</math>  הוא הפרדיקט "x" הוא ראשוני.
+
*  <math>P(x)</math>  הוא הפרדיקט המביע כי"x הוא ראשוני".
−
* <math>Q(x)</math> הוא הפרדיקט <math>\forall a,b : p|ab \Rightarrow (p|a \lor p|b)</math>
+
* <math>Q(x)</math> הוא הפרדיקט המביע <math>\forall a,b : p|ab \Rightarrow (p|a \lor p|b)</math>
  
 
הערה: אחרי שמכמתים על כל משתני הפרדיקט מקבלים פסוק ללא משתנים.  
 
הערה: אחרי שמכמתים על כל משתני הפרדיקט מקבלים פסוק ללא משתנים.  
  
−
נשים לב כי בשביל לקבוע אם הפסוק <math>\forall x P(x)</math> אנחנו צריכים לדעת איזה x ים "חוקיים" (בהנחה שאנחנו יודעים את P) ומכאן שנעבור להגדרות הבאות.
+
הערה: שמות המשתנים אינם חשובים למשל עבור הפרדיק <math>S(x,y)</math> המוגדר <math>x\leq y</math> הפסוק <math>\forall x\forall y S(x,y)</math> הוא זהה לפסוק
 +
<math>\forall t\forall s S(t,s)</math>
  
−
===הגדרות הקשורות לקבוצות===
+
הערה: סדר הכמתים כן משתנה (לפעמים) למשל <math>\exist x\forall y S(x,y)</math> לא שקול לפסוק <math>\forall y \exist x S(x,y)</math>
−
ההגדרה האינטואיטיבית לקבוצה הינה "אוסף של איברים".
+
−
בקבוצה אין משמעות לסדר האיברים, ואיבר אינו יכול להופיע פעמיים. דוגמאות ל3 קבוצות (קבוצות נוהגים לסמן בין 2 סוגריים מסולסלות):
+
  
−
<math>\{1,\mathrm{horse},3\}</math>,    <math>\{1,2,3\}</math>    ו<math>\{1,\{2,3\},\{\}\}</math>
 
  
−
איבר ה'''שייך''' לקבוצה אנו מסמנים בסימן <math>\in</math>. למשל <math>1\in\{1,2,3\}</math>, ואילו <math>4\notin\{1,2,3\}</math>. שימו לב שגם <math>1\notin\{\{1,2,3\}\}</math> שכן האיבר היחיד בקבוצה זו הינה הקבוצה <math>\{1,2,3\}</math>.
+
נשים לב כי בשביל לקבוע אם הפסוק <math>\forall x P(x)</math> אנחנו צריכים לדעת איזה x ים "חוקיים" (בהנחה שאנחנו יודעים את P) ומכאן שנעבור להגדרות הבאות.
−
*אומרים שקבוצה A '''מוכלת''' בקבוצה B (מסומן <math>A \subseteq B</math>) אם כל האיברים בA הם גם איברים בB.  
+
  
−
*'''חיתוך''' של שתי קבוצות A ו B הינו אוסף האיברים השייכים גם לA וגם לB (מסומן <math>A\cap B</math>).
+
===תרגיל===
−
*'''איחוד''' של שתי קבוצות A ו B הינו אוסף האיברים השייכים לA או לB (מסומן <math>A\cup B</math>).
+
הצרינו את הפסוקים
−
*A '''הפרש''' B הינה הקבוצה המכילה את כל האיברים בA שאינם בB (מסומן A\B).
+
−
*'''ההפרש הסימטרי''' בין שתי קבוצות A וB הוא אוסף האיברים הנמצאים באחת הקבוצות אך לא בחיתוך (מסומן <math>A\Delta B</math>).
+
  
−
'''תרגיל:'''
+
(a) "כל שתי נקודות שונות קובעות ישר" באמצעות הפרדיקט הדו-מקומי P(x,l) - x נמצא ב l כאשר המשתנה x הוא נקודה ו l הוא ישר.
−
*הצרן תנאי השקול לכך ש-a שייך לאיחוד של הקבוצות A וB
+
  
−
פתרון <math>a\in A \or a\in B</math>
+
(b) "כל שתי נקודות שונות קובעות ישר אחד ויחיד"
  
−
*הצרן תנאי השקול לכך ש-a אינו שייך לאיחוד של הקבוצות A וB
 
−
*הצרן תנאי השקול לכך ש-a שייך לחיתוך של הקבוצות A וB
 
−
*הצרן תנאי השקול לכך ש-a אינו שייך לחיתוך של הקבוצות A וB
 
  
−
הגדרה: קבוצה A מוכלת בקבוצה B  אם בB נמצאים כל האיברים מA (למשל הטבעיים מוכלים בשלמים <math>\mathbb{N}\subseteq\mathbb{Z}</math>, והשלמים מוכלים בממשיים  <math>\mathbb{Z}\subseteq\mathbb{R}</math>).
 
−
*הצרן תנאי השקול לכך ש-C מוכלת בחיתוך של A וB
 
  
−
פתרון: <math>\forall c [c\in C \rightarrow (c\in A \and c \in B)]</math>
 
  
−
*הצרן תנאי השקול לכך ש-C אינה מוכלת באיחוד של A וB
+
====תרגיל====
 +
נגדיר פרדיקט <math>R(x,z,y)</math> המביע כי <math>x<z<y</math>.
  
−
==טאוטולוגיות==
+
האם הפסוק <math>\forall x\forall y \exists z : (x<y)\to R(x,z,y)</math> אמיתי?
−
הגדרה : טאוטולוגיה הינה ביטוי שנכון תמיד ללא תלות בערכים שמציבים בו.
+
−
למשל <math>A \or \neg A</math>  
+
  
−
הגדרה: נאמר שביטוי <math>A</math> שקול טאוטולוגית לביטוי <math>B</math> (ונסמן <math>A \equiv B</math>)
+
פתרון: אם המשתנים מגיעים מהשלמים הפסוק שקרי (שהרי לא קיים z עבור x=1,y=2). אם המשתנים מגיעים מהרציונאלים הפסוק אמת (תכונה זאת נקראת צפיפות הרציונאלים). מסקנה: צריך לדעת מאיפה מגיעים משתני הפרדיקט.
−
אם הביטוי <math>A \iff B</math> הינו טאוטולוגיה (במילים: A קורה אמ"מ B קורה)
+
  
−
תרגיל: הוכח באמצעות טבלאות אמת שניתן להציג את הקשרים 'גרירה' ו'וגם' באמצעות 'או' ושלילה בלבד
+
מה לא חשוב? לא חשוב שמות המשתנים. למשל <math>\forall x\forall y \exists z : (x<y)\to R(x,z,y)</math>
 +
זה פסוק זהה לפסוק <math>\forall m\forall n \exists k : (m<n)\to R(m,k,n)</math>
  
−
פתרון:  
+
חשוב גם הסדר, והכוונה לשני דברים:
−
מתקיים <math>A\to B \equiv \neg A \or B</math>
+
*סדר הופעת הכמתים, למשל הפסוק <math>\forall x\exists z \forall y  : (x<y)\to R(x,z,y)</math> הוא שקרי גם כשהמשתנים מגיעים מהרציונאלים (שהרי אפשר למצוא y שבין x לz)
−
ומתקיים <math>A \and B \equiv \neg(\neg A \or \neg B)</math>
+
*סדר המשתנים בתוך הפרדיקט, למשל הפסוק <math>\forall x\forall y \exists z : (x<y)\to R(x,y,z)</math> נכון גם כשהמשתנים מגיעים מהשלמים.
  
−
הוכח את הבאים:
 
−
* <math>\ \neg(A \or B) \equiv \neg A \and \neg B</math>
 
−
* <math>\ A\or (B \and C ) \equiv (A \or B ) \and (A \or C)</math>
 
−
* <math>\ (A\rightarrow B) \equiv ((\neg A) \vee B)</math>.
 
−
* <math>\ (A \leftrightarrow B) \equiv ((A \wedge B)\vee((\neg A)\wedge (\neg B)</math>.
 
−
* <math>\ (A \leftrightarrow B) \equiv (A \rightarrow B) \wedge (B \rightarrow A)</math>.
 
−
* <math>\ (A \rightarrow B) \equiv ((\neg B) \rightarrow (\neg A))</math>.
 
  
−
הערה (טרמינולוגיה):
 
−
*כאשר אומרים ש B הוא תנאי הכרחי ל A פירושו הוא <math>A \to B</math>
 
−
*כאשר אומרים ש B הוא תנאי מספיק ל A פירושו הוא <math>B \to A</math>
 
−
*כאשר אומרים ש B הוא תנאי הכרחי ומספיק ל A פירושו הוא <math>B \iff A</math>
 
  
−
דוגמאות מילוליות:
+
==== תרגיל ====
−
*"כלב נובח אינו נושך" אם"ם "כלב נושך אינו נובח"
+
הוכח או הפרך (משתני הפרדיקט נלקחים מהטבעיים):
  
−
הסבר: נסמן ב- D את קבוצת כל הכלבים ב -A את הנובחים וב- B את הנושכים אז הדוגמא היא בעצם <math>\forall x\in D :((x\in A\to x\notin B)\iff (x\in B \to x\notin A)) </math>
+
א. <math>(\forall n (P(n) \lor Q(n))) \Rightarrow ((\forall n P(n)) \lor (\forall n Q(n)))</math>
  
−
שזה בעצם מהצורה (לכל כלב) * <math>\ (p \rightarrow q) \iff ((\neg q) \rightarrow (\neg p))</math>.
+
ב. <math>(\forall n (P(n) \lor Q(n))) \Leftarrow ((\forall n P(n)) \lor (\forall n Q(n)))</math>
  
−
* מי שלא לומד בסמסטר נכשל במבחן אמ"מ מי שלא נכשל במבחן למד בסמסטר
+
פיתרון:
  
−
===דרכי הוכחה===
+
א. הפרכה. ניקח את <math>P(n)</math> להיות <math>1</math> על הזוגיים ו-<math>0</math> על אי-זוגיים, ו-<math>Q(n)</math> להפך. אכן כל מספר טבעי הוא זוגי או אי-זוגי, אך זה לא נכון שכל מספר הוא זוגי או שכל מספר הוא אי-זוגי.
−
הוכח שהפסוקים הבאים הינם טאוטולוגיות:
+
−
*<math>(A\rightarrow B) \iff (\neg B \rightarrow \neg A)</math>
+
−
*<math>A \iff(\neg A \rightarrow F)</math>
+
−
*<math>(A\lor B) \iff(\neg A \rightarrow B)</math>
+
  
 +
ב. הוכחה: יהי <math>n</math>. אם מתקיים <math>P(n)</math> אז בפרט מתקיים <math>P(n) \lor Q(n)</math> כדרוש. אחרת, לפי השקילות <math>a\lor b \equiv \lnot a \rightarrow b</math>, מתקיים שלכל מס' טבעי, ובפרט עבור <math>n</math>, מתקיים <math>Q(n)</math>, ולכן מתקיים <math>P(n) \lor Q(n)</math> כדרוש.
  
−
(נהוג להחליף ביטויים מהצורה הזו בביטויים השקולים להם כי הם נוחים יותר להוכחה מידי פעם.)
+
==== תרגיל ====
 +
הטענה: "כלב נובח אינו נושך" אם"ם "כלב נושך אינו נובח" צריכה להיות מנוסחת בצורה פורמלית יותר כ: "עבור כל כלב מתקיים כי: (כלב נובח אינו נושך) אם"ם (כלב נושך אינו נובח)"
  
−
דוגמאות מילוליות:
+
נוכיח את הטענה: נסמן ב- D את קבוצת כל הכלבים ב -A את הנובחים וב- B את הנושכים אז הדוגמא היא בעצם <math>\forall x\in D :((x\in A\to x\notin B)\iff (x\in B \to x\notin A)) </math>
−
* בשביל להוכיח את הטענה ש "אם מישהו יכתוב בדיחה במבחן במקום תשובה אז הוא יקבל ניקוד חלקי" ניתן להוכיח באופן שקול כי " אם מישהו לא קיבל ניקוד חלקי במבחן אז זה אומר שהוא לא כתב בדיחה במבחן במקום תשובה"  
+
 
−
* בשביל להוכיח את הטענה ש "הגובה שלי נמוך מ- 3 מטר" אפשר להוכיח באופן שקול כי הגובה שלי לפחות 3 מטר ולהגיע לסתירה. למשל הטיעון הבא: "אם הגובה שלי לפחות 3 מטר, אז הראש שלי היה נוגע בתקרה. כיוון שהוא לא נוגע בתקרה, זו סתירה ולכן איני בגובה 3 מטר"
+
שזה בעצם מהצורה (לכל כלב) * <math>\ (p \rightarrow q) \iff ((\neg q) \rightarrow (\neg p))</math>.
 +
 
 +
באופן דומה ניתן לעשות אם הטענה: מי שלא לומד בסמסטר נכשל במבחן אמ"מ מי שלא נכשל במבחן למד בסמסטר
  
 
==שלילת פסוקים==
 
==שלילת פסוקים==
שורה 213: שורה 281:
  
 
לדוגמא:
 
לדוגמא:
−
 
 
*"לכל אדם בעולם קיים דג עם מספר קשקשים כגיל האדם או שאורכו עשירית מאורך האדם"
 
*"לכל אדם בעולם קיים דג עם מספר קשקשים כגיל האדם או שאורכו עשירית מאורך האדם"
  
 
השלילה היא:
 
השלילה היא:
−
 
 
*"'''קיים''' אדם כך ש'''לא''' קיים דג עם מספר קשקשים כגיל האדם או שאורכו עשירית מאורך האדם"
 
*"'''קיים''' אדם כך ש'''לא''' קיים דג עם מספר קשקשים כגיל האדם או שאורכו עשירית מאורך האדם"
  
 
נמשיך:
 
נמשיך:
−
 
 
*"קיים אדם ש'''לכל''' דג בעולם '''לא נכון''' ש(יש לו מספר קשקשים כגיל האדם או שאורכו עשירית מאורך האדם)"
 
*"קיים אדם ש'''לכל''' דג בעולם '''לא נכון''' ש(יש לו מספר קשקשים כגיל האדם או שאורכו עשירית מאורך האדם)"
  
 
כלומר
 
כלומר
 
*"קיים אדם שלכל דג בעולם יש מספר קשקשים שונה מגיל האדם וגם אורכו של הדג שונה מעשירית אורך האדם"
 
*"קיים אדם שלכל דג בעולם יש מספר קשקשים שונה מגיל האדם וגם אורכו של הדג שונה מעשירית אורך האדם"
−
 
  
 
הערה: סדר הכמתים הוא חשוב (כמו בעברית) - לדוגמא: יש הבדל בין "לכל סיר קיים מכסה" לבין "קיים מכסה שמתאים לכל סיר".דוגמא: הצרן את המשפט "לכל מספר טבעי יש מספר טבעי הגדול ממנו" פתרון: <math>\forall n\in\mathbb{N}\,\exists m\in\mathbb{N}:n<m</math> לעומת זאת <math>\exists m\in\mathbb{N}\,\forall n\in\mathbb{N}:n<m</math> פירושו שקיים מספר טבעי שגדול מכל המספרים הטבעיים.
 
הערה: סדר הכמתים הוא חשוב (כמו בעברית) - לדוגמא: יש הבדל בין "לכל סיר קיים מכסה" לבין "קיים מכסה שמתאים לכל סיר".דוגמא: הצרן את המשפט "לכל מספר טבעי יש מספר טבעי הגדול ממנו" פתרון: <math>\forall n\in\mathbb{N}\,\exists m\in\mathbb{N}:n<m</math> לעומת זאת <math>\exists m\in\mathbb{N}\,\forall n\in\mathbb{N}:n<m</math> פירושו שקיים מספר טבעי שגדול מכל המספרים הטבעיים.
  
−
*תרגיל: הצרן את המשפט "כל מספר ממשי ניתן לקרב ע"י מספרים רציונאליים בקירוב טוב כרצוננו"
+
===תרגיל (בהרצאה)===
 +
.3 נתונים 4 קלפים שבצד א יש מספר )בין 1 ל 10( ובצד ב יש צבע )ירוק או אדום(. אני טוען: "כל קלף שבצד א יש מספר זוגי הצד השני שלו ירוק".הצרינו את הפסוק בעזרת הפרדיקטים P(x) המביע "צד א של קלף x הוא זוגי" ו Q(x) המביע "צד ב של קלף x הוא ירוק". מה השלילה של הפסוק?בהיתן שרואים 2,3 ירוק ואדום. אילו קלפים הכרחי ומספיק להפוך כדי לוודא את נכונות הטענה.
 +
====תרגיל====
 +
הוכיחו או הפריכו:
 +
 
 +
<math>\lnot (\forall a\in \mathbb{N} \exists b\in \mathbb{N} (a|b\rightarrow (a\leq b\land a+b<a\cdot b)))</math>
 +
 
 +
פיתרון: ראשית נראה מה הטענה בעצם אומרת:
 +
 
 +
<math>\exists a\in \mathbb{N} \forall b\in \mathbb{N} (a|b \land (a>b \lor a+b\geq a\cdot b))</math>
 +
 
 +
שימו לב שנעזרו בשקילות <math>\ (A\rightarrow B) \equiv ((\neg A) \lor B)</math> ובחוקי דה-מורגן. כעת נשים לב שאם <math>a|b</math> אז <math>a\leq b</math> ולכן כדי שזה יהיה נכון צריך שיתקיים <math>a+b\geq a\cdot b</math> וזה אכן קורה עבור <math>a=1</math>.
 +
 
 +
====תרגיל====
 +
הצרן את המשפט "כל מספר ממשי ניתן לקרב ע"י מספרים רציונאליים בקירוב טוב כרצוננו"
 
פתרון: <math>\forall x\in\mathbb{R}\,\exists A\subset\mathbb{Q}:\forall\epsilon\in\mathbb{R}_{+}\exists q\in A\,:|x-q|<\epsilon</math> .
 
פתרון: <math>\forall x\in\mathbb{R}\,\exists A\subset\mathbb{Q}:\forall\epsilon\in\mathbb{R}_{+}\exists q\in A\,:|x-q|<\epsilon</math> .
  
שורה 246: שורה 324:
 
דוגמאות של הצרנת ושלילת המושגים 'תלות לינארית', 'גבול סדרה', 'חח"ע', וכדומה
 
דוגמאות של הצרנת ושלילת המושגים 'תלות לינארית', 'גבול סדרה', 'חח"ע', וכדומה
  
−
==צורות נורמליות: CNF ,DNF==
+
==צורות נורמליות: CNF ,DNF (אם רלוונטי לקורס שאתם לוקחים. אם לא שמעתם על הדברים האלה - תדלגו)==
 +
 
  
 
ישנן שתי "צורות נורמליות" להצגת '''כל''' פסוקית - DNF ו CNF.
 
ישנן שתי "צורות נורמליות" להצגת '''כל''' פסוקית - DNF ו CNF.
שורה 353: שורה 432:
 
באופן דומה נייצר <math>C_2,C_3,C_4,C_5</math> עבור שורות 2 , 5, 7 ו-8:
 
באופן דומה נייצר <math>C_2,C_3,C_4,C_5</math> עבור שורות 2 , 5, 7 ו-8:
  
−
<math>C_2= x_1 \lor \lnot x_2 \lor \lnot x_3, C_3=\lnot x_1\lor \lnot x_2 \lor x_3</math>
+
<math>C_2= \lnot x_1 \lor x_2 \lor x_3, C_3=\lnot x_1\lor \lnot x_2 \lor x_3</math>
  
 
<math> C_4=x_1 \lor \lnot x_2 \lor \lnot x_3, C_5= \lnot x_1 \lor \lnot x_2 \lor \lnot x_3</math>
 
<math> C_4=x_1 \lor \lnot x_2 \lor \lnot x_3, C_5= \lnot x_1 \lor \lnot x_2 \lor \lnot x_3</math>

גרסה אחרונה מ־15:25, 11 בינואר 2023

חזרה למערכי התרגול

סיכום הנושא המלא נמצא בדף 88-101 חשיבה מתמטית.

אזהרה: דף זה נועד להכיר ללומד המתחיל את החשיבה הלוגיקית הקשיחה. כיוון שמדובר בלומד המתחיל ואיננו רוצים להבריח אותו, הדוגמאות וההסברים לעיתים "מעגלים פינות" (מבחינת דיוק קשיח ופורמלי) לטובת הסבר ברור ומסביר פנים.

פסוקים וקַשָּרִים, הצרנה וטבלאות אמת

אטומים, פסוקים וקשרים

הגדרה (לא פורמאלית): השפה העברית מורכבת ממשפטים. המקבילה בשפה המתמטית נקראת "פסוק".האטומים הם חלק מאבני היסוד של הפסוקים. לדוגמא: הפסוק "שנת הלימודים החלה ויש 5 קורסים בשנה א'" מורכב משני אטומים- "שנת הלימודים החלה" ו"יש 5 קורסים בשנה א'" (שני האטומים מקשורים ע"י וו החיבור)

בצורה אחרת: אטומים הם יחידה תוכן בסיסית. פסוקים הם יחידות יותר מורכבות המורכבות מאטומים וקשרים. אטום מקבל ערך אמת TRUE ויסומן ב T או 1 (כלומר הוא אמיתי) או ערך אמת FALSE ויסומן ב F או 0 (כלומר הוא שקרי). פסוקים יקבלו ערך אמת לפי ערכי האמת של האטומים והקשרים המעורבים בפסוק.

כפי שציינו פסוקים הם יחידות תוכן יותר מורכבות בשל השימוש בקשרים.

קשרים

הגדרה: יהיו A,B אטומים (או פסוקים) היכולים להיות אמת (1) או שקר (0) אזי הקשרים

  • A\to B - "גרירה" (חד כיוונית)
  • A \or B "או"
  • A\and B "וגם"
  • \neg A "שלילה"

מוגדרים ע"י טבלאת האמת הבאה (טבלת שכל שורה בה מתאימה להצבה אחרת אחרת באטומים):

\neg A A\and B A \or B A \to B B A
1 0 0 1 0 0
1 0 1 1 1 0
0 0 1 0 0 1
0 1 1 1 1 1

הערה: קשר נוסף שהינו נפוץ בתחום המתמטקיה והוא גרירה דו-כיוונית (ידוע בכינויו אם ורק אם, אמ"מ). הגדרתו פשוטה (נובעת משמו..) והיא מוגדרת ע"י קשר הגרירה החד כיווני. A\leftrightarrow B שטבלת האמת שלו זהה לטבלת האמת של (A\to B)\and(B\to A)

דוגמאות מילוליות:

  • אם נסיים את החומר של השיעור אז נגמור מוקדם. אם נסיים את החומר וגם לא נגמור מוקדם אז הפסוק יקבל ערך F. אם לא נסיים את החומר וגם לא נגמור מוקדם אז הפסוק יקבל ערך T.
  • אינדוקציה לומדים בתיכון וגם זה קל. הפסוק יקבל ערך T רק אם האטומים המרכיבים אותו יקבלו ערך T (כלומר שניהם יתקיימו)
  • 3 הוא מספר ראשוני או 5 הוא מספר ראשוני. הפסוק הזה מקבל ערך T כיוון ש 3/5 מספר ראשוני. גם הפסוק "3 הוא מספר ראשוני או 4 הוא מספר ראשוני" הוא בעל ערך T.
  • מספר (טבעי) מסוים n ניתן להצגה בעזרת 2 ספרות (בבסיס עשרוני) \iff המספר n קטן מ 100. הפסוק יקבל ערך T רק אם שני התנאים יתקיימו ביחד. במילים אחרות, אם אחד מתקיים גם השני. במילים אחרות, אם אחד לא מתקיים אז השני גם לא מתקיים.


פסוקים מורכבים

פסוקים יכולים להיות מורכבים יותר מאשר האטומים או חיבור של אטומים ע"י קשרים. המורכבות נוצרת ע"י הפעלה חוזרת של קשרים. במילים אחרות, נתייחס לכל אחד מהבאים כפסוק: א. אטומים ב. אם p,q פסוקים אזי (p)\land (q),(p)\lor (q), (p)\to (q) פסוקים. ג. אם p פסוק אזי \lnot (p) פסוק.

הצרנה

הצרנה- כתיבת רעיון בעזרת ניסוח פורמאלי

דוגמא: נצרין את המשפט: "אם יש בגרות בשעה חופפת לקורס אז הוא מתבטל ". נגדיר A = יש בגרות בשעה שחופפת לקורס. B= הקורס מתבטל. המשפט אומר A\to B . כלומר בגרות בשעה חופפת לקורס זה תנאי מספיק לכך שהקורס מתבטל. שימו לב שזהו לא תנאי הכרחי כי יתכן שהקורס יתבטל מסיבות אחרות.

הצרן: למדתי היטב למבחן, ואף על פי כן נכשלתי בו.

פתרון: נסמן A למדתי לבמחן, B נכשלתי במבחן אזי ההצרנה היא A\land B

הצרן: "ערן לובש חולצה סגולה בכל פעם שהוא לובש מכנסיים בצבע שחור"

פתרון: נסמן A ערן לובש חולצה סגולה. נסמן B ערך לובש מכנסיים שחורות. ההצרנה B\to A

הצרן: "כאשר אני עייף ורעב אני נעשה עצבני, או שאני הולך לישון; אבל אם אני עצבני ולא עייף, אז אני רעב".

פתרון: נסמן A אני עייף, B אני רעב, C אני עצבני, D אני הולך לישון ההצרנה [(A\land B)\to (C\lor D)]\and[(C \land \lnot A)\to B]

טאוטולוגיות

הגדרה : טאוטולוגיה הינה ביטוי שנכון תמיד ללא תלות בערכים שמציבים בו. למשל A \or \neg A

הגדרה: נאמר שביטוי A שקול טאוטולוגית לביטוי B (ונסמן A \equiv B) אם הביטוי A \leftrightarrow B הינו טאוטולוגיה (במילים: A קורה אמ"מ B קורה)

תרגיל

הוכח באמצעות טבלאות אמת שניתן להציג את הקשרים 'גרירה' ו'וגם' באמצעות 'או' ושלילה בלבד

פתרון: מתקיים A\to B \equiv \neg A \or B ומתקיים A \and B \equiv \neg(\neg A \or \neg B)

תכונות הקשרים

כעת נוכל לנסח את הטענה בצורה מדויקת, תכונות הקשרים: לכל שלוש פסוקים A,B,C מתקיים כי:

  • קיבוציות (A\land B) \land C \equiv A\land (B \land C), (A\lor B) \lor C \equiv A\lor (B \lor C)
  • חילופיות A\land B\equiv B\land A, A\lor B \equiv B\lor A
  • פילוג A\lor (B\land C)\equiv (A\lor B)\land (A\lor C), A\land (B\lor C)\equiv (A\land B)\lor (A\land C)
  • כללי דה מורגן \neg (A \lor B) \equiv \neg A \land \neg B, \neg (A \land B) \equiv \neg A \lor \neg B. תוכיחו אחד מהם בתרגיל הבית

ועוד כמה תרגילים למי שיש זמן - הוכח

  • \ (A \leftrightarrow B) \equiv (A \wedge B)\vee((\neg A)\wedge (\neg B)).
  • \ (A \leftrightarrow B) \equiv (A \rightarrow B) \wedge (B \rightarrow A).

תרגיל

האם המשפטים הבאים שקולים:

א. אם אייל שמח אז ענת גבוהה, ואם ענת לא גבוהה אז אייל לא שמח.

ב. אייל שמח אם ורק אם ענת גבוהה.

פיתרון: לא. בא' יש פעמיים את אותו דבר, בגלל השקילות p\to q\equiv \lnot q\to \lnot p. עבור: אייל לא שמח וענת גבוהה, נקבל בא' אמת ובב' שקר.

טענת גרירה

"טענות גרירה" הם טענות נפוצות במתמטיקה. טענות אלו פשוט טוענות שמתקיים כי: אם (משהו) אז (משהו). בשביל לרמוז על נכונות הטענה מסמנים A\Rightarrow B להדגיש כי הפסוק A\rightarrow B הינו אמת. במידה ולא מגלים לכם אם טענה הגרירה נכונה או לא (או שאתם לא מאמינים למרצה) אזי עומדות בפניכם שתי אופציות:

1. אם הטענה נכונה אזי כדאי להוכיח אותה ע"י כך שתראו שאם A נכון אז גם B נכון. או בצורה פרקטית יותר: נניח שA נכון ונוכיח שגם B נכון.

2. אם הטענה אינה נכונה אזי כדאי למצוא דוגמא שתפריך אותה. דוגמא מפריכה היא דוגמא עבורה A נכון וB לא נכון.

תרגיל

האם משני הנתונים:

א. אם אני מנגן בחצוצרה אז אני לא מנגן בתופים ובפסנתר יחד.

ב. אם אני לא מנגן בחצוצרה אז אני לא מנגן בפסנתר.

ניתן להסיק: אני לא מנגן בפסנתר אז אני מנגן בתופים.

פתרון: לא, זה תלוי מי זה "אני": במידה ו"אני" לא מנגן על אף כלי (מתאים לשורה F,F,F בטבלת האמת שאטומיה הן: "מנגן בחצוצרה", "מנגן בתופים", "מנגן בפנתר") נקבל כי הנתונים (א+ב) מקבלים ערך T והמסקנה F. ולכן הפסוק "(מסקנה)\to(נתונים)" אינו נכון.

תרגיל

האם משני הנתונים:

א. אם אני מנגן בחצוצרה אז אני לא מנגן בתופים ובפסנתר יחד.

ב. אם אני לא מנגן בחצוצרה אז אני לא מנגן בפסנתר.

ניתן להסיק: אם אני מנגן בפסנתר אני לא מנגן בתופים.

פתרון: נכון, זה לא תלוי במי זה "אני" (במילים אחרות הפסוק "(מסקנה)\to(נתונים)" הוא טאוטולוגיה ולא מושפע מערכי האמת של האטומים שלו). בהינתן א+ב אנו רוצים להוכיח את המסקנה, שהיא בעצמה טענת גרירה. לכן: נניח שמנגן בפסנתר, לכן לפי ב מנגן בחצוצרה. ואז לפי א יוצא שלא מנגן בתופים או לא מנגן בפסנתר (דה-מורגן). כיון שנתון שמנגן בפסנתר מתחייב שלא בתופים.

הכרחי ומספיק

הערה (טרמינולוגיה):

  • כאשר אומרים ש B הוא תנאי הכרחי ל A פירושו הוא שהפסוק A \to B נכון. לעיתים, לצורך הדגשה מסמנים A \Rightarrow B
  • כאשר אומרים ש B הוא תנאי מספיק ל A פירושו הוא שהפסוק B \to A נכון. לעיתים, לצורך הדגשה מסמנים B \Rightarrow A
  • כאשר אומרים ש B הוא תנאי הכרחי ומספיק ל A פירושו הוא שהפסוק B \rightarrow A נכון. לעיתים, לצורך הדגשה מסמנים A \iff B

תרגיל

השלם את המשפט הבא: כדי שירד גשם _____ שיהיו עננים בשמים. לכן אם נסמן ע"י "יש עננים בשמים = A", "יורד גשם = B" נקבל "A____B".

פיתרון: הכרחי, \Leftarrow

תרגיל

השלם את המשפט הבא: כניסת המורה לכיתה הוא תנאי _____ שיהיה שקט בכיתה. לכן אם נסמן ע"י "כניסת המורה= A", "שקט בכיתה = B" נקבל "A____B".

פיתרון: מספיק, \Rightarrow

תרגיל

(a) כדי שלזכות בלוטו _____ למלא כרטיס לוטו.

(b) כדי שהיה שקט בכיתה _____ ללחוץ mute all

(c) לקבל ציון עם 3ספרות בקורס _____ לקבל 100 בקורס.

דרכי הוכחה

כאשר רוצים להוכיח טענה, לפעמים יותר נח להוכיח ניסוח שקול (לוגית) אליה. דוגמאות נפוצות מוצגים בטענה הבאה:

הוכח:

  • (A\rightarrow B) \equiv (\neg B \rightarrow \neg A)\equiv ((\neg A) \vee B)
  • (הנחה בשלילה) A \equiv (\neg A \rightarrow F)
  • (A\lor B) \equiv (\neg A \rightarrow B)


דוגמאות מילוליות:

  • בשביל להוכיח את הטענה ש "אם מישהו יכתוב בדיחה במבחן במקום תשובה אז הוא יקבל ניקוד חלקי" ניתן להוכיח באופן שקול כי " אם מישהו לא קיבל ניקוד חלקי במבחן אז זה אומר שהוא לא כתב בדיחה במבחן במקום תשובה"
  • בשביל להוכיח את הטענה ש "הגובה שלי נמוך מ- 3 מטר" אפשר להוכיח באופן שקול כי הגובה שלי לפחות 3 מטר ולהגיע לסתירה. למשל הטיעון הבא: "אם הגובה שלי לפחות 3 מטר, אז הראש שלי היה נוגע בתקרה. כיוון שהוא לא נוגע בתקרה, זו סתירה ולכן איני בגובה 3 מטר"

פרדיקטים וכמתים

בניגוד לאטומים שהם ללא משתנים הפרדיקטים הינם פונקציות התלויות במשתנים. לדוגמא ניתן להגדיר את הפרדיקט S(x) להיות פרדיקט שמביע כי x הינו סטודנט באוניברסיטה ("מביע" פירושו שאם x הוא סטודנט אזי S(x) הוא T ואם x אינו סטודנט S(x) הוא F).

כיוון שאטומים הם ללא משתנים הם יכולים להיות T או F אבל לא שניהם. לעומתם פרדיקטים הם תלויים במשתנים ולכן ערך האמת שלהם יקבע לפי ההצבה במשתנים. למשל הפרדיקט S(x,y)שמביע כי x<y יהיה נכון במקרה ש S(2,3) ולא נכון במקרה ש S(3,2). כלומר לכל הצבה במשתני הפרדיקטים נקבל פסוק. הערה: משמשים בקשרים גם בפרדיקטים למשל S(x,y) הפרדיקט המוגדר (x>0) \land (x<y)

בנוסף, ניתן להוסיף כמתים.

הכמת "לכל" \forall והכמת "קיים" \exist

תפקיד מרכזי של הכמת הוא להבהיר את כוונת הטענה. למשל הטענה ש "סטונדט הוא יצור חרוץ" יכולה לקבל 2 משמעויות בעזרת הכמתים. או "כל סטודנט הוא יצור חרוץ" או "קיים סטודנט שהוא יצור חרוץ".

הטענה הראשונה טוענת לגבי כלל הסטודנטים (אם רוצים להוכיח כי הטענה נכונה צריך לעבור בין כל הסטודנטים ולוודא שהם חרוצים ואם רוצים להוכיח כי הטענה לא נכונה מספיק למצוא סטודנט אחד שאינו חרוץ).

לעומתה הטענה השניה טוענת שניתן למצוא סטודנט אחד (לפחות) שהוא חרוץ (אם רוצים להוכיח את הטענה צריך למצוא סטודנט שהוא חרוץ ואם רוצים להוכיח כי הטענה לא נכונה צריך לעבור בין כל הסטודנטים ולוודא שהם אינם חרוצים

הצרן: לכל מספר p גדול מ-1: (p ראשוני) אמ"מ (אם הוא מחלק מכפלת מספרים אז הוא מחלק את אחד המספרים).

פתרון: ההצרנה \forall p >1 : (P(p)\iff Q(p)) כאשר

  • P(x) הוא הפרדיקט המביע כי"x הוא ראשוני".
  • Q(x) הוא הפרדיקט המביע \forall a,b : p|ab \Rightarrow (p|a \lor p|b)

הערה: אחרי שמכמתים על כל משתני הפרדיקט מקבלים פסוק ללא משתנים.

הערה: שמות המשתנים אינם חשובים למשל עבור הפרדיק S(x,y) המוגדר x\leq y הפסוק \forall x\forall y S(x,y) הוא זהה לפסוק \forall t\forall s S(t,s)

הערה: סדר הכמתים כן משתנה (לפעמים) למשל \exist x\forall y S(x,y) לא שקול לפסוק \forall y \exist x S(x,y)


נשים לב כי בשביל לקבוע אם הפסוק \forall x P(x) אנחנו צריכים לדעת איזה x ים "חוקיים" (בהנחה שאנחנו יודעים את P) ומכאן שנעבור להגדרות הבאות.

תרגיל

הצרינו את הפסוקים

(a) "כל שתי נקודות שונות קובעות ישר" באמצעות הפרדיקט הדו-מקומי P(x,l) - x נמצא ב l כאשר המשתנה x הוא נקודה ו l הוא ישר.

(b) "כל שתי נקודות שונות קובעות ישר אחד ויחיד"



תרגיל

נגדיר פרדיקט R(x,z,y) המביע כי x<z<y.

האם הפסוק \forall x\forall y \exists z : (x<y)\to R(x,z,y) אמיתי?

פתרון: אם המשתנים מגיעים מהשלמים הפסוק שקרי (שהרי לא קיים z עבור x=1,y=2). אם המשתנים מגיעים מהרציונאלים הפסוק אמת (תכונה זאת נקראת צפיפות הרציונאלים). מסקנה: צריך לדעת מאיפה מגיעים משתני הפרדיקט.

מה לא חשוב? לא חשוב שמות המשתנים. למשל \forall x\forall y \exists z : (x<y)\to R(x,z,y) זה פסוק זהה לפסוק \forall m\forall n \exists k : (m<n)\to R(m,k,n)

חשוב גם הסדר, והכוונה לשני דברים:

  • סדר הופעת הכמתים, למשל הפסוק \forall x\exists z \forall y : (x<y)\to R(x,z,y) הוא שקרי גם כשהמשתנים מגיעים מהרציונאלים (שהרי אפשר למצוא y שבין x לz)
  • סדר המשתנים בתוך הפרדיקט, למשל הפסוק \forall x\forall y \exists z : (x<y)\to R(x,y,z) נכון גם כשהמשתנים מגיעים מהשלמים.


תרגיל

הוכח או הפרך (משתני הפרדיקט נלקחים מהטבעיים):

א. (\forall n (P(n) \lor Q(n))) \Rightarrow ((\forall n P(n)) \lor (\forall n Q(n)))

ב. (\forall n (P(n) \lor Q(n))) \Leftarrow ((\forall n P(n)) \lor (\forall n Q(n)))

פיתרון:

א. הפרכה. ניקח את P(n) להיות 1 על הזוגיים ו-0 על אי-זוגיים, ו-Q(n) להפך. אכן כל מספר טבעי הוא זוגי או אי-זוגי, אך זה לא נכון שכל מספר הוא זוגי או שכל מספר הוא אי-זוגי.

ב. הוכחה: יהי n. אם מתקיים P(n) אז בפרט מתקיים P(n) \lor Q(n) כדרוש. אחרת, לפי השקילות a\lor b \equiv \lnot a \rightarrow b, מתקיים שלכל מס' טבעי, ובפרט עבור n, מתקיים Q(n), ולכן מתקיים P(n) \lor Q(n) כדרוש.

תרגיל

הטענה: "כלב נובח אינו נושך" אם"ם "כלב נושך אינו נובח" צריכה להיות מנוסחת בצורה פורמלית יותר כ: "עבור כל כלב מתקיים כי: (כלב נובח אינו נושך) אם"ם (כלב נושך אינו נובח)"

נוכיח את הטענה: נסמן ב- D את קבוצת כל הכלבים ב -A את הנובחים וב- B את הנושכים אז הדוגמא היא בעצם \forall x\in D :((x\in A\to x\notin B)\iff (x\in B \to x\notin A))

שזה בעצם מהצורה (לכל כלב) * \ (p \rightarrow q) \iff ((\neg q) \rightarrow (\neg p)).

באופן דומה ניתן לעשות אם הטענה: מי שלא לומד בסמסטר נכשל במבחן אמ"מ מי שלא נכשל במבחן למד בסמסטר

שלילת פסוקים

מהי השלילה של הפסוק "לכל סיר יש מכסה המתאים לו", או "לכל מאכל, יש מישהו שמכין אותו טעים"?

בעת שלילה של פסוק לוגי, הכמתים 'לכל' ו'קיים' מתחלפים זה עם זה, והשלילה עוברת הלאה. את השלילה על הקשרים ניתן לבצע באמצעות טאוטולוגיות וטבלאות אמת.

לדוגמא:

  • "לכל אדם בעולם קיים דג עם מספר קשקשים כגיל האדם או שאורכו עשירית מאורך האדם"

השלילה היא:

  • "קיים אדם כך שלא קיים דג עם מספר קשקשים כגיל האדם או שאורכו עשירית מאורך האדם"

נמשיך:

  • "קיים אדם שלכל דג בעולם לא נכון ש(יש לו מספר קשקשים כגיל האדם או שאורכו עשירית מאורך האדם)"

כלומר

  • "קיים אדם שלכל דג בעולם יש מספר קשקשים שונה מגיל האדם וגם אורכו של הדג שונה מעשירית אורך האדם"

הערה: סדר הכמתים הוא חשוב (כמו בעברית) - לדוגמא: יש הבדל בין "לכל סיר קיים מכסה" לבין "קיים מכסה שמתאים לכל סיר".דוגמא: הצרן את המשפט "לכל מספר טבעי יש מספר טבעי הגדול ממנו" פתרון: \forall n\in\mathbb{N}\,\exists m\in\mathbb{N}:n<m לעומת זאת \exists m\in\mathbb{N}\,\forall n\in\mathbb{N}:n<m פירושו שקיים מספר טבעי שגדול מכל המספרים הטבעיים.

תרגיל (בהרצאה)

.3 נתונים 4 קלפים שבצד א יש מספר )בין 1 ל 10( ובצד ב יש צבע )ירוק או אדום(. אני טוען: "כל קלף שבצד א יש מספר זוגי הצד השני שלו ירוק".הצרינו את הפסוק בעזרת הפרדיקטים P(x) המביע "צד א של קלף x הוא זוגי" ו Q(x) המביע "צד ב של קלף x הוא ירוק". מה השלילה של הפסוק?בהיתן שרואים 2,3 ירוק ואדום. אילו קלפים הכרחי ומספיק להפוך כדי לוודא את נכונות הטענה.

תרגיל

הוכיחו או הפריכו:

\lnot (\forall a\in \mathbb{N} \exists b\in \mathbb{N} (a|b\rightarrow (a\leq b\land a+b<a\cdot b)))

פיתרון: ראשית נראה מה הטענה בעצם אומרת:

\exists a\in \mathbb{N} \forall b\in \mathbb{N} (a|b \land (a>b \lor a+b\geq a\cdot b))

שימו לב שנעזרו בשקילות \ (A\rightarrow B) \equiv ((\neg A) \lor B) ובחוקי דה-מורגן. כעת נשים לב שאם a|b אז a\leq b ולכן כדי שזה יהיה נכון צריך שיתקיים a+b\geq a\cdot b וזה אכן קורה עבור a=1.

תרגיל

הצרן את המשפט "כל מספר ממשי ניתן לקרב ע"י מספרים רציונאליים בקירוב טוב כרצוננו" פתרון: \forall x\in\mathbb{R}\,\exists A\subset\mathbb{Q}:\forall\epsilon\in\mathbb{R}_{+}\exists q\in A\,:|x-q|<\epsilon .

מה היא שלילתו של המשפט?

פתרון: נכתוב את הרמות השונות

  • \neg(\forall x\in\mathbb{R}\,\exists A\subset\mathbb{Q}:\forall\epsilon\in\mathbb{R}_{+}\exists q\in A\,:|x-q|<\epsilon )
  • \exists x\in\mathbb{R}\,\neg( \exists A\subset\mathbb{Q}:\forall\epsilon\in\mathbb{R}_{+}\exists q\in A\,:|x-q|<\epsilon )
  • \exists x\in\mathbb{R}\, \forall A\subset\mathbb{Q}:\neg(\forall\epsilon\in\mathbb{R}_{+}\exists q\in A\,:|x-q|<\epsilon )
  • \exists x\in\mathbb{R}\, \forall A\subset\mathbb{Q}:\exists\epsilon\in\mathbb{R}_{+}\neg(\exists q\in A\,:|x-q|<\epsilon )
  • \exists x\in\mathbb{R}\, \forall A\subset\mathbb{Q}:\exists\epsilon\in\mathbb{R}_{+}\forall q\in A\,\neg(:|x-q|<\epsilon )
  • \exists x\in\mathbb{R}\,\forall A\subset\mathbb{Q}:\exists\epsilon\in\mathbb{R}_{+}\forall q\in A\,:|x-q|\geq\epsilon

תרגילים: דוגמאות של הצרנת ושלילת המושגים 'תלות לינארית', 'גבול סדרה', 'חח"ע', וכדומה

צורות נורמליות: CNF ,DNF (אם רלוונטי לקורס שאתם לוקחים. אם לא שמעתם על הדברים האלה - תדלגו)

ישנן שתי "צורות נורמליות" להצגת כל פסוקית - DNF ו CNF.

DNF

ביטוי בצורת DNF מורכב מאוסף "פסוקיות" המחוברות ביניהן על ידי פעולות "או". כל פסוקית בעצמה מורכבת מאטומים המחוברים ביניהם על ידי פעולות "וגם". כל אטום הוא משתנה או שלילת משתנה.

בצורה סכמטית: D_1 \lor D_2 \lor \dots \lor D_n כאשר כל D_i מהצורה p_1\land p_2 \land \dots \land p_m וכל p_i שווה למשתנה x או לשלילתו \lnot x.

דוגמא: נמצא את צורת DNF של טבלת האמת הבאה:


f(x_1,x_2,x_3) x_3 x_2 x_1
0 0 0 0
0 0 0 1
1 0 1 0
1 1 0 0
0 0 1 1
1 1 0 1
0 1 1 0
0 1 1 1

נתמקד בשורות שערך האמת שלהן הוא 1 (שורות 3, 4, 6).

לשורה 3 נתאים את הפסוקית D_1=\lnot x_1 \land x_2 \land \lnot x_3

מה עשינו? החלפנו כל משתנה שערכו 0 בשלילה שלו, וכל משתנה שערכו 1 השארנו בלי לגעת.

מה יצא לנו מזה? שימו לב שרק הצבה של ערכי האמת של x_1,x_2,x_3 שמופיעים בשורה 3 תתן ערך אמת 1 ב D_1. כל הצבה אחרת (כלומר: הצבה של ערכי אמת של המשתנים בשורה אחרת) תתן 0 ב D_1.

באופן דומה נייצר D_2 עבור שורה 4 ו D_3 עבור שורה 6:

D_2=\lnot x_1 \land\lnot x_2 \land x_3, \quad D_3=x_1\land \lnot x_2 \land x_3

כעת ה DNF של טבלת האמת היא פשוט

D_1\or D_2 \or D_3=(\lnot x_1 \land x_2 \land \lnot x_3) \or (\lnot x_1 \land \lnot x_2 \land x_3) \or (x_1 \land \lnot x_2 \land x_3).

CNF

ביטוי בצורת CNF מורכב מאוסף "פסוקיות" המחוברות ביניהן על ידי פעולות "וגם". כל פסוקית בעצמה מורכבת מאטומים המחוברים ביניהם על ידי פעולות "או". כל אטום הוא משתנה או שלילת משתנה.

בצורה סכמטית: C_1 \land C_2 \land \dots \land C_n כאשר כל C_i מהצורה q_1\lor q_2 \lor \dots \lor q_m וכל q_i שווה למשתנה x או לשלילתו \lnot x.

נדגים על הדוגמא לעיל.

נתמקד בשורות שערך האמת שלהן הוא 0 (שורות 1, 2, 5, 7, 8)

לשורה 1 נתאים את הפסוקית C_1= x_1 \lor x_2 \lor x_3

מה עשינו? כל משתנה שערכו 0 השארנו בלי לגעת, וכל משתנה שערכו 1 החלפנו בשלילתו.

מה יצא לנו מזה? שימו לב שרק הצבה של ערכי האמת של x_1,x_2,x_3 שמופיעים בשורה 1 תתן ערך אמת 0 ב C_1. כל הצבה אחרת (כלומר: הצבה של ערכי אמת של המשתנים בשורה אחרת) תתן 1 ב C_1.

באופן דומה נייצר C_2,C_3,C_4,C_5 עבור שורות 2 , 5, 7 ו-8:

C_2= \lnot x_1 \lor x_2 \lor x_3, C_3=\lnot x_1\lor \lnot x_2 \lor x_3

C_4=x_1 \lor \lnot x_2 \lor \lnot x_3, C_5= \lnot x_1 \lor \lnot x_2 \lor \lnot x_3

כעת ה CNF של טבלת האמת היא פשוט

C_1 \land C_2 \land C_3 \land C_4 \land C_5

הרחבה על עניינים אלו ניתן למצוא פה 88-101 חשיבה מתמטית

מקור: https://math-wiki.com/index.php?title=88-195_בדידה_לתיכוניסטים_תשעא/מערך_שיעור/שיעור_0&oldid=89579