מכסחי הכמתים

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

לוגיקה מסדר ראשון – כמה תוצאות של משפט השלמות

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

משפט השלמות של גדל, ההוכחה (חלק א')

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

מערכת הוכחה ללוגיקה מסדר ראשון

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

לוגיקה מסדר ראשון

אם נרצה לייחס את המצאת הלוגיקה המתמטית המודרנית לאדם יחיד, זה בוודאי יהיה המתמטיקאי הגרמני גוטלוב פרגה, ובפרט לספרו מ-1879, "Begriffsschrift" (אפילו לא אנסה להעמיד פנים שאני יכול לתרגם). בספר הזה פרגה המציא את מה שבימינו הוא הלחם והחמאה של … להמשיך לקרוא