הקיים הנעלם - הדוגמה ההסתברותית - מבוא לוגי

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

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

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

בצורה פורמלית כותבים “x וגם y” בתור \( x\wedge y \), ואת “x או y” (שפירושו: או x, או y, או שניהם גם יחד) בתור \( x\vee y \). הכללים ה”חשבוניים” הקשורים לפעולות אלו פשוטים: התוצאה של פעולת “וגם” היא “שקר” אלא אם שני המשתנים מקבלים את הערך “אמת” (ואז היא “אמת”), והתוצאה של פעולת “או” היא תמיד “אמת” אלא אם שני המשתנים מקבלים את הערך “שקר”.

יש הרבה צורות לכתוב פסוקים, ולרוב בוחרים צורה “קנונית” מסויימת שמועילה לנו. במקרה שלנו הצורה תהיה ספציפית מאוד:

\( (X_1\vee Y_1\vee Z_1)\wedge(X_2\vee Y_2\vee Z_2)\wedge\dots\wedge(X_n\vee Y_n\vee Z_n) \)

כלומר, הצורה היא זו: “שלשות של משתנים, כשכל המשתנים בשלשה מחוברים על ידי “או”, וכל השלשות מחוברות זו עם זו באמצעות “וגם””. העובדה שאלו דווקא שלשות של משתנים היא חשובה.

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

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

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

אבל, מה שכן נכון ואני עומד להוכיח, הוא שתמיד יש השמה שמספקת לפחות \( \frac{7}{8} \) מהפסוקיות - כלומר, מספקת “כמעט את כל” הפסוקיות. למעשה, הוכיחו שזה הדבר הכי טוב שמסוגלים לדעת בצורה טריוויאלית - כל בדיקה מסוג “האם יש השמה שמספקת יותר משבע שמיניות מהפסוקיות” היא קשה כמו הבדיקה “האם קיימת השמה שמספקת את כל הפסוקיות”.

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

אם עד עכשיו הכל ברור, בפוסט הבא אעבור להוכחה עצמה.