תחשיב הפסוקים – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה תגית: גרשיים שגויים |
|||
שורה 1:
ב[[לוגיקה]] וב[[לוגיקה מתמטית]], '''תחשיב פסוקים''' (באנגלית: propositional calculus, propositional logic או sentential calculus) הוא מערכת המאפשרת לייצג את הקשרים בין ערכי האמת של [[פסוק (לוגיקה מתמטית)|פסוקים לוגיים]] שונים. בדוגמה להלן כל שורה היא נוסחה 'בנויה היטב', והמסקנה לפי כללי תחשיב הפסוקים היא חד משמעית:
'''דוגמה''':
:א. '''כל''' גרסה שמורה ברשימת הגירסאות.
:ב. '''אם''' גרסה '''קיימת''' ברשימת הגרסאות - '''אזי''' אפשר לערוך אותה.
:מסקנה חד משמעית: אפשר לערוך את כל הגירסאות ברשימה.
תחשיב הפסוקים אינו מתחשב בתוכן הפסוקים אלא אך ורק בתוקף הפסוק (ערך האמת שבו, היותו תקף או כוזב) וּתְּקֵפוּת חלקיו. תחשיב הפסוקים אינו עוסק, לפיכך, בשאלה כיצד נקבעת אמיתות הפסוקים האטומיים, אלא בשאלה כיצד נקבע ערך האמת של פסוקים מורכבים יותר, המורכבים ממספר פסוקים אטומיים באמצעות [[קשר לוגי|קַשַּרים לוגיים]]. ערך האמת של הפסוקים האטומיים יכול להיקבע על ידי המשמעות (הפירוש [[סמנטיקה|הסמנטי]]) שאנו נותנים לאותיות הפסוקיות. לדוגמה, אם נרשום:
::'''אם א' - אזי ב''''.
:- נוכל לתת לאות א' את הערך 'תקף' (או 'אמת'), ואזי ינבע מהפסוק שגם ב' מקבל את הערך 'תקף' (או: 'אמת').
:- נוכל לתת לאות א' את הערך 'כוזב' (או 'שקר'), ואזי ינבע מהפסוק שגם ב' מקבל את הערך 'כוזב' (או: 'שקר').
במקרה הראשון, נוכל להחליף את המשתנה בערך בעל משמעות, אשר יהיה תקף בתנאֵי הבדיקה. לדוגמה, למשתנה א' נתן את הערך "עכשיו צהריים" ותנאי הבדיקה יהיו שאכן מדובר בבדיקה הנעשית בשעת הצהריים. למשתנה ב' נבחר משמעות המקיימת את המשפט באופן שהפסוק כולו תקף, לדוגמה: "השמש מופיעה בשיא הגובה". יודגש שתהליך תחשיב הפסוקים אינו עוסק בנכונות הטענות, אלא רק במסקנה המתקבלת '''אם''' נכונים כל חלקיה.
אולם ניתן גם לדון בטענות כנוסחאות עם משתנים, בלי לפרט דוגמאות למשמעותם של המשתנים. ניתן לבחון כך את כלל היחסים האפשריים בין הטענות המורכבות, עבור כל הצבה של ערכי אמת לאותיות הפסוקיות המשמשים כ'משתנים'.
הסמנטיקה של תחשיב הפסוקים מורה לנו כיצד עלינו להבין את היחס בין הסמלים המייצגים פסוקים שונים, ובין הטענות שהם מייצגים. כאשר אנו מעוניינים לנתח טיעון או הוכחה כלשהי באמצעות תחשיב הפסוקים, הצעד הראשון שעלינו לעשות מכונה '''הצרנה'''. בתהליך זה מסמנים כל [[משפט (בלשנות)|משפט]] בסיסי (למשל 'השמש תזרח מחר' או 'יוסי גר בלונדון') בסימן קבוע (בדרך כלל אות אנגלית גדולה כמו P או Q, או הסימן P<sub>i</sub> עם האינדקס i, המייצג מספר מסוים). סימן זה משמש לייצג את הטענה בכל מקום שתופיע בטיעון, והוא מכונה "פסוק יסודי", או "פסוק אטומי". גם הקָשַרים הלוגיים אינם נכתבים בתחשיב הפסוקים במלים אלא באמצעות סימונים מוסכמים.▼
במקרה של הדוגמה שלנו:
==תחביר==▼
:- נוכל להשאיר את א' כ''משתנה'', ובהתאם לכל ערך שהוא יקבל - בין אם הערך 'אמת' ובין אם 'שקר', נוכל לדעת על הערך ב'.
במקרה של דוגמה זו ''אם א' אזי ב''' - לפי הטענה, ב' הוא בעל אותו הערך שקיבל משתנה א'.
באמצעות הכללה כזו ניתן לקבוע כי טיעונים הם [[תקפות (לוגיקה)|תקפים]], כאשר עבור כל הצבה של ערכי אמת לפסוקים האטומיים המרכיבים את ההנחות, אם בעקבות הצבה כזו ההנחות של הטיעון תְקֵיפות, הרי שגם המסקנה תְקֵיפה.
'''דוגמה לבדיקת תקפות טיעונים על פי הכללה''':
:הנחה א: '''א'''' כלשהו '''קיים''' בתוך '''ר''''
:הנחה ב: '''אם''' ב' קיים בתוך ר' '''אזי''' אפשר לערוך את ב'.
:טענה ט: אפשר לערוך את א'.
במקרה זה, באמצעות תחשיב הפסוקים, ניתן להסיק באופן חד משמעי וכוללני שטענה ט' תהיה תקיפה לגבי כל קבוצת משתנים (א' ב' ו-ר') שלגביהם הנחה א' והנחה ב' תקפים.
==הצרנה (פורמליזציה) ==
הצרנה (מלשון צורה) או תיבנות של תחשיב פסוקים, היא תהליך העברת ההנחות והטענות הלוגיות לכיתוב תבניתי, במבנה מוסכם ([[פורמליזם (מתמטיקה)|פורמליסטי]]), דמוי סימני החשבון.
▲הסמנטיקה (מבנה המשמעות) של תחשיב הפסוקים מורה לנו כיצד עלינו להבין את היחס בין הסמלים המייצגים פסוקים שונים, ובין הטענות שהם מייצגים. כאשר
▲===תחביר===
תחשיב פסוקים מסוים כולל קבוצה של '''פסוקים יסודיים''' או "פסוקים אטומיים", ומספר קָשַרים לוגיים סטנדרטיים. לדוגמה, נגדיר ש P מייצג את הטענה "הגביע הוא שלנו", ו-Q מייצג את הטענה "אנחנו במפה"'. או אז ניתן להדגים את התחביר של חמשת הקשרים הלוגיים כך:
:שלילה: <math>\neg</math> - זהו קשר אונרי, דהיינו הוא מקושר לאות פסוקית אחת בלבד. לדוגמה, <math>\neg P</math> מייצג את "הגביע הוא לא שלנו".
:הֵלחֵם, או: 'קוניוקציה' ("וגם"): <math>\land</math> או & - קשר בינארי, מקשר בין שני פסוקים. לדוגמה, הפסוק המורכב <math>P \land Q</math> מייצג את הטענה "הגביע הוא שלנו ואנחנו
:ניתוק או דיסיונקציה ("או"): <math>\vee </math> - קשר בינארי, מקשר בין שני פסוקים. לדוגמה, הפסוק המורכב <math>P \vee Q</math> מייצג את הטענה "הגביע הוא שלנו או אנחנו
:תנאי ("אם-אז"): <math>\to</math> - קשר בינארי, מקשר בין שני פסוקים. לדוגמה, הפסוק המורכב <math>P \to Q</math> מייצג את הטענה "אם הגביע הוא שלנו
:תנאי כפול ("אם-ורק-אם", נקרא גם: "אך ורק אם"): <math>\leftrightarrow</math> - קשר בינארי, מקשר בין שני פסוקים. לדוגמה, הפסוק המורכב <math>P \leftrightarrow Q</math> מייצג את הטענה "הגביע הוא שלנו אם ורק אם אנחנו במפה".{{הערה|1=הביטוי העברי 'תנאי כפול' הוא מונח תלמודי משפטי, הנלמד מהחוזה התנ"כי בין משה לבין בני גד ובני ראובן, טרם הכניסה לארץ ישראל.}}
=== נוסחה בנויה כהלכה (נוסחה בנויה היטב) ===
באמצעות
נוסחה בנויה היטב מוגדרת בצורה [[רקורסיה|הרקורסיבית]] הבאה:▼
▲באמצעות הקשרים, מאפשר התחביר ליצור רצפים סופיים של פסוקים יסודיים, קָשַרים וסימני סוגריים, שאפשר לקרוא אותו באופן חד-משמעי. רצף כזה נקרא [[נוסחה בנויה היטב]] (נקראת גם '''נוסחה בנויה כהלכה''' ובראשי תיבות '''נב"כ''', (Well Formed Formula או WFF).<br /> )
▲נוסחה בנויה היטב מוגדרת בצורה הרקורסיבית הבאה:
* אם <math>P</math> הוא פסוק אטומי, אז <math>P</math> הוא נוסחה בנויה היטב.
* אם <math>A</math> היא נוסחה בנויה היטב, אז גם <math>(\neg A)</math> היא נוסחה בנויה היטב.
* אם <math>A</math> ו-<math>B</math> נוסחאות בנויות היטב, אז לכל קשר <math>\Omega</math> כך ש <math>\Omega \in \{ \to,\land,\vee,\leftrightarrow \}</math>, הרי ש <math>(A \Omega B)</math> היא נוסחה בנויה היטב (דהיינו עבור כל שני פסוקים אטומים, הצבתו של אחד מן הקשרים הבינריים ביניהם יוצרת נוסחה בנויה היטב).
* כל דבר אחר איננו נוסחה בנויה היטב.
* רצפים חסרי מובן כמו <math>(\to A \neg B)</math> אינם פסוקים, ואינם עונים על ההגדרה הרקורסיבית.
בניסוח הפורמלי של תחשיב הפסוקים, קיים [[אלגוריתם]] מסודר וסופי
יש לשים לב שהסוגריים חיוניים בדרך כלל, אם כי ניתן ומקובל להשמיט את זוג הסוגריים החיצוניים ביותר.
אפשר לבנות סוגים שונים של תחשיבי פסוקים, באמצעות בחירה שונה של הקשרים המשתתפים. לדוגמה, אפשר להחליף את הקשר "אם a אז b" ב- "b או (לא a)", וכך להגדיר את הקשר 'אם-אז' באמצעות הקשרים "או" ו"לא". [[כללי דה-מורגן]] מאפשרים לוותר על אחד משני הקשרים "או" או "וגם".
'''תחשיב פסוקים שלם''' (או '''קבוצה שלמה של קשרים''') הוא קבוצת קשרים שאפשר להציג באמצעותה כפסוק כל [[פעולה בוליאנית]], או כל טבלת אמת (ר' להלן). ישנם שני קשרים, שכל אחד מהם מהווה בעצמו "תחשיב פסוקים שלם", והם מכונים "הקשרים של שפר". קשרים אלו הם הקשרים "לא-וגם" ([[NAND לוגי|NAND]]) ו"לא-או" ([[NOR לוגי|NOR]]). התחביר הפורמלי של תחשיב הפסוקים המתמטי מתבסס על שני קשרים בלבד, "אם-אז" ו"לא" - כל שאר הקשרים מוגדרים כקיצורים של ביטויים הבנויים מקשרים בסיסיים אלו.▼
=== תחשיב פסוקים שלם (קבוצת קשרים שלמה) ===
'''תחשיב פסוקים שלם''' (או '''קבוצה שלמה של קשרים''') הוא קבוצת קשרים, שכפסוק אפשר להציג באמצעותה כל [[פעולה בוליאנית]], או כל טבלת אמת (ר' להלן).
▲
==אקסיומות וכללי היסק==▼
▲=== הנחות יסוד (אקסיומות) וכללי היסק ===
הוגה הדיעות והלוגיקאי פרופסור יאן לוּקאסייביץ' מאוניברסיטת [[לבוב]], גילה מערכת אקסיומטית (מערכת הנחות יסוד) פשוטה בעלת שני קשרים בלבד: תנאי ושלילה, המהווה תחשיב פסוקים שלם:
שלוש הנחות יסוד - [[אקסיומה|אקסיומות]] מן הצורה הבאה:
# <math>(p \to (q \to p))</math>
שורה 42 ⟵ 73:
[[כלל היסק]] אחד, [[מודוס פוננס]] (קיומו של תנאי ונביעת טענה מקיומו של התנאי), המוגדר כך:
:מ-<math>p</math>
:ומ- <math>(p \to q)</math>
שורה 68 ⟵ 99:
::::::::::::::::::::::::מודוס פוננס על שורות 3 ו-4: מש"ל.
==טבלת האמת וסמנטיקה - משמעות המסקנות של תחשיבי פסוקים ==
{{הפניה לערך מורחב|טבלת אמת}}
במסגרת הסמנטיקה (ניתוח המשמעות) המקובלת של תחשיב הפסוקים, כל פסוק יסודי יכול לקבל אחד משני [[ערך אמת|ערכי אמת]]: "אמת" או "שקר", ובלבד שהוא מקבל את אותו ערך בכל הופעה שלו באותו טיעון. כל קשר לוגי מובן כ[[פונקציה|פונקציית]]-אמת,
לדוגמה, השלילה מחזירה פסוק שקרי עבור כל פסוק אמיתי אליו היא מקושרת, ומחזירה פסוק שקרי עבור כל פסוק אמיתי. נוח לייצג פונקציות אמת באמצעות [[טבלת אמת]], בהן T ו-F מייצגים את הערכים אמת ושקר (ב[[אלגברה בוליאנית]] יוחלפו אלו בערכים 1 עבור אמת ו-0 שורה 100 ⟵ 133:
|}
|טבלת האמת של הקוניונקציה - ההֶלחֵם
{| border="1" cellpadding="3"
! | <math> P </math> || <math> Q </math> ||<math>P \land Q</math>
שורה 114 ⟵ 147:
|}
|טבלת האמת של הדיסיונקציה - הניתוק
{| border="1" cellpadding="3"
! | <math> P </math> || <math> Q </math> ||<math>P \vee Q</math>
שורה 144 ⟵ 177:
כל שיוך של ערכי אמת לפסוקים יסודיים נקרא '''פירוש''' ("אינטרפרטציה") או הצבה. בטבלאות האמת, כל שורה היא פירוש.
פסוק הוא קונטינגנטי אם ורק אם אינו סתירה ואינו טאוטולוגיה. קבוצה של פסוקים נקראת '''עקבית''' (קונסיסטנטית) אם קיים פירוש עבורו כל הפסוקים בקבוצה מקבלים ערך "אמת".▼
פסוק מורכב המקבל את הערך "אמת" בכל פירוש של הפסוקים היסודיים (כלומר כזה שבטבלת האמת שלו הוא מקבל T בכל השורות), נקרא [[טאוטולוגיה (לוגיקה)|טאוטולוגיה]] (אמת לאמיתה). משמעות הדבר היא שפסוק זה הוא אמיתי בזכות הקשרים הלוגיים שבין רכיביו, ללא תלות באמיתותם של הפסוקים האטומיים עצמם. פסוק המקבל את הערך "שקר" בכל פירוש נקרא '''סתירה'''.
▲פסוק הוא קונטינגנטי (תלוי, בעל תלות) אם ורק אם אינו סתירה ואינו טאוטולוגיה. קבוצה של פסוקים נקראת '''עקבית''' (קונסיסטנטית) אם קיים פירוש עבורו כל הפסוקים בקבוצה מקבלים ערך "אמת".
===טבלאות אמת ככלי לבדיקת תקפות טיעונים===
[[טבלת אמת|טבלאות אמת]] הן כלי נוח לשם בדיקת [[תקפות (לוגיקה)|תקפותם]] של טיעונים ([[היסק]]ים) בתחשיב הפסוקים. הטכניקה של טבלאות אמת מאפשרת לבטא את ערכי האמת של כל פסוק מורכב במונחי ערכי האמת של הפסוקים המרכיבים אותו, וכאשר הטבלה
לדוגמה, ננסה לבדוק אם הטיעון הבא תקף:
# השמש זורחת וגם אם האגם קפוא הברווזים עפים
שורה 158 ⟵ 193:
תחילה, נצרין את הפסוקים האטומים על פי הלקסיקון (מילון תמציתי) הבא:
: P: השמש זורחת
: Q: האגם קפוא
שורה 164 ⟵ 199:
על פי ההצרנה,
# <math>P \and (Q \to R)</math>
# <math>P \to \neg Q</math>
שורה 194 ⟵ 229:
==מערכות הוכחה==▼
לתחשיב הפסוקים אפשר 'לבנות' מערכות הוכחה המוכיחות טענות נוספות הנובעות מקבוצת טענות ראשונית. מערכות היסק כאלה בנויות מכללים תחביריים (סינטקטיים) טכניים בלבד.
מערכת ההוכחות הפשוטה ביותר לתחשיב פסוקים היא מערכת [[מערכת דדוקציה טבעית|דדוקציה טבעית]], המכילה עשרה כללי היסק. עבור כל אחד מחמשת הקשרים היא מכילה '''כלל הבאה''' (נקרא גם '''כלל הכנסה''' או '''אינטרודוקציה''') ו'''כלל סילוק''' (נקרא גם '''כלל הוצאה''' או '''אלימינציה''').
▲==מערכות הוכחה==
===דוגמאות מערכות הוכחה===
דוגמה ל'''כלל הבאה''' (כלל הכנסה - אינטרודוקציה) להקשר של פסוק התנאי:
::<math>\ P</math>
שורה 210 ⟵ 250:
::<math>\ P \land Q</math>
––––––––––––––––––––––––
::<math>\ P </math>
== ראו גם ==
| |||