מהי לוגיקה презентация

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

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

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

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

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

תחביר הגדרה: נוסחא נקראת בנויה היטב (well-formed formula) אם ניתן ליצור אותה לפי החוקים הבאים: כל פסוק אטומי p,q,... הוא נוסחא בנויה היטב. קבוע  הוא נוסחא בנויה היטב. 3. אם A ו- B הן נוסחאות בנויות היטב, אז גם (¬A) (AB), (A  B), (A  B), (A  B) הן נוסחאות בנויות היטב. 4. כל נוסחא בנויה היטב ניתן ליצור במספר סופי של צעדים ע"י שימוש בחוקים -31.

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

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

הצרנה זהו מקס או שההוא מוריץ ואני ליצן: p  q  r אני אגיע הביתה ואביא תותים אם לא ירד גשם. אם לא יובל ולא איל יעברו את הבחינה, גם חגי לא יעבור. לא כולם (מהשלושה) יכשלו.

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

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

שקילות אימפליקציה P→Q שקרי כאשר P אמיתי ו- Q שקרי, אחרת אמיתי. אם 1+1=3, אז פריס היא בירת צרפת.

יחס ספיקות הגדרה. (הרחבה של פירוש לפסוקים מורכבים) 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 עובדה. ערך האמת של פסוק מורכב היא פונקציה של ערכי האמת של הפסוקים אטומיים שלו (קריאה יחידה!).

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

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

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

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

טבלת אמת ל- ¬(p  q)(¬p  ¬q) טבלת אמת ל- ¬(p  q)(¬p  ¬q) תוך שימוש בשקילויות יסודיות ניתן להוכיח שקילויות חדשות בלי להשתמש בטבלאות אמת.

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

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

משפת (שלמות פונקציונאלית). לכל פונקצית אמת קיימת נוסחה המגדירה אותה. משפת (שלמות פונקציונאלית). לכל פונקצית אמת קיימת נוסחה המגדירה אותה. הוכחה. תהיה 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) .

קבוצות שלמות של קשרים הגדרה: קבוצה של קשרים שבאמצעותם ניתן לתאר כל פונקצית אמת נקראת קבוצה שלמה. P  Q  (PQ)  (QP) P  Q  ¬P  Q P  Q  ¬P  Q P  Q  ¬(¬P¬Q) P  Q  ¬(¬P¬Q) מסקנה. {¬, }, {¬, }, {¬, } הן קבוצות שלמות של קשרים. [נמק]

קבוצות לא שלמות של קשרים למה. {,,, } היא קבוצה לא שלמה של קשרים. הוכחה. להבדיל מ-¬p, כל נוסחה הבנויה מ- {,,, } היא אמיתית כאשר כל הפסוקים האטומיים שלה אמיתיים. [באינדוקציה על מספר הקשרים בנוסחה]. למה. {,¬} היא קבוצה לא שלמה של קשרים. [להוכיח]

קבוצות קשרים שלמות NAND – "לא ו-.." -  PQ מוגדרת ע"י PQ  ¬(PQ) קל לראות ש- PP  ¬P (PQ)  (PQ)  ~(PQ)  PQ (PP)(QQ)  PQ לכן {} היא קבוצת קשרים שלמה.

קבוצות קשרים שלמות NOR – "לא או" -  PQ מוגדר ע"י PQ  ¬(PQ) מתקיים: P  P  ¬P (PQ)(PQ)  PQ (PP)(QQ)  PQ לכן {} היא קבוצת קשרים שלמה.

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

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

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

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

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

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

CNF A  (pq) (¬p¬q) כל פסוקית מתאים לשורה עם ערך F בטבלת אמת. לכל משתנה p אנו רושמים p אם ערכו F ו- ¬p אם ערכו T בשורה זו.

אלגוריתמים לבניית 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)

פסוקיות הורן פסוקית הורן (Horn clause) היא פסוקית שמכילה לא יותר מליטרל חיובי אחד. p¬q1...¬qn (  (q1... qn)  p ) ¬q1...¬qn (  (q1... qn)   ) p (  T  p ) נוסחת הורן היא קוניונקציה של פסוקיות הורן.

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

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