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

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

בניגוד לאטומים שהם ללא משתנים הפרדיקטים הינם פונקציות התלויות במשתנים. לדוגמא ניתן להגדיר את הפרדיקט $S(x)$ להיות x הינו סטודנט באוניברסיטה.

כיוון שאטומים הם ללא משתנים הם יכולים להיות 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(p)$ הוא הפרדיקט "p" הוא ראשוני.
• $Q(p)$ הוא הפרדיקט $\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 n\in\mathbb{N}\,\exists m\in\mathbb{N}:n<m$ לעומת זאת $\exists m\in\mathbb{N}\,\forall n\in\mathbb{N}:n<m$ פירושו שקיים מספר טבעי שגדול מכל המספרים הטבעיים.

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

שלילת פסוקים

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

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

תרגיל

כתבו פסוק השקול לפסוק הבא ללא שימוש בקשר השלילה.

$\lnot (\forall a\in \mathbb{Z} \exists b\in \mathbb{N} (a|b\rightarrow (a<b\land a+b\neq 0)))$

פיתרון:

$\exists a\in \mathbb{Z} \forall b\in \mathbb{N} (a|b \land (a\geq b \lor a+b=0))$

תרגיל

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

א. $(\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 להיות 1 על הזוגיים ו-0 על אי-זוגיים, ןQ להיפך.אכן כל מספר טבעי הוא זוגי או אי-זוגי, אך זה לא נכון שכל מספר הוא זוגי או שכל מספר הוא אי-זוגי.

ב. הוכחה: יהי $n$ לפי הנתון מתקיים $P(n) \lor Q(n)$ כדרוש.

קבוצות

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

• X=אוסף כל הקבוצות שאינן שייכות לעצמן

אם X שייכת לקבוצה הזו, אזי היא אינה שייכת לקבוצה. אולם, אם היא אינה שייכת לקבוצה אזי היא כן שייכת לקבוצה.

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

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

$\{1,horse,3\}$, $\{1,2,3\}$ ו$\{1,\{2,3\},\{\}\}$

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

• אומרים שקבוצה A מוכלת בקבוצה B (מסומן $A \subseteq B$) אם כל האיברים בA הם גם איברים בB. בשפה מדויקת, A מוכלת בB אם מתקיים $\forall a\in A: a\in B$.

דוגמא:

$\mathbb{N}\subset\mathbb{Z}\subset\mathbb{Q}\subset\mathbb{R}\subset\mathbb{C}$ כאשר

$\mathbb{N}=\{1,2,3,\dots\}$ המספרים הטבעיים

$\mathbb{Z}=\{\dots,-2,-1,0,1,2,3,\dots\}$ המספרים השלמים

$\mathbb{Q}=\{\frac{m}{n} : m,n\in \mathbb{Z},n\neq 0\}$ המספרים הרציונאלים (שברים)

$\mathbb{R}$ המספרים הממשיים ("כל המספרים" על הישר)

$\mathbb{C}=\{a+bi : a,b\in \mathbb{R}, i^2 =-1\}$ המספרים המרוכבים

• חיתוך של שתי קבוצות A ו B הינו אוסף האיברים השייכים גם לA וגם לB (מסומן $A\cap B$). מתקיים ש$a \in A\cap B \iff (a\in A \and a\in B)$.

• איחוד של שתי קבוצות A ו B הינו אוסף האיברים השייכים לA או לB (מסומן $A\cup B$). מתקיים ש$a \in A\cup B \iff (a\in A \or a\in B)$.

• קבוצות הן שוות אם הן מכילות את אותם האיברים. הדרך הנפוצה להוכיח שיוויון הינה הכלה דו כיוונית: A=B אם ורק אם $(A\subseteq B) \and (B \subseteq A)$.

• A הפרש B הינה הקבוצה המכילה את כל האיברים בA שאינם בB (מסומן A\B). מתקיים ש $x\in A/B \iff (x\in A) \and (x\notin B)$.

• ההפרש הסימטרי בין שתי קבוצות A וB הוא אוסף האיברים הנמצאים באחת הקבוצות אך לא בחיתוך (מסומן $A\Delta B$). מתקיים ש $x\in A\Delta B \iff ((x\in A)\and (x\notin B)) \or ((x\in B)\and (x\notin A)) \iff x\in (A\cup B) / (A\cap B)$

דוגמא:

יהיו $A=\{1,2,\{1\}\},B=\{1,\{2\}\},C=\{2,\{1,2\}\}$ קבוצות.

אזי:

$A\cup B =\{1,2 ,\{1\},\{2\}\}$

$(A\cup B)\cap C =\{2\}$

$B \cap C = \emptyset$

$C \backslash A =\{\{1,2\}\}$

$B \Delta C = B \cup C$

$A \Delta C = \{1,\{1\},\{1,2\}\}$

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

תכונות האיחוד והחיתוך (דומה לכפל וחיבור)

• אסוציאטיביות: $(A\cap B)\cap C = A\cap (B\cap C)$ (וכנ"ל לגבי איחוד)
• חילוף: $A\cap B = B\cap A$ (וכנ"ל לגבי איחוד)
• דיסטריביוטיביות: $A\cap (B\cup C) = (A\cap B) \cup (A\cap C)$, וגם $A\cup (B\cap C) = (A\cup B) \cap (A\cup C)$

תרגיל

נוכיח שההפרש הסימטרי הוא קיבוצי, כלומר: לכל שלש קבוצות $A,B,C$ מתקיים : $A\triangle (B\triangle C)=(A\triangle B)\triangle C$

פתרון

אפשרי ע"י טבלת אמת הנקראת טבלת שכיחויות.

תרגיל

הוכח כי: א. הקבוצה הריקה $\phi=\{\}$ מוכלת בכל קבוצה A

ב. $\phi \cap A = \phi$

ג. $\phi \cup A = A$

פתרון

א. יש להוכיח את הפסוק הבא: $\forall a\in \phi: a\in A$. אבל מכיוון שאין איברים בקבוצה הריקה, המשפט הזה נכון באופן ריק. זכרו ששקר גורר כל דבר, לכן האטום "איבר a שייך לקבוצה הריקה" גורר כל דבר.

ב. $\phi \cap A = \{x:x\in \phi \and x\in A\}\subseteq \{x:x\in \phi \}=\phi$ כעזרת א קיבלנו הכלה בשני הכיוונים ולכן שיוויון.

ג. $\phi \cup A = \{x:x\in \phi \or x\in A\}= \{x:x\in A \}=A$ כי $F\lor p\equiv p$.

הכללה לאיחודים וחיתוכים כל שהם

מוטיבציה: הגדרנו את החיתוך והאיחוד עבור שתי קבוצות. לעיתים נרצה לחתוך או לאחד יותר קבוצות, לדוגמא נרצה לדבר על חיתוכן של 17 הקבוצות $A_1,A_2,\ldots,A_{17}$. מכיוון שחיתוך ואיחוד הן פעולות אסוציטיביות, ניתן לרשום $A_1\cap A_2\cap \ldots\cap A_{17}$, וזה ביטוי חד משמעי. אך צורת רישום זו היא ארוכה, ולכן אנו מסמנים את החיתוך הזה בקיצור הבא: $\bigcap _{i=1} ^{17} A_i$. לעיתים נרצה לחתוך או לאחד אוסף אינסופי של קבוצות, ולכך באה ההכללה הבאה:

הגדרה: יהיו $\{A_i\}_{i\in I}$ אוסף קבוצות כאשר $I$ הוא קבוצת אינדקסים אזי נגדיר את האיחוד והחיתוך של אוסף הקבוצות כך:

$\bigcup _{i\in I} A_i := \{x| \exist i\in I :x\in A_i \}$

$\bigcap _{i\in I} A_i := \{x| \forall i\in I :x\in A_i \}$. כאן יש להניח שקבוצת האינדקסים $I$ לא ריקה.

דוגמא:

נגדיר $\forall n\in \mathbb{N} \; A_n:=[n,n+1]$ אזי

$\bigcup _{i\in \mathbb{N}} A_i = [ 1,\infty )$

$\bigcap _{i\in \mathbb{N}} A_i = \phi$

תרגיל

נתון $A=\{\phi\}$ ונתון $B=\{\phi,\{\phi\}\}$. סמן את הביטויים הנכונים:

1. $\phi\subseteq B$ (כן)
2. $\phi\in \phi$ (לא)
3. $\phi \subseteq \phi$ (כן)
4. $A\subseteq B$ (כן)
5. $A\in B$ (כן)
6. $A\cup B = B$ (כן)
7. $A\cap B=\phi$ (לא)

תרגיל

הוכח כי $A\cap (B/C)=(A\cap B) / (A\cap C)$

פתרון

דרך גרירות לוגיות:

$x\in A\cap (B/C)\iff (x\in A) \and [(x\in B) \and (x\notin C)]\iff [(x\in A) \and (x\in B) \and (x\notin C)] \or [(x\in A) \and (x\in B) \and (x\notin A)]$

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

$\iff [(x\in A) \and (x\in B)]\and [(x\notin C)\or(x\notin A)]\iff [(x\in A) \and (x\in B)]\and \neg [(x\in C)\and(x\in A)]$

וזה בדיוק מה שרצינו.

דרך הכלה דו כיוונית:

($\subseteq$) נניח $x\in A\cap(B\backslash C)$ אזי

$x\in A \land x\in B \land x\not\in C \Leftarrow$ $x\in A\cap B \land x\not\in A\cap C \Leftarrow$ $x\in (A\cap B) \backslash (A\cap C)$

($\supseteq$) נניח $x\in (A\cap B) \backslash (A\cap C)$ אזי

$x\in A\cap B \land x\not\in A\cap C \Leftarrow$ $x\in A \land x\in B \land x\not\in C \Leftarrow$ (כי אם $x\in C$ אזי $x\in A\cap C$ סתירה) $x\in A\cap(B\backslash C)\Leftarrow$

תרגיל

נתונות $A=\{2m+1:m\in\mathbb{Z}\}$, ו $B=\{2m+3:m\in\mathbb{Z}\}$. הוכח שA=B.

פתרון

נוכיח הכלה דו כיוונית. נניח $x\in A$ לכן קיים מספר שלם m כך ש $x=2m+1$. קל לראות שמתקיים $x=2(m-1)+3$ אבל אז מכיוון ש m-1 הינו מספר שלם מתקיים $x\in B$ כפי שרצינו.

ההכלה בכיוון ההפוך דומה.

משלים

הגדרה: תהי קבוצה U (אוניברסלית) ותהי תת קבוצה שלה $A\subseteq U$. נגדיר את המשלים של A (ביחס ל $U$ להיות:

$A^c=\bar{A}=U-A={x\in U|x\notin A}$

תכונות בסיסיות:

• $A\cup A^c = U$
• $\emptyset^c = U$
• $U^c = \emptyset$
• $(A^c)^c = A$

על המשלימים מתקיימים חוקי דה מורגן (הנובעים ישירות מחוקי דה מורגן בלוגיקה):

• $(A\cap B)^c = A^c \cup B^c$
• $(A\cup B)^c = A^c \cap B^c$

הערה: באופן כללי מתקיים

א. $(\cap _{i\in I} A_i)^c = \cup _{i\in I} A_{i}^c$

ב. $(\cup _{i\in I} A_i)^c = \cap _{i\in I} A_{i}^c$

הוכחה לסעיף א:

$x\in (\cap _{i\in I} A_i)^c \iff x\in U \land \exists i\in I:x\notin A_i \iff \exists i\in I: x\in A_i^c \iff x\in \cup_{i\in I}A_i^c$

תרגיל

הוכיחו: $A-(B\cap C)=(A-B)\cup (A-C)$

פתרון

$A-(B\cap C)=A\cap (B\cap C)^c=A\cap (B^c\cup C^c)=(A\cap B^c)\cup (A\cap C^c)=(A-B)\cup (A-C)$

קבוצת החזקה

הגדרה: תהי קבוצה A. נגדיר את קבוצת החזקה של A בתור אוסף כל תתי הקבוצות של A. מסומן $P(A)=\{X:X\subseteq A\}$

דוגמא:

$A=\{1,2\}$ אזי $P(A)=\{\{\},\{1\},\{2\},\{1,2\}\}$.

האם אתם יכולים למנות כמה איברים יש בקבוצת החזקה?

תרגיל ממבחן

יהיו A,B,C קבוצות. הוכיחו/הפריכו:

א. אם $A \not\subseteq B \cap C$ אזי $(A/B)\cap(A/C)\neq \phi$

ב. אם $A\subseteq B$ אזי $A\cup(B/A)=B$

ג. אם $A\cap B=\phi$ אזי $P(A)\cap P(B) = \{\phi\}$

פתרון

א. הפרכה: $A=\{1,2\},B=\{1\},C=\{2\}$. אזי ברור שA איננה מוכלת בחיתוך של B וC אבל $(A/B)\cap(A/C)=\{2\}\cap\{1\}=\phi$

ב. נתון שלכל $a\in A$ מתקיים $a \in B$. אזי $x\in [A\cup(B/A)] \iff (x\in A) \or [(x\in B)\and (x\notin A)] \iff [(x\in A) \or (x\in B)] \and [(x \in A)\or (x\notin A)]$

כעת, הצד הימני הוא טאוטולוגיה וניתן להסיר אותו. מכיוון שנתון $(x\in A)\rightarrow (x\in B)$ ניתן להסיק בקלות ש$(x\in A)\or (x\in B) \iff (x\in B)$ כפי שרצינו.

דרך נוספת: נגדיר את B להיות הקבוצה האוניברסאלית $U:=B$ ואז צריך להוכיח כי $A\cap A^c =U$ וזה אכן נכון!

ג. נניח בשלילה ש$P(A)\cap P(B)\neq \{\phi\}$. מכיוון שהקבוצה הריקה שייכת לכל קבוצת חזקה החיתוך אינו ריק. לכן לפי הנחת השלילה קיימת קבוצה לא ריקה $\phi \not=C$ השייכת לחיתוך $P(A)\cap P(B)$. קבוצות החזקה הן אוסף תתי הקבוצות, ולכן $C\subseteq A \and C\subseteq B$. מכיוון שC אינה ריקה קיים בה איבר $\exists c\in C$ וקל מאד לראות ש$(c\in A)\and (c\in B)$ ולכן c מוכל בחיתוך בסתירה לכך שהחיתוך ריק.