קורס-עזר – לוגיקה למדעי המחשב


לוגיקה למדעי המחשב


02על הנושא

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


03מהנושאים הנלמדים בקורס

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

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

  1. מהי טענה.
  2. שפה טבעית ושפה פורמלית. מבנה שפת תחשיב הפסוקים. הגדרת נב"כ (wff). 
  3. הצרנות.
  4. סמנטיקה
    א. מצב-עניינים או מודל - טבלאות אמת.
    ב. טענה ספיקה.
    ג. טענות טאוטולוגיות, קונטינגנטיות וסתירתיות.
    ד. תקפות ובטלות.
    ה. בדיקת סוגי טענות הוכחת שקילויות לוגיות באמצעות טבלאות אמת.
    ו.  עצי-אמת (מתן ערכים).
  5. צורה דיסיונקטיבית נורמלית (DNF) וצורה קוניונקטיבית נורמלית (CNF).
  6. שלמות פונקציונאלית - המשפט, קבוצות קשרים שלמות, הוכחות.
  7. משפט הקריאה היחידה.
  8. אינדוקציה מבנית.
  9. תחביר - דדוקציה טבעית
                דדוקציה ע"פ הילרט (HPC)
  10. פסוקיות הורן ואלגוריתם הכרעת ספקות.
  11. משפטי השלמות והנאותות.
  12. משפט הקומפקטיות.

      ג. תחשיב היחסים (הפרדיקטים)

  1. אי-המספיקות של תחשיב הפסוקים והצורך בתחשיב היחסים.
  2. מבנה שפת תחשיב היחסים (משתנים ושמות-עצם, כמתים, פרדיקטים). הגדרת נב"כ. הצבות.
  3. הצרנות.
  4. סמנטיקה - מודל והשמות.
                    ספיקות.
                    תקפות (גרירה סמנטית) ובטלות.
                    צורה פרנקס (תחילת) נורמלית.
  5. מודל של הרברנד.
  6. צורת סקולם, משפט ארברן.
  7. משפט הקומפקטיות.
  8. תחביר - דדוקציה טבעית
                שיטת הרזולוציה 
                    

הכנה לבגרות במתמטיקה אפשרויות הלימוד

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

 


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