שאלה 1 — אינדוקציה מבנית על פסוקים

השאלה

בשפה הפסוקית L משתמשים בקשרים הבאים:

{¬, ∧, ∨, →, ↔}

נסמן ב־S(φ) את מספר הסוגריים בפסוק φ, לפי ההגדרה הרקורסיבית:

לפסוק אטומי φ נקבע S(φ)=0.

כאשר φ=¬ψ, מתקיים S(φ)=S(ψ).

כאשר φ=(ψ @ χ) ו־@ הוא קשר בינארי, מתקיים S(φ)=S(ψ)+S(χ)+2.

הראו באמצעות אינדוקציה מבנית שלכל פסוק φ מתקיים S(φ)=2·bin(φ).

מהו bin?

bin(φ) הוא פשוט מספר הקשרים הבינאריים המופיעים בפסוק φ.

בפסוק אטומי אין קשרים בינאריים.

שלילה ¬ היא קשר אונרי, ולכן אינה מוסיפה קשר בינארי.

בפסוק (ψ@χ) סופרים את הקשרים שב־ψ, את הקשרים שב־χ, ועוד את הקשר החיצוני @.

נסמן את הטענה שאותה מוכיחים:

P(φ): S(φ)=2·bin(φ)

כל קשר בינארי חדש מוסיף קשר בינארי אחד ושני סוגריים. שלילה אינה מוסיפה אף אחד מהם.

הוכחה באינדוקציה מבנית

בסיס — פסוק אטומי

יהי φ=p פסוק אטומי.

S(p)=0 לפי הגדרת S עבור פסוק אטומי.

bin(p)=0 בפסוק אטומי אין קשר בינארי.

S(p)=0=2·0=2·bin(p) מציבים את שני הערכים שקיבלנו.

לכן הטענה P(p) נכונה בבסיס.

צעד — שלילה

הנחת האינדוקציה: הטענה נכונה עבור תת־הפסוק ψ:

S(ψ)=2·bin(ψ)

נוכיח אותה עבור φ=¬ψ:

S(¬ψ)=S(ψ) לפי ההגדרה הרקורסיבית של S במקרה של שלילה.

S(¬ψ)=2·bin(ψ) מציבים את הנחת האינדוקציה.

S(¬ψ)=2·bin(¬ψ) שלילה היא קשר אונרי, ולכן מספר הקשרים הבינאריים אינו משתנה.

לכן הטענה P(¬ψ) נכונה.

צעד — קשר בינארי

יהי φ=(ψ@χ).

הנחות האינדוקציה:

S(ψ)=2·bin(ψ)

S(χ)=2·bin(χ)

S((ψ@χ))=S(ψ)+S(χ)+2 לפי ההגדרה הרקורסיבית של S לקשר בינארי.

=2·bin(ψ)+2·bin(χ)+2 מציבים את שתי הנחות האינדוקציה.

=2·(bin(ψ)+bin(χ)+1) מוציאים גורם משותף 2.

=2·bin((ψ@χ)) מספר הקשרים הבינאריים הוא אלה שבשני תת־הפסוקים ועוד הקשר החיצוני @.

לכן הטענה P((ψ@χ)) נכונה לכל קשר בינארי @.

הטענה הוכחה בבסיס ובכל דרכי הבנייה של פסוק בשפה L. לכן, באינדוקציה מבנית, לכל פסוק φ מתקיים S(φ)=2·bin(φ).

שאלה 2 — XOR ושלמות פונקציונלית

השאלה

הקשר ⊕ מקבל T בדיוק כאשר אחד משני הפסוקים מקבל T והאחר מקבל F.

א.קבעו, ונמקו, האם קבוצת הקשרים {⊕, ∧} שלמה.

ב.קבעו, ונמקו, האם קבוצת הקשרים {⊕, ∨} שלמה.

ג.בעזרת טבלת אמת בנו DNF ו־CNF עבור הפסוק ((A ⊕ B) → C).

הרעיון

בודקים פעם אחת את הקבוצה הגדולה K={∧,∨,⊕}.

במודל שבו כל המשתנים מקבלים F, כל שלושת הקשרים מחזירים F.

אבל שלילה מחזירה T כאשר המשתנה הוא F. לכן K אינה שלמה.

כל תת־קבוצה של K אינה יכולה להיות שלמה; מכאן מקבלים יחד את סעיפים א ו־ב.

בסעיף ג: בונים טבלת אמת. שורות שבהן θ=T נותנות את ה־DNF; שורות שבהן θ=F נותנות את ה־CNF.

א–ב. הוכחה אחת לשתי הקבוצות

שתי הקבוצות שבשאלה הן תת־קבוצות של הקבוצה הגדולה:

K = {∧, ∨, ⊕}

טענה: כל נוסחה φ הנבנית בעזרת קשרים מ־K מקבלת את הערך F כאשר כל המשתנים מקבלים F.

נסמן ב־v_F את המודל שבו כל משתנה מקבל את הערך F. נוכיח את הטענה באינדוקציה מבנית.

בסיס

אם φ=p הוא משתנה, אז לפי הגדרת המודל:

v_F(p)=F

הנחת האינדוקציה

לנוסחאות α,β שכבר נבנו נניח:

v_F(α)=v_F(β)=F

צעד האינדוקציה

לכל אחת משלוש דרכי הבנייה הבינאריות:

v_F((α ∧ β)) = v_F(α) ∧ v_F(β) = F ∧ F = F

v_F((α ∨ β)) = v_F(α) ∨ v_F(β) = F ∨ F = F

v_F((α ⊕ β)) = v_F(α) ⊕ v_F(β) = F ⊕ F = F

לכן כל נוסחה מעל K שומרת את הערך F. אבל כאשר p=F, מתקיים ¬p=T. מכאן שאי אפשר לבטא שלילה בעזרת K, ולכן K אינה שלמה.

{⊕,∧} ⊆ K, ולכן הקבוצה בסעיף א אינה שלמה.

{⊕,∨} ⊆ K, ולכן הקבוצה בסעיף ב אינה שלמה.

אילו אחת מתת־הקבוצות הייתה שלמה, גם הקבוצה הגדולה K המכילה אותה הייתה שלמה. קיבלנו ש־K אינה שלמה, ולכן אף אחת משתי תת־הקבוצות אינה שלמה.

ג. טבלת אמת וממנה DNF ו־CNF

נסמן θ=((A⊕B)→C). גרירה שקרית רק כאשר הרישה אמיתית והסיפה שקרית.

A	B	C	A⊕B	θ
F	F	F	F	T
F	F	T	F	T
F	T	F	T	F
F	T	T	T	T
T	F	F	T	F
T	F	T	T	T
T	T	F	F	T
T	T	T	F	T

DNF — כל השורות שבהן θ=T

בכל שורה: ערך T נותן משתנה, ערך F נותן את שלילתו. בתוך כל שורה מחברים ב־∧, ואת כל השורות מחברים ב־∨.

DNF = (¬A∧¬B∧¬C) ∨ (¬A∧¬B∧C) ∨ (¬A∧B∧C) ∨
(A∧¬B∧C) ∨ (A∧B∧¬C) ∨ (A∧B∧C)

CNF — כל השורות שבהן θ=F

בכל שורה: ערך F נותן משתנה, ערך T נותן את שלילתו. בתוך כל שורה מחברים ב־∨, ואת כל השורות מחברים ב־∧.

בשורה (A,B,C)=(F,T,F) הפסוקית השקרית היא (A∨¬B∨C).

בשורה (A,B,C)=(T,F,F) הפסוקית השקרית היא (¬A∨B∨C).

CNF = (A ∨ ¬B ∨ C) ∧ (¬A ∨ B ∨ C)

dsall.netlify.app

שאלה 3 — תקפות ומודלים בשפת היחסים

השאלה

א. בדקו אם הנוסחה הבאה תקפה לוגית, והוכיחו את קביעתכם: (∀x∀y(R(x,y) → R(y,x))) → ∀x∀y(R(x,y) ↔ R(y,x))

ב. הכריעו אם הנוסחה הבאה תקפה לוגית; אם לא, הציגו הפרכה: (∀x∃y R(x,y)) → ∃y∀x R(x,y)

ג. נתון מודל M שתחומו ℤ, ובו R(x,y) מתפרש כ־x<y. קבעו אם הנוסחה הבאה אמיתית במודל: ∀x∃y (R(x,y) ∧ ¬∃z(R(x,z) ∧ R(z,y)))

א. הוכחה

אמיתית לוגית

יהי 𝔄 מבנה כלשהו שבו רישת הגרירה אמיתית:

𝔄 ⊨ ∀x∀y(R(x,y) → R(y,x))

1 נבחר איברים שרירותיים a,b בתחום.

2 מההנחה, בהצבה x=a,y=b:

R(a,b) → R(b,a)

3 אותה הנחה חלה גם אחרי החלפת האיברים, כלומר בהצבה x=b,y=a:

R(b,a) → R(a,b)

4 משתי הגרירות נקבל R(a,b)↔R(b,a).

מאחר ש־a,b שרירותיים, מתקיים ∀x∀y(R(x,y)↔R(y,x)). לכן הנוסחה אמיתית בכל מבנה.

ב. הפרכה באמצעות מודל נגדי

אינה אמיתית לוגית

נבחר מודל 𝔐 עם התחום:

D = {1,2}

נפרש את R כיחס השוויון:

R^𝔐 = {(1,1),(2,2)}

R	y=1	y=2
x=1	1	0
x=2	0	1

הרישה אמיתית: עבור x=1 בוחרים y=1; עבור x=2 בוחרים y=2. לכן ∀x∃yR(x,y).

הסיפה שקרית: אם y=1, אז R(2,1) שקרי; אם y=2, אז R(1,2) שקרי. לכן ¬∃y∀xR(x,y).

במודל זה הרישה אמיתית והסיפה שקרית, ולכן הגרירה שקרית. זהו מודל נגדי.

ג. בדיקה במודל המספרים השלמים

הנוסחה אמיתית תחת M

יהי x∈ℤ שרירותי. נבחר:

… x → y=x+1 …

1 מתקיים R(x,y), מפני ש־x<x+1.

2 לא קיים מספר שלם z המקיים בו־זמנית x<z וגם z<x+1.

3 לכן ¬∃z(R(x,z)∧R(z,y)).

לכל x∈ℤ מצאנו y=x+1 המקיים את שני חלקי החיתוך. לכן M ⊨ ∀x∃y(R(x,y)∧¬∃z(R(x,z)∧R(z,y))).

שאלה 4 — לוגיקה בשפת היחסים

השאלה

נתונות שתי הנחות, ומתבקשים לבדוק אם המסקנה אכן נובעת מהן:

הנחה 1: כל סטודנט שהקשיב בהרצאה עבר את הבחינה.

הנחה 2: קיים לפחות סטודנט אחד שלא עבר את הבחינה.

מסקנה: קיים סטודנט שלא הקשיב בהרצאה.

S(x)
‏x הוא סטודנט

L(x)
‏x הקשיב בהרצאה

P(x)
‏x עבר את הבחינה

הרעיון

כדי להוכיח שהמסקנה נובעת, מוסיפים להנחות את שלילת המסקנה.

מבצעים סקולמיזציה לכל אחת משלוש הנוסחאות.

בונים את יקום הרברנד ואת בסיס הרברנד של הקבוצה שהתקבלה.

מציבים את איברי יקום הרברנד בנוסחאות האוניברסליות עד שמתקבלת סתירה.

כאן יש רק קבוע אחד ואין סימני פונקציה, ולכן יקום הרברנד הוא {a} והסתירה מתקבלת כבר בהצבה הראשונה.

א. הצרנה

H₁ — הנחה 1 H₁ = ∀x ((S(x) ∧ L(x)) → P(x))

H₂ — הנחה 2 H₂ = ∃x (S(x) ∧ ¬P(x))

M — מסקנה M = ∃x (S(x) ∧ ¬L(x))

נבדוק אם ההנחות יחד עם שלילת המסקנה אינן ספיקות.

ב. שלילת מה שמוכיחים

המסקנה שאותה רוצים להוכיח היא:

M = ∃x (S(x) ∧ ¬L(x))

לכן מוסיפים להנחות את שלילתה:

¬M = ¬∃x (S(x) ∧ ¬L(x))

≡ ∀x ¬(S(x) ∧ ¬L(x))

≡ ∀x (¬S(x) ∨ L(x))

כעת בודקים את הספיקות של {H₁,H₂,¬M}.

ג. סקולמיזציה — התהליך המלא

הנחה H₁

H₁ = ∀x ((S(x) ∧ L(x)) → P(x)) ≡ ∀x (¬(S(x) ∧ L(x)) ∨ P(x)) ≡ ∀x (¬S(x) ∨ ¬L(x) ∨ P(x))

אין כמת קיומי, ולכן לא מוסיפים סימן סקולם.

H₁ˢ = ∀x (¬S(x) ∨ ¬L(x) ∨ P(x))

הנחה H₂

H₂ = ∃x (S(x) ∧ ¬P(x))

לפני ∃x אין כמתים אוניברסליים. לכן בוחרים קבוע סקולם חדש a.

x := a S(a) ∧ ¬P(a)

מסירים את הכמת הקיומי לאחר ההחלפה.

H₂ˢ = S(a) ∧ ¬P(a)

שלילת המסקנה ¬M

¬M = ¬∃x (S(x) ∧ ¬L(x)) ≡ ∀x ¬(S(x) ∧ ¬L(x)) ≡ ∀x (¬S(x) ∨ L(x))

לא נשאר כמת קיומי, ולכן לא מוסיפים סימן סקולם.

(¬M)ˢ = ∀x (¬S(x) ∨ L(x))

הקבוצה המסוקלמת היא Φˢ = {H₁ˢ, H₂ˢ, (¬M)ˢ}.

ד. יקום ובסיס הרברנד

מתוך Φˢ קוראים את החתימה:

קבועים: Const = {a}

פונקציות: Func = ∅

פרדיקטים: {S,L,P}

מתחילים מכל הקבועים:

שלב 0 HU₀ = {a}

אין פונקציות שבעזרתן אפשר לבנות איברים חדשים, ולכן התהליך נעצר:

יקום הרברנד HU = HU₀ = {a}

מציבים כל איבר של HU בכל מקום אפשרי בפרדיקטים:

בסיס הרברנד HB = {S(a), L(a), P(a)}

ה. הצבות קרקעיות

נסמן ב־G את קבוצת כל המופעים הקרקעיים של Φˢ מעל יקום הרברנד HU. כל נוסחה בקבוצה תסומן Gᵢ.

האיבר היחיד ב־HU הוא a. לכן מציבים x=a בכל נוסחה אוניברסלית:

G₁ H₁ˢ[a/x] ¬S(a) ∨ ¬L(a) ∨ P(a)

G₂ H₂ˢ S(a) ∧ ¬P(a)

G₃ (¬M)ˢ[a/x] ¬S(a) ∨ L(a)

G = {G₁, G₂, G₃}

זהו כל פיתוח הרברנד: אין איברים נוספים ב־HU, ולכן אין הצבות קרקעיות נוספות.

ו. הסתירה

1מן הנוסחה G₂ מוכרחים לקבל:

S(a)=T, P(a)=F

2ב־G₃, מאחר ש־S(a)=T:

L(a)=T

3נציב את הערכים ב־G₁:

F ∨ F ∨ F = F

4לכן אין השמת אמת לבסיס הרברנד המספקת את כל הנוסחאות.

סתירה

הקבוצה המסוקלמת אינה ספיקה. לכן {H₁,H₂,¬M} אינה ספיקה, ומכאן H₁,H₂ ⊨ M: המסקנה נובעת מן ההנחות.