לוגיקה למדעי המחשב; כרך ב'

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

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

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