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

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

סוגי שאלות

שוויון/הכלה של קבוצות עם דיאגרמות ון ודוגמאות נגדיות
טבלאות אמת ושקילות לוגית
כמתים: $\forall$ , $\exists$ — קביעת ערך אמת

שאלה מייצגת: שוויון קבוצות

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

כן. זהו חוק דה-מורגן להפרש קבוצות. ציור דיאגרמת ון מאמת.

כלל אצבע

$A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)$ ו- $A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)$ . שימו לב: $\cup \leftrightarrow \cap$ מתהפכים.

דוגמה נגדית עם איבר אחד

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

לא. דוגמה: $A = \emptyset$ , $B = C = \{1\}$ .

אגף שמאל: $(\{1\} \setminus \emptyset) \cap \{1\} = \{1\}$ . אגף ימין: $\emptyset \cap \{1\} = \emptyset$ .

שקילות לוגית

שאלה: האם $(P \leftrightarrow Q) \land R \iff (P \land R) \leftrightarrow (Q \land R)$ ?

לא. הצבה $P = Q = R = 0$ : אגף שמאל = $0$ , אגף ימין = $1$ .

שאלה: האם $(P \leftrightarrow Q) \lor R \iff (P \lor R) \leftrightarrow (Q \lor R)$ ?

כן. טבלאות האמת זהות.

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

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

טענה	ערך	הסבר
$\forall x \in A\ \exists y \in B:\ x+y < 7$	נכון	$1 \mapsto 4, 2 \mapsto 4, 3 \mapsto 3$
$\exists x \in A\ \forall y \in B:\ x+y < 7$	לא נכון	שום $x$ לא עובד עם $y=6$
$\forall y \in B\ \exists x \in A:\ x+y < 7$	לא נכון	$y=6$ : שום $x \in A$ לא מקיים
$\exists y \in B\ \forall x \in A:\ x+y < 7$	נכון	$y=3$ : $1+3, 2+3, 3+3$ כולם $< 7$

טיפים לתרגיל בית 1

דוגמאות נגדיות

כשטענה לא מתקיימת, צריך דוגמה מפורשת. התנאי בדרך כלל: $A \cup B \cup C$ בעלת איבר אחד — מצמצם את מרחב החיפוש.

שיטת עבודה לכמתים

כתבו את הטענה במילים. 2. נסו להציב ערכים ספציפיים. 3. עבור $\forall$ — חפשו דוגמה נגדית. עבור $\exists$ — חפשו עד אחד.

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

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

סוגי שאלות

שוויון/הכלה של קבוצות עם דיאגרמות ון ודוגמאות נגדיות
טבלאות אמת ושקילות לוגית
כמתים: $\forall$ , $\exists$ — קביעת ערך אמת

שאלה מייצגת: שוויון קבוצות

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

כן. זהו חוק דה-מורגן להפרש קבוצות. ציור דיאגרמת ון מאמת.

כלל אצבע

$A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)$ ו- $A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)$ . שימו לב: $\cup \leftrightarrow \cap$ מתהפכים.

דוגמה נגדית עם איבר אחד

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

לא. דוגמה: $A = \emptyset$ , $B = C = \{1\}$ .

אגף שמאל: $(\{1\} \setminus \emptyset) \cap \{1\} = \{1\}$ . אגף ימין: $\emptyset \cap \{1\} = \emptyset$ .

שקילות לוגית

שאלה: האם $(P \leftrightarrow Q) \land R \iff (P \land R) \leftrightarrow (Q \land R)$ ?

לא. הצבה $P = Q = R = 0$ : אגף שמאל = $0$ , אגף ימין = $1$ .

שאלה: האם $(P \leftrightarrow Q) \lor R \iff (P \lor R) \leftrightarrow (Q \lor R)$ ?

כן. טבלאות האמת זהות.

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

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

טענה	ערך	הסבר
$\forall x \in A\ \exists y \in B:\ x+y < 7$	נכון	$1 \mapsto 4, 2 \mapsto 4, 3 \mapsto 3$
$\exists x \in A\ \forall y \in B:\ x+y < 7$	לא נכון	שום $x$ לא עובד עם $y=6$
$\forall y \in B\ \exists x \in A:\ x+y < 7$	לא נכון	$y=6$ : שום $x \in A$ לא מקיים
$\exists y \in B\ \forall x \in A:\ x+y < 7$	נכון	$y=3$ : $1+3, 2+3, 3+3$ כולם $< 7$

טיפים לתרגיל בית 1

דוגמאות נגדיות

כשטענה לא מתקיימת, צריך דוגמה מפורשת. התנאי בדרך כלל: $A \cup B \cup C$ בעלת איבר אחד — מצמצם את מרחב החיפוש.

שיטת עבודה לכמתים

כתבו את הטענה במילים. 2. נסו להציב ערכים ספציפיים. 3. עבור $\forall$ — חפשו דוגמה נגדית. עבור $\exists$ — חפשו עד אחד.