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

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

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

קשרים, כמתים, הצרנה

ראשית, נכיר את הקשרים הלוגיים (וגם, או, שלילה, גורר), הכמתים (לכל, קיים) ואת מושג ההצרנה.

תרגיל: הגדרה: איחוד של שתי קבוצות A וB הוא קבוצת האיברים שנמצאים לפחות באחת הקבוצות. החיתוך הוא קבוצת האיברים שנמצאים בשתי הקבוצות.

• הצרן תנאי השקול לכך ש-a שייך לאיחוד של הקבוצות A וB
• הצרן תנאי השקול לכך ש-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
• הצרן תנאי השקול לכך ש-C אינה מוכלת באיחוד של A וB

טבלאות אמת

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

הוכח אחד או יותר מבין טאוטולוגיות הבאות (נציג בהזדמנות זאת את המושג טאוטולוגיה)

• [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].

דרכי הוכחה

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

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

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

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

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

שלילת פסוקים

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

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

לדוגמא:

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

השלילה היא:

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

נמשיך:

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

כלומר

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

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