קומבינטוריקה להנדסה תרגול 1 - היסטוריית גרסאות

Mathzeta2: /* איחוד, חיתוך, הפרש והפרש סימטרי */

2020-10-16T10:28:01Z

איחוד, חיתוך, הפרש והפרש סימטרי

→ הגרסה הקודמת		גרסה מ־10:28, 16 באוקטובר 2020
שורה 70:		שורה 70:
	*'''ההפרש הסימטרי''' בין שתי קבוצות A וB הוא אוסף האיברים הנמצאים באחת הקבוצות אך לא בחיתוך (מסומן <math>A\triangle B</math>). מתקיים כי		*'''ההפרש הסימטרי''' בין שתי קבוצות A וB הוא אוסף האיברים הנמצאים באחת הקבוצות אך לא בחיתוך (מסומן <math>A\triangle B</math>). מתקיים כי
	<math>x\in A\triangle B \iff ((x\in A)\and (x\notin B)) \or ((x\in B)\and (x\notin A))</math>		<math>x\in A\triangle B \iff ((x\in A)\and (x\notin B)) \or ((x\in B)\and (x\notin A))</math>
	<math>\iff x\in (A\cup B) / (A\cap B)</math>		<math>\iff x\in (A\cup B) \setminus (A\cap B)</math>

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

Mathzeta2: Mathzeta2 העביר את הדף תרגול 1 ל־קומבינטוריקה להנדסה תרגול 1: שם פחות כללי

2020-10-16T10:18:25Z

Mathzeta2 העביר את הדף תרגול 1 ל־קומבינטוריקה להנדסה תרגול 1: שם פחות כללי

→ הגרסה הקודמת	גרסה מ־10:18, 16 באוקטובר 2020
(אין הבדלים)

אריאל ב־15:18, 14 באוקטובר 2020

2020-10-14T15:18:41Z

→ הגרסה הקודמת		גרסה מ־15:18, 14 באוקטובר 2020
שורה 115:		שורה 115:

	מצד ימין נקבל: <math>(A\triangle B) \cap (A\triangle C)=\{2,3\}\cap \{1,3\}=\{3\}\neq A</math>.		מצד ימין נקבל: <math>(A\triangle B) \cap (A\triangle C)=\{2,3\}\cap \{1,3\}=\{3\}\neq A</math>.

			===מכפלה קרטזית===
			הגדרה: '''המכפלה הקרטזית''' של שתי קבוצות <math>A</math> ו-<math>B</math> הינה אוסף כל ה'''זוגות הסדורים''' - <math>A\times B = \{(a,b)\|a\in A \and b\in B\}</math>. ההבדל בין זוג סדור לבין קבוצה המכילה זוג איברים היא שהאיברים יכולים להיות שווים בזוג סדור, והסדר שלהם מהותי. כלומר שני האיברים הבאים שונים <math>(1,2),(2,1)</math> והאיבר הבא הינו זוג חוקי <math>(1,1)</math>.

			דוגמה: <math>A=\{1,2,3\}</math> ו-<math>B=\{a,b\}</math> אזי מתקיים <math>A\times B =\{(1,a),(2,a),(3,a),(1,b),(2,b),(3,b)\}</math>

			למתכנתים: זה מאוד דומה ללולאות for מקוננות.

			===תרגיל===
			הוכיחו שלכל 4 קבוצות <math>A,B,C,D</math> מתקיים: <math>(A\times B)\cap (C\times D)=(A\cap C)\times (B\cap D)</math>

			====פתרון====
			<math>(x,y)\in (A\times B)\cap (C\times D) \iff </math>

			<math>(x,y)\in A\times B \land (x,y)\in C\times D \iff</math>

			<math>(x\in A \and y\in B) \and (x\in C\and y\in D) \iff</math>

			<math>(x\in A\and x\in C) \and (y\in B\and y\in D) \iff</math>

			<math>(x,y)\in (A\cap C)\times (B\cap D)</math>

אריאל ב־15:15, 14 באוקטובר 2020

2020-10-14T15:15:38Z

@@ שורה 1: / שורה 1: @@
 ==קבוצות==
@@ שורה 73: / שורה 91: @@
 <math> A \triangle C = \{1,\{1\},\{1,2\}\}</math>
 ====תרגיל====

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

2020-10-14T15:12:36Z

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

דף חדש

==קבוצות==

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

<math>\{1,\text{horse},3\}</math>, <math>\{1,2,3\}</math> ו<math>\{1,\{2,3\},\{\}\}</math>

===שייכות והכלה===

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

*אומרים שקבוצה A '''מוכלת''' בקבוצה B (מסומן <math>A \subseteq B</math>) אם כל האיברים בA הם גם איברים בB. בשפה מדויקת, A מוכלת בB אם מתקיים <math>\forall a\in A: a\in B</math>.

:דוגמא:
<math>\mathbb{N}\subset\mathbb{Z}\subset\mathbb{Q}\subset\mathbb{R}\subset\mathbb{C}</math>
כאשר
::<math>\mathbb{N}=\{1,2,3,\dots\}</math> המספרים הטבעיים
::<math>\mathbb{Z}=\{\dots,-2,-1,0,1,2,3,\dots\}</math> המספרים השלמים
::<math>\mathbb{Q}=\{\frac{m}{n} : m,n\in \mathbb{Z},n\neq 0\}</math> המספרים הרציונאלים (שברים)
::<math>\mathbb{R}</math> המספרים הממשיים ("כל המספרים" על הישר)
::<math>\mathbb{C}=\{a+bi : a,b\in \mathbb{R}, i^2 =-1\}</math> המספרים המרוכבים

====תרגיל====

נסמן <math>A=\{ 1,2,3\} ,B=\{ \{ 1\} ,\{ 2\} ,\{ 3\} \} ,C=\{1 \} ,D=\{ \{1\} \}</math>. השלימו ע"י הכלה או שייכות:

א. <math>B</math>__<math>A</math>

ב. <math>C</math>__<math>A</math>

ג. <math>B</math>__<math>C</math>

ד. <math>A</math>__<math>D</math>

ה. <math>B</math>__<math>D</math>

ו. <math>D</math>__<math>C</math>

===איחוד, חיתוך, הפרש והפרש סימטרי===

מתרגל, צייר דיאגרמות מתאימות.

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

*'''איחוד''' של שתי קבוצות A ו B הינו אוסף האיברים השייכים לA או לB (מסומן <math>A\cup B</math>). מתקיים ש<math>a \in A\cup B \iff (a\in A \or a\in B)</math>.

*קבוצות הן שוות אם הן מכילות את אותם האיברים. הדרך הנפוצה להוכיח שיוויון הינה '''הכלה דו כיוונית''': A=B אם ורק אם <math>(A\subseteq B) \and (B \subseteq A) </math>.

*A '''הפרש''' B הינה הקבוצה המכילה את כל האיברים בA שאינם בB (מסומן A\B). מתקיים ש <math>x\in A\setminus B \iff (x\in A) \and (x\notin B)</math>.

*'''ההפרש הסימטרי''' בין שתי קבוצות A וB הוא אוסף האיברים הנמצאים באחת הקבוצות אך לא בחיתוך (מסומן <math>A\triangle B</math>). מתקיים כי
<math>x\in A\triangle B \iff ((x\in A)\and (x\notin B)) \or ((x\in B)\and (x\notin A))</math>
<math>\iff x\in (A\cup B) / (A\cap B)</math>

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

דוגמא:

יהיו <math>A=\{1,2,\{1\}\},B=\{1,\{2\}\},C=\{2,\{1,2\}\}</math> קבוצות.

אזי:

<math>A\cup B =\{1,2 ,\{1\},\{2\}\} </math>

<math>(A\cup B)\cap C =\{2\} </math>

<math> B \cap C = \varnothing</math>

<math>C \setminus A =\{\{1,2\}\}</math>

<math> B \triangle C = B \cup C</math>

<math> A \triangle C = \{1,\{1\},\{1,2\}\}</math>

===כמתים===

החשובים שבהם הם הכמת "לכל" <math>\forall</math> (זו A הפוכה, קיצור המילה All) והכמת "קיים" <math>\exist</math> (זו E הפוכה, קיצור המילה Exist).

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

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

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

====תרגיל====

הוכיחו או הפריכו:

א. לכל 3 קבוצות <math>A,B,C</math> מתקיים: <math>A\cap (B\cup C)=(A\cap B) \cup (A\cap C)</math>

ב. לכל 3 קבוצות <math>A,B,C</math> מתקיים: <math>A\triangle (B\cap C)=(A\triangle B) \cap (A\triangle C)</math>

=====פתרון=====

א. הוכחה בעזרת הכלה דו כיוונית: תהיינה <math>A,B,C</math> קבוצות.

בכיוון (<math>\subseteq</math>): רוצים להוכיח ש'''לכל''' <math>x\in A\cap (B\cup C)</math> מתקיים <math>x\in (A\cap B) \cup (A\cap C)</math>. לכן ניקח איבר כללי של צד שמאל ונראה שהוא של צד ימין. פורמלית:

יהי <math>x\in A\cap (B\cup C)</math>, לכן <math>x\in A \land (x\in B \lor x\in C)</math>. שימו לב, אנחנו יושעים כעת ש- <math>x\in A</math>, ובנוסף אחד מהבאים: <math>x\in B \lor x\in C</math>. זאת אומרת שמתקיים: <math>x\in A\cap B \lor x\in A\cap C</math>, כדרוש.

בכיוון (<math>\supseteq</math>): יהי <math>x\in (A\cap B) \cup (A\cap C)</math>. לכן <math>x\in A\cap B \lor x\not\in A\cap C </math>, מה שאומר <math>x\in A</math> ובנוסף, לפחות אחד מהבאים <math>x\in B\lor x\in C</math>. כלומר בסה"כ <math>x\in A\cap (B\cup C)</math>

ב. הפרכה. כדי להפריך צריך להראות שלא לכל 3 קבוצות מתקיימת הטענה. כלומר, למצוא 3 קבוצות עבורן לא מתקיימת הטענה. זה דורש קצת משחק, לפעמים כדאי לנסות להוכיח ולראות איפה זה נתקע. כאן נשים לב שאם ניקח <math>B\cap C=\emptyset</math> אז מצד שמאל נקבל את <math>A</math>. מאידך, אם נדאג שיהיו איברים משותפים ל- <math>A,B</math> אז בצד ימין לא נקבל את כל <math>A</math>.

למשל, ניקח <math>A=\{1,2,3\},B=\{1\},C=\{2\}</math>. כאמור, מצד שמאל נקבל את <math>A</math>.

מצד ימין נקבל: <math>(A\triangle B) \cap (A\triangle C)=\{2,3\}\cap \{1,3\}=\{3\}\neq A</math>.