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

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

בואו נתחיל עם אמירה של חזאים: “מחר ירד גשם או שמחר לא ירד גשם”. זו אמירה מעצבנת, כי היא לא באמת אומרת לנו כלום, ועם זאת ברור לנו שהיא נכונה תמיד. לאמירות כאלו, שהן נכונות תמיד ולא משנה מה, קוראים טאוטולוגיות (יש למילה משמעות דומה בשפת היום יום ובספרות, אבל לא זהה; טאוטולוגיה “ספרותית” היא להגיד כמה פעמים את אותו הדבר, כמו למשל “החוק הראשון של מועדון הטאוטולוגיה הוא החוק הראשון של מועדון הטאוטולוגיה” של xkcd - אמירה שהיא מטבעה גם טאוטולוגיה מתמטית). הבה ונתבונן בטאוטולוגיה מתחום הספורט דווקא: “או שננצח במשחק או שלא ננצח בו” הוא ביטוי שגור בקרב מאמנים מסויימים. ואילו המתמטיקאי יכול להגיד “או ש-\( p \) ראשוני, או ש-\( p \) איננו ראשוני”. בכל המקרים הללו הטאוטולוגיה היא בעצם אותה הטאוטולוגיה: זו טענה מהצורה “או שמשהו, או שלא משהו”, כש”משהו” יכול להיות כל מה שנרצה. למעשה, זה בכלל לא משנה מהו אותו ה”משהו” - הנכונות של הטאוטולוגיה נובעת מהמבנה של המשפט, ולא מהתוכן שאנחנו יוצקים בו. בכתיבה מתמטית פורמלית, המשפט הזה יכתב בתור \( X\vee\neg X \): כאן \( X \) הוא משתנה שיכול לקבל ערך של “אמת” או “שקר”, ו-\( \vee \) מייצג את “או”, ו-\( \neg \) מייצג את “לא”. קראו את הפסוק הזה בתור “איקס או לא איקס”. הנה לנו דוגמה לפסוק בתחשיב הפסוקים.

הבה ונישאר בדוגמאות מתחום הספורט. “אם נבקיע יותר שערים מהקבוצה השניה, אז ננצח” הוא עוד פסוק לגיטימי: במתמטית כותבים אותו בתור \( X\to Y \), כלומר “איקס גורר וואי”. דוגמה אחרת לאותו פסוק אבל מתחום אחר היא אמרתו של פסקל כי “אם היה אפה של קליאופטרה קצר יותר ההיסטוריה היתה כולה אחרת”. כאן \( X \) הוא “אפה של קליאופטרה היה קצר יותר” ו-\( Y \) הוא “ההיסטוריה היתה כולה אחרת”. כעת, כשמדובר על המשפט של ה”אם נבקיע יותר שערים” ברור לנו שהוא נכון; אבל בקשר למשפט של פסקל לא ממש ברור אם הוא נכון. אנחנו נזקקים לידע חיצוני כלשהו כדי לדעת את זה - האם באמת לאף של קליאופטרה הייתה השפעה קריטית על מרקוס אנטוניוס? למעשה, אין לנו ממש דרך לדעת. מכאן כבר ברור לנו ש-\( X\to Y \) הוא כנראה לא טאוטולוגיה: קיימת האפשרות שהפסוק הזה יהיה נכון או לא נכון, בהתאם למשמעות של \( X,Y \). זה קיים גם בדוגמת הכדורגל; אם חוקי הכדורגל היו שונים כך שמי שמבקיע יותר דווקא מפסיד, אז “אם נבקיע יותר שערים מהקבוצה השניה, אז ננצח” היה משפט שגוי. ברור לנו, אם כן, שהנכונות של \( X\to Y \) היא לא צורנית בלבד.

הפסוקים שתחשיב הפסוקים עוסק בהם הם בדיוק אמירות פשוטות מהצורה שהצגתי כאן - כאלו שמערבות “משהו”-ים שיכולים להיות נכונים או לא נכונים, ומחוברים זה לזה באמצעות קשרים לוגיים של “או” (\( \vee \)), “וגם” (\( \wedge \)), “אז” (\( \to \)) ו”לא” (\( \neg \)). פסוק בנוי בערך כמו ביטוי חשבוני עם נעלמים: בשביל להבין מי בא קודם משתמשים בסוגריים, כלומר \( \left(X\to Y\right)\vee\left(Y\to Z\right) \) הוא יצור שונה מ-\( X\to\left(Y\vee\left(Y\to Z\right)\right) \).

כמו בביטוי חשבוני רגיל עם נעלמים, אפשר להציב ערכים בנעלמים; במקרה שלנו הערכים הם “אמת” או “שקר”, \( T \) או \( F \). מרגע שהצבנו ערכים במשתנים, אפשר לחשב את הערך של הפסוק - שוב, כמו שמחשבים את ערכו של ביטוי חשבוני. כך למשל \( X\vee Y \) מקבל ערך \( T \) אם לפחות אחד מהמשתנים קיבל ערך \( T \); \( X\wedge Y \) מקבל \( T \) רק אם שניהם קיבלו \( T \); ו-\( X\to Y \) מקבל \( T \) אלא אם \( X \) קיבל \( T \) ו-\( Y \) קיבל \( F \). מכיוון שלכל משתנה יש רק שני ערכים אפשריים, אפשר להגדיר קשר בקלות פשוט על ידי כתיבת הערך שהוא מחזיר עבור כל זוג קלטים אפשרי - לדבר כזה קוראים טבלת האמת של הקשר. קצת קומבינטוריקה: אם יש לנו קשר שפועל על שני משתנים, אז יש לו \( 2^{2} \) קלטים אפשריים (\( \left(F,F\right),\left(T,F\right),\left(F,T\right),\left(T,T\right) \)) ולכן יש רק \( 2^{\left(2^{2}\right)}=16 \) קשרים שונים שפועלים על שני משתנים (קשר מוגדר באופן מוחלט על ידי ערכי האמת שהוא מחזיר לכל קלט אפשרי; יש 4 קלטים אפשריים ולכל אחד בוחרים אחד משני פלטים אפשריים ולכן יש \( 2^{4} \) אפשרויות). זה לא כל כך הרבה; אפשר לשבת ולכתוב את כולם אם יש לכם מספיק זמן. הסיבה שבגללה מכל הקשרים הללו בחרנו לדבר דווקא על \( \vee,\wedge,\to \) היא לא מקרית; אלו כנראה הקשרים הכי נוחים להבנה והכי פשוטים לתיאור מילולי.

שאלה אחת שכדאי לטפל בה מראש היא - האם הקשרים הללו מגבילים את יכולת ההבעה שלנו? האם יש משפטים שלא ניתן למדל אם אין לנו אותם? למשל, משפט כמו “בגרף סופי וקשיר יש מעגל אוילרי אם ורק אם דרגת כל צומת זוגית” הוא בבסיסו טענת \( A\leftrightarrow B \), שמקבלת ערך “אמת” כל עוד הערכים של \( A,B \) זהים ואחרת מקבלת “שקר”; אבל אפשר לבנות אותה גם באופן שונה מהקשרים שכבר יש לנו: \( \left(A\to B\right)\wedge\left(B\to A\right) \). די קל לראות, על ידי בדיקה של כל המקרים, שגם זה פסוק שמקבל ערך “אמת” רק כאשר ערכי האמת של \( A,B \) שווים.

באופן כללי, בעזרת \( \wedge,\vee,\neg \) אפשר לכתוב פסוק עבור כל פונקציה \( f:\left\{ F,T\right\} ^{n}\to\left\{ F,T\right\} \), לא משנה על כמה משתנים היא. זה כבר די קסם - בעזרת כמה קשרים פשוטים על שני משתנים, אפשר לכתוב ביטוי עבור כל פונקציה על משתנים לוגיים, לא משנה כמה מסובכת. נסו להשוות את זה לעובדה שבעזרת ארבע פעולות החשבון הבסיסיות ממש אי אפשר לכתוב את רוב הפונקציות האפשריות מהרציונליים לעצמם (למה? ובכן, למי שמכיר עוצמות - יש \( 2^{\aleph_{0}} \) פונקציות כאלו אבל רק \( \aleph_{0} \) נוסחאות שאפשר לכתוב עם פעולות החשבון, כל עוד דורשים שהן יהיו סופיות).

ובכן, איך הקסם עובד? אפשר לחשוב על \( f \) כעל אוסף של \( n \)-יות של ערכים לוגיים שבדיוק עליהם היא מקבלת ערך \( T \) (אם \( f \) מחזירה \( F \) לכל דבר, אז \( X\wedge\neg X \) הוא פסוק שמחשב אותה). בואו נניח ש-\( \left(a_{1},\dots,a_{n}\right) \) היא \( n \)-יה כזו של ערכים לוגיים (כלומר, \( a_{i}\in\left\{ T,F\right\} \)) ונגדיר פסוק \( \left(l_{1}\wedge\dots\wedge l_{n}\right) \) כך ש-\( l_{i}=X_{i} \) אם \( a_{i}=T \), ו-\( l_{i}=\neg X_{i} \) אם \( a_{i}=F \). קל לראות שהפסוק הזה מקבל ערך \( T \) אך ורק על ההשמה \( \left(a_{1},\dots,a_{n}\right) \) למשתנים \( X_{1},\dots,X_{n} \); וכעת נוסחה עבור \( f \) נקבל על ידי ביצוע \( \vee \) לכל הפסוקים הללו. למשל, עבור \( f\left(X_{1},X_{2},X_{3}\right) \) שמחזירה \( T \) אם בדיוק שניים מתוך שלושת המשתנים קיבלו \( T \) נקבל את הנוסחה \( \left(X_{1}\wedge X_{2}\wedge\neg X_{3}\right)\vee\left(X_{1}\wedge\neg X_{2}\wedge X_{3}\right)\vee\left(\neg X_{1}\wedge X_{2}\wedge X_{3}\right) \). נוסחה בצורה הזו (\( \mbox{\vee} \) של תת-פסוקים - “פסוקיות” - שכל אחד מהם הוא \( \wedge \) של משתנה או של \( \neg \) של משתנה) נקראת נוסחת DNF (מלשון Disjunctive normal form). מה שראינו הוא שלכל פונקציה לוגית יש DNF ולכן די בשלושת הקשרים שמשתתפים ב-DNF כדי לכתוב פסוק שמבטא כל פונקציה לוגית אפשרית. מכיוון שאפשר לקבל את \( \vee \) ואת \( \wedge \) באמצעות הקשרים \( \neg \) ו-\( \to \), אפשר להסתפק רק בשני קשרים אלו כדי לקבל כל פונקציה (ולעתים קרובות זה מה שעושים בספרי לוגיקה, כי יותר קל להוכיח משפטים כשיש פחות קשרים שצריך לדבר עליהם). למעשה, יש גם קשרים לוגיים שאיתם לבד אפשר לכתוב כל נוסחה: הקשר הידוע ביותר הוא NAND, שמסומן ב-\( \uparrow \) ומוגדר בתור \( \neg\left(X_{1}\wedge X_{2}\right) \) (כלומר, מקבל \( F \) רק כאשר \( X_{1}=X_{2}=T \)). זה תרגיל נחמד להוכיח שאכן אפשר לקבל ממנו את \( \neg \) ואת (למשל) \( \to \) ולכן די להשתמש רק בו. אז למה לא עושים את זה בדרך כלל? כי עדיין יותר פשוט להבין נוסחאות שכתובות עם \( \to,\neg \).

אם כבר הצגתי את DNF, כדאי להציג גם צורה נורמלית נוספת של פסוקים שדואלית לה - CNF (Conjunctive normal form). זו נוסחה שמורכבת מ-\( \wedge \) של פסוקיות שכל אחת מהן כוללת \( \vee \) של משתנים ושלילות של משתנים (“משתנה או שלילה של משתנה” נקרא בדרך כלל “ליטרל” כדי לפשט עניינים). לכל טבלת אמת קיים פסוק בצורת CNF שמממש אותה; אבל זה כבר לא מובן מאליו כמו DNF. נסו שניה לחשוב למה ותראו שזה בעייתי. הפתרון הוא תעלול קטן ונחמד: אם אנחנו רוצים לבנות פסוק עבור טבלת אמת כלשהי, נתחיל מפסוק \( \varphi \) בצורת DNF עבור טבלת האמת ההפוכה; עכשיו פסוק ה-CNF המתאים יהיה מה שמתקבל מ-\( \neg\varphi \) כשמפעילים עליו את כללי דה מורגן, שאציג כרגע.

יש שני כללי דה-מורגן: האחד הוא ש-\( \neg\left(X\vee Y\right)=\neg X\wedge\neg Y \) והשני הוא ש-\( \neg\left(X\wedge Y\right)=\neg X\vee\neg Y \) (כאן שוויון פירושו שקילות). למה זה נכון? ובכן, אפשר לבדוק את הנוסחאות הללו באופן ישיר על ידי הצבה של כל הערכים האפשריים ב-\( X,Y \), ואפשר גם לחשוב בהגיון שניה - להגיד “זה לא נכון שמתמטיקה היא גם משעממת וגם פדנטית” זה כמו להגיד “או שהמתמטיקה לא משעממת או שהמתמטיקה לא פדנטית. אולי שניהם”.

פסוק DNF נראה כך: \( C_{1}\vee C_{2}\vee\dots\vee C_{n} \) כשכל \( C_{i} \) הוא מהצורה \( \left(l_{1}\wedge l_{2}\wedge\dots\wedge l_{k}\right) \). אחרי שנפעיל \( \neg \) עליו נקבל \( \neg C_{1}\wedge\dots\wedge\neg C_{n} \), ואחרי שנכניס את ה-\( \neg \) לתוך כל אחד מהסוגריים נקבל בהם \( \left(\neg l_{1}\vee\dots\vee\neg l_{k}\right) \). ייתכן שנקבל כך דברים כמו \( \neg\neg X \) שאותם אפשר כמובן להחליף ב-\( X \); סוף הסיפור. אם כן, כלל האצבע פשוט: רוצים CNF? קודם תמצאו DNF של ההפך, ואז תהפכו.

זה מסיים את הדיון בתחביר - באופן שבו ניתן לבנות סדרות של סימנים שתהיה להן משמעות עבורנו; בפרט, שהמבנה שלהן יהיה ברור לנו באופן חד משמעי. לנוסחאות כאלו קוראים Well-formed formulas, או WFF-ים; אני אקרא להן פשוט “פסוקים” או “נוסחאות” ואתייחס לסדרות אחרות של סימנים כאל ג’יבריש חסר חשיבות. נקודה חשובה אחת שקודם רפרפתי מעליה היא שבהינתן נוסחה, יש לה “קריאה יחידה” - דרך אחת בלבד לתאר אותה בתור עץ שבו העלים הם משתנים והצמתים הם הפעולות הלוגיות - כמו בביטוי חשבוני רגיל, שגם לו יש קריאה יחידה אם שמים סוגריים בצורה נבונה. די הופתעתי לגלות שיש ספרי לוגיקה רציניים (מנדלסון…) שפשוט מתעלמים מהעניין הזה לחלוטין. לתשומת לב כל מי שטוען שלוגיקאים הם פדנטיים.