בחרו את התשובה הנכונה בכל סעיף. כתבו את התשובות במחברת הבחינה.
בשאלה זו בלבד אין צורך בהוכחה או בנימוק. הניקוד ינתן אך ורק על-סמך התשובה שבחרתם.
(6 נק') א. נתון ש- α,β הם פסוקים פורמליים כלשהם (לאו דוקא משתנים פסוקיים!). נתבונן בפסוקים:
α→(α∨β)(∗)(α∨β)→α(∗∗)
אזי:
[1] מהנתון נובע ש-**(∗)** ו-(∗∗) שניהם טאוטולוגיות.
[2] מהנתון לא נובע ש-(∗) הוא טאוטולוגיה, ולא נובע ש-(∗∗) הוא טאוטולוגיה.
[3] מהנתון נובע ש-**(∗)** הוא טאוטולוגיה וש-(∗∗) אינו טאוטולוגיה.
[4] אף אחת מהטענות [1]-[3] אינה נכונה.
(7 נק') ב. הגדרה: נאמר כי קבוצות A,B הן כמעט שוות אם ∣AΔB∣≤ℵ0.
נתון: S⊆P(R); כל A,B∈S הן כמעט שוות. כמו כן, ידוע (נתון), שעוצמת הקבוצה {X⊆R∣X בת-מניה} היא ℵ.
אזי:
[1] מהנתון נובע ש-∣S∣≤ℵ0.
[2] טענה [1] אינה נכונה, אבל מהנתון נובע ש-∣S∣≤ℵ.
[3] טענה [2] אינה נכונה, אבל מהנתון נובע ש-∣S∣≤ℵ. (תזכורת: ∣P(R)∣=ℵ.)
[4] אף אחת מהטענות [1]-[3] אינה נכונה.
הערה: חוק הצמצום של פעולת ההפרש הסימטרי עשוי לעזור כאן.
(6 נק') ג. נתבונן בתנאי הבא על עץ T:
(∗)T עץ על {1,2,…,10}, ומתקיים degT(1)≥7.
מהו מספר העצים המקיימים את (∗), בהנחה שעצים איזומורפיים נחשבים זהים?
[1] 36
[2] 64
[3] 2800
[4] 2341
[5] אף אחת מהתשובות [1]-[4] אינה נכונה.