תרגול 1 — קבוצות, לוגיקה וכמתים

תרגיל כיתה 1 | מתמטיקה דיסקרטית — HUJI | ספר: ליניאל ופרנס

שאלות קבוצות ודיאגרמות ון

שוויון קבוצות בעזרת ון

שאלה: האם $A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)$ לכל $A, B, C$?

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

הכלה עם דוגמה נגדית

שאלה: האם $(A \cup C) \setminus (B \setminus C) \subseteq (A \setminus B) \cup (C \setminus A)$?

תשובה: לא. דוגמה נגדית: $A = B = C = \{1\}$.

אגף שמאל: $(A \cup C) \setminus (B \setminus C) = \{1\} \setminus \emptyset = \{1\}$

אגף ימין: $(A \setminus B) \cup (C \setminus A) = \emptyset \cup \emptyset = \emptyset$

ולכן $\{1\} \not\subseteq \emptyset$.

טבלאות אמת

בניית טבלת אמת

שאלה: בנו טבלת אמת ל-$(P \to Q) \lor \neg R$.

שקילות לוגית

שאלה: האם $\neg(P \to Q) \iff P \land \neg Q$?

שתי דרכים לפתור:

1. טבלת אמת — בונים טבלאות לשני הצדדים ורואים שהעמודות זהות.

2. אלגברה בוליאנית:

$\neg(P \to Q) \iff \neg(\neg P \lor Q) \iff P \land \neg Q$

כמתים (Quantifiers)

כמת אוניברסלי vs. קיומי

תהא $A = \{1, 2, 3\}$.

• $\forall x \in A:\ 2 \mid x$ — לא נכון ($x=1$ לא מתחלק ב-2)
• $\exists x \in A:\ 2 \mid x$ — נכון ($x=2$ מתחלק ב-2)

כמתים מקוננים

יהיו $A = \{1,2,3\}$, $B = \{4,5,6\}$.

• $\forall x \in A\ \exists y \in B:\ x + y = 7$ — נכון (לכל $x$ מתאים $y$: $1 \mapsto 6, 2 \mapsto 5, 3 \mapsto 4$)
• $\exists x \in A\ \forall y \in B:\ x + y = 7$ — לא נכון (אין $x$ יחיד שעובד לכל $y$)