פסוק (לוגיקה מתמטית)

פסוק הוא ביטוי שניתן לייחס לו ערך אמת שהוא "אמת" או "שקר". למשל 1+1=2 הוא פסוק אמיתי, 1<0 הוא פסוק שקרי, ואילו 5×2 אינו פסוק כלל. בלוגיקה מתמטית פסוק מוגדר באופן פורמלי כדי לאפשר טיפול ריגורוזי במושג פסוק מלוגיקה כללית.

בתחשיב פסוקים

ההגדרה הבסיסית ביותר של פסוק ניתנת במסגרת תחשיב פסוקים. השפה של תחשיב פסוקים כוללת אינסוף סימנים, $P_1, P_2, P_3,\ldots$, הקרויים "פסוקים יסודיים". יתר הפסוקים נבנים מתוכם באופן רקורסיבי לפי הכללים הבאים:

• לכל n טבעי, הפסוק היסודי $P_n$ הוא פסוק.
• לכל פסוק $A$, הביטוי $\neg(A)$ הוא פסוק, כאשר $\neg$ הוא הקשר הלוגי "לא".
• לכל שני פסוקים $A$ ו-$B$, הביטוי $(A)\Box (B)$ הוא פסוק, כאשר $\Box$ הוא אחד מבין הסימנים $\to,\land,\vee,\leftrightarrow$ המייצגים (משמאל לימין) את הקשרים הלוגיים "אם-אז", "וגם", "או" ו"אם ורק אם".
• כל פסוק מתקבל מרצף פעולות סופיות של הכללים הללו.

למשל $(P_1) \to ((\neg(P_2)) \vee (P_1))$ הוא פסוק.

האופי הרקורסיבי של בניית פסוקים מאפשר להוכיח עליהם משפטים באינדוקציה מבנית (המבוססת על אינדוקציה של מספרים טבעיים), לפי בניית הפסוק. אם טענה כלשהי מתקיימת לכל הפסוקים היסודיים, ואם בהינתן שהיא מתקיימת לפסוקים $A$ ו-$B$, היא מתקיימת גם לפסוקים $\neg(A)$ ו-$(A)\Box (B)$ (לכל קשר לוגי), אז בהכרח הטענה מתקיימת לכל הפסוקים. למשל, כך ניתן להוכיח שאורכו של כל פסוק (מספר הסימנים שבו) משאיר שארית 1 בחלוקה ב-3.

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

ערך האמת של פסוק נקבע על פי ערכי האמת של הפסוקים היסודיים המופיעים בו, ולפי טבלת האמת של כל קשר לוגי. למשל אם $P_1$ אמיתי ו-$P_2$ שקרי, אז הפסוק $P_1\land (\neg P_2)$ (שמשמעו "$P_1$ וגם לא $P_2$") הוא אמיתי. התאמה המתאימה ערך אמת לכל פסוק יסודי נקראת מבנה, והיא שקובעת את ערכי האמת של כל הפסוקים האפשריים בתחשיב פסוקים.

פסוק שהוא אמיתי תמיד, ללא תלות בערכי האמת של הפסוקים היסודיים המופיעים בו (כלומר אמיתי בכל מבנה; למשל $P_1 \to P_1$ שאמיתי בין אם $P_1$ אמיתי ובין אם הוא שקרי) קרוי טאוטולוגיה. פסוק שתמיד שקרי, ללא תלות בערכי האמת של הפסוקים היסודיים המופיעים בו, קרוי סתירה.

בתחשיב יחסים

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

פסוק הינו נוסחא ללא משתנים חופשיים.

אינטואיציה

אנו מצפים מפסוקים שיהיה להם ערך אמת יחיד וקבוע, אך לא כל הנוסחאות עונות לתנאי הזה. למשל אמיתות הנוסחא $x\approx 1$ תלויה בערך של x. היא אמיתית אם x הוא הקבוע 1, ושקרית אחרת. כדי לאפיין מבין הנוסחאות את אלו שהן פסוקים יש צורך להגדיר את המושג "משתנה חופשי". נאמר על כמת שהוא כימות של משתנה $x$ בנוסחא, אם $x$ מופיע כתו הראשון מימין לכמת (למשל $\exists_x$). בכל נוסחא, לאחר כימות של משתנה נפתחים סוגריים. משתנה $x$ בנוסחא נקרא "משתנה מכומת" אם הוא מופיע כתו הראשון מימין לכמת, או שהוא בתוך הסוגריים שנפתחים על ידי כמת המכמת אותו. משתנה שאינו מכומת נקרא "משתנה חופשי". נוסחא שבה אין משתנים חופשיים נקראת פסוק. באופן אינטואיטיבי, פסוק הוא נוסחא שמייצגת טענה כללית כלשהי, שאמיתותה אינה תלויה בערכים שמקבלים המשתנים שבה, מאחר שלא ניתן להציב ערכים במשתנים מכומתים.

דוגמאות

הנוסחא $x \approx 1$, למשל, אינה פסוק, כי המשתנה $x$ המופיע בה הוא משתנה חופשי. לעומת זאת $\exists x(x=1)$ הוא פסוק. הפסוק אמיתי, שכן הוא טוען שקיים x כלשהו ששווה ל-1. גם הנוסחא $\forall x(x=1)$ היא פסוק. פסוק זה שקרי (מעל המספרים הממשיים), שכן הוא קובע שכל מספר שווה ל-1.

דוגמאות

• $\forall x\forall y (x\times y=y\times x)$ - פסוק זה קובע שכפל הוא פעולה קומוטטיבית. הפסוק נכון במספרים הממשיים. הוא לא נכון, למשל, באלגברת הקווטרניונים של המילטון.
• $\forall x\forall y\exists z(x<y \to x<z<y)$ - הפסוק קובע שהסדר בקבוצה הוא סדר צפוף. הפסוק נכון במספרים הממשיים. הוא לא נכון במספרים השלמים.
• $\forall x(x=x)$ - פסוק זה נכון תמיד.

ראו גם

• משפט
• תורה