יום חמישי, 31 באוקטובר 2019

לוגיקה לתלמידי מדעי המחשב ברמה של האונירסיטה הפתוחה כל החומר שצריך לדעת

לוגיקה עוסקת בשאלות הבאות:
מהי הוכחה? מהי הוכחה טובה? מה ניתן להוכיח / לא ניתן להוכיח?

קורסים שקשורים ללוגיקה במדעי המחשב:
1. אוטומטים ושפות פורמליות
2. A.I בינה מלאכותית
3. אימות מערכות (תוכנה או חומרה) (קורס בחירה).

דוגמה להוכחה "מוזרה":
1. לוח קיים
2. אנחנו קיימים
3. לפחות אחד משלושת הטענות לא נכונה

נניח שטענה 3 לא נכונה, אזי כל שלושת הטענות נכונות, כולל טענה 3 סתירה.
נסיק טענה 3 נכונה, אחד משני הטענות 1 ו-2 אינו נכון, וזה בלתי אפשרי במציאות גם אנחנו קיימים וגם הלוח.



הלימודים בקורס זה יתחלקו לשלושה חלקים עיקריים:
חלק ראשון: תחשיב פסוקים
חלק שני: תחשיב יחסים (נחשב קשה!)
חלק שלישי: לוגיקה מסדר שני (נעסוק בו ממש מעט)



תחשיב פסוקים
אנו נגדיר שפה של תחשיב פסוקים, אפשר להסתכל על שפה בשני דרכים:
1. Syntax - תחביר / צורה
2. Semantic - משמעות

כעת נעסוק ב-Syntax.


הגדרה של שפת תחשיב פסוקים:
א"ב:
(,),∨,∧,→,↔,¬


p,q,x,.... - פסוקים אלמנטריים

מהי מחרוזת?
מחרוזת היא סידרה סופית של אותיות מ-א"ב.

למשל:
p,pp,→

נגדיר קבוצה / שפה של פסוקים.
מגדירים שפה של פסוקים בעזרת אינדוקציה מבנית.
כלומר תחשיב פסוקים בנוי משני דברים:
1. (מקביל לבסיס האינדוקציה): אטומים (פסוקים אלמנטריים למשל p,q,x...)
2. (מקביל לצעד האינדוקציה): כללי יצירה: איך מקבלים אובייקטים חדשים שיהיו שייכים לקבוצה.
כללי היצירה הם:
אם p (=פסוק אלמנטרי) שייך לשפה, אזי שלילת p גם היא שייכת לשפה.
שלילת p מסומנת כך: p¬
אם p,q שייכים לשפה, אזי:
(p∨q)
(p∧q)
(p→q)
(p↔q)
שייכים לשפה (/קבוצה), ובקיצור p@q שייכים לקבוצה.

[הערה: @ הוא קיצור לאחד מארבעת הקשרים הדו מקומיים: ∨,∧,→,
שימו לב שקשרים דו מקומיים מחייבים הימצאות סוגריים סביבם]

כל פסוק אלמנטרי הוא פסוק!
דוגמאות לפסוקים
p - פסוק אלמנטרי
q - פסוק אלמנטרי
¬p - הפעלת כלל יצירה על פסוק אלמנטרי
¬¬p - הפעלת כלל יצירה על מי שבשפה
(q¬p) - הפעלת כלל יצירה על מי שבשפה


בשפת הפסוקים יש אינסוף פסוקים.

איך בודקים האם מחרוזת היא פסוק או לא פסוק? (פסוק= נימצא בקבוצה שהגדרנו כעת):
כדי להוכיח שמחרוזת היא פסוק ניתן להשתמש ב:
- סדרת יצירה (/בנייה)
- עץ בנייה (/יצירה)
- משפט הקריאה היחידה


סדרת בנייה (=סדרת יצירה) לפסוק φ
סדרה סופי של איברים:
α1,α2,...αn
המקיימת: האיבר האחרון בסדרה שווה ל-φ, כלומר: αn=φ
αi יכול להיות:
1. פסוק אלמנטרי
או
2. תוצאת הפעלה כלל יצירה על α-יות קודמות.

דוגמאות:
מצא סדרת יצירה לפסוק
(p→q)
למשל:
p,q,(p→q)

[הערה: הצלחנו לבנות סדרת יצירה ל (p→q) כלומר האיבר האחרון הוא (p→q) ולכן הוא פסוק]

משפט חשוב: אם למחרוזת יש סדרת יצירה אזי היא פסוק.
משפט חשוב: כל איבר בסדרת יצירה הוא פסוק.

ניתן לכתוב אינסוף סדרות יצירה, כלומר סדרת יצירה אינה יחידה.


עץ בנייה - אם מחרוזת היא פסוק אזי ניתן לבנות עבורה עץ בנייה.
דוגמה:

מהם השלבים המחזוריים ליצירת עץ בנייה?
1. בדיקה האם ישנו שלילה שחלה על כל הפסוק, משהו מהמבנה:
¬(asdasdasd)
אם קיים: נשמיט את השלילה ואת הסוגריים החיצוניים של השלילה (אם יש).
אם לא קיים נעבור לשלב 2
2. נחפש את הקשר הראשי (בצד ימין שלו יהיה מספר מאוזן של סוגריים, ובצד שמאל שלו יהיה מספר מאוזן של סוגריים) [מספר מאוזן של סוגריים מתייחס לכך שיש x סוגריים מהצורה ")"  וגם x סוגרים מהצורה"("].
אם קיים קשר ראשי הריי שהוא יחיד.

אם קיים קשר ראשי: נשמיט סוגריים חיצוניים ונפריד את המחרוזת לשני הצדדים.

נמשיך כך באופן מחרוזי עד שנגיע לאבני היסוד, שהם פסוקים אלמנטריים.


דוגמה:
הראה בעזרת עץ בנייה ש
φ=¬((p∨q)→r)
פסוק.


¬((pq)→r)
¬
(pq)→r
r
pq


q
p



(כל פסוק אלנטרי הוא עלה)

סימנים התחלתיים שצריך לדעת
p - פסוק אלמנטרי
[פסוק אלמנטרי מסומן באות לטינית קטנה]
¬ - שלילה
[אם p פסוק אזי p¬ פסוק]
∨ - או
∧ - גם
∑- אוסף של סימנים

קשרים דו מקומיים מחייבים הימצאות סוגריים סביבם
(A→B) 
אם A אז B

(A↔B)
A אם ורק אם B
[אם A ו-B פסוקים, אזי A@B פסוק, כאשר @ הוא קשר דו מקומי שמקשר ביניהם]


דרגות של פסוקים:
E0 - פסוקים אלמנטריים
למשל: p,t

E1- דרגה ראשונה

למשל:
¬p,¬t

E2 - דרגה שנייה
לדוגמה
(p∨(p→t)),¬¬t




איך נוכל לדעת האם פסוק מסוים הוא מחרוזת?
שיטה ראשונה: עץ בנייה

נדגים את שיטת עץ בנייה עבור הביטוי
(((p→t)∨(q∧t))∨(¬p¬q))
נשתמש בטבלה אשר תייצג את העץ


(((p→t)(qt))(¬p¬q))

3
(¬p¬q)
((p→t)(qt))
2
¬q
¬p
(qt)
(p→t)
1
q
p
t
q
t
p
0




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

ראינו איך בעזרת סדרת בנייה ניתן להראות שמחרוזת היא פסוק.
ראינו איך בעזרת עץ בנייה ניתן להראות שמחרוזת היא פסוק או שמחרוזת לא פסוק.

אינדוקציה מבנית - כעת נראה דרך נוספת וחשובה להראות שמחרוזת אינה פסוק (בעזרת אינדוקציה מבנית).


משפט ההוכחה באינדוקציה מבנית הפורמלי:
תהי R תכונה שיש לחלק מהמחרוזות או לכולן, נניח כי נתון:
א. לכל פסוק אלמנטרי יש את התכונה R.
ב. אם לפסוק φ יש את התכונה R, הרי גם לפסוק φ¬ יש את התכונה R.
ג. לכל קשר דו מקומי @, אם לפסוקים φ1 ו-φ2 יש את התכונה R, הרי גם לפסוק (φ1@φ2) יש את התכונה R.

אזי לכל פסוק יש את התכונה R.




רעיון השיטה:
כדי להוכיח שמחרוזת היא לא פסוק ננחש תכונה λ ונראה שכל פסוק מקיים λ והמחרוזת לא מקיימת λ, ולכן המחרוזת לא פסוק.

לצורך ההבנה נגדיר U שיהיה כל המחרוזות בעולם, ואילו P יהיה כל הפסוקים בעולם, הריי ש P מוכל ב-U.
ניתן לחלק את זה לשלושה מקרים:
1. פסוק מסוים מקיים תכונה λ.
2. מחרוזת מסוימת מקיימת תכונה λ והיא אינה פסוק.
3. מחרוזת מסוימת לא מקיימת תכונה λ והיא אינה פסוק.

אם נתקלנו במקרה מספר 2 הריי שהניחוש לא מוצלח, המחרוזת מקיימת תכונה λ אבל היא עדיין לא פסוק.

אם נתקלנו במקרה מספר 3 הריי שהניחוש מוצלח, המחרוזת לא מקיימת תכונה λ, לכן היא לא פסוק.





העיקרון של אינדוקציה מבנית (הלכה למעשה):
1. (בסיס האינדוקציה) יש להראות שאטום (פסוק אלמנטרי) מקיים תכונה λ.
2. (צעד האינדוקציה) נניח ש-φ1,φ2 מקיימים λ, יש להראות ש:
¬φ1
φ1@φ2
מקיימים תכונה λ.


דוגמה: הראה ש:
φ=p→q)
אינו פסוק.


(ניחוש לתכונה λ): כל פסוק הוא מאוזן סוגריים.
אחרי שנוכיח שכל פסוק מקיים λ מיד נסיק ש-φ אינו פסוק.

הוכחה: בסיס האינדוקציה: כל פסוק אלמנטרי מכיל 0 סוגריים מכול סוג ולכן מאוזן.
צעד האינדוקציה: נניח φ1 ו-φ2 מקיימים λ ונבדוק ש                                               -
¬φ1
(φ1@φ2)
מקיימים גם כן.
φ1¬ - מאוזן סוגריים, כי לפי הנחת האינדוקציה φ1 מאוזן סוגריים ואנו הוספנו סימן שלילה.
φ1@φ2 - 
φ1 ו-φ2 מאוזנים סוגריים לפי הנחת האינדוקציה.
נחשב את כמות הסוגריים:
(φ1@φ2)
Kamot_"("_(φ1@φ2)=1+Kamot_"("_φ1+Kamot_"("_φ2
Kamot_")"_(φ1@φ2)=Kamot_")"_φ1+Kamot_")"_φ2+1
לפי הנחת האינדוקציה:
Kamot_"("_φ1=Kamot_")"_φ1
Kamot_"("_φ2=Kamot_")"_φ2
וברור ש-
1=1

לכן (φ1@φ2) מאוזן סוגריים.
ולכן לפי עיקרון אינדוקציה מבנית כל פסוק הוא מאוזן סוגריים.
ולכן 
p→q)
אינו פסוק.


האם:
φ=(((pq)))
פסוק?
(ניחוש): תכונה λ: בין כל שני פסוקים אלמנטריים תמיד יש קשר דו מקומי.
אחרי שנוכיח את התכונה נסיק ש-φ לא פסוק
כעת נוכיח באינדוקציה מבנית שכל פסוק מקיים תכונה λ.
הוכחה: בסיס האינדוקציה: כל פסוק אלמנטרי מקיים λ באופן ריק. (פסוק אלמנטרי מכיל פסוק יחיד, ואילו התכונה מדברת על שני פסוקים אלמנטריים)
צעד האינדוקציה: נניח ש-φ1 ו-φ2 מקיימים λ, ונוכיח ש

¬φ1

(φ1@φ2)
גם מקיימים את התכונה.

φ1¬ - מקיים את התכונה כי ¬ זה לא קשר דו מקומי, לא פסוק אלמנטרי, ו-φ1 מקיים λ לפי הנחת האינדוקציה.

כעת נבדוק ש-(φ1@φ2) מקיים λ:
ייתכן 1 מ-3 מקרים:
1. שני הפסוקים האלמנטריים שייכים ל-φ1, סיימנו: הנחת האינדוקציה.
1. שני הפסוקים האלמנטריים שייכים ל-φ2, סיימנו: הנחת האינדוקציה.
3. פסוק אלמנטרי אחד שייך ל-φ1 ואילו השני שייך ל-φ2, אז יש ביניהם קשר דו מקומי @.
זאת אומרת תכונה λ מתקיימת.

לפי עקרון אינדוקציה מבנית, כל פסוק מקיים λ, ולכן (((pq))) לא פסוק.


למה ספירת הסוגריים: כל פסוק הוא מאוזן סוגריים: מספר הסוגריים השמאליים שווה למספר הסוגריים הימניים.


מהו משפט הקריאה היחידה? (=מקביל לכללי היצירה שהוסברו לעיל)
משפט הקריאה היחידה אומר שיש רק דרך אחת לקרוא את הפסוק, ואם יש ספק בנוגע לקריאתו אזי הוא אינו פסוק.
מה משפט הקריאה היחידה אומרת?
הפסוקים נחלקים לשלושה סוגים:
א. פסוקים אלמנטריים, מכונים גם אטומים / אבני יסוד.
ב. פסוקי שלילה, זאת אומרת אם φ פסוק, אזי φ¬ פסוק גם כן.
ג. פסוקים מקושרים, אם φ1 הוא פסוק, וגם φ2 הוא פסוק, אזיי 
(φ1@φ2)
פסוק בעצמו.


הגדרות:
סימן השלילה בראש מחרוזת יהיה הקשר הראשי.
הקשר הראשי שהוא אינו שלילה, אם קיים, יהיה יחיד ובצד ימין ושמאל שלו הסוגריים יהיו מאוזנים.






משפט הקריאה היחידה לגביי כתיבה פולנית:
א. כל פסוק אלמנטרי p הוא פסוק.
ב. אם φ פסוק אז גם φ¬ הוא פסוק.
ג. אם φ1 ו-φ2 הם פסוקים, אז גם φ1φ2@ הוא פסוק.



בנוסף לרובד של ה-syntax (סינטקס = תחביר, אופן הכתיבה), ישנו רובד נוסף של Semantic (סמנטיקה = משמעות) לשפת תחשיב הפסוקים.


הגדרה: השמה / מודל M הוא פונקציה שלכל פסוק אלמנטרי נותנת ערך אמת יחיד:
1. T הכוונה ל-True
2. F הכוונה ל-False

אם p הוא T אנו נגיד ש-M מספקת את p:
סימון: M⊧p או M(p)=T

אחרת: M לא מספקת את p:
סימון:  M(p)=F

ניתן להגדיר ערך אמת שמודל M מותן לפסוק 
φ באינדוקציה מבנית, ובעזרת טבלאות אמת הבאות:


φΨ
φΨ
φΨ
φΨ
¬φ
Ψ
 φ
T
T
T
T
F
T
T
F
F
F
T
F
F
T
F
T
F
T
T
T
F
T
T
F
F
T
F
F



דוגמה: 
נתון מודל (השמה):
M(p)=F
M(q)=F
M(z)=T

M(((p→q)→z))=?
נפתור זאת בעזרת טבלת אמת:


p
q
z
(p→q)
((p→q)→z)
F
F
T
T
T



לכן:
M(((p→q)→z))=T


משפט: ערך הפסוק נקבע באופן יחיד על ידי מודל M.

מהי הצרנה? הצרנה באופן לא פורמלי היא תרגום משפטים משפתינו לשפת תחשיב הפסוקים.

נגיד שמודל M מספק פסוק φ אם M(φ)=T.


מודל M מספק קבוצת פסוקים k, אם 
∀i Mφi

כאשר k:
k={φ1,φ2,...}

משפט: תהיה k קבוצה סופית של פסוקים, אזי מודל M מספק את k
M⊧K, אם ורק אם Mφ1φ2φ3...φn

הוכחה:
כיוון ראשון:
מתקיים M⊧K
k={φ1,φ2,...φn}
אז לפי הגדרה
1≤i≤n
∀i Mφi
∀i M⊧k
לפי טבלת האמת של ∩:
M(φ1φ2φ3...φn)=T

זאת אומרת
M(φ1φ2φ3...φn)


כיוון שני:
מתקיים Mφ1φ2φ3...φn
זאת אומרת לפי הטבלת אמת של ∩:
1≤i≤n
∀i Mφi
k={φ1,φ2,...φn}
לפי הגדרה 

M⊧k


הגדרה: פסוק φ נקרא טאוטולוגיה (=אמת לוגית) אם בכל מודל M הפסוק φ מקבל ערך אמת T.
∀M M(φ)=T
דוגמאות:
(p¬p)
(A→(B→A))
נוכיח את הפסוק האחרון בעזרת טבלת אמת של 2 בחזקת 2 שורות (+1 של הפסוקים):



A
B
(B→A)
(A→(B→A))
T
T
T
T
T
F
T
T
F
T
F
T
F
F
T
T




סיבוכיות של פתרון:
מספר השורות
2^(מספר הפסוקים האלמנטריים)

*הגדרה:
פסוק φ נקרא סתירה אם הוא מקבל ערך אמת F בכל מודל
∀M M(φ)=F
דוגמה:
(p¬p)
ניתן לבדוק האם φ סתירה בעזרת טבלת אמת.

משפט:
אם φ טאוטולוגיה אזי φ¬ סתירה.
אם φ סתירה אזי φ¬ טאוטולוגיה.

*הגדרה:
שני פסוקים φ ו-ψ פסוקים שקולים אם:
∀M M(φ)=M(ψ)
בכל מודל (השמה) הם מקבלים אותו ערך אמת.
סימון:
φψ

למשל:
¬¬p≡p

*הגדרה:
נגיד שפסוק φ נובע לוגית מפסוק ψ (אפשר להגיד גם ψ גורר לוגית את φ), אם בכל מודל ש-ψ מקבל ערך אמת T, גם φ מקבל ערך אמת T.

∀M: M(ψ)=T M(φ)=T
∀M: Mψ Mφ
סימון:
ψφ

*הגדרה: φ נובע לוגית מקבוצת פסוקים k:
k={φ1,φ2,...}
1≤i
∀i Mφi Mφ



הגדרות שיש לזכור ללא הסבר הבנתי:
1.
φ
φ חייב להיות טאוטולוגיה.


2.
{¬p,p}φ

קבוצת הפסוקים מצד שמאל אינה ספיקה, כלומר היא לעולם לא מקבלת ערך אמת T, לכן φ יכול להיות פסוק.

תרגיל:
הוכח או הפרך (לא הוספנו סוגריים מטעמי נוחות):
אם φ ספיק ו-ψ ספיק אזי:
א. φψ ספיק
ב. φψ ספיק

א. נכון, הוכחה:
נתון ש-φ ספיק, זאת אומרת קיים:
M(φ)=T
לפי טבלת האמת של ∨:
M(φψ)=T
לכן (φψ) ספיק.

ב. הטענה אינה נכונה. נפריך אותה באמצעות דוגמה:
φ=p - ספיק על מודל ידי מודל:
M(p)=T

ψ=¬p - ספיק על מודל ידי מודל:
M(¬p)=T

∀M M(¬p∧p)=∀M M(φψ)=F
הרי שמדובר בפסוק סתירה ובטח שאינו ספיק

תרגיל 1 הוכח / הפרך את הטענה הבאה:
אם A→B טאוטולוגיה, ו-A טאוטולוגיה אז בהכרח B טאוטולוגיה.
פתרון תרגיל 1:
הטענה נכונה.
הוכחה:
A טאוטולוגיה ולכן (על פי ההגדרה)
∀M M(A)=T
A→B גם טאוטולוגיה ולכן (על פי ההגדרה) 
∀M M(A→B)=T

על פי טבלת האמת של "→", על מנת ש- A→B יקבל ערך אמת T תמיד (כי הוא טאוטולוגיה), ו-A גם טאוטולוגיה, אסור ש-B יקבל ערך אמת F.
אם B יקבל ערך אמת F אז A→B יקבל ערך אמת F, בסתירה לנתון שאומר שהוא טאוטולוגיה. לכן B חייב לקבל ערך אמת T בכל מודל, לכן הוא טאוטולוגיה.

תרגיל 2 הוכח / הפרך את הטענה הבאה.
אם A→B ספיק, וגם A ספיק, אז B ספיק.

פתרון תרגיל 2:
הטענה איננה נכונה, נפריך בעזרת דוגמה נגדית.

על מנת לסתור את הטענה, אנו צריכים לקיים את נתוני השאלה, כלומר A→B ספיק, וגם A ספיק, אבל לסתור את המסקנה: B ספיק, הסתירה היא B סתירה.
אם B לא ספיק, זאת אומרת שהוא לא מקבל ערך אמת T (במילים אחרות לא קיים מודל שייספק אותו)



B=(p¬p)
A=p
A הוא ספיק כי יש מודל M שיספק אותו (p הוא פסוק אלמנטרי).


A→B ספיק, כי A ספיק, ואילו B סתירה, לכן במצב שבו A מקבל ערך אמת F על פי מודל כלשהו ו-B סתירה אז A→B מקבל ערך אמת T ולכן A→B ספיק.


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

תרגיל 3: הוכח את הטענה הבאה:
A ו-B פסוקים.
יש ל-A ו-B פסוק אלמנטרי אחד משותף בלבד, P.
ידוע ש-((A→(A→B) טאוטולוגיה:
אז מתקיים לפחות אחד משניים:
1. p→¬A טאוטולוגיה
2. P→B טאוטולוגיה.

פתרון תרגיל 3:
נניח בשלילה ש 1. ו-2. לא מתקיימים, זאת אומרת ש1. ו-2. לא טאוטולוגיות, זאת אומרת קיים איזשהו מודל שבו הם מקבלים ערך F):
∃M1 M1(p→¬A)=F
∃M2 M2(P→B)=F
על פי טבלת האמת של "→" ו"¬":
M1(P)=T  M1(A)=T
M2(P)=T M2(B)=F

נגדיר את M3 באופן הבא:
נניח ב-A יש פסוקים אלמנטריים α1,...αn ו-p
נניח ב-A יש פסוקים אלמנטריים β1,...,βn ו-p
הריי שלפי הנתון הפסוקים האלמנטריים α1,...αn ו- β1,...,βn שונים זה מזה, ורק p הוא הפסוק המשותף.

M3(C)=
{
if C=P  T
if C=αi  M1(αi)
if C=βi  M2(βi)
}
טענה: M3 לא מספק את ((A→(A→B).
על פי מודל M3:
M3(A)=M1(A)=T
M3(B)=M2(B)=F

על פי טבלת האמת של "→":
M3((A→B))=F
M3(((A→(A→B))=F
סתירה לנתון ש-((A→(A→B) טאוטולוגיה, לכן ההנחה שהנחנו לא נכונה,
לכן אחד או יותר מ-1, ו-2 חייב להיות נכון.

תרגיל 4:
נתונה קבוצת הפסוקים:
Σ1={(pi→pj)|1≤i≠j≤∞}
מהי קבוצת כל המודלים שמספקים את Σ1.

סה"כ יש 2 מודלים שמספיק את Σ1:
1. 
MF=(Pk)=F ∀k
2.

MT=(Pk)=T ∀k

אין מודלים נוספים.

נניח בשלילה שקיימים מודל אחר, M3, אז קיים m ו-n כך ש:
M3(Pm)=T
M3(Pn)=F

M3((Pm→Pn))=F

תרגיל 5:
נתונה קבוצת הפסוקים:
Σ1={(pi→¬pj)|1≤i≠j≤∞}
מהי קבוצת כל המודלים שמספקים את Σ1.

1.
MF=(Pk)=F ∀k

2. נגדיר קבוצת מודלים
Mx (Px)=T
Mx (Py (y≠x)=F

על פי טבלת האמת של  "→", שני המצבים שיכולים להתקיים:

Mx(Px)=T
Mx (Py (y≠x)=F

Mx((Px¬Py))=T
Mx((Py¬Px))=T

Mx⊧T

אין מודל נוסף שמספק את Σ1.
נניח בשלילה שקיים מודל כזה (M3), אזי חייבים להיות בו שני פסוקים אלמנטריים לפחות שעבורם המודל מספק ערך אמת T.
על פי טבלת האמת (pi→¬pj) אם:
M3(Pi)=M3(Pi)=T
T→F=F
לכן לא קיים מודל נוסף.

הצורה הנורמלית הדיסיונקטיבית (DNF)
הגדרה: הפסוק φ הוא בצורת DNF (צורה דיסיונקטיבית נורמלית) אם הוא אחד מתוך שלושת הדברים הבאים:
1. φ הוא פסוק אלמנטרי.
2. φ הוא בצורה של קוניונקציה. קוניונקציה הוא פסוק שמורכב מפסוקים אלמנטריים, שלילתם והקשר "וגם" ∧.
3. דיסיונקציה של קוניונקציה, הכוונה היא לאיחוד/ים של קוניונקציות.


משפט: לכל פסוק φ קיים פסוק ψ בצורת DNF, כך ש ψ≡φ (כלומר כל פסוק ניתן לתרגם ל -DNF).

מהם הדרכים להפוך כל פסוק לפסוק בצורת DNF?
1. אלגוריתם מפורט
2. טבלת אמת

נסביר על שיטת טבלת האמת:
לביטוי מסוים מבצעים טבלת אמת מלאה.
אחרי שנסיים למלא את טבלת האמת אנו נסתכל בשורות שבהן יצא לנו ערך אמת T.
נשים לב לפסוקים האלמנטריים.
נניח שבשורה אחת של אמת הפסוק האלמנטרי P היא ערך אמת T, ואילו הפסוק האלמנטרי q היה ערך פסוק F.
נבנה מהמידע הזה קוניונקציה, p וגם שלילה של q.
נעשה איחוד
נניח שבשורה אחרת של אמת הפסוק האלמנטרי P היא ערך אמת F, ואילו הפסוק האלמנטרי q היה ערך פסוק F.
נבנה מהמידע הזה קוניונקציה, שלילה ל p וגם שלילה של q.
אם יש שורות נוספות נעשה איחוד ונמשיך, אם אין, סיימנו.

שיטה זו לא תעבוד על פסוק שהוא סתירה, משום שאין בו שום שורה שתניב לנו ערך אמת T.


מערכת קשרים שלמה
מהי מערכת קשרים שלמה?
מערכת קשרים נקראת שלמה אם בעזרת ניתן לממש או לבנות כל טבלת אמת.
דוגמה למערכות שלמות:
1. צורה דיסיונקטיבית נורמלית היא מערכת שלמה, המורכבת מ-
{¬,∧,}

2.
{¬,}
ההוכחה לכך הוא משפט דה מורגן
3.
{¬,}
ההוכחה לכך הוא משפט דה מורגן
4.
{¬,→}

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



הוכיחו שקבוצת הקשרים {v,→} אינה שלמה.

הוכחה:
נראה שלא ניתן לקבל את קשר השלילה בעזרת קבוצת הקשרים הנתונה.


נניח שיש מודל M כך ש M(p)=T, נראה שלא נוכל לקבל פסוק שמופיע בו רק הפסוק האלמנטרי p וערך האמת שלו F בעזרת קבוצת הקשרים הנתונה.
נוכיח את הטענה באינדוקציה מבנית.

פסוק אלמנטרי:M(p)=T

פסוק מורכב:
(pvp)
(p→p)
במודל M
M((pvp))=T
M((p→p))=T
נניח שהוכחנו את הטענה עבור פסוקים φ ו-ψ כלשהם.
כלומר M(φ)=T ו- M(ψ)=T
מכאן M(φvψ)=T   M(φ→ψ)=T

לכן לא ניתן לבטא את קשר השלילה בעזרת הקשרים {v,→}, ולכן קבוצת קשרים זו אינה שלמה.



תזכורת: מערכת קשרים נקראת שלמה אם בעזרתה ניתן לממש כל טבלת אמת.
הראינו שמערכת קשרים הבאה:{¬,∧,} שלמה.

משפט: אם קבוצת קשרים K שלמה, אז K∨M גם שלמה. (כאשר M קבוצת קשרים).
אן קבוצת קשרים K לא שלמה, אזי K/M (חיסור) לא שלמה.

איך מוכיחים שמערכת קשרים שלמה?
1.הגדרה (בעזרת K ניתן לממש כל טבלת אמת)
2. אפשר להראות שמ-K ניתן לקבל מערכת קשרים שלמה וידועה.



תרגיל: הוכח שמערכת הקשרים {,→}

פתרון:
טענה: מערכת הקשרים {,→} לא שלמה.



A
B
A→B
AB
T
T
T
T
T
F
F
F
F
T
T
F
F
F
T
F



הסבר: לא ניתן לממש טבלת אמת  בעזרת קשרים ,→, ראו בטבלה, כאשר המודל M מספק את A, וגם מספק את B, אז לא ניתן לקבל פסוק שלילה.

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

בסיס: פסוק אלמנטרי (אטומי), ערך של A בהשמה T הוא T, כנ"ל ערך של B.

צעד האינדוקציה: נניח ש-φ ו-ψ שני פסוקים שעל השמה שכולה T נותנים ערך T.
נבדוק ש:
ψ→φ - מתן ערך T של השמה שהיא כולה T.
ψφ - נותן ערך T של השמה שהיא כולה T.

ערך אמת של ψ→φ על השנה שכולה T יהיה גם T, לפני הנחת אינדוקציה וטבלת אמת של "→".
כנ"ל ψφ.

ולכן בעזרת הקשרים ,→ לא ניתן לממש טבלת אמת המופיעה לעיל, ולכן מערכת זו לא שלמה.


תזכורת: מערכת קשרים נקראת שלמה אם בעזרת ניתן לממש כל טבלת אמת.
הוכח ש-{¬,↔} אינה מערכת קשרים שלמה.
טענה: המערכת {¬,↔} לא שלמה, כי לא יכולה לממש את טבלת האמת הבאה:


נוכיח באינדוקציה מבנית שלא ניתן לממש טבלת אמת על שתי פסוקים אלמנטריים A ו-B שערך הפסוק יקבל כמות אי זוגית של T.

בסיס: על פסוקים אלמנטריים הטענה נכונה.

צעד האינדוקציה: נניח ש-φ מקיים את הטענה, נבדוק φ¬:
φ מקיים את הטענה ולכן נקבל ערך T ב-2k השמות / מודלים (k הוא מספר שלם).
φ מקיים את הטענה ולכן מקבל ערך T ב-4-2k מודלים.
אזי φ¬ מקבל ערך אמת ב-4-2k פעמים, מספר זוגי.
φ¬ מקבל ערך אמת ב-2k פעמים, מספר זוגי/
אזי הטענה נכונה.

נניח ש-φ ו-ψ מקיימים את הטענה, נוכיח ש φψ מקיים את הטענה.

נבדוק את המקרים הבאים:
φ מקבל ערך אמת T ב-0 השמות (זוגי)
ψ מקבל ערך אמת T ב-0 השמות (זוגי)

φ מקבל ערך אמת T ב-2 השמות (זוגי)
ψ מקבל ערך אמת T ב-0 השמות (זוגי)


φ מקבל ערך אמת T ב-4 השמות (זוגי)
ψ מקבל ערך אמת T ב-0 השמות (זוגי)

וכך הלאה... נבדוק את כל המקרים, ונראה האם יתקיים מצב שבו נקבל מספר אי זוגי של ערכי T?


ψ
φ
φ)
F
F
T
F
F
T
F
F
T
F
F
T
דוגמה לכך ש-φ ו-ψ מקבלים ערך אמת T 0 פעמים


ניתן לראות כי  ↔ φ) מקבל ערך אמת T, ארבע פעמים - מספר זוגי


ψ
φ
φ)
F
F
T
F
T
F
F
T
F
F
F
T
דוגמה לכך ש-  φ מקבל ערך אמת T  פעמיים, ו-ψ מקבל ערך אמת T 0 פעמים


ניתן לראות כי  ↔ φ) מקבל ערך אמת T, פעמיים - מספר זוגי



ψ
φ
φ)
F
T
F
F
T
F
F
T
F
F
T
F
דוגמה לכך ש-  φ מקבל ערך אמת T  4  פעמים, ו-ψ מקבל ערך אמת T 0 פעמים


ניתן לראות כי  ↔ φ) מקבל ערך אמת T, אפס פעמים - מספר זוגי

נמשיך באופן הבא ונראה שהטענה מתקיימת.
והריי שהוכחנו באינדוקציה מבנית את הטענה.


דוגמה למערכת קשרים שלמה בת קשר אחד, שער לוגי בשם NAND.


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


אקסיומות בתחשיב הילברט

AX1: (α→(β→α))
AX2: (((α→(β→ɣ))→((α→β)→(α→ɣ)))
AX3: ((¬α→¬β)→(β→α))

כאשר α,β,ɣ הם פסוקים.

כלומר יש אינסוף אקסיומות משלושה סוגים שונים.


קבעו לאיזו אקסיומה הפסוקים הבאים שייכים:
(A→(B→A))
(AX1)

((¬¬¬A→¬A)→(A→¬¬A))
(AX3)


בעזרת עץ מבנה (=בנייה) ניתן לבדוק האם מדובר באקסיומה או לא.
נגדיר אוסף של משפטים פורמליים בתחשיב הילברט: נגדיר את הקבוצה באינדוקציה מבנית.

(האקסיומות, RULESׁ)

האקסיומות:
ניתן להשתמש בכל שלושת האקסיומות, ונסמן אותן כך:
AX1, AX2, AX3

RULES - הכוונה היא לחוקים / כללים שניתן להשתמש בהם.
כלל ראשון- כלל ניתוק MP
הנחה φ 
הנחה φ→ψ
מסקנה 
ψ

* היא קבוצת כל המשפטים הפורמליים.
אם פסוק נימצא ב-* אז הוא ניקרא משפט.
וסידרת יצירה שלו היא הוכחה פורמלית.

סימון:
φ
אומר ש-φ יכיח (ניתן להוכיח אותו) מהאקסיומות.

תרגיל: הוכח:
⊢(A→(B→A))
φ=(A→(B→A))
הוכח פורמלית ש-φ הוא משפט.
כאשר A ו-B פסוקים אלמנטריים.

פתרון:
נבנה סידרת יצירה ל-(A→(B→A)).
1. (A→(B→A))  AX1.
סוף הוכחה.




תרגיל: הוכח פורמלית:
⊢(A→A)
A פסוק אלמנטרי.

פתרון:
B=(A→A) סימון עזר

1. (((A→(B→A))→((A→B)→(A→A)))  [AX2]
2.(A→(B→A)) [AX1]
3.((A→B)→(A→A)) MP on 1,2
הצבה
B=(A→A) 
3. הצבה
((A→(A→A))→(A→A)) 
4.(A→(A→A)) [AX1]
5. A→A [MP on 3,4]


הוכחנו
 ⊢(A→A)

משפט דדוקציה עוזר לבנות הוכחות פורמליות:
⊢(αβ)
אם ורק אם
αβ
סימון: פסוק φ יכיח מקבוצת פסוקים k, 
kφ

φ∈(k+AX1,AX2,AX3 ; MP)

תרגיל: הוכח פורמלית:
{A→C, C→B}⊢(A→B)


לפי משפט הדדוקציה:

{A→C, C→B,A}⊢B
(בעצם הזזנו את A לצד של ההנחות.

1. (A→C) הנחה
2. A הנחה
3. C [MP on 1,2]
4.(C→B)
5. B [MP 4,3]
סוף הוכחה פורמלית



תחשיב הילברט:


תחום סימנטי פירוש / ערך אמת

תחום סינטקטי תחביר / צורה
φ
משפט נאותות
φ
kφ
משפט שלמות
kφ
{x φ} ⊧ B
X (φ→B)

{x φ} ⊢ B
X (φ→B)



X תורה, ל-x יש מודל
X עקבית
X תורה שלמה, ל-x יש מודל יחיד
X עקבית מקסימלית


הוכחה פורמלית מתוך קבוצת הנחות,
סימון:
kφ


בהינתן פסוק φ, איך נראה שהוא יכיח? בעזרת הוכחה פורמלית.

בהניתן פסוק φ, איך נראה שהוא לא יכיח? שאלה לא פשוטה.

טענה: אקסיומות של הילברט טאוטולוגיות.
הוכחה: בעזרת טבלת אמת.

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

הגדרה: קבוצת פסוקים K נקראת עקבית, אם לא קיים פסוק φ:
kφ  וגם  k¬φ
הגדר שקולה: קבוצת פסוקים K נקראת עקבית, אם קיים פסוק φ שלא ניתן להוכחה מ-k:
φ: K NOT⊢ φ

הקבוצה עקבית אם בעזרת לא ניתן להוכיח כל דבר.


הגדרה: קבוצת פסוקים K נקראת עקבית מקסימלית אם רק אחד מ-2 מתקיים:
φ: kφ or  k¬φ

משפט: אפשר לקחת קבוצת פסוקים עקבית K ולהשלים אותה לקבוצה עקבית מקסימלית.

משפט הנאותות:
kφ ⇒  k⊧φ 


  משפט השלמות:
k⊧φ kφ



kφ ⇔ k⊧φ 

אם K קבוצה ריק אז:
φ ⇔ ⊧φ 

φ  = הפסוק יכיח בעזרת אקסיומות בלבד
⊧φ  = הפסוק טאוטולוגיה


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

* תורה היא קבוצת פסוקים שיש לה מודל אחד.
(תורה = ניתנת לסיפוק).

* משפט: קבוצת פסוקים K היא עקבית מקסימלית אם ורק אם יש לה מודל אחד אחד, וקוראים לה תורה שלמה.


שאלות תאורטיות:
1.האם קבוצת אקסיומות של הילברט עקבית מקסימלית?
תשובה: הקבוצה לא עקבית מקסימלית, כי היא לא יודעת להוכיח ש-P: לא יכיח
ולא יודעת להוכיח ש:  P¬ לא יכיח.
זאת אומרת ש-p הוא לא טאוטולוגיה, וגם לא יודעת להוכיח ששלילה של P היא גם לא טאוטולוגיה.

קבוצת האקסיומות של הילברט לא עקבית מקסימלית.

האם הקבוצה היא עקבית?
התשובה: כן, כי יש פסוק למשל, P שלא ניתן להוכיח מאקסיומות, p אינו טאוטולוגיה, לפי משפט נאותות. לכן P לא יכיח.

האם הקבוצה הבאה היא עקבית מקסימלית:
K={p1,p2,...}
ל-K יש מודל אחד ויחיד, כך פסוק מקבל ערך T ולכן K עקבית מקסימלית.

תרגיל קבעו האם הקבוצה הבאה: עקבית / עקבית מקסימלית / לא עקבית:
K={p,¬p}
K לא עקבית, כי אין לה מודל שמספק אותה.

מסתירה ניתן להוכיח כל דבר.

דוגמה נוספת:
K={p,¬p→q}
טענה: k עקבית, K עקבית לא מקסימלית.
הוכחה: על פי טבלת אמת ניתן לראות כי יש שני מודלים שמספקים אותה. (כלומר שתי השמות שבעזרתן יש ערך אמת T לכל לפסוק P וגם לפסוק p→q¬


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

תחשיב יחסים
המקלדת של השפה / א"ב השפה:
כמתים: ∃ , ∀
קשרים:   ∨ , ∧ , → , ↔ , ¬
סוגריים: ( , )
משתנים: y,z,p1,p2,....
קבועים - c0,c1,c2,c3,...
פונקציות:
f() פונקציה אונרית מקבלת ערך אחד ומחזירה ערך אחד
f2(,)  פונקציה בינארית מקבלת שני ערכים ומחזירה ערך אחד
f3(, ,) פונקציה טרינרית מקבלת שלושה ערכים ומחזירה ערך אחד
יחסים:
R( , )
R4( , , )

כדי להגדיר שפה בתחשיב יחסים, יש להגדיר שלושה דברים:
1. קבועים
2. פונקציות
3. יחסים

כעת נגדיר באינדוקציה מבנית משהו שם עצם / אובייקט:
קבוצת שמות עצם / אובייקטים=I(הבסיס מכיל: משתנים וקבועים, הפעלת כללי יצירה: פונקציה על שמות עצם)

כעת נגדיר נוסחה בתחשיב יחסים:
בסיס: יחס שמופעל על שמות עצם

כללי יצירה:
אם φ ו-ψ נוסחאות אזי:
(φ@ψ)
¬φ
∀xφ
∃xφ
כאשר x זה משתנה.


כעת נגדיר מושג של משתנה חופשי (הערך שלו משנה כלומר משפיע) ומשתנה קשור (הערך שלו לא משנה, כלומר לא משפיע).
נגדיר מתי x הוא משתנה חופשי או קשור בנוסחה בעזרת אינדוקציה מבנית.

בסיס: אם φ נוסחה אטומית, כלומר רק יחס, ו-x מופיע ב-φ אזי x חופשי.
(משתנה שלא מופיע נחשב משתנה קשור)
כללי יצירה:
¬φ
אם היה חופשי ב-φ אזי הוא נשאר חופשי ב-φ¬.
(φ@ψ) - אם x חופשי ב-φ או ב-ψ או בשניהם אזי x חופשי ב (φ@ψ)

∀xφ
אם y חופשי ב-φ ו-x הוא לא y אזי y חופשי xφ∀ אחרת y קשור.


∀zR(y) = y חופשי
∀yR(y) = y קשור



נתונה הנוסחה הבאה:
(R(x,a)→∀xR(x,y))

R הוא יחס.
a הוא קבוע.
x,y משתנים.

קבעו מי מהמשתנים הבאים הוא משתנה חופשי ומי מהם קשור



(R(x,a)→xR(x,y))
R(x,a)

R(x,y)
X – חופשי
Y – קשור מפני שאינו מופיע

X – חופשי
Y – חופשי




xR(x,y))



X – קשור
Y - חופשי

(R(x,a)→xR(x,y))
X – חופשי
Y – חופשי



הגדרה: אם בנוסחה אין משתנים חופשיים היא נקראת פסוק.


הצרנה 
- לא קל לעשות הצרנה בתחשיב יחסים
 - אין אלגוריתם להצרנה
 - היום נראה דרך טובה להצרנה 

הדרך מתבססת על תבניות הבאות:
1. כל p הוא Q
תרגום תחשיב היחסים: לכל משתנה x אם הוא p אז הוא Q.
∀x(p(x)→Q(x))

2. אין p שהוא Q
תרגום תחשיב היחסים: לכל משתנה x אם הוא p אזי הוא לא Q.
∀x(p(x)→¬Q(x))

3. קיים p שהוא Q
תרגום בתחשיב יחסים: קיים x שהוא p  וגם שהוא Q.
∃x(p(x)∧Q(x))

4. קיים p שלא Q
תרגום בתחשיב יחסים: קיים x שהוא p וגם לא Q.
∃x(p(x)¬Q(x))


תרגול:
הצרינו את המשפטים הבאים לתחשיב יחסים:

1. כל חתול צהוב הוא נעים
Yellow(x) = y(x) צהוב
Cat(x)= c(x) חתול
pleasent (x) = p(x) נעים


תרגום לתחשיב יחסים:
כל חתול, אם הוא צהוב בנוסף להיותו חתול, אז הוא נעים
x((c(x)y(x))→p(x))


2. קיים כלב שאוהב את את כל בני האדם
dog(x)=d(x) כלב
persons(x)=p(x)
loves(x,y) = l(x,y)  x loves y

תרגום לתחשיב יחסים: קיים x שהוא כלב, שבנוסף (וגם) להיותו כלב:  לכל משתנה y אם הוא בנאדם אז הכלב אוהב אותו.
∃x(d(x) ∧ ∀y(p(y) → l(x,y)) )


כל בנאדם אוהב לפחות כלב אחד
תרגום לתחשיב יחסים:
כל x, אם הוא בנאדם אז קיים y שהוא גם כלב וגם  x אוהב אותו
x(p(x)→∃y(d(y)  ∧ l (x,d))


כל שני פנקייקים הם בעלי אותו טעם
pancake(x)=p(x)
Tasesimilar(x,y)=t(x,y) x taste similar to x

כל x, כל y אם הם פנקייקים אז הם בעלי אותו טעם
x∀y(p(x)∧p(y)→t(x,y))



כל בנאדם מכיר לפחות שני אנשים
תרגום לשפת תחשיב יחסים:
כל x אם הוא בנאדם אז x מכיר y שהוא אדם וגם z שהוא אדם



נדבר על סמנטיקה, זאת אומרת על המשמעות של תחשיב היחסים.
בתחשיב יחסים מתחילים להגדיר את השפה מהמילון שלה, והוא נראה כך:
ϴ=<c0,c1,....,f1,f2,...,R1,R2,...>
כאשר במקרה זה:
c מסמן קבועים
f מסמן פונקציות
R מסמן יחסים

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

∀x(f(x,y)→R(x))
מדובר בפסוק, לא בנוסחה משום ש-x הוא משתנה קשור.

באופן כללי יש להגדיר את כל הפונצקיות, יחסים וקבועים, ובנוסף לכך גם תחום המסומן ב-D.
בהינתן מילון לשפה φ ניתן להגדיר מודל M.
φ=<c0,c1,f0,R1,R2,R3> - אין תחום
M=<D,c0(M),c1(M),f0(M),R1(M),R2(M),R3(M)>
יש תחום במודל, תחום לא ריק!

דוגמה:
Y=<c0,R1>
M1=<ℕ,0,>

יחס השוויון נכלל בשפה אלא אם נגדיר אחרת.

האם הנוסחה הבאה נכונה?
R(x,y)
D=
R מסמן ≤.

לא ניתן לקבוע.
אנחנו צריכים שני דברים על מנת לקבוע
1. מודה
2. השמה (לתת ערכים למשתנים)

לעומת זאת אם קיימת נוסחה ללא משתנים חופשיים, אנחנו צריכים רק מודל)

כדי לקבוע ערך אמת צריך לקבוע מודל והשמה.

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

הגדרה: השמה S היא פונקציה שלכל משתנה נותנת ערך מתחום D.

בהינתן השמה S שנותנת ערכים למשתנים, אפשר לגזור ערך של של שם עצם.

ערך אמת של נוסחה φ במודל M והשמה S:
הגדרה באינדוקציה על מבנה נוסחה:
1. מהו ערך אמת של נוסחה אטומית:
R(t1,t2)
t1 ו-t2 הם שמות עצום, אם t1 נימצא ביחד אם t2 אזי הערך של הנוסחה T, אחרת F.

2. כללי יצירה: כמתים וקשרים.
קשרים
(R(,)→R2(,,,))
פשוט לפי טבלאות אמת של כל קשר וקשר.


כעת נגדיר ערך אמת של נוסחאות כאלו:
∀xφ
xφ


S(d is x)
השמה שבה נותנת ערך d ל-x.

S(d is x)=
{
if x: d
if not x: S
}

S: x=1, y=2,z=3

S(5 is y):x=1,y=5,z=3

במודל M והשמה S ערך אמת של xφ הוא T אם לכל d∈D: מתקיים φ נכון עבור מודל M והשמה S when d is x

במודל M והשמה S, ערך אמת של xφ∃ הוא T אם קיים d∈D: כך ש-φ נכון עבור מודל M והשמה S when d is x.


∃xφ(x)¬∀x¬φ(x)
∀xφ(x)¬x¬φ(x)

הערות:
- ערך אמת של פסוק (נוסחה בלי משתנים חופשיים), לא תלוי בהשמה.
(נוסחה בלי משתנים חופשיים היא פסוק)

למשל:
∀x∀yR(x,y)
ניתן לקבוע ערך אמת של פסוק בעזרת מודל בלבד. (כל המשתנים קשורים / מקושר.

לכן בהינתן פסוק φ כלשהו, ערך האמת שלו תלוי רק במודל.

הגדרה:
נגיד שנוסחה φ היא אמת לוגית (=טאוטולוגיה) אם בכל מודל ובכל השמה φ מקבל ערך אמת T.

for all M and for all S:  M⊧(S)φ
דוגמאות לטאוטולוגיות
1.
∀x x=x
2.
(∀x∀y R(x,y) → ∀y∀x R(x,y))
3. אם φ הוא טאוטולוגיה בתחשיב פסוקים, למשל:(p¬p)
אזי אם לוקחים נוסחה ומציבים במקום פסוק אז מקבלים טאוטולוגיה.

ψ=R(x,y)

(R(x,y)¬R(x,y))
מדובר גם בטאוטולוגיה.




אמת לוגית (=טאוטולוגיה).
φ הוא אמת לוגית אם φ מקבלת ערך אמת בכל מודל M ובכל השמה S.


סתירה: φ סתירה אם בכל מודל M והשמה S, מתקיים ש-φ מקבל ערך אמת F.

φ ספיקה אם קיימת השמה S ומודל M שמספק אותה, זאת אומרת שנותן לה ערך אמת T.
⊧ (S)φ
M= מודל
S = השמה

משפט: אם φ אמת לוגית (=טאוטולוגיה), אזי φ¬ סתירה.

הערה: Mφ  אם לא כותבים השמה S כלשהי, אז φ מקבלת ערך אמת בכל השמה.

M NOTφ אזי φ לא טאוטולוגיה.


סימון:
ψφ
ψ גוררת לוגית את φ: אם בכל מודל M ובכל השמה S שמספקים את ψ, גם ערך האמת של φ הוא T.

Σφ
כאשר Σ היא קבוצת פסוקים.
אם M ו-S מספרים על פסוק ב-Σ אזי הם נותנים ערך אמת T ל-φ.

ציון ספיקות
Mφ
M⊧(S)φ


ציון גרירה לוגית
ψ⊧φ
Σφ


שקילות לוגית
ψφ ⇔ בכל מודל ובכל השמה ל-ψ ול-φ יש אותו ערך אמת.

משפט:
φ) טאוטולוגיה אם ורק אם  ψφ


מהי הצבה?
סימון
 φ[t|x]
מציבים t במקום משתנה חופשי x/

למשל
φ=∀x∀yR(x,y)→R(x,y))
φ=[F(c)|x]

בכל מקום ש-x חופשי, מציבים F של c
φ[F(c)|x]=∀x∀yR(x,y)→R(F(c),y))


מהי הצבה כשרה?
הצבה כשרה היא הצבה שכאשר מבצעים אותה (על משתנים חופשיים), אף משתנה מ-t לא הפך להיות קשור.

רענון משתנים:
(∃xp(x)∃xG(x))
רענון משתנים בצורה לא טובה:
∃x(p(x)G(x))

רענון משתנים בצורה טובה:
∃x∃y(p(x)G(y))

שימו לב: רענון משתנים והצבה זה לא אותו דבר!


צורה פרנסקית נורמלית
אם פסוק (או נוסחה) הוא בצורה פרנקסית נורמלית אזי:
1. כל הכמתים בתחילת הנוסחה.
2. הנוסחה היא בצורת DNF: דיסיונקציה של קוניוקציות (כלומר: קבוצות של חיתוכים שמה שמפריד ביניהם זה איחודים).

דוגמאות:
∀x∀y [R(x,y)∨R(y,x)] 

משפט: לכל פסוק (או נוסחה) φ קיים (לא באופן יחיד) פסוק / נוסחה ψ בצורה פרנקסית נורמלית כך ש:
φψ


אלגוריתם, רשימת צעדים על מנת להפוך כל פסוק לצורה פרנקסית נורמלית:

1. נטפל בקשרים →, ↔ על ידי שימוש בנוסחאות:
A→B≡ ¬A∨B
2. רענון משתנים
3. מטפלים בשלילה לפני כמתים:
¬∃xR(x)∀x¬R(x)

¬∀xR(x)∃x¬R(x)
4. נהפוך פסוק ונוסחה לצורת DNF.
5. הוצאת כמתים החוצה.


תרגיל

φ=((∀xp(x)→∃yQ(y))∃xt(x))
נטפל בקשר →:
A→B¬A∨B

((¬∀xp(x)∃yQ(y))∃xt(x))
נחליף סדר בין שלילה וכמת (נכניס את השלילה פנימה)
((x¬p(x)∃yQ(y))∃xt(x))

רענון משתנים - נחליף x אחרון ב-z:
((x¬p(x)∃yQ(y))∃zt(z))
נוציא כמתים החוצה

x∃y∃z((¬p(x)Q(y))t(z))

כעת זה בצורה פרנקסית נורמלית.


תרגיל נוסף
((xp(x)→∃zT(z))→(∀xT(x)→∃zp(z))

נטפל בחץ הימני והשמאלי

((¬xp(x)∃zT(z))→(¬∀xT(x)∃zp(z))
נטפל בחץ שנותר

(¬(¬xp(x)∃zT(z))(¬∀xT(x)∃zp(z))



נפעיל דה מורגן בצד שמאל

((xp(x)¬∃zT(z))(¬∀xT(x)∃zp(z))

נכניס שלילה פנימה ונקבל
((xp(x)z¬T(z))(x¬T(x)∃zp(z))

נבצע רענון משתנים, את ה-x השני נשנה ל-y, את ה-z השני נשנה ל-w
((xp(x)z¬T(z))(∃y¬T(y)∃wp(w))


נוציא כמתים החוצה

xz∃y∃w((p(x)¬T(z))(¬T(y)p(w))

והריי לנו פסוק בצורה פרנקסית נורמלית.


מערכת הוכחה פורמלית בתחשיב יחסים / תחשיב הילברט / לוגיקה מסדר ראשון.
הערה: בתחשיב הילברט נעזר ונשתמש בכמתים: ∀ ו-  ¬,→

formal sentance=I(AX,creating sentances)

AX=אקסיומות
Creating sentance = כללי יצירה

אקסיומות:
AX1: (φ(x)→(ψ(x)φ(x)))
AX2: (((φ(x)→(ψ(x)Θ(x))→((φ(x)ψ(x))→(α→Θ(x))))
AX3: ((¬α→¬ψ(x))→(ψ(x)α))



כאשר φ,ψ,Θ הן נוסחאות, בכל אובייקט אפשר להציב נוסחה, 3 תבניות.

אקסיומת הזזה:
(∀x(F→G)→(F→∀xG))
כאשר G,F נוסחאות, X לא מופיע חופשי ב-F.

∀x(∃xR(x)→Q(y))→(∃x(R(x)→∀xQ(y))

∃xR(x)=F 
x לא חופשי ב-F

אקסיומת ההצבה:∀xF→F[t|x]
כאשר F נוסחה, t שם עצם וההצבה כשרה.
∀xR(x)→R(y)

R(x)=F
F[y|x]

אם φ∈S, כאשר S זאת קבוצת כללי היצירה והאקסיומות, אזי יש לו סידרת יצירה, ולה קוראים הוכחה פורמלית.


כלל היסק / ניתוק /MP:
IF:
φ→ψ
φ
THEREFORE:
ψ

2. אם הוכחנו 
φ(x) 
אזי נסיק
∀xφ(x)

משפט דדוקציה:
תהי:
k - תורה (=קבוצת פסוקים שיש להם מודל, יש מודל שמספק אותם (ספיק))
ψ - פסוק
t - נוסחה
k⊢(ψ→φ)
אם ורק אם
{kψ}φ



תרגיל
⊢[∀x(P(x)→Q(x))→(∀xP(x)→∀xQ(x))]
לפי משפט דדוקציה מספיק להוכיח:
∀x(P(x)→Q(x))(∀xP(x)→∀xQ(x))
שוב נשתמש במשפט דדוקציה:
∀x(P(x)→Q(x)),∀xP(x)∀xQ(x)


הוכחה
1.∀x(P(x)→Q(x))  
הנחה
2.∀x(P(x)→Q(x))→(P(t)→Q(t))   
אקסיומת הצבה
3.P(t)→Q(t)
MP ON 1,2
4.∀xP(x)
הנחה
5.∀xP(x) →P(t)
6.P(t)
Mp ON 4,5
7.Q(t)
MP ON 3,6
8.∀xQ(x)
כלל יצירה שני




הערה:
p,q ⊧ p∧q
↓ משפט שלמות
p,q p∧q
ולכן משפט p∧q ניתן להוכיח מ- p ו-q.

תחשיב יחסים, לוגיקה מסדר ראשון
תזכורת: בתחשיב יחסים הוכחנו משפט: קבוצת פסוקים היא עקבית מקסימלית אם יש לה מודל 1.
עקבית: אם היא יודעת על כל דבר להחליט האם הוא T או F.

הגדרה: הומומורפיזם (=שם נרדף לפונקציה על)
יהיו M1, M2 מודלים לאותה שפה.
פונקציה H:
H: D_M1→D_M2
מוגדרת מהתחום של M1 אל התחום של M2 או בקיצור:
H: M1→ M2
נקראת הומומורפיזם אם היא מקיימת:

1.לכל קבוע
 ∀i H(Ci (M1))= Ci (M2)
כל קבוע במודל M1 שנציב בפונקציה, יהיה שווה למודל ב-M2.

2. לכל פונקציה f:
H(f^M1(a1,...,an))=f^M2(H(a1),H(a2),...,H(an))∈R^M2


3. לכל יחס R:
(a1,...,am)∈R^M1→(H(a1),H(a2),...,H(an))∈R^M2




זאת אומרת H שומרת על קבועים, פונקציות ויחסים.

(תזכורת: במילון אין תחום, קודם כל מילון ואז המודל נותן משמעות.)




דוגמאות:
dictinary: <c,f2>
M1: <Even,0,+>
M2: <ℕ,0,+>

H:M1→M2
H(x)=2x
נבדוק האם H הוא הומומורפיזם:
1. נבדוק האם קבוע אפס עובר לאפס:
H(0)=2*0=0

ואכן זה כך

2. נבדוק:
H(a,b)=H(a)+H(b)
2(a+b)=2a+2b
האם קיים קשר בן התמונה של הפונקציה f1 לפונקצייה של f2.

אכן הומומורפיזם מ- M1 ל-M2


דוגמה שנייה:

<>

M1=<[0,1]>
M2=<{0,1,2}>
H(x)=0
כל פונקציה חוקית תישמר באופן ריק, לכן הומומורפיזם באופן ריק.



הגדרה:
איזומומורפיזם מוכלל, זה הומומורפיזם על M1,M2 כלומר H הוא פונקציה מ-M1 על M2. (בכל איבר ב-M2 יש מקור)
ובנוסף לכל יחס R:
(a1,a2,...,an)ℝ^M1 ⇔ (H(a1),H(a2),...,H(an))ℝ^M2



למשל בדוגמה הראשונה, 
H:M1→M2
H אינה פונקציה על ולכן היא לא איזומורפיזם מוכלל.


דוגמה:
dictionary <>
M1=<ℝ\{0}>
M2=<{0,1}>
H:M1→M2


H(x)=1 if xℝ^+
H(x)=0 if xℝ^-
H הוא איזומורפיזם מוכלל, כי H פונקציה על והיא גם הומומורפיזם.
מקור של 0 הוא 1-.
מקור של 1 הוא 0.


הגדרה: איזומורפיזם H היא פונקציה איזומורפיזם מוכלל ובנוסף H היא פונקציה חח"ע.

דוגמה:
dictionary <c1,f2>
M1=<ℝ^+,1,*>
M2=<ℝ,0,+>
H(x)=ln(x)
H:M1→M2
צריך לבדוק האם מוגדר בכלל

האם הגודמה האחרונה היא הומומורפיזם:
קבוע:
H(1)?=?0
ln(1)=0
האם היא שומרת על פונקציה:
H(a*b)?=?H(a)+H(b)
ln(a*b)=lna+lnb
מתקיים לפי תכונות של ln
ולכן H הומומורפיזם.
כעת נבדוק האם H היא פונקציה על, כדי לבדוק האם H איזומורפיזם מוכלל.

תשובה: H היא על כי לכל איבר ב-R יש מקור.

אם xℝ אז המקור שלו:
e^xℝ^+
כי
lne^x=x
נסיק כי H איזומורפעזם מוכלל.

כעת נבדוק האם * פונקציה חח"ע.

הערה: lnx היא פונקציה הפיכה, e^x, ולכן H חח"ע ועל.

הערה: כל מה שעשינו היה נכון בתנאי שאין יחס שוויון בשפה..

דגומה: דוגמה קודמת ביחד עם  יחס שוויון:
dictionary <c1,f2>
M1=<ℝ^+,1,*,=>
M2=<ℝ,0,+,=>
H(x)=ln(x)

H:M1→M2

(a=b)⇔lna=lnb
לכן H בדוגמה הזאת היא איזומורפיזם מוכלל.

משפט: אם בשפה יש קבועים (לפחות קבוע אחד) ויש יחס שוויון, אזי כל איזומורפיזם מוכלל הוא איזומורפיזם.

דוגמה:
בדוגמה זו יש יחס שוויון!
dictionary <>
M1=<R>
M2=<(0,1)>
H(x)0.5+1/π arctanx
חח"ע  ועל

משפט: אם קיים איזומורפיזם בין M1 ל-M2 אזי M1 ו-M2 נקראים איזומורפיים.


משפט חשוב: אם M1 ו-M2 שתי מודלים איזומורפיים אזי לכל נוסחה φ:
M2 ⊧ φ ⇔ M1 ⊧ φ
בעזרת משפט זה נוכל להוכיח ששתי מודלים לא איזומורפיים.


דוגמאות הכוללות יחס שוויון
dictionary <c>
M1<{a,b},a>
M2=<{a},a>
שאלה: האם M1 איזומורפי ל-M2?
אם משפט היה נכון, אם הם היו איזומורפיים כל נוסחה היית נכונה בשניהם.
התשובה: לא.
פתרון:
φ=∀x∃y¬(x=y)
M1 ⊧ φ
M2 NOT⊧ φ


הערה: השפה (=תחשיב יחסים) לא מסוגלת להבדיל בין שתי מודלים איזומורפיים (בשבילה זה אותו דבר, אין דרך להבדיל ביניהם).
או במילים אחרות: השפה של תחשיב יחסים מסוגלת להבדיל בין מודלים עד כדי איזומורפיזם.

משפטים: תהי T תורה אם מודל ∞, אזי ל-T יש מודלים אינסופיים מכל עוצמה אינסופית.

(תזכורת: תורה = קבוצת נוסחאות שיש לה מודל אחד, שניתנת לסיפוק. מודל אחד לפחות שניתן ערך אמת T והוא אינסופי).

תורה שלמה - יודעת להגיד על כל פסוק אם הוא T או F.

בתחשיב פסוקים T היא תורה שלמה אם יש לה בדיוק מודל 1.

בתחשיב יחסים תורה T היא שלמה אם בכל עוצמה יש לה מודל יחיד עד כדי איזומורפיזם.

גם בתחשיב יחסים מתקיימים המשפטים הבאים: שלמות ונאותות.


מודל ותת מודל
הגדרה: יהיו M1,M2 שתי מודלים של אותה שפה.
נגיד ש-M2 הוא תת מודל של M1 אם M2 מוגדר בדיוק כמו M1 ומתקיים:
Dom M2 ⊆ M1

dictionary <c,f,R>

M1=<Even,0,+>
M2=<ℕ,0,+>
M3=<Odd,1,+>
M4=<{0},0,+>
M5=<{1,2},1,+>


האם M1 הוא תת מודל ל M2? כן
האם M2 הוא תת מודל M1? לא
האם M4 הוא תת מודל של M1? כן
האם M4 הוא תת מודל של M3? לא
האם M5 הוא תת מודל של M3? לא


1. תת מודל / תוו מודל מינימלי.
2. גדירות

המרכיבים במילון: הכל חוץ מתחום: קבועים, יחסים, פונקציות (=השמות שלהם).
נתונה שפה עם מילון L.
ניתן להגדיר ∞ מודלים עבור שפה.
נגיד שמתקיים M1⊆M2 אם DOMAINֹֹ_M1⊆DOMAIN_M2 וכל הקבועים, פונקציות ויחסים מוגדרים באותה דרך.

דוגמה:
L=<f+,R,a,b>
M1=<ℕ,+,≤,0,1>
M2=<{0,1,2,3},+,≤0,1>
M2⊆M1

M3=<{0},+,≤,0,0>
M3 NOT⊆ M2
M3 NOT⊆ M1


יכול להיות שיש מודל M שמכיל בתוכו תת מודלים זרים.

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

חיתוך של כולם זה תת מודל מינימלי.

אם בשפה אין קבועים, אפשר להגדיר תתי מודלים זרים.

דוגמה:
L=<>
M=<>
M1=<Even>
M2=<Odd>

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

דוגמה:
L=<f,a>
M1=<M,*,0>
M2=<Even,*,0>
M3=<{0,1,2},*,0>
M2M1
M3M1

הגדרה: תת מודל מינימלי למודל M הוא חיתוך על כל Mi שמוכל ב-M.

לוקחים את כל תתי המודלים של M וחותכים אותם.
תת מודל שלא מכיל ממש תת מודל.
∩Mi
Mi
⊆M
תת מודל מוכל בכולם ואין משהו יותר קטן ממנו.
אפשר להגיד את זה כקבועים של המודל.

משפט: תת מודל מינימלי הוא יחיד עד כדי איזומורפיזם.

(אם צורת נוסחה "יש" או "קיים" נכונה בתת מודל מינימלי, אזי היא נכונה לכל תחום יותר גדול ממנו.)

אם φ היא נוסחה "קיים/יש" שנכונה בתת מודל מינימלי, אז φ נכונה בכל מודל שמכיל תת מודל מינימלי.

אם φ היא נוסחה "לכל" (=כל הכמתים הם לכל בתחילת הנוסחה), ו-φ נכונה במודל M אז φ נכונה בכל תת מודל של M.

טענה: לא כל נוסחה אפשר להפוך לצורה של נוסחה "לכל", או נוסחה "קיים".

דוגמה:
(כל הכמתים צריכים להיות בחוץ)
(∀xφ(x)→∃xψ(x))
נבצע רענון משתנים:
(∀xφ(x)→∃yψ(y))

A→B¬A∨B

(¬∀xφ(x)∨∃yψ(y))

¬∀x∃x¬

(∃x¬φ(x)∨∃yψ(y))
∃x∃y(¬φ(x)∨ψ(y))

הגענו לצורה פרנקסית נומלית, אך לא כל הנוסחאות יכולות להיות בצורה אוניברסלית / לכל.


גדירות: קבוצת מבנים / מודלים K, גדירה בשפה L אם קיימת קבוצת נוסחאות ∑:

K={M:M }
זאת אומרת בעזרת קבוצת מודלים K, ניתן להגדיר שפה L כך שכל M מקיים את קבוצת הנוסחאות.

Mφ   נכון במודל זה. אם אין השמה אז נכון בכל השמה

φψ  גרירה לוגית


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

מגדירים אוסף מודלים בעזרת נוסחאות - אם זה אפשרי, קבוצת המודלים גדירה בשפה L.

צריך לבחור שפה.

דוגמה:  נבחר שפה L (עם יחס שוויון).
L=<>
K קבוצת כל המודלים עם תחום בגודל

דוגמה:
נתונה שפה L.
L=<>
K קבוצת מודלים עם לפחות n איברים בתחום.
האם K גדירה ב-L?
≥n ={∃x1,...,∃xn ∩i≠j ¬(xi=xj)}


דוגמה נוספת:
L=<>
K הוא אוסף המבנים עם תחום לכל היותר n איברים.
רעיון: לכל n+1 משתנים שונים, לפחות 2 מביניהם שווים.
≤n={∀x1,∀x2...∀xn+1 ∪i≠j (xi=xj)

אוסף כל המבנים עם בדיוק n איברים בתחום

≥n  ∩ ≤n



דומה נוספת:
L=<R(,)>
נגדיר קבוצת מודלים K באופן הבא:
ב-K יש את כל המודלים שבהם היחס R הוא יחס סדר מלא.
האם K גדיר ב-L?
∑order={כל שני איברים נתנים להשוואה}={∀x∀y R(x,y)∪R(y,x) }

אזי
∀x∀y (R(x,y)∧ R(y,x) → x=y))

∀xy∀z (R(x,y)∧ R(y,z) → R(x,z))


דוגמה נוספת:
L=<>
K קבוצת מבנים עם תחום אינסופי.
האם K גדיר ב-L?
אין נוסחה שתגדיר מבנים עם תחום אינסופי, כי נוסחה זה משהו סופי.

לסיכום
אסור נוסחה אינסופית!
מותר קבוצה אינסופית!

גדירות במבנה / מודל
נתונה שפה L, נתון מודל M עם תחום D^M.
מטרה: "להגדיר תת קבוצה מ-D^M".
דוגמה:
L=<f(,), g(), N() , a,b>
M=<ℕ,+,*,Next,0,1>

Even={a : a זוגי}
האם זה גדיר ב-M של L
φ(x)= ∃y x=f(y,y)
זאת אומרת שקבוצה זו גדירה ב-L.

הקבוצה Even גדירה ב-L.

מודל הרבדנט
נראה איך להוכיח בעזרת מודל H, כי φ אמת לוגית (=טאוטולוגיה).
או φ יכיח (φ)


תזכורת: שפה L: מילון (מה יש, ללא פירוש / משמעות). מודל / מבנה שמגדיר תחום D וגם נותן פירוש לכל איברים בשפה.

* M1 תת של מודל (מבנים = בדיוק אותו פירוש) M1⊆M2.
אם M1,M2 נותנים אותו פירוש לקבועים, פונקציות ויחסים אבל D_M1⊆D_M2.


אם בשפה יש לפחות קבוע אחד אזי כל תתי מודלים לא זרים וקיים (עד כדי איזומורפיזם) תת מודל מינימלי יחיד.

(חיתוך של כל תתי קבוצות=מינימום).

אם φ היא נוסחת קיים, נכונות של φ נשמרת כלפי חוץ.

אם φ נוסחת לכל / אוניברסלית, אז נכונות נשמרת כלפי פנים.

לא כל נוסחה אפשר להעביר לנוסחה בצורה קיים או לכל ששקולה לה.

משפט הרברנד (=משפט שבעזרתו נראה שקבוצה / נוסחה נכונה או לא):
תהי T אוניברסלית (תורה = קבוצת פסוקים שניתנת לסיפוק בשפה אם לפחות קבוע אחד, כי אז יש תת מודל מינימלי).
אזי T ספיקה אם ורק אם T* ספיקה.

T* קבוצת כל ההצבות של שמות עצם לתוך משתנים.

דוגמה:
T={∀x (R(x)→R(f(a))}

מרחב הרברנד, של שפה L עם לפחות קבוע אחד: קבוצת כל שמות העצם ללא משתנים.

{a,f(a),f(f(a)),f(f(f(a))),....}
אם לא היה לנו פונקציה, אז היו לנו שמות עצם כמו קבועים.
T*={(R(a)→R(f(a)),(R(f(a))→R(f(a)),...}

רעיון: נרצה להראות ש- φ יכיח, נסתכל על φ¬, ונראה ש-φ¬ לא ספיק.

משפט הרברנד מדבר על נוסחאות אוניברסליות

אלגוריתם סקולם (סקולומיזציה) מאפשר להעביר נוסחה φ בנוסחה φ* אוניברסלית ששקולה ל-φ.
(נקבל נוסחה שונה לוגית, ייתכן עם מהות שונה).

אלגוריתם סקולם:
1. להפוך את φ לצורה פרנקסית נורמלית. DNF.
2. לטפל בכמת קיים.
∃x∀yR(x,y)
נהפוך ל:
∀yR(a,y)



דוגמה נוספת
∀y∃xR(x,y)
נהפוך ל:
∀yR(g(y),y)




∀x∀y∃zR(x,y,z)
נהפוך ל
∀x∀yR(x,y,g1(x,y))


דוגמה:
φ=∀x[R(x)→∀y(P(x,y)→∃x(Q(x))]
נהפוך את φ לפסוק אוניברסלי בעזרת אלגוריתם סקולם.

רענון משתנים:
∀x[R(x)→∀y(P(x,y)→∃z(Q(z))]


A→B¬A∨B

∀x[¬R(x)∀y(¬P(x,y)∃z(Q(z))]
הוצאת כמתים:


∀x∀y∃z[¬R(x)(¬P(x,y)(Q(z))]


∀x∀y[¬R(x)(¬P(x,y)∨(Q(g(x,y))]


והריי לנו צורה אוניברסלית.

תרגיל: הוכח בעזרת משפט הרברנד H, ש φ יכיח.

x∀y(P(x,y)→∀yxP(x,y))

ניקח את φ¬, ובעזרת משפט H נראה ש-φ¬ לא ספיקה.

φ=¬x∀y(P(x,y)→∀yxP(x,y))
נשתמש אלגוריתם סקולם כדי להפוך את φ¬ לנוסחה אוניברסלית.

נבצע רענון משתנים:
¬∃x∀y(P(x,y)→∀w∃zP(z,w))
¬(A→B)¬(¬A∨B)≡(A¬B)

x∀y(P(x,y)¬∀wzP(z,w))
נכניס שלילה פנימה
x∀y(P(x,y)wz¬P(z,w))
מוציאים כמתים החוצה
∃xw∀yz(P(x,y)¬P(z,w))

סקולומיזציה
w∀yz(P(a,y)¬P(z,w))


∀yz(P(a,y)¬P(z,b))

הגענו לנוסחה אוניברסלית.

מרחב הרברנד:
T*={p(a,a)¬P(a,b) , p(a,a)¬P(b,b) , p(a,b)¬P(a,b)...}

p(a,b)¬P(a,b)  - לא ספיקה, סתירה

קבוצת מודל היא ספיקה אם יש מודל שמספק את כולם.

קבוצת פסוקים φ1,φ2,φ3,... ספיקה אם קיים מודל M כך ש:
Mφ1,φ2,φ3,...
מסקנה T* לא ספיקה, לכן φ¬ לא ספיקה, לכן φ אמת לוגית.

דוגמה, הוכח בעזרת משפט H כי שני פסוקים שקולים לוגית:
φ1= ∀x∃y(R(x,y)→∀y∃xR(x,y))
φ2= ¬(∀x∃y(R(x,y)∃y∀x¬R(x,y))

נסתכל ב-φ1 ובשלילה של φ2.


φ1= ∀x∃y(R(x,y)→∀y∃xR(x,y))

¬φ2= (∀x∃y(R(x,y)∃y∀x¬R(x,y))

¬φ2= (∀x∃y(R(x,y)∃z∀d¬R(d,z))
∀x∃y∃z∀d((R(x,y)¬R(d,z))
∀x∃z∀d((R(x,g(x))¬R(d,h(x)))

מרחב הרבנד (=כל שמות העצם בלי משתנים)
{a,f(a),g(a),h(a),h(f(a)),...}

עבור נוסחה 2 אם נציב
T'=   x=a,g(x)=a, t=a, h(t)=a
נקבל סתירה

לכן φ1 ו-φ2 שקולים


נושאים אחרונים:
1. משפט הרברנד.
2. לוגיקה מסדר שני
3. משפט גודל
4. נושאים

1. מודל / משפט הרברנד (=דרך שמאפשרת לבדוק האם פסוק הוא אמת לוגית או לא).


שימושים:  1. לבדוק האם φ אתמ לוגית. רעיון של פתרון: לבדוק של-φ¬ אין מודל הרברנד.

2. לבדוק האם פסוק נובע מפסוקים ψ1,ψ2,ψ3,... 
רעיון: נראה שאין מודל H לפסוקים φ,ψ1,ψ2,ψ3¬ 

תרגיל:
φ=¬∀x(P(x,f(x)¬P(b,y))
בעזרת משפט או מודל H תראה ש-φ יכיח.

פתרון:

¬φ=∀x(P(x,f(x)¬P(b,y))
יש להפוך את φ¬ לפסוק בצורה אוניברסלית
∀x(P(x,f(x)¬P(b,y))

מגיעים לזה בצורה מיידית.

מרחב הרברנד
{a,f(b),f(f(b)),...}

T*={y=f(b) x=b : P(b,f(b)¬P(b,f(b))
סתירה.
T* קיבלנו סתירה, ולכן אין מודל הרברנד ל φ¬ ולכן φ יכיח.


תרגיל:
נתון.
1. רק בנאדם אחד הצליח במבחן
2. לפחות שני אנשים ניסו
3. מסקנה: לפחות בנאדם אחד נכשל.

הוכיח בעזרת משפט הרברנד ש-3 נובע לוגית מ-1,2.

נסמן
S(x) - הצליח
N(x) - ניסה

1. φ1=∃x (S(x)∀y (S(y)→x=y))
2. φ2=∃x∃y(N(x)∧N(y)¬ (x=y))
3.φ3=∃x¬S(X)

ניקח φ1,φ2,¬φ3 ונראה שאין לקבוצה זו מודל H.
¬φ3=¬∃x¬S(X)=∀xSׂ(x)

φ1=∃x (S(x)∀y (S(y)→x=y))
A→B¬A∨B
נטפל בקשר חץ
∃x (S(x)∀y (¬S(y)x=y))
הוצאת כמת לכל
∃x∀y (S(x)(¬S(y)x=y))
נשתמש בחוג הפילוג
∃x∀y (S(x)¬S(y))∨(S(x)x=y)

סקולומיזציה, טיפול בכמת קיים
∃x a|x
φ1=∀y (S(a)¬S(y))∨(S(a)a=y)


φ2=∃x∃y(N(x)∧N(y)¬ (x=y))
סקולומיזציה

φ2=(N(b)∧N(c)¬ (b=c))


לסיכום:

φ1=∀y (S(a)¬S(y))∨(S(a)a=y)
φ2=(N(b)∧N(c)¬ (b=c))
¬φ3=∀xSׂ(x)

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

{a,b,c}

T*=
{
1)Sׂ(a),Sׂ(b),Sׂ(c)
2)(N(b)∧N(c)¬(b=c))
3)(S(a)¬S(a))∨(S(a)a=a)
4)(S(a)¬S(b))∨(S(b)a=b)
5)(S(a)¬S(c))∨(S(c)a=c)
}


מ-1) אנחנו יכולים להגיד שחייב להתקיים:
¬(b=c) 
מ -4) 5), אנחנו יכולים להגיד שחייב להתקיים:

a=c
b=c
לכן
b=c

מצאנו סתירה. זאת אומרת אין מודל H לפסוקים φ1,φ2,¬φ3 ולכן נתקיים 
{φ1,φ2}¬φ3


לוגיקה מסדר שני:
דוגמה: אם סטודנט יודע לפתור את כל הבעיות אז הוא מצטיין.
∀x^s∀y^p(SOLVE(x,y)→exelent(x))

אף סטודנט לא יכול לפתור את כל הבעיות
¬∃x^s∀y^p Solve(x^s,y^p)

קיימת בעיה שאף סטודנט לא יודע לפתור
∃y^p∀x^s(¬Solve(x^s,y^p))

משפט קומפקטיות נובע מנאותות ושלמות:
קבוצת פסוקים ספיקה אם ורק אם כל תת קבוצה סופית של הפסוקים ספיקה.

על מנת להוכיח שמשהו לא גדיר, משפט הקומפקטיות יכול לשמש לנו ככלי עזר.

1. אינדוקציה מבנית: של תחשיב יחסים או של תחשיב פסוקים.
2. קבוצת קשרים מלאה / משפט שלמות, נאותות (האם מערכת אקסיומות שלמה / נאותה).
3. בדיקת אמת לוגית: הוכחה פורמלית / דדוקציה טבעית
4. גדירות, הצרנה, לוגיקה מסדר שני.
5. תתי מודלים, מודל מינימלי, איזומורפיזם, מודל הרבנד.


תרגול בהצרנה:

1. לכל מספר טבעי x קיים y גדול ממנו.
∀x∃y((N(x)∧N(y)→R(x,y))

2. לכל 2 מספרים טבעיים x,y, אם x>y אזי לא נכון y<x


∀xy((N(x)∧N(y)R(x,y))→¬R(y,x))

3. C לא מספר טבעי
¬N(c)

4. C גדול מכל מספר טבעי
∀x(N(x)→R(x,c))



לא לשכוח להוסיף את הטבלה המסכמת!

ALT+253