א. (6 נק') נתון: α,β,γ פסוקים פורמליים (לאו דוקא משתנים פסוקיים);
α∧(¬β) אינו גורר טאוטולוגית את γ.
אזי:
[1] מהנתון נובע, כי α גורר טאוטולוגית את β.
[2] מהנתון נובע, כי α אינו גורר טאוטולוגית את β.
[3] מהנתון נובע, כי β גורר טאוטולוגית את α.
[4] מהנתון נובע, כי β אינו גורר טאוטולוגית את α.
[5] אף אחת מהטענות [1]-[4] אינה נכונה.
ב. (7 נק') נתבונן בשני התנאים הבאים על קבוצה A:
(*) לכל יחס סדר חלקי ≺ על A, בקבוצה הסדורה חלקית ⟨A,≺⟩ יש איבר מינימלי.
() A=∅, ולא קיימת f:N→A** חח"ע.
אזי:
[1] כל קבוצה **A המקיימת את (*) מקיימת גם את (), אבל לא כל קבוצה A המקיימת את (**) מקיימת את (*).
[2] כל קבוצה **A המקיימת את () מקיימת גם את (*), אבל לא כל קבוצה A המקיימת את (*) מקיימת את (**).
[3] כל קבוצה **A המקיימת את (*) מקיימת גם את (), וכל קבוצה A המקיימת את (**) מקיימת את (*).
[4] לא כל קבוצה **A המקיימת את (*) מקיימת גם את (), ולא כל קבוצה A המקיימת את (**) מקיימת את (*).
הערה: תוכלו להיעזר בעובדה, שהיחס הריק הוא יחס סדר חלקי על הקבוצה הריקה.
ג. (6 נק') הגדרה: מסלול גמור בגרף G הוא מסלול P ב-G, המקיים את התנאי הבא: אין ב-G אף מסלול ארוך יותר מ-P, שמתקבל מ-P על-ידי הוספת מספר חיובי של קשתות וצמתים בסופו.
נתבונן בתנאי הבא על גרף G:
(*) כל מסלול גמור ב-G מסתיים בצומת שדרגתו (ב-G) היא 1.
נתון: T עץ, המקיים ∣V(T)∣≥2 ; H גרף, שמתואר על-ידי השרטוט הבא:
אזי:
[1] T אינו מקיים את (*), וגם H אינו מקיים את (*).
[2] T מקיים את (*), אבל H אינו מקיים את (*).
[3] H מקיים את (*), אבל T אינו מקיים את (*).
[4] גם T וגם H מקיימים את (*).