בחרו את התשובה הנכונה בכל סעיף. כתבו את התשובות במחברת הבחינה. בשאלה זו בלבד אין צורך בהוכחה או בנימוק. הניקוד ינתן אך ורק על-סמך התשובה שבחרתם.
(6 נק') א. נתון: α,β פסוקים פורמליים כלשהם (לאו דווקא משתנים פסוקיים!).
נתבונן בפסוקים הבאים:
(α→β)∨(β→α)(∗)α↔β(∗∗)
אזי:
[1] מהנתון נובע, שהפסוקים (*) ו-(**) גוררים טאוטולוגית זה את זה.
[2] מהנתון נובע, ש-(*) גורר טאוטולוגית את () וש-() אינו גורר טאוטולוגית את (*).
[3] מהנתון נובע, ש-() גורר טאוטולוגית את (*) וש-(*) אינו גורר טאוטולוגית את ().
[4] מהנתון לא נובע ש-(*) גורר טאוטולוגית את (), ולא נובע ש-() גורר טאוטולוגית את (*).
[5] אף אחת מהטענות [1]–[4] אינה נכונה.
(7 נק') ב. נתון: A קבוצה אינסופית ; f:AN→A ; לכל סדרה ⟨a0,a1,a2,…⟩ של איברי A
מתקיים התנאי הבא: f(⟨a0,a1,a2,…⟩)=a0,a1,a2,… (במלים: הדמות על-ידי f של הסדרה ⟨a0,a1,a2,…⟩ שונה מכל אחד מרכיבי הסדרה הזו.)
אזי:
[1] מהנתון נובע, כי ℵ0=∣A∣.
[2] מהנתון נובע, כי ℵ=∣A∣.
[3] אף אחת מהטענות [1]-[2] אינה נכונה, אבל מהנתון נובע ש- ℵ0≤∣A∣≤ℵ.
[4] אף אחת מהטענות [1]-[3] אינה נכונה, אבל מהנתון נובע ש- ∣A∣>ℵ0.
[5] אף אחת מהטענות [1]-[4] אינה נכונה.
(6 נק') ג. יהי k מספר העצים המתויגים T, המקיימים את התנאים הבאים, כאשר עצים מתויגים איזומורפיים (במובן של הגדרה 2.8) נחשבים זהים:
(*) T עץ על ארבעה צמתים.
() תגי הצמתים ב-T הם 1,2,3,4**.
(***) דרגת כל צומת ב-T שונה מהתג של אותו צומת ב-T.
אזי:
[1] k=5.
[2] k=6.
[3] k=8.
[4] אף אחת מהטענות [1]–[3] אינה נכונה.