תחשיב פסוקים
מתוך ויקיפדיה, האנציקלופדיה החופשית
בלוגיקה מתמטית, תחשיב פסוקים או לוגיקה פסוקית הוא מערכת לטיפול בפסוקים באופן שתלוי במבנה בלבד, ולא בהקשר. תחשיב הפסוקים הוא אבן הפינה של הלוגיקה המתמטית.
תוכן עניינים |
[עריכה] הצרנה
כדי לבצע פישוט של השפה הטבעית לשפה מתמטית של סמלים המתארת את המבנה ולא את התוכן, מתבצע תהליך הנקרא הצרנה. בתהליך זה מסמנים כל משפט חיווי בסיסי בו מטפלים (למשל 'השמש תזרח מחר' או 'יוסי גר בלונדון') בסימן קבוע (בדרך כלל אות אנגלית גדולה או הסימן Pi כאשר i הוא מספר). סימן זה משמש לייצג את המשפט בכל מקום שיופיע בטיעון. למשפט כזה מקובל לקרוא 'פסוק יסודי'. תחשיב הפסוקים אינו עוסק בערך האמת של פסוקים יסודיים, אלא בשאלה כיצד נקבע ערך האמת של פסוקים מורכבים יותר, הנוצרים מפסוקים יסודיים באמצעות קָשַרים לוגיים, כאשר ידוע ערך האמת של הפסוקים היסודיים (דהיינו, ידוע האם יוסי גר בלונדון או לא).
- לדוגמה, אם נסמן את 'יוסי גר בלונדון' באות A ואת 'השמש תזרח מחר' באות B, האמירה 'אם יוסי גר בלונדון אז השמש תזרח מחר' תהפוך ל'אם A אז B'.
גם הקָשַרים הלוגיים אינם נכתבים בתחשיב הפסוקים במלים כי אם באמצעות סימונים מוסכמים. חץ <--- מסמן "אם-אז", הסימן ~ מסמן "לא", והסימנים "וגם" ו"או" מסומנים על ידי הסימנים \/ ו /\ בהתאמה.
- הפסוק שטיפלנו בו יהפוך כעת ל - B <--- A
[עריכה] תחביר
תחשיב הפסוקים המקובל כולל סדרה אינסופית של פסוקים יסודיים, ומספר קָשַרים לוגיים סטנדרטיים (למשל "וגם", "או", "לא", "אם-אז"). פסוק הוא רצף סופי של פסוקים יסודיים, קשרים וסימני סוגריים, שאפשר לקרוא אותו באופן חד-משמעי. לדוגמה:
- "אם ((אם A אז B) וגם (אם B אז C)) אז (אם A אז C)"
הוא פסוק, שבשפה טבעית אפשר להתייחס אליו כאל הטרנזיטיביות של הקשר אם-אז. גם
- " A וגם (לא A)"
הוא פסוק (למרות שהוא שקרי תמיד). לעומת זאת
- "A וגם B או C"
אינו פסוק, משום שהוא ניתן לקריאה דו משמעית. גם רצפים חסרי מובן כמו "אם או A וגם A B אז" אינם פסוקים.
בניסוח הפורמלי של תחשיב הפסוקים, קיים אלגוריתם מסודר וסופי לזיהוי האם רצף סימנים מסוים הוא פסוק.
אפשר לבנות סוגים שונים של תחשיבי פסוקים, באמצעות בחירה שונה של הקשרים המשתתפים. לדוגמה, אפשר להחליף את הקשר "אם a אז b" ב- "b או (לא a)", וכך להגדיר את הקשר 'אם-אז' באמצעות הקשרים 'או' ו'לא'. כללי דה-מורגן מאפשרים לוותר על אחד משני הקשרים 'או' או 'וגם'.
תחשיב פסוקים שלם (או קבוצה שלמה של קשרים) הוא קבוצת קשרים שאפשר להציג באמצעותה כפסוק כל פעולה בוליאנית. ישנם שני קשרים המהווים בפני עצמם "תחשיב פסוקים שלם", והן מכונים "הקשרים של שפר". קשרים אלו הם הקשרים "לא-וגם" (NAND) ו"לא-או" (NOR). התחביר הפורמלי של תחשיב הפסוקים המתמטי מתבסס על שני קשרים בלבד, "אם-אז" ו"לא" - כל שאר הקשרים מוגדרים כקיצורים של ביטויים הבנויים מקשרים בסיסיים אלו.
[עריכה] סמנטיקה
במסגרת הסמנטיקה של תחשיב הפסוקים, כל פסוק יסודי יכול לקבל אחד משני ערכים: 'אמת' או 'שקר', ובלבד שהוא מקבל את אותו ערך בכל הופעה שלו באותו הפסוק. לכל קשר מוגדרת טבלאות אמת, המגדירה האם הקשר ייתן 'אמת' או 'שקר' בהתאם לערכים שהוא מקבל כנתון. לדוגמה, הקשר "או" תלוי בשני משתנים, והוא תמיד מופיע בצורה "a או b" (כאשר a ו- b הם פסוקים). הוא מחזיר ערך 'אמת' אם לפחות אחד משני הפסוקים a ו- b הוא בעל ערך אמת, וערך 'שקר' אחרת (כדאי לשים לב שזו אינטרפטרציה השונה מזו שאנו מייחסים למילה 'או' בדיבור יומיומי).
שיוך מסוים של ערכי אמת לפסוקים יסודים נקרא אינטרפטציה. באופן פורמלי, אינטרפרטציה היא פונקציה מקבוצת הפסוקים היסודים לקבוצה {אמת, שקר}. שיוך ערכי אמת לכל המשתנים נקרא 'אינטרפרציה מלאה'. פסוק המקבל את הערך 'אמת' בכל אינטרפרטציה במשתנים, נקרא טאוטולוגיה. פירוש הדבר הוא שהפסוק אמיתי בכל מקרה, ללא תלות באמיתותם של הפסוקים היסודיים, ומכאן ללא תלות ב"מצב בעולם" (החיצוני ללוגיקה). מכיוון שפסוק הוא לעולם סופי, מופיעים בו מספר סופי של משתנים ולכן אפשר לבדוק האם הוא מהווה טאוטולוגיה בזמן סופי. פסוק המקבל את הערך 'שקר' בכל אינטרפרטציה נקרא סתירה. נוסחה היא קונטינגנצית אם ורק אם אינה סתירה ואינה טאוטולוגיה. קבוצה של נוסחאות היא קונסיסטנטית אם ורק ישנה שורה בלוח האמת שבה כל הנוסחאות בקבוצה מקבלות ערך אמת.
[עריכה] מערכות הוכחה
ניתן לבנות לתחשיב הפסוקים מערכות הוכחה, שבהן ניתן להוכיח מקבוצת טענות נתונה טענות נוספות שנובעות ממנה. מערכות היסק אלה בנויות מכללים סינטקטיים (תחביריים) טכניים בלבד. המערכת הפשוטה ביותר היא מערכת דדוקציה טבעית: NDC (ראשי-תיבות של Natural Deduction Calculus ) המכילה אחד-עשר כללים - עבור כל אחד מחמשת הקשרים היא מכילה כלל הכנסה (Introduction) וכלל הוצאה (Elimination). מערכת זו היא נאותה (כלומר, כל טענה שניתנת להוכחה בה מהנחות מסוימות, אכן נובעת מהן) ושלמה (כלומר, כל טענה הנובעת מקבוצת הנחות, גם ניתנת להוכחה מקבוצה זו במערכת). קיומה של מערכת היסק נאותה ושלמה לתחשיב הפסוקים מבליטה את הפשטות שלו לעומת תחשיבים אחרים (מסדר שני), שלהם לא ניתן לבנות מערכות היסק כאלה. למערכות מסדר ראשון (FOL - First Order Logic) ניתן לבנות מערכות דדוקציה טבעית ומערכת הילברט אשר מפשטת את המערכת.
[עריכה] ראו גם
- שפה מסדר ראשון
- מערכת דדוקציה טבעית
- מערכת הילברט לתחשיב הפסוקים
- פורמליזם (מתמטיקה)
- טבלת אמת
- אלגברה בוליאנית
- לוגיקה בוליאנית
