נקודות זכות באוניברסיטה העברית: 2

תואר: מוסמך

היחידה האקדמית שאחראית על הקורס: פילוסופיה

סמסטר: סמסטר ב'

שפת ההוראה: עברית

קמפוס: הר הצופים

מורה אחראי על הקורס (רכז): ד"ר אביב הופמן

דוא"ל של המורה האחראי על הקורס: selfidentical@yahoo.com

שעות קבלה של רכז הקורס: יום ד', 17:00 - 16:00 (בתיאום מראש)

מורי הקורס:
ד"ר אביב הופמן

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

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

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

דרישות נוכחות (%):
100 (איני אוכף את הדרישה)

שיטת ההוראה בקורס: הרצאה והגשת תרגילים

רשימת נושאים / תכנית הלימודים בקורס:
שיעור 1: מושגים בתורת הקבוצות – חלק א'. קבוצות: איברים ותתי-קבוצות; עקרון האקסטנציונליות; עקרון הקומפרהנציה; איחוד; חיתוך; הפרש; משלים; פרדוקס ראסל.
שיעור 2: מושגים בתורת הקבוצות – חלק ב'. זוגות סדורים; מכפלה קרטזית; יחס; פונקציה (חלקית, חד-חד ערכית, על); קבוצות שקולות (עוצמה); יחס שקילות; מחלקת שקילות; קבוצות סופיות ואינסופיות; קבוצה בת-מניה; קבוצת חזקה; משפט קנטור.
שיעור 3: מערכות היסק. שפה פורמאלית; שפת גל-חץ (נב"כ בשפה); קבוצה אינדוקטיבית; סוגריים; מערכת היסק (אקסיומות סכמטיות, כללי היסק); הוכחה; הוכחה מהנחות; תכונות יסוד של הוכחות (רישא, שרשור, הכלה, משפט עזר, סופיות); משפט הדדוקציה; 'טרנזיטיביות' החץ.
שיעור 4: הוכחה בדרך השלילה ומשפט הנאותות. עקביות; למת הסופיות; משפט ההוכחה בדרך השלילה; נביעה לוגית; משפט הנאותות.
שיעור 5: שלמות תחשיב הפסוקים – חלק א'. הוכחה באינדוקציה על מבנה הפסוק; קבוצת נב"כים שלמה; יחידות המודל; השלמת קבוצה עקבית; משפט השלמות; משפט הקומפקטיות.
שיעור 6: שפות שמות עצם. הגדרת המושג "שם עצם"; עומק המבנה של שם עצם; הגדרה באינדוקציה מבנית של פונקציה מקבוצת הנוסחאות בשפה.
שיעור 7: לוקאליות ההגדרה. הצבה (והצבה קבילה); מבנה בשפה; השמה למשתנים (והשמה רלבנטית); ערך של שם-עצם בהשמה רלבנטית; לוקליות ההגדרה.
שיעור 8: תחביר שפת תחשיב הפרדיקטים. הנוסחאות בשפה; הגדרה באינדוקציה מבנית; מופע קשור ומופע חופשי של משתנה; הצבה (בתחשיב הפרדיקטים).
שיעור 9: סמנטיקה של שפת תחשיב הפרדיקטים. מבנה; פירוש סימן השוויון; השמה רלבנטית לנוסחה; פירוש של נוסחה בהשמה רלבנטית; פסוק; תיקון של השמה; ערך אמת של נוסחה בהשמה רלבנטית במבנה; לוקאליות הגדרת הפירוש.
שיעור 10: אמת לוגית ושקילות לוגית. שקילות לוגית היא יחס קונגרואנציה; האמיתות הלוגיות של השוויון; משפט רענון המשתנים; גרירת כמתים לתחילת הנוסחה; צורה פרנקסית (נורמאלית).
שיעור 11: המערכת הדדוקטיבית. הוכחה; אקסיומות טאוטולוגיות; אקסיומות כימות; אקסיומות השוויון; כללי היסק; משפט הנאותות; משפט הדדוקציה.
שיעור 12: הוכחת משפט השלמות – חלק א'. עקביות; משפט ההוכחה בדרך השלילה; כמתים, שמות קבועים; קבוצה שלמה וקבוצה מקסימאלית; קבוצת הנקין ומשפט השלמות; חלק ראשון של הוכחת משפט השלמות בלוגיקה בלי שוויון: הרחבת קבוצת פסוקים עקבית לקבוצת הנקין.
שיעור 13: הוכחת משפט השלמות – חלק ב'. עומק המבנה של נוסחה; הוכחה באינדוקציה על עומק המבנה של נוסחה; חלק שני של הוכחת משפט השלמות בלוגיקה בלי שוויון: הוכחה שלכל קבוצת הנקין יש מודל; מבנה ותת-מבנה; סגור של קבוצה תחת משפחה של פונקציות.
שיעור 14: הוכחת משפט השלמות בלוגיקה עם שוויון. תת-מבנה מינימאלי; הומומורפיזם, מונומורפיזם ואיזומורפיזם; קונגרואנציה ומבנה המנה; קונגרואנציה ביחס למשפחת יחסים ופונקציות; משפט מבנה המנה; משפט השלמות בלוגיקה עם שוויון; משפט הקומפקטיות; משפט לוונהיים-סקולם.

חומר חובה לקריאה:
אין

חומר לקריאה נוספת:
לוגיקה למדעי המחשב, יורם הירשפלד, האוניברסיטה הפתוחה

Herbert B. Enderton, Elements of Set Theory 1st Edition;

Herbert B. Enderton, A Mathematical Introduction to Logic 3nd Edition;

Hunter Geoffrey, Metalogic, Macmillan

Thomason R.H., Symbolic Logic: An Introduction, Macmillan

Hamilton A.G., Logic for Mathematicians, Cambridge University Press

הערכת הקורס - הרכב הציון הסופי :
מבחן מסכם בכתב/בחינה בעל פה 100 %
הרצאה0 %
השתתפות 0 %
הגשת עבודה 0 %
הגשת תרגילים 0 %
הגשת דו"חות 0 %
פרויקט מחקר 0 %
בחנים 0 %
אחר 0 %
ראו הערה בהמשך

מידע נוסף / הערות:
אם לא תהייה אפשרות לקיים בחינה במתכונת הרגילה, אז תתקיים בקורס בחינת בית. בחינת הבית תיראה כמו התרגילים שהסטודנטים מקבלים במהלך הקורס, אך יהיו בה יותר שאלות. הסטודנטים יוכלו, למשל, לענות על 10 שאלות מתוך 12. מועד הגשת הבחינות יהיה כמה ימים לאחר שהסטודנטים יקבלו אותן. בין אם תהיה בחינה אמריקאית בכיתה ובין אם בחינת בית, תרומת התרגילים לציון הסופי תישאר כפי שכבר קבעתי (והודעתי לסטודנטים): הציון על כל תרגיל יוסיף נקודות לציון הסופי, לפי הנוסחה: ציון*0.01*5 (עד 20 נקודות).