תחשיב אינדקסים
תחשיב האינדקסים היא שיטה למציאת "לוגריתם בדידי". לוגריתם בדידי אומר כמה פעמים מרימים את המספר α בחזקה כדי לקבל את β. חבורה ציקלית היא קבוצה שבה אלמנט אחד מייצר את כל שאר האיברים על ידי חזקות. המהלך קצר: בוחרים קבוצה קטנה של "גורמי בסיס". אלה הם מספרים קטנים שמשמשים כחלקים לבניית מספרים אחרים. מייצ...
תחשיב הפסוקים
תחשיב פסוקים הוא דרך רשמית לבדוק טענות אמיתיות או שקריות. המערכת מסתכלת רק על "אמת" ו"שקר", לא על התוכן. אם אומרים: "אם חרק הוא נמלה אז הוא חי בתל" ו"החרק הוא נמלה", אז המסקנה היא שהוא חי בתל. זהו סוג של חשיבה לוגית פשוטה. משנים משפטים לאותיות קבועות. כל אות מייצגת טענה אחת. קשרים חשובים: - שלילה...
תחשיב למדא
תחשיב למדא (Lambda calculus) הוא דרך לכתוב פונקציות בלי שם. פונקציה היא חוק שאומר מה קורה עם קלט. כותבים פונקציה כך: λx.M. הכוונה: קח x ועשה M. הסימן λ קורא לו "למדה". ביטוי למדא עשוי ממשפטים קטנים שמתחברים. משתנה שהוא לא תחת λ נקרא חופשי. ביטוי ללא משתנים חופשיים נקרא סגור. - אלפא: מותר לשנו...
פסוק (לוגיקה)
פסוק הוא משפט שלם. משפט זה יכול להיות אמת או שקר. (אמת - משהו שנכון; שקר - משהו שלא נכון.) פסוק חיווי אומר טענה. (טענה - משהו שאפשר לבדוק אם נכון או לא.) דוגמה פשוטה: "יורד גשם". גם משפטים דמיוניים כמו "יש חד־קרן על צדק" הם פסוקים כי אפשר לדמיין אם הם נכונים או לא. בספרים של לוגיקה אומרים: נוסחה ב...
לוגיקה מתמטית
לוגיקה מתמטית בוחנת איך מראים שמשהו נכון. מערכת פורמלית היא שפה עם סימנים וכללים ברורים. כדי לבדוק משפטים, מתרגמים אותם לשפה מדויקת. יש שתי דרכים חשובות: תחשיב הפסוקים (שמביא בחשבון אם טענות הן אמיתיות או לא) ותחשיב הפרדיקטים (שמדבר על פריטים ותכונות שלהם). הוכחה מתחילה מאקסיומות. אקסיומה היא כלל ...
אלונזו צ'רץ'
אלונזו צ'רץ' (Alonzo Church; 14 ביוני 1903, 11 באוגוסט 1995) היה מתמטיקאי ולוגיקן. נולד בוושינגטון די.סי. והלך ללמוד בפרינסטון. הוא היה פרופסור שם, ואז לימד גם ב-UCLA. הוא פיתח את תחשיב למדא. תחשיב למדא הוא דרך להסביר מה מחשבים יכולים לחשב, בעזרת פונקציות (מה שהן חישובים קטנים). ב-1936 הראה צ'רץ...
חישוביות
תורת החישוביות עוסקת במה מחשבים ו"דגמים" דמיוניים יכולים לחשב. דגם חשוב נקרא מכונת טיורינג. זו דמות דמיונית של מחשב. השאלה הגדולה היא: מה אפשר לחשב ומה לא. יש בעיה שנקראת בעיית העצירה. משמעותה: אי אפשר תמיד לדעת אם תוכנית תעצור או תרוץ לנצח. בתחילת המאה ה-20 חוקרים רצו לדעת מהי דרך פשוטה לפתור בע...
כמת
כמת הוא סימן שאומר על מי מדברים. יש שני כמתים חשובים: "לכל" ו"קיים". "לכל" אומר את זה על כולם. "קיים" אומר שיש לפחות אחד כזה. יש שפה לוגית פשוטה שמחברת משפטים עם מילים כמו "ו", "או" ו"לא". אבל כדי לומר דברים על כל הפריטים או על כמה מהם מוסיפים את המילים "לכל" ו"קיים". למשל "לכל חתול יש זנב" אומר שז...
סתירה (לוגיקה)
סתירה היא משפט שאי אפשר שיהיה נכון אף פעם. היא בנויה משני חלקים שסותרים זה את זה. "סותרים" אומרים שהם הפוכים ולא יכולים להיות אמיתיים יחד. דוגמה פשוטה: להגיד גם "אני בירושלים" וגם "אני לא בירושלים". משתמשים בסתירה כדי להראות שטענה לא נכונה. אם הנחה מובילה לסתירה, אז היא שגויה. ההיפך של סתירה נקר...
אלגברת בנך
אלגברת בנך היא מקום מתמטי שבו יש חיבור וכפל, ויש דרך למדוד גודל שנקראת נורמה. נורמה = מדד לגודל של איברים. מספרים ממשיים וכולי הם דוגמה פשוטה. גם המספרים המרוכבים נכנסים כאן. מטריצות (טבלאות של מספרים) הן דוגמה נוספת. קבוצת כל הפונקציות הרציפות על מרחב קומפקטי גם היא אלגברה כזו. לכל איבר אפשר לה...
משפט הקומפקטיות
משפט הקומפקטיות אומר שאם כל קבוצה קטנה של משפטים מתקיימת, גם כל הקבוצה כולה יכולה להתקיים. מודל הוא מקום שבו המשפטים נכונים.\n\n= הוכחות למשפט =\nיש כמה דרכים להוכיח את המשפט. אחת מהן משתמשת במשפט השלמות של גדל. המשפט הזה מחבר בין "אין סתירה" לבין "יש מודל". דרך אחרת היא טופולוגית. שם מסתכלים על מרח...
טאוטולוגיה (לוגיקה)
טאוטולוגיה היא משפט שתמיד נכון. תמיד נכון פירושו: לא משנה מה קורה, הוא נכון. סתירה היא ההפך. סתירה תמיד שקר. דוגמה פשוטה: או שכל הבתים לבנים, או שיש לפחות בית שאינו לבן. תמיד אחד מהשניים נכון. גם אם אין בתים בכלל, אומרים ש"כל הבתים לבנים" נכון במקרה כזה. פילוסוף בשם לודוויג ויטגנשטיין כתב שטאוטול...
לוגיקה
לוגיקה היא חקר איך לחשוב נכון. היא בודקת מתי מסקנה נובעת מהנחות. ביוון העתיקה חשבו על טיעונים. אפלטון שאל שאלות כדי לבדוק עקביות. אריסטו ארגן שיטות לקשר בין משפטים. הוא המציא סילוגיזם ".סילוגיזם" זה טיעון עם שתי הנחות ומסקנה. אריסטו קבע כללים חשובים: # חוק אי-הסתירה: דבר לא יכול להיות נכון ושקרי ב...
תזת צ'רץ'-טיורינג
תזת צ'רץ'-טיורינג הוצעה על ידי אלן טיורינג ואלונזו צ'רץ' בשנות ה־30. היא אומרת: כל חישוב הגיוני אפשר לעשות עם מכונת טיורינג. מכונת טיורינג היא מכונה מדומיינת. היא קוראת וכותבת סימנים על סרט, בצעדים פשוטים. יש גרסאות שונות של התזה. גרסה חזקה מדברת על זמן ומשאבים. גרסה פיזיקלית אומרת שכל דבר שמערכת פ...
גוטלוב פרגה
באד קליינן, מקלנבורג-שוורין פרידריך פרגה (1848, 1925) היה מדען גרמני חשוב. הוא עבד על מתמטיקה ולוגיקה. לוגיקה, חוקי המחשבה. פרגה נולד בוויסמר. הוא למד באוניברסיטאות יינה וגטינגן. קיבל דוקטורט ועבד כפרופסור במתמטיקה. בסוף חייו הוא כתב דעות פוגעניות נגד קבוצות אחרות. פרגה מת ב-1925. פרגה שינה א...
סילוגיזם היפותטי
זהו דגם של טיעון שבו דברים מתחברים לפי צורה פשוטה. אם א' גורר ב'. אם ב' גורר ג'. אז א' גורר ג'. דוגמה: אם אני לא אתעורר, לא אגיע לעבודה. אם לא אגיע לעבודה, לא אקבל משכורת. לכן לא להתעורר אומר גם לא לקבל משכורת. 'היסק תקף' (פירוש: מסקנה נכונה לפי צורת הטיעון) אומר שהקשר בין הטענות נכון לפי המבנה....
טבלת אמת
טבלת אמת היא טבלה שמראה מה קורה למשפטים לוגיים כשהם אמיתים או שקריים. אמת פירושו שמשהו נכון. שקר פירושו שמשהו לא נכון. קשרים לוגיים הם כללים שמקשרים משפטים. שלילה אומרת להפוך אמת לשקר ושקר לאמת. "וגם" אומר ששני המשפטים צריכים להיות אמת. "או" אומר שאחד מהם מספיק. כל משפט בסיסי יכול להיות רק אמת או...
פילוסופיה של הלשון
פילוסופיה של השפה בודקת איך מילים עובדות. היא שואלת איך שפה אומרת אמת ומה מילים בעצם משמעותן. אפלטון חשב שיש רעיונות נסתרים שמעניקים דבר משמעות. אריסטו גם דיבר על מילים ומשמעות. בימי הביניים שאלו אם שמות ניתנו בטבע או בהסכמה של בני אדם. פרגה רצה שפה ברורה יותר. הוא בנה שפות פורמליות, שהן שפות מדוי...