קומבינטוריקה להנדסה תרגול 1
כמתים
נתבונן בשני כמתים חשובים: הכמת "לכל" [math]\displaystyle{ \forall }[/math] (זו A הפוכה, קיצור המילה All) והכמת "קיים" [math]\displaystyle{ \exist }[/math] (זו E הפוכה, קיצור המילה Exist).
תפקיד מרכזי של הכמת הוא להבהיר את כוונת הטענה. למשל הטענה ש "סטונדט הוא יצור חרוץ" יכולה לקבל 2 משמעויות בעזרת הכמתים. או "כל סטודנט הוא יצור חרוץ" או "קיים סטודנט שהוא יצור חרוץ".
הטענה הראשונה טוענת לגבי כלל הסטודנטים (אם רוצים להוכיח כי הטענה נכונה צריך לעבור בין כל הסטודנטים ולוודא שהם חרוצים ואם רוצים להוכיח כי הטענה לא נכונה מספיק למצוא סטודנט אחד שאינו חרוץ).
לעומתה הטענה השניה טוענת שניתן למצוא סטודנט אחד (לפחות) שהוא חרוץ (אם רוצים להוכיח את הטענה צריך למצוא סטודנט שהוא חרוץ ואם רוצים להוכיח כי הטענה לא נכונה צריך לעבור בין כל הסטודנטים ולוודא שהם אינם חרוצים).
שלילת כמתים
מהי השלילה של הפסוק "לכל סיר יש מכסה המתאים לו", או "לכל מאכל, יש מישהו שמכין אותו טעים"?
בעת שלילה של פסוק לוגי, הכמתים 'לכל' ו'קיים' מתחלפים זה עם זה, והשלילה עוברת הלאה. כלומר לכל טענה [math]\displaystyle{ P }[/math],
- [math]\displaystyle{ \ \neg \forall x: P(x) \equiv \exists x: \neg P(x) }[/math], וכך גם
- [math]\displaystyle{ \ \neg \exists x: P(x) \equiv \forall x: \neg P(x) }[/math].
קבוצות
- הגדרה (לא מדוייקת, אך מספיקה לצרכינו):
קבוצה הינה אוסף של איברים שונים. בקבוצה אין משמעות לסדר האיברים, ואיבר אינו יכול להופיע פעמיים. דוגמאות ל3 קבוצות:
[math]\displaystyle{ \{1,\text{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 אם מתקיים [math]\displaystyle{ \forall a\in A: a\in B }[/math].
- דוגמא:
[math]\displaystyle{ \mathbb{N}\subset\mathbb{Z}\subset\mathbb{Q}\subset\mathbb{R}\subset\mathbb{C} }[/math] כאשר
- [math]\displaystyle{ \mathbb{N}=\{1,2,3,\dots\} }[/math] המספרים הטבעיים
- [math]\displaystyle{ \mathbb{Z}=\{\dots,-2,-1,0,1,2,3,\dots\} }[/math] המספרים השלמים
- [math]\displaystyle{ \mathbb{Q}=\{\frac{m}{n} : m,n\in \mathbb{Z},n\neq 0\} }[/math] המספרים הרציונאלים (שברים)
- [math]\displaystyle{ \mathbb{R} }[/math] המספרים הממשיים ("כל המספרים" על הישר)
- [math]\displaystyle{ \mathbb{C}=\{a+bi : a,b\in \mathbb{R}, i^2 =-1\} }[/math] המספרים המרוכבים
תרגיל
נסמן [math]\displaystyle{ A=\{ 1,2,3\} ,B=\{ \{ 1\} ,\{ 2\} ,\{ 3\} \} ,C=\{1 \} ,D=\{ \{1\} \} }[/math]. השלימו ע"י הכלה או שייכות:
א. [math]\displaystyle{ B }[/math]__[math]\displaystyle{ A }[/math]
ב. [math]\displaystyle{ C }[/math]__[math]\displaystyle{ A }[/math]
ג. [math]\displaystyle{ B }[/math]__[math]\displaystyle{ C }[/math]
ד. [math]\displaystyle{ A }[/math]__[math]\displaystyle{ D }[/math]
ה. [math]\displaystyle{ B }[/math]__[math]\displaystyle{ D }[/math]
ו. [math]\displaystyle{ D }[/math]__[math]\displaystyle{ C }[/math]
איחוד, חיתוך, הפרש והפרש סימטרי
מתרגל, צייר דיאגרמות מתאימות.
- חיתוך של שתי קבוצות A ו B הינו אוסף האיברים השייכים גם לA וגם לB (מסומן [math]\displaystyle{ A\cap B }[/math]). מתקיים ש[math]\displaystyle{ a \in A\cap B \iff (a\in A \and a\in B) }[/math].
- איחוד של שתי קבוצות A ו B הינו אוסף האיברים השייכים לA או לB (מסומן [math]\displaystyle{ A\cup B }[/math]). מתקיים ש[math]\displaystyle{ a \in A\cup B \iff (a\in A \or a\in B) }[/math].
- קבוצות הן שוות אם הן מכילות את אותם האיברים. הדרך הנפוצה להוכיח שיוויון הינה הכלה דו כיוונית: A=B אם ורק אם [math]\displaystyle{ (A\subseteq B) \and (B \subseteq A) }[/math].
- A הפרש B הינה הקבוצה המכילה את כל האיברים בA שאינם בB (מסומן A\B). מתקיים ש [math]\displaystyle{ x\in A\setminus B \iff (x\in A) \and (x\notin B) }[/math].
- ההפרש הסימטרי בין שתי קבוצות A וB הוא אוסף האיברים הנמצאים באחת הקבוצות אך לא בחיתוך (מסומן [math]\displaystyle{ A\triangle B }[/math]). מתקיים כי
[math]\displaystyle{ x\in A\triangle B \iff ((x\in A)\and (x\notin B)) \or ((x\in B)\and (x\notin A)) }[/math] [math]\displaystyle{ \iff x\in (A\cup B) / (A\cap B) }[/math]
הדרכה למתרגל: צייר בשתי דיאגרמות את ההפרש הסימטרי, פעם ע"י ציור האיחוד ומחיקת החיתוך, ופעם ע"י איחוד ההפרשים, על מנת שיראו בציור את שקילות ההגדרות.
דוגמא:
יהיו [math]\displaystyle{ A=\{1,2,\{1\}\},B=\{1,\{2\}\},C=\{2,\{1,2\}\} }[/math] קבוצות.
אזי:
[math]\displaystyle{ A\cup B =\{1,2 ,\{1\},\{2\}\} }[/math]
[math]\displaystyle{ (A\cup B)\cap C =\{2\} }[/math]
[math]\displaystyle{ B \cap C = \varnothing }[/math]
[math]\displaystyle{ C \setminus A =\{\{1,2\}\} }[/math]
[math]\displaystyle{ B \triangle C = B \cup C }[/math]
[math]\displaystyle{ A \triangle C = \{1,\{1\},\{1,2\}\} }[/math]
תרגיל
הוכיחו או הפריכו:
א. לכל 3 קבוצות [math]\displaystyle{ A,B,C }[/math] מתקיים: [math]\displaystyle{ A\cap (B\cup C)=(A\cap B) \cup (A\cap C) }[/math]
ב. לכל 3 קבוצות [math]\displaystyle{ A,B,C }[/math] מתקיים: [math]\displaystyle{ A\triangle (B\cap C)=(A\triangle B) \cap (A\triangle C) }[/math]
פתרון
א. הוכחה בעזרת הכלה דו כיוונית: תהיינה [math]\displaystyle{ A,B,C }[/math] קבוצות.
בכיוון ([math]\displaystyle{ \subseteq }[/math]): רוצים להוכיח שלכל [math]\displaystyle{ x\in A\cap (B\cup C) }[/math] מתקיים [math]\displaystyle{ x\in (A\cap B) \cup (A\cap C) }[/math]. לכן ניקח איבר כללי של צד שמאל ונראה שהוא של צד ימין. פורמלית:
יהי [math]\displaystyle{ x\in A\cap (B\cup C) }[/math], לכן [math]\displaystyle{ x\in A \land (x\in B \lor x\in C) }[/math]. שימו לב, אנחנו יושעים כעת ש- [math]\displaystyle{ x\in A }[/math], ובנוסף אחד מהבאים: [math]\displaystyle{ x\in B \lor x\in C }[/math]. זאת אומרת שמתקיים: [math]\displaystyle{ x\in A\cap B \lor x\in A\cap C }[/math], כדרוש.
בכיוון ([math]\displaystyle{ \supseteq }[/math]): יהי [math]\displaystyle{ x\in (A\cap B) \cup (A\cap C) }[/math]. לכן [math]\displaystyle{ x\in A\cap B \lor x\not\in A\cap C }[/math], מה שאומר [math]\displaystyle{ x\in A }[/math] ובנוסף, לפחות אחד מהבאים [math]\displaystyle{ x\in B\lor x\in C }[/math]. כלומר בסה"כ [math]\displaystyle{ x\in A\cap (B\cup C) }[/math]
ב. הפרכה. כדי להפריך צריך להראות שלא לכל 3 קבוצות מתקיימת הטענה. כלומר, למצוא 3 קבוצות עבורן לא מתקיימת הטענה. זה דורש קצת משחק, לפעמים כדאי לנסות להוכיח ולראות איפה זה נתקע. כאן נשים לב שאם ניקח [math]\displaystyle{ B\cap C=\emptyset }[/math] אז מצד שמאל נקבל את [math]\displaystyle{ A }[/math]. מאידך, אם נדאג שיהיו איברים משותפים ל- [math]\displaystyle{ A,B }[/math] אז בצד ימין לא נקבל את כל [math]\displaystyle{ A }[/math].
למשל, ניקח [math]\displaystyle{ A=\{1,2,3\},B=\{1\},C=\{2\} }[/math]. כאמור, מצד שמאל נקבל את [math]\displaystyle{ A }[/math].
מצד ימין נקבל: [math]\displaystyle{ (A\triangle B) \cap (A\triangle C)=\{2,3\}\cap \{1,3\}=\{3\}\neq A }[/math].
מכפלה קרטזית
הגדרה: המכפלה הקרטזית של שתי קבוצות [math]\displaystyle{ A }[/math] ו-[math]\displaystyle{ B }[/math] הינה אוסף כל הזוגות הסדורים - [math]\displaystyle{ A\times B = \{(a,b)|a\in A \and b\in B\} }[/math]. ההבדל בין זוג סדור לבין קבוצה המכילה זוג איברים היא שהאיברים יכולים להיות שווים בזוג סדור, והסדר שלהם מהותי. כלומר שני האיברים הבאים שונים [math]\displaystyle{ (1,2),(2,1) }[/math] והאיבר הבא הינו זוג חוקי [math]\displaystyle{ (1,1) }[/math].
דוגמה: [math]\displaystyle{ A=\{1,2,3\} }[/math] ו-[math]\displaystyle{ B=\{a,b\} }[/math] אזי מתקיים [math]\displaystyle{ A\times B =\{(1,a),(2,a),(3,a),(1,b),(2,b),(3,b)\} }[/math]
למתכנתים: זה מאוד דומה ללולאות for מקוננות.
תרגיל
הוכיחו שלכל 4 קבוצות [math]\displaystyle{ A,B,C,D }[/math] מתקיים: [math]\displaystyle{ (A\times B)\cap (C\times D)=(A\cap C)\times (B\cap D) }[/math]
פתרון
[math]\displaystyle{ (x,y)\in (A\times B)\cap (C\times D) \iff }[/math]
[math]\displaystyle{ (x,y)\in A\times B \land (x,y)\in C\times D \iff }[/math]
[math]\displaystyle{ (x\in A \and y\in B) \and (x\in C\and y\in D) \iff }[/math]
[math]\displaystyle{ (x\in A\and x\in C) \and (y\in B\and y\in D) \iff }[/math]
[math]\displaystyle{ (x,y)\in (A\cap C)\times (B\cap D) }[/math]