שאלת מבחן במתמטיקה בדידה - האוניברסיטה הפתוחה 2026 - לוגיקה

בחרו את התשובה הנכונה בכל סעיף. כתבו את התשובות במחברת הבחינה. בשאלה זו בלבד אין צורך בהוכחה או בנימוק. הניקוד ניתן אך ורק על-סמך התשובה שבחרתם. (6 נק') א. נתון: $\alpha, \beta$ פסוקים פורמליים (לאו דווקא משתנים פסוקיים!). עוד נתון, שהפסוק $\alpha \to \beta$ גורר טאוטולוגית את $\beta$. [1] מהנתון נובע, ש-$\beta$ גורר טאוטולוגית את $\alpha$. [2] מהנתון נובע, ש-$\beta$ אינו גורר טאוטולוגית את $\alpha$. [3] מהנתון נובע, ש-$\alpha$ גורר טאוטולוגית את $\neg \beta$. [4] מהנתון נובע, ש-$\alpha$ אינו גורר טאוטולוגית את $\neg \beta$. [5] הנתון בודאות אינו נכון: למעשה, לא יתכן שהפסוק $\alpha \to \beta$ יגרור טאוטולוגית את $\beta$. (תוכלו להיעזר בעובדה הבאה: אם $L$ הוא לוח אמת המאוחד של פסוקים $x_1, \dots, x_n, \psi, \varphi$, אז: $\varphi$ גורר טאוטולוגית את $\psi$ אם ורק אם מתקיים התנאי הבא: $\psi$ הוא אמת בכל שורה ב-$L$ שבה $\varphi$ אמת.) (7 נק') ב. נתון, ש-$F$ היא קבוצת כל הפונקציות $f: \mathbb{N} \to \mathbb{N}$ המקיימות $f(n) \le n$ לכל $n \in \mathbb{N}$ (או, באופן שקול: קבוצת כל הסדרות האינסופיות $(f(0), f(1), f(2), \dots)$ המקיימות $f(n) \le n$ לכל $n \in \mathbb{N}$). אזי: [1] $|F| < \aleph_0$. [2] $|F| = \aleph_0$. [3] $\aleph_0 < |F| < \aleph$. [4] $|F| = \aleph$. [5] $|F| > \aleph$. (6 נק') ג. הגדרה: נאמר שצמתים $u, v$ (לאו דווקא שונים) של גרף $G$ מחוברים בפשטות ב-$G$ (וכן נאמר, ש-$u$ מחובר בפשטות ל-$v$ ב-$G$) אם מתקיימים התנאים הבאים: ראשית, יש מסלול פשוט ב-$G$ המחבר את $u, v$; שנית, אין מסלול לא-פשוט ב-$G$ המחבר את $u, v$. לדוגמה: בגרף המתואר בשרטוט שלהלן, $v_0$ מחובר בפשטות ל-$v_1$. לעומת זאת, $v_2$ אינו מחובר בפשטות ל-$v_2$ (כי $(v_2, e_3, v_3, e_4, v_4, e_5, v_2)$ הוא מסלול לא-פשוט בגרף, המחבר את $v_2$ לעצמו.) נתבונן כעת בטענות הבאות: (*) לכל גרף $G$, אם $G$ עץ, אז כל $u, v \in V(G)$ מחוברים בפשטות ב-$G$. (**) לכל גרף $G$, אם כל $u, v \in V(G)$ מחוברים בפשטות ב-$G$, אז $G$ עץ. אזי: [1] אף אחת מבין הטענות (*) ו-(**) אינה נכונה. [2] טענה (*) נכונה, ואילו (**) אינה נכונה. [3] טענה (**) נכונה, ואילו (*) אינה נכונה. [4] הטענות (*) ו-(**) נכונות שתיהן.

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

פתרון: א. [2] ב. [4] ג. [4] **נימוק:** **סעיף א':** התשובה הנכונה היא [2]. הטענה שהפסוק $\alpha \to \beta$ גורר טאוטולוגית את $\beta$ שקולה לכך שהפסוק $(\alpha \to \beta) \to \beta$ הוא **טאוטולוגיה**. נפשט את הפסוק: $(\alpha \to \beta) \to \beta \equiv \neg(\neg\alpha \lor \beta) \lor \beta \equiv (\alpha \land \neg\beta) \lor \beta$ על פי חוק הפילוג, הביטוי שקול ל- $(\alpha \lor \beta) \land (\neg\beta \lor \beta) \equiv (\alpha \lor \beta) \land T \equiv \alpha \lor \beta$ לכן, הנתון בשאלה שקול לכך שהפסוק $\alpha \lor \beta$ הוא טאוטולוגיה. כעת נבחן את טענה [2]: "מהנתון נובע, ש-$\beta$ אינו גורר טאוטולוגית את $\alpha$". נניח בשלילה שהטענה אינה נכונה, כלומר, $\beta$ כן גורר טאוטולוגית את $\alpha$. פירוש הדבר הוא שגם $\beta \to \alpha$ היא טאוטולוגיה. אם כך, שתי הטענות הבאות הן טאוטולוגיות: 1. $\alpha \lor \beta$ 2. $\beta \to \alpha \equiv \neg\beta \lor \alpha$ מהטאוטולוגיה השנייה אנו למדים שבכל השמה של ערכי אמת שבה $\alpha$ הוא שקרי, $\beta$ חייב להיות גם כן שקרי. אך אם קיימת השמה כזו, שבה גם $\alpha$ וגם $\beta$ שקריים, הדבר עומד בסתירה לטאוטולוגיה הראשונה ($"\alpha \lor \beta$"). הדרך היחידה ליישב סתירה זו היא אם לא קיימת כלל השמה שבה $\alpha$ הוא שקרי. במילים אחרות, $\alpha$ חייב להיות טאוטולוגיה בעצמו. מכאן, שהמצב בו $\beta$ גורר טאוטולוגית את $\alpha$ יכול להתרחש רק במקרה המיוחד (המנוון) שבו $\alpha$ היא טאוטולוגיה. מכיוון שהנתון המקורי אינו מחייב ש-$"\alpha$ תהיה טאוטולוגיה (למשל, עבור $\alpha = p, \beta = \neg p$, הנתון מתקיים), המסקנה הכללית היא ש-$\beta$ אינו גורר טאוטולוגית את $\alpha$. **סעיף ב':** התשובה הנכונה היא [4]. הקבוצה $F$ היא קבוצת כל הפונקציות $f: \mathbb{N} \to \mathbb{N}$ המקיימות $f(n) \le n$ לכל $n \in \mathbb{N}$. עלינו לקבוע את העוצמה $|F|$. נמצא חסם תחתון וחסם עליון עבור $|F|$. **חסם תחתון:** לכל $n \in \mathbb{N}$, מספר האפשרויות לבחירת הערך של $f(n)$ הוא $n+1$ (הערכים $0, 1, \dots, n$). עבור $n=0$, חייב להתקיים $f(0)=0$ (אפשרות 1). עבור $n \ge 1$, יש לפחות שתי אפשרויות לערך של $f(n)$ (למשל, $0$ ו-$1$). נגדיר תת-קבוצה $F' \subseteq F$ של פונקציות המקיימות $f(0)=0$ ו-$f(n) \in \{0,1\}$ לכל $n \ge 1$. כל פונקציה כזו מקיימת את התנאי $f(n) \le n$ לכל $n \ge 1$. מספר הפונקציות ב-$F'$ הוא $|\{0,1\}|^{|\mathbb{N} \setminus \{0\}\}|} = 2^{\aleph_0} = \aleph$. מכיוון ש-$F' \subseteq F$, מתקיים $|F| \ge |F'| = \aleph$. **חסם עליון:** הקבוצה $F$ היא תת-קבוצה של קבוצת כל הפונקציות מ-$\mathbb{N}$ ל-$\mathbb{N}$, שנסמנה $G = \mathbb{N}^{\mathbb{N}}$. העוצמה של $G$ היא $|G| = |\mathbb{N}|^{|\mathbb{N}|} = \aleph_0^{\aleph_0} = (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0 \cdot \aleph_0} = 2^{\aleph_0} = \aleph$. מכיוון ש-$F \subseteq G$, מתקיים $|F| \le |G| = \aleph$. משילוב החסמים, על פי **משפט קנטור-שרדר-ברנשטיין**, אנו מקבלים $\aleph \le |F| \le \aleph$, ולכן $|F|=\aleph$.$\blacksquare$ **סעיף ג':** התשובה הנכונה היא [4]. ננתח את שתי הטענות. **טענה (*): לכל גרף $G$, אם $G$ עץ, אז כל $u, v \in V(G)$ מחוברים בפשטות ב-$G$.** נניח ש-$G$ הוא עץ. **עץ** הוא גרף קשיר וחסר מעגלים. יהיו $u,v$ צמתים כלשהם ב-$G$. 1. קיום מסלול פשוט: מכיוון ש-$G$ קשיר, קיים מסלול בין $u$ ל-$v$. בעץ, כל מסלול הוא בהכרח פשוט, כי קיום מסלול לא פשוט גורר קיום מעגל. 2. אי-קיום מסלול לא-פשוט: מסלול לא-פשוט מכיל צומת שחוזר על עצמו, ולכן הוא מכיל מעגל. מכיוון ש-$G$ הוא עץ, אין בו מעגלים, ולכן לא קיימים בו מסלולים לא-פשוטים כלל. שני התנאים להגדרה מתקיימים, ולכן טענה (*) **נכונה**.$\blacksquare$ **טענה (**): לכל גרף $G$, אם כל $u, v \in V(G)$ מחוברים בפשטות ב-$G$, אז $G$ עץ.** נניח שכל $u, v \in V(G)$ מחוברים בפשטות. כדי להוכיח ש-$G$ הוא עץ, עלינו להוכיח שהוא קשיר וחסר מעגלים. 1. **קשירות:** יהיו $u,v$ שני צמתים שונים בגרף. לפי הנתון, הם מחוברים בפשטות. התנאי הראשון של ההגדרה הוא שקיים מסלול פשוט המחבר אותם. מכיוון שקיים מסלול בין כל שני צמתים בגרף, הגרף $G$ **קשיר**. 2. **חוסר מעגלים:** יהי $u$ צומת כלשהו בגרף. לפי הנתון, $u$ מחובר בפשטות לעצמו. נבחן את התנאי השני של ההגדרה עבור המקרה $v=u$: "אין מסלול לא-פשוט ב-$G$ המחבר את $u, u$". מסלול לא-פשוט מ-$u$ לעצמו הוא בדיוק **מעגל** העובר דרך $u$. מכיוון שתנאי זה נכון לכל צומת $u$ בגרף, נובע שבגרף אין מעגלים כלל. כלומר, $G$ הוא **חסר מעגלים**. מכיוון ש-$G$ הוא גרף קשיר וחסר מעגלים, הוא **עץ**. לכן טענה (**) **נכונה**.$\blacksquare$