תרגול 1 מדמח קיץ תשעז

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

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

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

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

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

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

קשרים

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

• [math]\displaystyle{ A\to B }[/math] - "גרירה" (חד כיוונית)
• [math]\displaystyle{ A \or B }[/math] "או"
• [math]\displaystyle{ A\and B }[/math] "וגם"
• [math]\displaystyle{ \neg A }[/math] "שלילה"

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

[math]\displaystyle{ \neg A }[/math]	[math]\displaystyle{ A\and B }[/math]	[math]\displaystyle{ A \or B }[/math]	[math]\displaystyle{ A \to B }[/math]	[math]\displaystyle{ B }[/math]	[math]\displaystyle{ A }[/math]
1	0	0	1	0	0
1	0	1	1	1	0
0	0	1	0	0	1
0	1	1	1	1	1

הערה: קשר נוסף שהינו נפוץ בתחום המתמטקיה והוא גרירה דו-כיוונית (ידוע בכינויו אם ורק אם, אמ"מ). הגדרתו פשוטה (נובעת משמו..) והיא מוגדרת ע"י קשר הגרירה החד כיווני. [math]\displaystyle{ A\leftrightarrow B := (A\rightarrow B)\and(B\rightarrow A) }[/math]

קשר נוסף הינו "או מוציא", נגדיר אותו ע"י: [math]\displaystyle{ A \oplus B := \lnot(A\leftrightarrow B) }[/math]

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

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

טאוטולוגיות

הגדרה : טאוטולוגיה הינה פסוק המקבל ערך אמת [math]\displaystyle{ T }[/math] לכל הצבה באטומים המעורבים בפסוק. למשל [math]\displaystyle{ A \or \neg A }[/math]

הגדרה: נאמר שביטוי [math]\displaystyle{ A }[/math] שקול טאוטולוגית לביטוי [math]\displaystyle{ B }[/math] (ונסמן [math]\displaystyle{ A \equiv B }[/math]) אם יש להם את אותה טבלת אמת. הערה: במקרה זה הביטוי [math]\displaystyle{ A \leftrightarrow B }[/math] הינו טאוטולוגיה (במילים: A קורה אמ"מ B קורה)

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

• קיבוציות [math]\displaystyle{ (A\land B) \land C =A\land (B \land C), (A\lor B) \lor C =A\lor (B \lor C) }[/math]
• חילופיות [math]\displaystyle{ A\land B =B\land A, A\lor B = B\lor A }[/math]
• פילוג [math]\displaystyle{ 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]\displaystyle{ \neg (A \lor B) = \neg A \land \neg B, \neg (A \land B) = \neg A \lor \neg B }[/math]. תוכיחו אחד מהם בתרגיל הבית
• [math]\displaystyle{ \ (A\rightarrow B) \equiv ((\neg A) \vee B) }[/math].
• [math]\displaystyle{ \ (A \leftrightarrow B) \equiv ((A \wedge B)\vee((\neg A)\wedge (\neg B) }[/math].
• [math]\displaystyle{ \ (A \rightarrow B) \equiv ((\neg B) \rightarrow (\neg A)) }[/math].

תרגיל

הוכח: [math]\displaystyle{ \lnot (p\lor (q\land \lnot r))\land q\equiv \lnot p\land (r\land q) }[/math]

פיתרון: [math]\displaystyle{ \lnot (p\lor (q\land \lnot r))\land q\equiv (\lnot p\land \lnot (q\land \lnot r))\land q\equiv (\lnot p\land (\lnot q \lor \lnot \lnot r))\land q \equiv (\lnot p\land (\lnot q\lor r))\land q \equiv }[/math]

[math]\displaystyle{ \lnot p \land(q\land (\lnot q \lor r)) \equiv \lnot p \land ((q\land \lnot q)\lor (q\land r))\equiv \lnot p\land (F\lor (q\land r))\equiv \lnot p\land (r\land q) }[/math]

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

• כאשר אומרים ש B הוא תנאי הכרחי ל A פירושו הוא [math]\displaystyle{ A \to B }[/math]
• כאשר אומרים ש B הוא תנאי מספיק ל A פירושו הוא [math]\displaystyle{ B \to A }[/math]
• כאשר אומרים ש B הוא תנאי הכרחי ומספיק ל A פירושו הוא [math]\displaystyle{ B \iff A }[/math]

הצרנה

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

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

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

פתרון: נסמן A למדתי לבמחן, B נכשלתי במבחן אזי ההצרנה היא [math]\displaystyle{ A\land B }[/math]

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

פתרון: נסמן A ערן לובש חולצה סגולה. נסמן B ערך לובש מכנסיים שחורות. ההצרנה [math]\displaystyle{ B\to A }[/math]

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

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

צורות נורמליות: CNF ,DNF

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

DNF

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

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

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

[math]\displaystyle{ f(x_1,x_2,x_3) }[/math]	[math]\displaystyle{ x_3 }[/math]	[math]\displaystyle{ x_2 }[/math]	[math]\displaystyle{ x_1 }[/math]
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 נתאים את הפסוקית [math]\displaystyle{ D_1=\lnot x_1 \land x_2 \land \lnot x_3 }[/math]

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

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

באופן דומה נייצר [math]\displaystyle{ D_2 }[/math] עבור שורה 4 ו [math]\displaystyle{ D_3 }[/math] עבור שורה 6:

[math]\displaystyle{ D_2=\lnot x_1 \land\lnot x_2 \land x_3, \quad D_3=x_1\land \lnot x_2 \land x_3 }[/math]

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

[math]\displaystyle{ 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) }[/math].

CNF

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

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

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

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

לשורה 1 נתאים את הפסוקית [math]\displaystyle{ C_1= x_1 \lor x_2 \lor x_3 }[/math]

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

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

באופן דומה נייצר [math]\displaystyle{ C_2,C_3,C_4,C_5 }[/math] עבור שורות 2 , 5, 7 ו-8:

[math]\displaystyle{ 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]\displaystyle{ 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]

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

[math]\displaystyle{ C_1 \land C_2 \land C_3 \land C_4 \land C_5 }[/math]

קבוצות קשרים שלמות

נגדיר את הקשר ,נור, באמצעות: [math]\displaystyle{ q*r = \lnot(q\lor r) }[/math]

תרגיל

הוכח ש [math]\displaystyle{ {*} }[/math] הינה קבוצת קשרים שלמה.

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

[math]\displaystyle{ \lnot q \equiv \lnot (q\lor q) \equiv q*q }[/math]

[math]\displaystyle{ q\lor r\equiv \lnot \lnot (q\lor r) \equiv \lnot (q*r)\equiv (q*r)*(q*r) }[/math]

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