בחרו את התשובה הנכונה בכל סעיף. כתבו את התשובות במחברת הבחינה.
בשאלה זו בלבד אין צורך בהוכחה או בנימוק. הניקוד ניתן אך ורק על-סמך התשובה שבחרתם.
(6 נק') א. נתון: α,β פסוקים פורמליים (לאו דווקא משתנים פסוקיים!). עוד נתון, שהפסוק α→β גורר טאוטולוגית את β.
[1] מהנתון נובע, ש-β גורר טאוטולוגית את α.
[2] מהנתון נובע, ש-β אינו גורר טאוטולוגית את α.
[3] מהנתון נובע, ש-α גורר טאוטולוגית את ¬β.
[4] מהנתון נובע, ש-α אינו גורר טאוטולוגית את ¬β.
[5] הנתון בודאות אינו נכון: למעשה, לא יתכן שהפסוק α→β יגרור טאוטולוגית את β.
(תוכלו להיעזר בעובדה הבאה: אם L הוא לוח אמת המאוחד של פסוקים x1,…,xn,ψ,φ, אז: φ גורר טאוטולוגית את ψ אם ורק אם מתקיים התנאי הבא: ψ הוא אמת בכל שורה ב-L שבה φ אמת.)
(7 נק') ב. נתון, ש-F היא קבוצת כל הפונקציות f:N→N המקיימות f(n)≤n לכל n∈N (או, באופן שקול: קבוצת כל הסדרות האינסופיות (f(0),f(1),f(2),…) המקיימות f(n)≤n לכל n∈N).
אזי:
[1] ∣F∣<ℵ0.
[2] ∣F∣=ℵ0.
[3] ℵ0<∣F∣<ℵ.
[4] ∣F∣=ℵ.
[5] ∣F∣>ℵ.
(6 נק') ג. הגדרה: נאמר שצמתים u,v (לאו דווקא שונים) של גרף G מחוברים בפשטות ב-G (וכן נאמר, ש-u מחובר בפשטות ל-v ב-G) אם מתקיימים התנאים הבאים: ראשית, יש מסלול פשוט ב-G המחבר את u,v; שנית, אין מסלול לא-פשוט ב-G המחבר את u,v.
לדוגמה: בגרף המתואר בשרטוט שלהלן, v0 מחובר בפשטות ל-v1. לעומת זאת, v2 אינו מחובר בפשטות ל-v2 (כי (v2,e3,v3,e4,v4,e5,v2) הוא מסלול לא-פשוט בגרף, המחבר את v2 לעצמו.)
נתבונן כעת בטענות הבאות:
(*) לכל גרף G, אם G עץ, אז כל u,v∈V(G) מחוברים בפשטות ב-G.
() לכל גרף G, אם כל u,v∈V(G) מחוברים בפשטות ב-G, אז G** עץ.
אזי:
[1] אף אחת מבין הטענות (*) ו-(**) אינה נכונה.
[2] טענה (*) נכונה, ואילו (**) אינה נכונה.
[3] טענה (**) נכונה, ואילו (*) אינה נכונה.
[4] הטענות (*) ו-(**) נכונות שתיהן.