מהי לוגיקה

Август 4, 2022

Содержание

2. לוגיקה במדעי המחשב מחשב מחקה יכולת שכלית (היגיון) תוכנית מחשב – סוג של הוכחה. תורת התכנות-
3. טיעונים אם רכבת מאחרת וגם אין מוניות זמינות בתחנה, אז אלי מאחר לפגישה. אבל אלי לא
4. נדון בפסוקיי חיווי, אשר יש להם בדיוק אחד משני ערכים: אמת (True) או שקר (False). 1.
5. קשרים לוגיים שלילה (negation) ¬P : "לא P". קוניונקציה (conjunction, גימום) P∧Q: "P ו- Q“. דיסיונקציה
6. תחביר הגדרה: נוסחא נקראת בנויה היטב (well-formed formula) אם ניתן ליצור אותה לפי החוקים הבאים: כל
7. פסוקים מורכבים דוגמא: ,(p∨q) ,((p∧q)∨(¬p)) ,((¬p)∨q) ¬(¬p))) ולא ((p ∧ q)), (p ∧ q ∧ r),
8. אינדוקציה על נוסחאות אם תכונה P נכונה לכל הפסוקים האטומיים, ומהנחה ש-P נכונה לנוסחאות A ו-B
9. הצרנה זהו מקס או שההוא מוריץ ואני ליצן: p ∨ q ∧ r אני אגיע הביתה
10. סמנטיקה פירוש או מודל הוא השמה l: P → {F,T} - שיוך ערכיי אמת לפסוקים אטומיים.
11. דיסיונקציה קוניונקציה P∧Q אמיתי כאשר גם P וגם Q אמיתי, אחרת שקרי: P∨Q שיקרי כאשר גם
12. שקילות אימפליקציה P→Q שקרי כאשר P אמיתי ו- Q שקרי, אחרת אמיתי. אם 1+1=3, אז פריס
13. יחס ספיקות הגדרה. (הרחבה של פירוש לפסוקים מורכבים) l(⊥)=F l(¬A)=T אם ורק אם l(A)=F l(A∧B)=T אם
14. בעיות ספיקות ותקפות נוסחה נקראת ספיקה (או עקבית) אם יש לה מודל. נוסחה לא ספיקה נקראת
15. טבלאות אמת טבלת אמת של פסוק מורכב מתארת את ערכי האמת של הפסוק עבור כל פרוש.
16. טאוטולוגיות וסתירות נוסחה המקבלת ערך אמת T לכל הצבה עבור המשתנים שלה היא טאוטולוגיה. נוסחה המקבלת
17. שקילות של פסוקים שני פסוקים נקראים שקולים אם יש להם אותם מודלים. פסוקים שקולים מהבאים אותה
18. טבלת אמת ל- ¬(p ∧ q)↔(¬p ∨ ¬q) תוך שימוש בשקילויות יסודיות ניתן להוכיח שקילויות חדשות
19. שקילויות יסודיות
20. שלמות פונקציונאלית כל נוסחה A(p1,…,pn) מגדירה פונקצית אמת n-מקומית: לכל ,l g(l(p1),…,l(pn))=l(A) דוגמה. (p ∧ q
21. משפת (שלמות פונקציונאלית). לכל פונקצית אמת קיימת נוסחה המגדירה אותה. הוכחה. תהיה f פונקצית אמת n-מקומית.
22. קבוצות שלמות של קשרים הגדרה: קבוצה של קשרים שבאמצעותם ניתן לתאר כל פונקצית אמת נקראת קבוצה
23. קבוצות לא שלמות של קשרים למה. {↔,∨,∧, →} היא קבוצה לא שלמה של קשרים. הוכחה. להבדיל
24. קבוצות קשרים שלמות NAND – "לא ו-.." - ↑ P↑Q מוגדרת ע"י P↑Q ≡ ¬(P∧Q) קל
25. NOR – "לא או" - ↓ P↓Q מוגדר ע"י P↓Q ≡ ¬(P∨Q) מתקיים: P ↓ P
26. שערים (gates) שער NOT: שער AND: שער OR:
27. רשת לתיאור הנוסחה: (a∨b)∧(¬a∨¬b)
28. שערים נוספים שער NAND: שער NOR: דוגמא: a b a∨b
29. צורות נורמאליות אם p הוא פסוק אטומי, אז p ו-¬p הם ליטרלים. הגדרה. נוסחה בצורה דיסיונקטיבית
30. דואליות הגדרה: תהי A נוסחה שמכילהT , ⊥, ∧, ∨, ו- ¬ בלבד. נוסחה דואלית ל-
31. צורות נורמליות - המשך פסוקית (clause) היא דיסיונקציה של ליטרלים: r∨¬q∨¬p הגדרה. נוסחה בצורה קוניונקטיבית נורמאלית
32. CNF A ≡ (p∨q) ∧(¬p∨¬q) כל פסוקית מתאים לשורה עם ערך F בטבלת אמת. לכל משתנה
33. אלגוריתמים לבניית DNF ו-CNF סילוק → ו- ;↔ הכנסת שלילה פנימה (צורת (NNF פריסה של ∨
34. פסוקיות הורן פסוקית הורן (Horn clause) היא פסוקית שמכילה לא יותר מליטרל חיובי אחד. p∨¬q1∨...∨¬qn (
35. אלגוריתם הכרעה לנוסחאות הורן אלגוריתם HORN להכרעת ספיקות: נסמן אטומים בנוסחת הורן לפי כללים הבאים: נסמן
37. Скачать презентацию

Слайд 2

לוגיקה במדעי המחשב
מחשב מחקה יכולת שכלית (היגיון)
תוכנית מחשב – סוג של

הוכחה. תורת התכנות- לוגיקה שימושית. אימות תוכנה.
תכנות לוגי.
בינה מלאכותית

Слайд 3

טיעונים
אם רכבת מאחרת וגם אין מוניות זמינות בתחנה, אז אלי מאחר

לפגישה. אבל אלי לא איחר לפגישה למרות שרכבת איחרה. לכן היו מוניות זמינות בתחנה.
אם יורד גשם ולטלי אין מטריה איתה, אז היא מצטננת. טלי לא הצטננה למרות שהיה גשם. לכן לטלי הייתה מטריה.
מבנה הטיעון:
אם p וגם לא q, אז r. לא r ו-p. לכן q.
(p∧¬q)→r, ¬r ∧ p├ q

Слайд 4

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

(True) או שקר (False).
1. קנדה היא מדינה.
2. משה הוא כלב
3. סגור את הדלת!
4. |X| = X
5. משפט זה הוא שקר.
מפסוקים יסודיים ניתן לבנות פסוקים מורכבים בתוספת מילות חיבור כגון: ו, או, לא, וכו':
קנדה היא מדינה ומשה הוא כלב.

תחשיב הפסוקים

Слайд 5

קשרים לוגיים
שלילה (negation) ¬P : "לא P".
קוניונקציה (conjunction, גימום) P∧Q: "P

ו- Q“.
דיסיונקציה (disjunction, איווי) P∨Q : P” או Q“.
אימפליקציה (implication, אימוז) P→Q : "אם P אז Q“.
שקילות (equivalence) P↔Q : " P אם ורק אם Q“.

Слайд 6

תחביר
הגדרה: נוסחא נקראת בנויה היטב (well-formed formula) אם ניתן ליצור אותה

לפי החוקים הבאים:
כל פסוק אטומי p,q,... הוא נוסחא בנויה היטב.
קבוע ⊥ הוא נוסחא בנויה היטב.
3. אם A ו- B הן נוסחאות בנויות היטב, אז גם (¬A)
(A↔B), (A → B), (A ∨ B), (A ∧ B) הן נוסחאות בנויות היטב.
4. כל נוסחא בנויה היטב ניתן ליצור במספר סופי של צעדים ע"י שימוש בחוקים -31.

Слайд 7

פסוקים מורכבים
דוגמא: ,(p∨q) ,((p∧q)∨(¬p)) ,((¬p)∨q) ¬(¬p)))
ולא ((p ∧ q)), (p

∧ q ∧ r), (∨ p
משפט. (קריאה יחידה) כל נוסחה שייכת בדיוק לאחד מהסוגים הבאים:
פסוק אטומי.
(¬A) עבור נוסחה אחת ויחידה A.
(A ○ B) עבור קשר בינארי ○ אחד ויחיד ונוסחאות יחידות A ו-B. (בלי הוכחה)

Слайд 8

אינדוקציה על נוסחאות
אם תכונה P נכונה לכל הפסוקים האטומיים, ומהנחה ש-P

נכונה לנוסחאות A ו-B נובע ש-P נכונה ל-(¬A) (A↔B), (A→B), (A∨B), (A∧B),, אזי P נכונה לכל נוסחא בנויה היטב.
הסכם: אפשר להשמיט סוגריים חיצוניות וסוגריים
עבור ¬. לדוגמא נרשום ¬P∧Q במקום ((¬P)∧Q)

Слайд 9

הצרנה
זהו מקס או שההוא מוריץ ואני ליצן: p ∨ q ∧

r
אני אגיע הביתה ואביא תותים אם לא ירד גשם.
אם לא יובל ולא איל יעברו את הבחינה, גם חגי לא יעבור.
לא כולם (מהשלושה) יכשלו.

Слайд 10

סמנטיקה
פירוש או מודל הוא השמה l: P → {F,T} - שיוך

ערכיי אמת לפסוקים אטומיים.
פשר של הקשרים – פונקציות אמת:
f : {F,T} n → {F,T}
לא כל הפסוקים בשפה טבעית הם פונקציות אמת:
"אני יודע ש-P", "מחר יהיה P".
שלילה. ¬P אמיתי אם ורק אם P שקרי.
קבוע שקר. l(⊥)=F

Слайд 11

דיסיונקציה קוניונקציה
P∧Q אמיתי כאשר גם P וגם Q אמיתי, אחרת

שקרי:

P∨Q שיקרי כאשר גם P וגם Q שיקרי, אחרת אמיתי :

Слайд 12

שקילות אימפליקציה
P→Q שקרי כאשר P אמיתי ו- Q שקרי, אחרת

אמיתי.
אם 1+1=3, אז פריס היא בירת צרפת.

P↔Q אמיתי כאשר ל- P ול- Q יש אותו ערך אמת, ושקרי אחרת:

Слайд 13

יחס ספיקות
הגדרה. (הרחבה של פירוש לפסוקים מורכבים)
l(⊥)=F
l(¬A)=T אם ורק אם l(A)=F
l(A∧B)=T

אם ורק אם l(A)=l(B)=T
l(A∨B)=T אם ורק אם l(A)=T או l(B)=T
l(A→B)=T אם ורק אם l(A)=F או l(B)=T
l(A↔B)=T אם ורק אם l(A)=l(B)
פירוש l מספק A, או l הוא מודל של A, אם l(A)=T
עובדה. ערך האמת של פסוק מורכב היא פונקציה של ערכי האמת של הפסוקים אטומיים שלו (קריאה יחידה!).

Слайд 14

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

נוסחה לא ספיקה נקראת סתירה.
בעיית ספיקות (SAT problem): האם (ומתיי) הנוסחה ספיקה? SAT היא בעיית NP.
נוסחה A נקראת תקפה, או טאוטולוגיה, אם כל פירוש הוא מודל של A .
בעיית תקפות: האם נוסחה A תקפה?
A היא טאוטולוגיה אם ורק אם ¬A היא לא ספיקה.

Слайд 15

טבלאות אמת
טבלת אמת של פסוק מורכב מתארת את ערכי האמת של

הפסוק עבור כל פרוש.
אם הפסוק מורכב מ- m פסוקים אטומיים, אזי יש 2m, צרופים ובטבלת האמת שלו תהיינה 2m שורות.

Слайд 16

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

היא טאוטולוגיה.
נוסחה המקבלת ערך F לכל הצבה כזאת היא סתירה.

ניתן להוכיח טאוטולוגיות וסתירות בשיטת השלילה.
דוגמא: (A→B) →(¬A∨B)

Слайд 17

שקילות של פסוקים
שני פסוקים נקראים שקולים אם יש להם אותם מודלים.

פסוקים שקולים מהבאים אותה טענה.
נסמן את השקילות ב- ≡. בדוגמא: A ≡ A∨A.
משפט: נוסחאות A ו- B שקולות אם ורק אם A↔B
היא טאוטולוגיה.
הוכחה נובעת מן ההגדרות [נמק].

Слайд 18

טבלת אמת ל- ¬(p ∧ q)↔(¬p ∨ ¬q)
תוך שימוש בשקילויות יסודיות

ניתן להוכיח שקילויות חדשות בלי להשתמש בטבלאות אמת.

Слайд 19

שקילויות יסודיות

Слайд 20

שלמות פונקציונאלית
כל נוסחה A(p1,…,pn) מגדירה פונקצית אמת n-מקומית: לכל ,l
g(l(p1),…,l(pn))=l(A)
דוגמה.
(p

∧ q ∧ ¬r)∨(¬p ∧ q ∧ r)

Слайд 21

משפת (שלמות פונקציונאלית). לכל פונקצית אמת קיימת נוסחה המגדירה אותה.
הוכחה. תהיה

f פונקצית אמת n-מקומית. נגדיר
Hf={(a1,a2,…,an)∈{F,T}n :f(a1,…,an)=T}
לכל x=(a1,a2,…,an) נשייך נוסחה
Ax = ř1∧ř2… ∧řn
כך ש: ři הוא ri אם ai=T, אחרת ři הוא ¬ri. אז פירוש l מספק את Ax אם"ם x=(l(r1),...,l(rn)) [?].
נגדיר Af= Ax1∨Ax2∨ … ∨Axk עבור כל xi מ- Hf.
אז, לכל פירוש l, l(Af)=T אם"ם קיים Hf ∈ x כך ש x=(l(r1),...,l(rn)) [?], ז"א f(l(r1),…,l(rn))=l(Af) .

Слайд 22

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

פונקצית אמת נקראת קבוצה שלמה.
P ↔ Q ≡ (P→Q) ∧ (Q→P)
P → Q ≡ ¬P ∨ Q P ∨ Q ≡ ¬P → Q
P ∨ Q ≡ ¬(¬P∧¬Q) P ∧ Q ≡ ¬(¬P∨¬Q)
מסקנה. {¬, ∨}, {¬, ∧}, {¬, →} הן קבוצות שלמות של קשרים. [נמק]

Слайд 23

קבוצות לא שלמות של קשרים
למה. {↔,∨,∧, →} היא קבוצה לא שלמה

של קשרים.
הוכחה. להבדיל מ-¬p, כל נוסחה הבנויה מ- {↔,∨,∧, →} היא אמיתית כאשר כל הפסוקים האטומיים שלה אמיתיים. [באינדוקציה על מספר הקשרים בנוסחה].
למה. {↔,¬} היא קבוצה לא שלמה של קשרים.
[להוכיח]

Слайд 24

קבוצות קשרים שלמות
NAND – "לא ו-.." - ↑
P↑Q מוגדרת ע"י

P↑Q ≡ ¬(P∧Q)
קל לראות ש-
P↑P ≡ ¬P
(P↑Q) ↑ (P↑Q) ≡ ~(P↑Q) ≡ P∧Q
(P↑P)↑(Q↑Q) ≡ P∨Q
לכן {↑} היא קבוצת קשרים שלמה.

Слайд 25

NOR – "לא או" - ↓
P↓Q מוגדר ע"י P↓Q ≡

¬(P∨Q)
מתקיים: P ↓ P ≡ ¬P
(P↓Q)↓(P↓Q) ≡ P∨Q
(P↓P)↓(Q↓Q) ≡ P∧Q
לכן {↓} היא קבוצת קשרים שלמה.

קבוצות קשרים שלמות

Слайд 26

שערים (gates)
שער NOT:
שער AND:
שער OR:

Слайд 27

רשת לתיאור הנוסחה: (a∨b)∧(¬a∨¬b)

Слайд 28

שערים נוספים
שער NAND:
שער NOR:
דוגמא:
a
b
a∨b

Слайд 29

צורות נורמאליות
אם p הוא פסוק אטומי, אז p ו-¬p הם ליטרלים.
הגדרה.

נוסחה בצורה דיסיונקטיבית נורמאלית (DNF) היא דיסיונקציה של קוניונקציות של ליטרלים.
דוגמא: (p∧¬q∧r)∨(r∧p) ∨ (r∧¬q∧¬p)
מסקנה 1. כל נוסחה שקולה לנוסחה בצורת DNF.
הוכחה. אם f היא פונקצית אמת המוגדרת ע"י נוסחה B , אז הנוסחה Af שבנינו בהוכחת משפת שלמות פונקציונאלי שקולה ל-B , והיא בצורת DNF.

Слайд 30

דואליות
הגדרה: תהי A נוסחה שמכילהT , ⊥, ∧, ∨, ו- ¬

בלבד.
נוסחה דואלית ל- A מתקבלת ממנה בהחלפת כל ∧ ב- ∨ וכל ∨ ב- ∧, כל T ב- ⊥ וכל ⊥ ב-T
למת עזר. השלילה של נוסחה שקולה לנוסחה דואלית שבה כל משתנה מוחלף בשלילה שלו. [למה?]
דוגמא: ¬((P∨Q)∧R) ≡ ¬(P∨Q)∨¬R ≡ (¬P∧¬Q)∨¬R

Слайд 31

צורות נורמליות - המשך
פסוקית (clause) היא דיסיונקציה של ליטרלים:
r∨¬q∨¬p
הגדרה. נוסחה

בצורה קוניונקטיבית נורמאלית (CNF) היא קוניונקציה של פסוקיות.
דוגמא: (p∨¬q∨r)∧(r∨p) ∧(r∨¬q∨¬p)
מסקנה 2. כל נוסחה שקולה לנוסחה בצורת CNF.
הוכחה. נניח ש- f היא פונקצית אמת המוגדרת ע"י נוסחה ¬B , ו- Af היא הנוסחה המקבילה ב- DNF. אז ¬Af שקולה ל-B, וניתן להפוך ¬Af לנוסחה דואלית בצורת CNF[?].

Слайд 32

CNF
A ≡ (p∨q) ∧(¬p∨¬q)
כל פסוקית מתאים לשורה עם ערך F בטבלת

אמת.
לכל משתנה p אנו רושמים p אם ערכו F ו- ¬p אם
ערכו T בשורה זו.

Слайд 33

אלגוריתמים לבניית DNF ו-CNF
סילוק → ו- ;↔
הכנסת שלילה פנימה (צורת (NNF
פריסה

של ∨ או ∧.
דוגמה. ((p ∧ q) ∨¬(q ∧ r)) → s
¬((p ∧ q) ∨¬(q ∧ r)) ∨ s
(¬(p ∧ q) ∧(q ∧ r)) ∨ s
((¬p ∨ ¬q) ∧(q ∧ r)) ∨ s
(¬p ∨ ¬q ∨ s) ∧((q ∧ r) ∨ s)
(¬p ∨ ¬q ∨ s) ∧(q ∨ s) ∧ (r ∨ s)

Слайд 34

פסוקיות הורן
פסוקית הורן (Horn clause) היא פסוקית שמכילה לא יותר מליטרל

חיובי אחד.
p∨¬q1∨...∨¬qn ( ≡ (q1∧... qn) → p )
¬q1∨...∨¬qn ( ≡ (q1∧... qn) → ⊥ )
p ( ≡ T → p )
נוסחת הורן היא קוניונקציה של פסוקיות הורן.

Слайд 35

אלגוריתם הכרעה לנוסחאות הורן
אלגוריתם HORN להכרעת ספיקות:
נסמן אטומים בנוסחת הורן לפי

כללים הבאים:
נסמן T אם הוא קיים בנוסחה.
אם יש פסוקית (Q1∧... ∧Qn) → P בנוסחה כך שכל Qi בו מסומן, נסמן גם P ונחזור ל-2, אחרת נעבור ל-3.
הנוסחה היא ספיקה אם ורק אם ⊥ לא מסומן.