שינויים

88-101 חשיבה מתמטית

נוספו 1,194 בתים, 10:37, 11 ביולי 2011
/* כמתים */
'''דוגמא'''. את הפסוק "אין מספר גדול ביותר" אפשר להצרין באופן פשטני, כך: <math>\ \neg \exists x: L(x)</math>, כאשר <math>\ L(x)</math> הוא הפרדיקט "x הוא מספר גדול ביותר". הצרנה מעט יותר מתוחכמת תגדיר את הפרדיקט <math>\ P(x,y)</math> שפירושו "x<y", ותצרין ל-<math>\ \forall x: \exists y: P(x,y)</math>, כלומר, לכל מספר יש מספר הגדול ממנו.
 
זהו הסוג השלישי (והאחרון עבורנו) של פסוקים לוגיים: הפסוקים של ה"לוגיקה מסדר ראשון". נסכם: פסוק הוא או פרדיקט (לרבות אטומים, שהם פרדיקטים ללא משתנים), או חיבור של פסוקים קצרים יותר באמצעות קשרים לוגיים, או החלה של כמת על פסוק קצר יותר.
גם לאחר ההרחבה הזו, בכל פסוק יש "פעולה אחרונה": הקשר האחרון או הכמת האחרון שהופעל כדי ליצור את הפסוק. לדוגמא:
* הפעולה האחרונה ב- <math>\ \forall x: ((x<y) \rightarrow (x<0))</math> ("לכל x, אם x קטן מ-y אז x שלילי") היא הכמת הכולל על x; לעומת זאת הפעולה האחרונה ב- <math>\ (\forall x: (x<y)) \rightarrow (y<0))</math> ("אם כל x הוא קטן מ-y, אז y שלילי") היא הקשר "אם-אז".
 
לפסוקים שיש בהם כמתים אי אפשר לבנות טבלאות אמת, משום שלצד האטומים המקבלים רק שני ערכי אמת אפשריים, יש בהם משתנים העשויים לעבור על-פני מספר אינסופי של אפשרויות. לכן הלוגיקה המטפלת בפסוקים עם כמתים (הנקראת "לוגיקה מסדר ראשון") מורכבת יותר מן הלוגיקה הפסוקית, ויש לה יכולת ביטוי רחבה יותר. גם בלוגיקה זו אומרים ששני פסוקים <math>\ \varphi, \psi</math> הם שקולים אם <math>\ \varphi \leftrightarrow \psi</math> מקבל ערך אמת לכל הצבה של המשתנים המעורבים.
 
אנו מגיעים לנקודה חשובה ביותר הנוגעת לשמות המשתנים. לכל כמת יש אזור תחולה. אם נכתוב למשל <math>\ \forall x : P(x) \rightarrow \exists y : P(y)</math>, אזור התחולה של הכמת הראשון הוא ההופעה הראשונה של P, ואזור התחולה של הכמת השני הוא ההופעה השניה. בתוך אזור התחולה הזה, '''אין כל חשיבות לשם המשתנה''' - אין שום הבדל בין "לכל נורה x יש מתג y כך ש-y מפעיל את x" (הצרן את הפסוק הזה), לבין "לכל נורה z יש מתג y כך ש-y מפעיל את z". לעומת זאת, הפסוק "לכל נורה x יש מתג y כך ש-y מפעיל את z".
הכמתים היסודיים מאפשרים לנסח טענות סטנדרטיות נוספות.
'''תרגיל'''. נאמר שאיבר a של קבוצת מספרים A הוא "חסם עליון" אם הוא גדול מכל איבר אחר בקבוצה. הצרן את הטענה "לקבוצה A יש חסם עליון". הצרן את הטענה "אם יש לקבוצה חסם עליון, אז הוא יחיד".
 
=== שלילת כמתים ===