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

תואר: בוגר

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

סמסטר: סמסטר א'

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

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

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

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

שעות קבלה של רכז הקורס: ימי שישי, בזום, בתאום מראש

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

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

מטרות הקורס:

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

דרישות נוכחות (%):

שיטת ההוראה בקורס:

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

חומר חובה לקריאה:
הירשפלד יורם, לוגיקה למדעי המחשב, האוניברסיטה הפתוחה
Enderton Herbert B., Elements of Set Theory, 1st Edition
Enderton Herbert B., A Mathematical Introduction to Logic, 3nd Edition

חומר לקריאה נוספת:

מרכיבי הציון הסופי :
מבחן מסכם בכתב/בחינה בעל פה % 100

מידע נוסף / הערות:
ציון: ציון הבחינה + נקודות בונוס על הגשת תרגילים + נקודות בונוס על נוכחות. בחינה אמריקאית הכוללת 25 שאלות (ערך כל שאלה 4 נקודות). בנוסף, יוכלו התלמידים לצבור עד 10 נקודות בונוס, מעל ומעבר לציון הבחינה. במהלך הקורס יקבלו התלמידים שישה תרגילי בית ויוכלו להגיש שלושה מהם לכל היותר. תרומת כל תרגיל לציון הסופי תיקבע לפי הנוסחה הבאה: ציון התרגיל*0.01*3. כך אפשר יהיה לקבל לכל היותר 9 נקודות בונוס עבור הגשת תרגילים. יתר על כן, מי שיהיה נוכח ב- 13/12/11 הרצאות יקבל בהתאמה 3/2/1 נקודות בונוס עבור הנוכחות. כאמור, סה"כ נקודות הבונוס לא יעלה על 10.