בחרו את התשובה הנכונה בכל סעיף. כתבו את התשובות במחברת הבחינה.
בשאלה זו בלבד אין צורך בהוכחה או בנימוק. הניקוד יינתן אך ורק על-סמך התשובה שבחרתם.
(6 נק') א. נתון ש- α,β פסוקים פורמליים (לאו דווקא משתנים פסוקיים!) וש- α→β גורר טאוטולוגית את α.
אזי:
[1] מהנתון נובע, כי α גורר טאוטולוגית את ¬β.
[2] מהנתון נובע, כי α גורר טאוטולוגית את β.
[3] מהנתון נובע, כי β גורר טאוטולוגית את α.
[4] אף אחת מהטענות [1]-[3] אינה נכונה.
(תוכלו להיעזר בעובדה הבאה: אם L הוא לוח אמת המאוחד של פסוקים φ,ψ,χ1,…,χn, אז: φ גורר טאוטולוגית את ψ אם"ם מתקיים התנאי הבא: ψ הוא אמת בכל שורה ב-L שבה φ אמת.)
(7 נק') ב. תהי F קבוצת כל הפונקציות f:N→N שעבורן הקבוצה {k∈N∣f(k)=0} סופית. אזי:
[1] ∣F∣=ℵ0.
[2] ℵ0<∣F∣<ℵ.
[3] ∣F∣=ℵ.
[4] אף אחת מהטענות [1]-[3] אינה נכונה.
רמז: חשבו על קבוצת כל הסדרות מהצורה ⟨a0,a1,…,am,0,0,0,…⟩ המקיימות m,a0,a1,…,am∈N. מהי עוצמתה? ומה הקשר לשאלה שלעיל?
(6 נק') ג. נתבונן בתנאים הבאים על עץ מתויג T:
(*) התגים של T הם 1,2,3,…,10.
() צמתי T שתגיהם 1,2,3,4 הם עלים ב-T**.
(***) לצמתים שתגיהם 1,2 יש שכן משותף ב-T, וגם לצמתים שתגיהם 3,4 יש שכן משותף ב-T.
יהי k מספר העצים המתויגים המקיימים את התנאים (*)-(***), כאשר עצים מתויגים איזומורפיים (במובן של הגדרה 2.8) נחשבים זהים. אזי:
[1] k=46656
[2] k=38880
[3] k=77760
[4] k=7680
[5] אף אחת מהטענות [1]-[4] אינה נכונה.