20283 מתמטיקה דיסקרטית: תורת הקבוצות, קומבינטוריקה ולוגיקה
20283 מתמטיקה דיסקרטית:
תורת הקבוצות, קומבינטוריקה ולוגיקה1
4 נקודות זכות ברמה רגילה
שיוך: מדעים / מתמטיקה
ידע קודם מומלץ: הקורס אשנב למתמטיקה.
פיתוח הקורס: פרופ' אברהם גינזבורג (ריכוז הפיתוח), שמואל ברגר, איתי הראבן (כתיבה); ענת לרנר, טלי צורף-עילם, יוסי קאופמן; אורה מאור, תלמה מוקדי (עריכה)
יועצים: פרופ' מרצל הרצוג, פרופ' שלמה וינר, פרופ' עמירם יהודאי, פרופ' אלי לוין, ד"ר לאוניד גרינבלט, ד"ר ורדה ליברמן
מטרת הקורס היא ללמד מושגים, תוצאות ודרכי עבודה בנושאים מתמטיים המהווים כלים חשובים לטיפול ביסודות התאורטיים של מדעי המחשב ולתרום לפיתוח התחכום המתמטי של הסטודנט.
נושאי הלימוד
תורת הקבוצות – קבוצה, איבר, שוויון והכלה בין קבוצות. פעולות בין קבוצות. קבוצת החזקה. עצמה. מכפלה קרטזית. יחס (רלציה). כפל יחסים. יחס הפוך. יחס רפלקסיבי, סימטרי, טרנזיטיבי. סגור של יחס לגבי תכונה. יחס שקילות. מחלקות שקילות. קבוצות מנה. פונקציות. פונקציות על, פונקציות חד-חד-ערכיות. סדר חלקי ומלא. אינדוקציה. קבוצות בנות מנייה. עצמת הרצף. משפט קנטור-שרדר-ברנשטיין. חיבור, כפל וחזקה של עצמות. משפט קנטור.
קומבינטוריקה – עקרונות החיבור והכפל. תמורות, צירופים וחליפות עם חזרות ובלי חזרות. הבינום של ניוטון. זהויות במקדמים בינומיים. עקרון ההכלה וההפרדה. פונקציית אוילר. אי-סדר מלא. עקרון שובך היונים. יחסי נסיגה, פתרון יחסי נסיגה לינאריים. פונקציות יוצרות.
לוגיקה – תחשיב הפסוקים: תחביר וסמנטיקה – פסוקים; קשרים; טבלאות אמת; טאוטולוגיות וסתירות; קבוצות שלמות של קשרים; צורות נורמליות; מודלים. תורת ההיסק2 – מערכות היסק והוכחות. מבוא לתחשיב היחסים: תחביר – כמתים, שמות עצם, סימני יחסים ונוסחאות; סמנטיקה – אינטרפרטציות, אמיתות במבנה ואמיתות לוגית.
1 החל מסמסטר ב2011 מתוכננת הפסקת ההוראה של קורס זה. יחליף אותו הקורס מתמטיקה בדידה: תורת הקבוצות, קומבינטוריקה ותורת הגרפים (20476). להשלכות על צבירת נ"ז בשל חפיפה עם קורס(ים) אחר(ים), ראו טבלת קורסים חופפים.
2 נלמד בתמציתיות.