מהי לוגיקה

1.

‫מהי לוגיקה?‬
‫• תורת ההיגיון‬
‫• תורת ההיסק מתארת טיעונים תקפים ‪ -‬טיעונים‬
‫ששומרים על אמיתות‪ .‬תקפות היא תכונה מבנית‬
‫(תחבירית) של טיעונים‬
‫• תנאיי‪-‬קדם ללוגיקה‪ :‬שפה בעלת תחביר‬
‫וסמנטיקה‪.‬‬
‫תחביר – מבנה של ביטוים בשפה‪.‬‬
‫סמנטיקה – פשר (משמעות) של הביטויים‪ ,‬הקשר‬
‫שבין השפה לבין מה שהיא מדברת עליו‪.‬‬

2.

‫לוגיקה במדעי המחשב‬
‫•‬
‫•‬
‫•‬
‫•‬
‫מחשב מחקה יכולת שכלית (היגיון)‬
‫תוכנית מחשב – סוג של הוכחה‪ .‬תורת‬
‫התכנות‪ -‬לוגיקה שימושית‪ .‬אימות תוכנה‪.‬‬
‫תכנות לוגי‪.‬‬
‫בינה מלאכותית‬

3.

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

4.

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

5.

‫קשרים לוגיים‬
‫•‬
‫•‬
‫•‬
‫•‬
‫•‬
‫שלילה (‪" : ¬P )negation‬לא ‪."P‬‬
‫קוניונקציה (‪ ,conjunction‬גימום) ‪ P" P Q:‬ו‪.“Q -‬‬
‫דיסיונקציה (‪ ,disjunction‬איווי) ‪ P” : P Q‬או ‪.“Q‬‬
‫אימפליקציה (‪ ,implication‬אימוז) ‪P→Q‬‬
‫"אם ‪ P‬אז ‪.“Q‬‬
‫‪:‬‬
‫שקילות (‪P↔Q )equivalence‬‬
‫"‪ P‬אם ורק אם ‪.“Q‬‬
‫‪:‬‬

6.

‫תחביר‬
‫הגדרה‪ :‬נוסחא נקראת בנויה היטב ( ‪well-formed‬‬
‫‪ )formula‬אם ניתן ליצור אותה לפי החוקים הבאים‪:‬‬
‫‪ .1‬כל פסוק אטומי‪ p,q,...‬הוא נוסחא בנויה היטב‪.‬‬
‫‪ .2‬קבוע ‪ ‬הוא נוסחא בנויה היטב‪.‬‬
‫‪ .3‬אם ‪ A‬ו‪ B -‬הן נוסחאות בנויות היטב‪ ,‬אז גם (‪(¬A‬‬
‫)‪ (A B), (A B), (A B), (A B‬הן נוסחאות‬
‫בנויות היטב‪.‬‬
‫‪ .4‬כל נוסחא בנויה היטב ניתן ליצור במספר סופי של‬
‫צעדים ע"י שימוש בחוקים ‪.1-3‬‬

7.

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

8.

‫אינדוקציה על נוסחאות‬
‫אם תכונה ‪ P‬נכונה לכל הפסוקים האטומיים‪ ,‬ומהנחה‬
‫ש‪ P-‬נכונה לנוסחאות ‪ A‬ו‪ B-‬נובע ש‪ P-‬נכונה ל‪-‬‬
‫(‪ ,(A B), (A B), (A B), (A B), (¬A‬אזי ‪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 .‬‬
‫‪P ¬P‬‬
‫‪T‬‬
‫‪F‬‬
‫‪F‬‬
‫‪T‬‬

11.

‫דיסיונקציה‬
‫‪ P Q‬שיקרי כאשר גם ‪P‬‬
‫וגם ‪ Q‬שיקרי‪ ,‬אחרת‬
‫אמיתי ‪:‬‬
‫קוניונקציה‬
‫‪ P Q‬אמיתי כאשר גם ‪P‬‬
‫וגם ‪ Q‬אמיתי‪ ,‬אחרת‬
‫שקרי‪:‬‬
‫‪P Q P Q‬‬
‫‪P Q P Q‬‬
‫‪F‬‬
‫‪F‬‬
‫‪T‬‬
‫‪T‬‬
‫‪F‬‬
‫‪F F‬‬
‫‪F‬‬
‫‪F T‬‬
‫‪F‬‬
‫‪T F‬‬
‫‪T‬‬
‫‪T T‬‬
‫‪F‬‬
‫‪T‬‬
‫‪T‬‬
‫‪T‬‬
‫‪F‬‬
‫‪T‬‬
‫‪F‬‬
‫‪T‬‬

12.

‫שקילות‬
‫‪ P↔Q‬אמיתי כאשר‬
‫ל‪ P -‬ול‪ Q -‬יש אותו‬
‫ערך אמת‪ ,‬ושקרי‬
‫אחרת‪:‬‬
‫‪P Q P↔Q‬‬
‫‪F F‬‬
‫‪T‬‬
‫‪F T‬‬
‫‪F‬‬
‫‪T F‬‬
‫‪F‬‬
‫‪T T‬‬
‫‪T‬‬
‫אימפליקציה‬
‫‪ P→Q‬שקרי כאשר ‪P‬‬
‫אמיתי ו‪ Q -‬שקרי‪,‬‬
‫אחרת אמיתי‪.‬‬
‫‪Q P→Q‬‬
‫‪P‬‬
‫‪F‬‬
‫‪T‬‬
‫‪F‬‬
‫‪T‬‬
‫‪F‬‬
‫‪F‬‬
‫‪T‬‬
‫‪T‬‬
‫‪T‬‬
‫‪T‬‬
‫‪F‬‬
‫‪T‬‬
‫אם ‪ ,1+1=3‬אז פריס היא‬
‫בירת צרפת‪.‬‬

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‬שורות‪.‬‬
‫‪p q ¬ p q‬‬
‫‪F F T F T F‬‬
‫‪F T T F T T‬‬
‫‪T F F T F F‬‬
‫‪T T F T T T‬‬
‫‪2 1 3 1‬‬

16.

‫טאוטולוגיות וסתירות‬
‫נוסחה המקבלת ערך אמת ‪ T‬לכל הצבה עבור המשתנים שלה‬
‫היא טאוטולוגיה‪.‬‬
‫נוסחה המקבלת ערך ‪ F‬לכל הצבה כזאת היא סתירה‪.‬‬
‫‪p p‬‬
‫‪p ¬p‬‬
‫‪¬p‬‬
‫‪p‬‬
‫‪T‬‬
‫‪F‬‬
‫‪T‬‬
‫‪F‬‬
‫‪T‬‬
‫‪F‬‬
‫‪F‬‬
‫‪T‬‬
‫ניתן להוכיח טאוטולוגיות וסתירות בשיטת השלילה‪.‬‬
‫דוגמא‪:‬‬
‫)‪(A B) →(¬A B‬‬

17.

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

18.

‫טבלת אמת ל‪¬)p q) (¬p ¬q( -‬‬
‫)‪q‬‬
‫¬‬
‫‪ ‬‬
‫‪p‬‬
‫¬( ‪q) ‬‬
‫‪ ‬‬
‫‪(p‬‬
‫¬‬
‫‪q‬‬
‫‪p‬‬
‫‪F‬‬
‫‪T‬‬
‫‪F‬‬
‫‪T‬‬
‫‪1‬‬
‫‪T‬‬
‫‪F‬‬
‫‪T‬‬
‫‪F‬‬
‫‪2‬‬
‫‪T‬‬
‫‪T‬‬
‫‪T‬‬
‫‪F‬‬
‫‪3‬‬
‫‪F‬‬
‫‪F‬‬
‫‪T‬‬
‫‪T‬‬
‫‪1‬‬
‫‪F‬‬
‫‪T‬‬
‫‪F‬‬
‫‪T‬‬
‫‪1‬‬
‫‪F‬‬
‫‪F‬‬
‫‪F‬‬
‫‪T‬‬
‫‪2‬‬
‫‪F‬‬
‫‪F‬‬
‫‪T‬‬
‫‪T‬‬
‫‪1‬‬
‫‪T‬‬
‫‪T‬‬
‫‪T‬‬
‫‪F‬‬
‫‪3‬‬
‫‪F‬‬
‫‪T‬‬
‫‪F‬‬
‫‪T‬‬
‫‪F‬‬
‫‪F‬‬
‫‪T‬‬
‫‪T‬‬
‫‪T‬‬
‫‪T‬‬
‫‪F‬‬
‫‪F‬‬
‫‪2‬‬
‫‪T‬‬
‫‪T‬‬
‫‪T‬‬
‫‪T‬‬
‫‪4‬‬
‫תוך שימוש בשקילויות יסודיות ניתן להוכיח שקילויות‬
‫חדשות בלי להשתמש בטבלאות אמת‪.‬‬

19.

‫שקילויות יסודיות‬
P P P
P P P
(P Q) R P (Q R)
(P Q) R P (Q R)
P Q Q P
P Q Q P
P (Q R)
(P Q) (P R)
P P
P (Q R) (P Q) (P R)
P T T
P
P ¬P T
P ¬P F
P (P Q) P
P (P Q) P
¬(P Q) ¬P ¬Q
¬(P Q) ¬P ¬Q
P T P
¬¬P P

20.

‫שלמות פונקציונאלית‬
p
q
r
A
T
T
T
F
T
T
F
T
T
F
T
F
T
F
F
F
F
T
T
T
F
T
F
F
F
F
T
F
F
F
F
F
‫ מגדירה‬A(p1,…,pn) ‫כל נוסחה‬
,l ‫ לכל‬:‫מקומית‬-n ‫פונקצית אמת‬
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‬נשייך נוסחה‬
‫‪ř1 ř2… řn = Ax‬‬
‫כך ש‪ ři :‬הוא ‪ ri‬אם ‪ ,T=ai‬אחרת ‪ ři‬הוא ‪ .¬ri‬אז‬
‫פירוש ‪ l‬מספק את ‪ Ax‬אם"ם ))‪.]?[ x=(l(r1),...,l(rn‬‬
‫נגדיר ‪ Af= Ax1 Ax2 … Axk‬עבור כל ‪ xi‬מ‪.Hf -‬‬
‫אז‪ ,‬לכל פירוש ‪ l(Af)=T ,l‬אם"ם קיים ‪ x Hf‬כך ש‬
‫))‪ ,]?[ 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.

‫קבוצות קשרים שלמות‬
P
F
F
T
T
Q
F
T
F
T
P Q
T
T
T
F
- "..-‫ – "לא ו‬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.

‫קבוצות קשרים שלמות‬
P
F
F
T
T
Q
F
T
F
T
P Q
T
F
F
F
- "‫ – "לא או‬NOR
P Q ¬)P Q) ‫ מוגדר ע"י‬P Q
P P ¬P :‫מתקיים‬
(P Q) (P Q) P Q
(P P) (Q Q) P Q
.‫{ היא קבוצת קשרים שלמה‬ } ‫לכן‬

26.

)gates( ‫שערים‬
a
a
b
¬a
:NOT ‫שער‬
:AND ‫שער‬
a b
:OR ‫שער‬
a
b
a b

27.

‫רשת לתיאור הנוסחה‪(a b) (¬a ¬b( :‬‬
‫‪a‬‬
‫‪b‬‬
‫‪a‬‬
‫‪b‬‬

28.

‫שערים נוספים‬
a
b
¬)a b)=¬a ¬b
a
b
¬)a b)=¬a ¬b
: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) (P (¬Q ¬S(( ¬)P Q) (P (¬Q ¬S‬‬
‫למת עזר‪ .‬השלילה של נוסחה שקולה לנוסחה דואלית שבה‬
‫כל משתנה מוחלף בשלילה שלו‪[ .‬למה?]‬
‫דוגמא‪¬))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‬‬
‫‪p q‬‬
‫‪¬p ¬q‬‬
‫‪A‬‬
‫‪F‬‬
‫‪T‬‬
‫‪T‬‬
‫‪F‬‬
‫‪q‬‬
‫‪F‬‬
‫‪T‬‬
‫‪F‬‬
‫‪T‬‬
‫‪p‬‬
‫‪F‬‬
‫‪F‬‬
‫‪T‬‬
‫‪T‬‬
‫)‪A (p q) (¬p ¬q‬‬
‫כל פסוקית מתאים לשורה עם ערך ‪ F‬בטבלת אמת‪.‬‬
‫לכל משתנה ‪ p‬אנו רושמים ‪ p‬אם ערכו ‪ F‬ו‪ ¬p -‬אם‬
‫ערכו ‪ T‬בשורה זו‪.‬‬

33.

CNF-‫ ו‬DNF ‫אלגוריתמים לבניית‬
; -‫ ו‬ ‫• סילוק‬
(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‬להכרעת ספיקות‪:‬‬
‫נסמן אטומים בנוסחת הורן לפי כללים הבאים‪:‬‬
‫‪ .1‬נסמן ‪ T‬אם הוא קיים בנוסחה‪.‬‬
‫‪ .2‬אם יש פסוקית ‪ (Q1 ... Qn) P‬בנוסחה כך‬
‫שכל ‪ Qi‬בו מסומן‪ ,‬נסמן גם ‪ P‬ונחזור ל‪ ,2-‬אחרת‬
‫נעבור ל‪.3-‬‬
‫‪ .3‬הנוסחה היא ספיקה אם ורק אם ‪ ‬לא מסומן‪.‬‬

36.

‫משפט‪ .‬אלגוריתם ‪ HORN‬מכריע בעיית ספיקות לנוסחאות‬
‫הורן‪.‬‬
‫הוכחה‪ .‬אם בנוסחת הורן ‪ A‬יש ‪ n‬אטומים‪ ,‬האלגוריתם מסיים‬
‫בלא יותר מ‪ (n+1)-‬צעדים‪ .‬נוכיח‪:‬‬
‫כל ‪ P‬מסומן הוא אמיתי בכל מודל של ‪ A‬באינדוקציה על מספר‬
‫הצעדים של האלגוריתם‪ .‬בסיס (צעד ‪ T :)1‬אמיתי בכל מודל‪.‬‬
‫אם בפסוקית ‪ (Q1 ... Qn) P‬כל ‪ Qi‬מסומן‪ ,‬אז גם הפסוקית‬
‫וגם כל ‪( Qi‬בהנחת אינדוקציה) חייבים להיות אמיתיים בכל‬
‫מודל של ‪ .A‬לכן גם ‪ P‬חייב להיות אמיתי בכל מודל של ‪.]?[A‬‬
‫(א) אם ‪ ‬מסומן‪ A ,‬לא ספיקה‪ ,‬כי ‪ ‬לא יכול להיות אמיתי‪.‬‬
‫(ב) אם ‪ ‬לא מסומן‪ ,‬נגדיר פירוש ‪ l‬שבו האטומים המסומנים‪,‬‬
‫ורק הם‪ ,‬אמיתיים‪ .‬נניח ש‪ l-‬הוא לא מודל של ‪ .A‬אז קיימת‬
‫פסוקית ‪ (Q1 ... Qn) P‬של ‪ A‬שהיא שקרית ב‪.l -‬אבל זה‬
‫אפשרי רק כאשר כל ‪ Qi‬אמיתי (מסומן) ו‪ P-‬שקרי (לא מסומן)‬
‫– סתירה[?]‪ .‬לכן ‪ l‬הוא מודל של ‪ A‬ומכאן ‪ A‬ספיקה‪.‬‬