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

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


בצורה סכמטית <math>D_1 \lor D_2 \lor \dots \lor D_n</math> כאשר כל <math>D_i</math> מהצורה <math>q_1\land q_2 \land \dots \land q_m</math> וכל <math>q_i</math> שווה למשנה <math>x</math>  
בצורה סכמטית <math>D_1 \lor D_2 \lor \dots \lor D_n</math> כאשר כל <math>D_i</math> מהצורה <math>q_1\land q_2 \land \dots \land q_m</math> וכל <math>q_i</math> שווה למשתנה <math>x</math>  
או לשלילותו <math>\lnot x</math>
או לשלילותו <math>\lnot x</math>




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

גרסה מ־11:32, 19 באוקטובר 2014

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


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

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

אטומים ופרדיקטים

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

בניגוד לאטומים שהם ללא משתנים הפרדיקטים הינם פונקציות התלויות במשתנים. לדוגמא ניתן להגדיר את הפרדיקט [math]\displaystyle{ S(x) }[/math] להיות x הינו סטודנט באוניברסיטה.

גם אטומים וגם פרדיקטים יכולים להיות אמיתיים (מסמנים 1 או F) או שקריים (מסמנים 0 או F). המינוח המקובל הוא שאטום/פרדיקט הוא בעל ערך אמת T (במידה שהוא נכון) או בעל ערך אמת F (במידה שאינו נכון) כיוון שאטומים הם ללא משתנים הם יכולים להיות T או F אבל לא שניהם. לעומתם פרדיקטים הם תלויים במשתנים ולכן ערך האמת שלהם יקבע לפי ההצבה במשתנים. למשל הפרדיקט [math]\displaystyle{ S(x,y)=x\lt y }[/math] יהיה נכון במקרה ש [math]\displaystyle{ S(2,3) }[/math] ולא נכון במקרה ש [math]\displaystyle{ S(3,2) }[/math]

על מנת לבנות פסוקים יותר מורכבים משתמשים בקשרים וכמתים.

קַשָּרִים וְכַמָּתִים

ִִִִִִ

הגדרה: יהיו 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\iff B := (A\Rightarrow B)\and(B\Rightarrow A) }[/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{ \forall }[/math] והכמת "קיים" [math]\displaystyle{ \exist }[/math]

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

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

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

הצרנה

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

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

הגדרות הקשורות לקבוצות

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

[math]\displaystyle{ \{1,\mathrm{horse},3\} }[/math], [math]\displaystyle{ \{1,2,3\} }[/math] ו[math]\displaystyle{ \{1,\{2,3\},\{\}\} }[/math]

איבר השייך לקבוצה אנו מסמנים בסימן [math]\displaystyle{ \in }[/math]. למשל [math]\displaystyle{ 1\in\{1,2,3\} }[/math], ואילו [math]\displaystyle{ 4\notin\{1,2,3\} }[/math]. שימו לב שגם [math]\displaystyle{ 1\notin\{\{1,2,3\}\} }[/math] שכן האיבר היחיד בקבוצה זו הינה הקבוצה [math]\displaystyle{ \{1,2,3\} }[/math].

  • אומרים שקבוצה A מוכלת בקבוצה B (מסומן [math]\displaystyle{ A \subseteq B }[/math]) אם כל האיברים בA הם גם איברים בB.
  • חיתוך של שתי קבוצות A ו B הינו אוסף האיברים השייכים גם לA וגם לB (מסומן [math]\displaystyle{ A\cap B }[/math]).
  • איחוד של שתי קבוצות A ו B הינו אוסף האיברים השייכים לA או לB (מסומן [math]\displaystyle{ A\cup B }[/math]).
  • A הפרש B הינה הקבוצה המכילה את כל האיברים בA שאינם בB (מסומן A\B).
  • ההפרש הסימטרי בין שתי קבוצות A וB הוא אוסף האיברים הנמצאים באחת הקבוצות אך לא בחיתוך (מסומן [math]\displaystyle{ A\Delta B }[/math]).

תרגיל:

  • הצרן תנאי השקול לכך ש-a שייך לאיחוד של הקבוצות A וB

פתרון [math]\displaystyle{ a\in A \or a\in B }[/math]

  • הצרן תנאי השקול לכך ש-a אינו שייך לאיחוד של הקבוצות A וB
  • הצרן תנאי השקול לכך ש-a שייך לחיתוך של הקבוצות A וB
  • הצרן תנאי השקול לכך ש-a אינו שייך לחיתוך של הקבוצות A וB

הגדרה: קבוצה A מוכלת בקבוצה B אם בB נמצאים כל האיברים מA (למשל הטבעיים מוכלים בשלמים [math]\displaystyle{ \mathbb{N}\subseteq\mathbb{Z} }[/math], והשלמים מוכלים בממשיים [math]\displaystyle{ \mathbb{Z}\subseteq\mathbb{R} }[/math]).

  • הצרן תנאי השקול לכך ש-C מוכלת בחיתוך של A וB

פתרון: [math]\displaystyle{ \forall c [c\in C \rightarrow (c\in A \and c \in B)] }[/math]

  • הצרן תנאי השקול לכך ש-C אינה מוכלת באיחוד של A וB

טאוטולוגיות

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

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

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

פתרון: מתקיים [math]\displaystyle{ A\to B \equiv \neg A \or B }[/math] ומתקיים [math]\displaystyle{ A \and B = \neg(\neg A \or \neg B) }[/math]

הוכח את הבאים:

  • [math]\displaystyle{ \ \neg(A \or B) \equiv \neg A \and \neg B }[/math]
  • [math]\displaystyle{ \ A\or (B \and C ) \equiv (A \or B ) \and (A \or C) }[/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 \leftrightarrow B) \equiv (A \rightarrow B) \wedge (B \rightarrow A) }[/math].
  • [math]\displaystyle{ \ (A \rightarrow B) \equiv ((\neg B) \rightarrow (\neg A)) }[/math].

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

  • "כלב נובח אינו נושך" אם"ם "כלב נושך אינו נובח"

הסבר: נסמן ב- D את קבוצת כל הכלבים ב -A את הנובחים וב- B את הנושכים אז הדוגמא היא בעצם [math]\displaystyle{ \forall x\in D :((x\in A\to x\notin B)\iff (x\in B \to x\notin A)) }[/math]

שזה בעצם מהצורה (לכל כלב) * [math]\displaystyle{ \ (p \rightarrow q) \iff ((\neg p) \rightarrow (\neg q)) }[/math].

  • מי שלא לומד בסמסטר נכשל במבחן אמ"מ מי שלא נכשל במבחן למד בסמסטר

דרכי הוכחה

הוכח שהפסוקים הבאים הינם טאוטולוגיות:

  • [math]\displaystyle{ (A\rightarrow B) \leftrightarrow (\neg B \rightarrow \neg A) }[/math]
  • [math]\displaystyle{ A \leftrightarrow (\neg A \rightarrow F) }[/math]


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

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

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

שלילת פסוקים

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

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

לדוגמא:

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

השלילה היא:

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

נמשיך:

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

כלומר

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


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

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

פתרון: [math]\displaystyle{ \forall x\in\mathbb{R}\,\exists A\subset\mathbb{Q}:\forall\epsilon\in\mathbb{R}_{+}\exists q\in A\,:|x-q|\lt \epsilon }[/math] .

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

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

  • [math]\displaystyle{ \neg(\forall x\in\mathbb{R}\,\exists A\subset\mathbb{Q}:\forall\epsilon\in\mathbb{R}_{+}\exists q\in A\,:|x-q|\lt \epsilon ) }[/math]
  • [math]\displaystyle{ \exists x\in\mathbb{R}\,\neg( \exists A\subset\mathbb{Q}:\forall\epsilon\in\mathbb{R}_{+}\exists q\in A\,:|x-q|\lt \epsilon ) }[/math]
  • [math]\displaystyle{ \exists x\in\mathbb{R}\, \forall A\subset\mathbb{Q}:\neg(\forall\epsilon\in\mathbb{R}_{+}\exists q\in A\,:|x-q|\lt \epsilon ) }[/math]
  • [math]\displaystyle{ \exists x\in\mathbb{R}\, \forall A\subset\mathbb{Q}:\exists\epsilon\in\mathbb{R}_{+}\neg(\exists q\in A\,:|x-q|\lt \epsilon ) }[/math]
  • [math]\displaystyle{ \exists x\in\mathbb{R}\, \forall A\subset\mathbb{Q}:\exists\epsilon\in\mathbb{R}_{+}\forall q\in A\,\neg(:|x-q|\lt \epsilon ) }[/math]
  • [math]\displaystyle{ \exists x\in\mathbb{R}\,\forall A\subset\mathbb{Q}:\exists\epsilon\in\mathbb{R}_{+}\forall q\in A\,:|x-q|\geq\epsilon }[/math]

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

DNF,CNF

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

DNF

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

בצורה סכמטית [math]\displaystyle{ D_1 \lor D_2 \lor \dots \lor D_n }[/math] כאשר כל [math]\displaystyle{ D_i }[/math] מהצורה [math]\displaystyle{ q_1\land q_2 \land \dots \land q_m }[/math] וכל [math]\displaystyle{ q_i }[/math] שווה למשתנה [math]\displaystyle{ x }[/math] או לשלילותו [math]\displaystyle{ \lnot x }[/math]


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