סיכום מקיף – מתמטיקה דיסקרטית למ"מ – לוגיקה, קבוצות ויחסים

לוגיקה בסיסית

• טענה (Proposition): אמירה אשר ערך האמת שלה $T$ או $F$.
  • סימון מקובל: $A,B,a,b,\dots$
  • דוגמאות
  • "היום יום שישי" – שקר $F$.
  • "אנחנו לומדים מתמטיקה דיסקרטית" – אמת $T$.
  • "בואו לטיול בלונדון" – אינה טענה, חסר ערך־אמת.
• לא כל אמירה היא טענה – תנאי חיוני: ניתן לקבוע אמת/שקר.

קשרים לוגיים וטבלאות אמת

• ארבעת הקשרים הבסיסיים: "לא" $\lnot$, "וגם" $\land$, "או" $\lor$, "אם-אז" $\to$.
• ניתן לבנות כל נוסחה באמצעות תת-קבוצה קטנה יותר, אך נוח להשאיר את כל הארבעה.
• טבלאות אמת מרכזיות
  • $A\lor B$ – אמת אם לפחות אחת מהטענות אמת.
  • $\lnot A$ – הופכי הערך של $A$.
  • $A\land B$ – אמת רק כאשר שתיהן אמת.
  • $A\to B$ – שקר רק כש$A=T,\,B=F$; בכל מקרה אחר אמת (נכונות ריקה).
• דוגמת הקלפים (Wason Selection Task) מדגימה הגדרת $A\to B$ באמצעות בדיקת סתירות.

קשר "אם ורק אם"

• סימון $A\iff B$ או $A\leftrightarrow B$.
• פרשנות: $\big(A\to B\big)\land\big(B\to A\big)$.
• תנאי הכרחי ומספיק, שימוש נפוץ בהוכחות.

שקילות לוגית וחוקים אלגבריים

• שקילות $P\equiv Q$ – לשני משפטים אותה טבלת אמת.
• חוקים עיקריים
  • $\lnot(\lnot A)\equiv A$ (כפילת הכפילה).
  • קומוטטיביות
  • $A\land B\equiv B\land A$ ; $A\lor B\equiv B\lor A$.
  • אסוציאטיביות
  • $(A\land B)\land C\equiv A\land(B\land C)$ (ולמקבילה עבור $\lor$).
  • דיסטריבוטיביות
  • $(A\lor B)\land C\equiv(A\land C)\lor(B\land C)$ וכו'.
• חוקי דה-מורגן ללוגיקה
  • $\lnot(P\lor Q)\equiv(\lnot P)\land(\lnot Q)$.
  • $\lnot(P\land Q)\equiv(\lnot P)\lor(\lnot Q)$.

היסקים ושיטות הוכחה

• Modus Tollens, Modus Ponens, חלוקה למקרים.
• קונטרפוזיטיב: $A\to B\equiv \lnot B\to\lnot A$ – מאפשר "הוכחה בשלילה".

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

• פרדיקט – אמירה עם משתנים; הצבה הופכת לטענה.
• כמתים
  • "לכל" $\forall$ – $\forall x\in A: P(x)$.
  • "קיים" $\exists$ – $\exists x\in A: P(x)$.
• שלילת כמתים
  • $\lnot\forall x\,P(x)\equiv\exists x\,\lnot P(x)$.
  • $\lnot\exists x\,P(x)\equiv\forall x\,\lnot P(x)$.
• סדר כמתים זרים חשוב: $\forall a\exists b\ne\exists b\forall a$.

מבוא לתורת הקבוצות

• "קבוצה" ו"איבר" – מושגים פרימיטיביים; קבוצה = אוסף עצמים.
• סימון איבר: $x\in A$; העדר איבר: $x\notin A$.
• אוספים סטנדרטיים
  • $\emptyset$ – הריקה.
  • $\mathbb N,\,\mathbb Z,\,\mathbb Q,\,\mathbb R$.
• ייצוג סט עם סוגריים מסולסלים, ללא חזרות, סדר לא קובע.

פעולות על קבוצות וחוקי דה-מורגן

• חיתוך $A\cap B$, איחוד $A\cup B$, הפרש $A\setminus B$.
• משלים ביחס ליקום $U$: $A^c = U\setminus A$.
• דה-מורגן לקבוצות
  • $(A\cap B)^c=A^c\cup B^c$ ; $(A\cup B)^c=A^c\cap B^c$.

קבוצת החזקה ועיקרון העוצמה

• $\mathcal P(A)={X\mid X\subseteq A}$.
• אם $|A|=n$ סופי, אז $|\mathcal P(A)|=2^n$.

חיתוך ואיחוד כללי

• איחוד אינדקסיאלי $\bigcup<em>{i\in I}A</em>i={x\mid\exists i\in I:\,x\in A_i}$.
• חיתוך אינדקסיאלי $\bigcap<em>{i\in I}A</em>i={x\mid\forall i\in I:\,x\in A_i}$.
• שימוש במשפחות – מקל על עבודה עם $n$ ואף $\infty$ קבוצות.

חלוקות ועידון

• חלוקה $\mathcal F\subseteq\mathcal P(A)$: כיסוי מלא, מחלקות זרות, לא ריקות.
• עידון: $\mathcal F<em>1$ מעדנת $\mathcal F</em>2$ אם כל מחלקה של $\mathcal F<em>1$ כלולה באחת מ$\mathcal F</em>2$.

מכפלה קרטזית וטפלות

• $A\times B={(a,b)\mid a\in A,\,b\in B}$.
• זוג סדור בלתי מתחלף $(a,b)\neq(b,a)$.
• עקרון הכפל (לספור): $|A\times B|=|A|\cdot|B|$.
• הרחבה ל-$n$ טפלות $\prod<em>{i=1}^{n}A</em>i$.

יחסים – הגדרה ומספר היחסים

• יחס $R$ מ-$A$ ל-$B$ – תת-קבוצה $R\subseteq B\times A$.
• על קבוצה בגודל $n$ יש $2^{n^2}$ יחסים אפשריים.

תכונות יחסים

• רפלקסיבי – $\forall a:\,(a,a)\in R$.
• סימטרי – $\forall a,b:(a,b)\in R\Rightarrow(b,a)\in R$.
• אנטי-סימטרי – $\forall a\ne b:(a,b),(b,a)\in R\Rightarrow a=b$.
• טרנזיטיבי – $\forall a,b,c:(a,b),(b,c)\in R\Rightarrow(a,c)\in R$.
• יחס עשוי להיות "ריק" באופן רפלקסיבי/טרנזיטיבי אם התנאי השמאלי אינו מתקיים.

יחסי שקילות ומחלקות שקילות

• יחס שקילות = רפלקסיבי $+$ סימטרי $+$ טרנזיטיבי.
• מחלקת שקילות $[a]_R={x\in A\mid aRx}$.
• כל שתי מחלקות זרות או זהות; אוסף המחלקות יוצר חלוקה $A/R$.

קבוצת מנה ומבנה $\mathbb Q$

• בונים $\mathbb Q$ כקבוצת מחלקות שקילות על $A=\mathbb Z\times\mathbb N^+$ עם $(a,b)\sim(c,d)\iff ad=bc$.
• כל מחלקה מייצגת שבר מצומצם $\tfrac ab$.

יחסי סדר חלקי ומלא

• סדר חלקי (Poset) – יחס רפלקסיבי, אנטי-סימטרי, טרנזיטיבי.
• משווה: לכל $x\ne y$ – $xRy$ או $yRx$.
• סדר מלא (טוטלי/לינארי) = חלקי $+$ משווה.
• היחס ההפוך $R^{-1}$ שומר על מאפייני סדר/שקילות.

איברים מיוחדים במערכות מסודרות

• מינימלי – אין קטן ממש ממנו; עשויים להיות רבים.
• מינימום – קטן (או שווה) לכולם, ייחודי ואם קיים ⇒ מינימלי.
• מקסימום/מקסימלי – הגדרות דואליות.
• בטוטאלי – מינימום הוא "איבר ראשון", מקסימום "אחרון".

סדרים נפוצים: לקסיקוגרפי וקרטזי

• $\le<em>{\text{lex}}$ — משווים קודם רכיב ראשון ("מילון"), ורק אם שווים עוברים לשני. $(a</em>1,b<em>1)\le</em>{lex}(a<em>2,b</em>2) \iff a<em>1<a</em>2 \text{ or }(a<em>1=a</em>2 \land b<em>1\le b</em>2)$.
• $\le<em>{\text{cart}}$ — דרישה בו-זמנית: $a</em>1\le a<em>2 \land b</em>1\le b_2$.
• $\le<em>{lex}$ יוצר קס"ל; $\le</em>{cart}$ יוצר קס"ח בלבד.

דיאגרמת האסה

• ייצוג גרפי חסכוני של Poset.
• קו אנכי אחד = "יש איבר ביניים" לא מצויר.
• Poset ליניארי ⇒ הדיאגרמה קו ישר.

קשרים לקורסים במדעי המחשב

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