תחשיב הפסוקים – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
הנדב הנכון (שיחה | תרומות) מאין תקציר עריכה |
מאין תקציר עריכה תגיות: עריכה חזותית עריכה ממכשיר נייד עריכה דרך האתר הנייד עריכה מתקדמת מהנייד |
||
שורה 12:
:- נוכל לתת לאות א' את הערך 'אמת', ואזי ינבע מהפסוק שגם ב' מקבל את הערך 'אמת'.
:- נוכל לתת לאות א' את הערך 'שקר', ובמקרה זה פסוק ב' יוכל לקבל את הערך 'שקר' או את הערך 'אמת'.
במקרה הראשון, נוכל להחליף את המשתנה בערך בעל משמעות, אשר יהיה תקף בתנאֵי הבדיקה. לדוגמה, למשתנה א'
אולם ניתן גם לדון בטענות כנוסחאות עם משתנים, בלי לפרט דוגמאות למשמעותם של המשתנים. ניתן לבחון כך את כלל היחסים האפשריים בין הטענות המורכבות, עבור כל הצבה של ערכי אמת לאותיות הפסוקיות המשמשים כ'משתנים'.
שורה 18:
במקרה של הדוגמה שלנו:
:- נוכל להשאיר את א' כ''משתנה'', ובהתאם לכל ערך שהוא יקבל - בין אם הערך 'אמת' ובין אם 'שקר', נוכל לדעת על הערך ב'.
באמצעות הכללה כזו ניתן לקבוע כי טיעונים הם [[תקפות (לוגיקה)|תקפים]], כאשר עבור כל הצבה של ערכי אמת לפסוקים האטומיים המרכיבים את ההנחות, אם בעקבות הצבה כזו ההנחות של הטיעון תְקֵיפות, הרי שגם המסקנה תְקֵיפה.
שורה 37 ⟵ 36:
===תחביר===
תחשיב פסוקים מסוים כולל קבוצה של '''פסוקים יסודיים''' או "פסוקים אטומיים", ומספר קָשַרים לוגיים סטנדרטיים. לדוגמה, נגדיר ש P מייצג את הטענה "הגביע הוא שלנו",
:'''שלילה''': <math>\neg</math> - זהו קשר אונרי, דהיינו הוא מקושר לאות פסוקית אחת בלבד. לדוגמה, <math>\neg P</math> מייצג את "הגביע הוא לא שלנו".
:'''הֵלחֵם''', או: '
:'''ניתוק''' או
:'''תנאי''' ("אם-אז"): <math>\to</math> - קשר בינארי, מקשר בין שני פסוקים. לדוגמה, הפסוק המורכב <math>P \to Q</math> מייצג את הטענה "אם הגביע הוא שלנו אזי אנחנו על המפה".
:'''תנאי כפול''' ("אם-ורק-אם", נקרא גם: "אך ורק אם"): <math>\leftrightarrow</math> - קשר בינארי, מקשר בין שני פסוקים. לדוגמה, הפסוק המורכב <math>P \leftrightarrow Q</math> מייצג את הטענה "הגביע הוא שלנו אם ורק אם אנחנו במפה".{{הערה|1=הביטוי העברי 'תנאי כפול' הוא מונח תלמודי משפטי, הנלמד מהחוזה התנ"כי בין משה לבין בני גד ובני ראובן, טרם הכניסה לארץ ישראל.}}
=== נוסחה בנויה כהלכה (נוסחה בנויה היטב) ===
באמצעות הֶקשֵרים, התחביר מאפשר יצירת רצפים סופיים של פסוקים יסודיים, קָשַרים וסימני סוגריים, אשר קריאתם היא חד-משמעית. רצף כזה נקרא [[נוסחה בנויה היטב]] (נקראת גם '''נוסחה בנויה כהלכה''' ובראשי תיבות '''נב"כ''', (Well Formed Formula או WFF).
נוסחה בנויה היטב מוגדרת בצורה ה[[רקורסיה|
* אם <math>P</math> הוא פסוק אטומי, אז <math>P</math> הוא נוסחה בנויה היטב.
* אם <math>A</math> היא נוסחה בנויה היטב, אז גם <math>(\neg A)</math> היא נוסחה בנויה היטב.
שורה 57 ⟵ 56:
יש לשים לב שהסוגריים חיוניים בדרך כלל, אם כי ניתן ומקובל להשמיט את זוג הסוגריים החיצוניים ביותר.
אפשר לבנות סוגים שונים של תחשיבי פסוקים, באמצעות בחירה שונה של הקשרים המשתתפים. לדוגמה, אפשר להחליף את הקשר "אם a אז b" ב-
=== תחשיב פסוקים שלם (קבוצת קשרים שלמה) ===
'''תחשיב פסוקים שלם''' (או '''
ישנם שני קשרים, שכל אחד מהם מהווה בעצמו "תחשיב פסוקים שלם", והם מכונים "הקשרים של שפר". קשרים אלו הם הקשרים "לא-וגם" ([[NAND לוגי|NAND]]) ו"לא-או" ([[NOR לוגי|NOR]]). התחביר הפורמלי של תחשיב הפסוקים המתמטי מתבסס על שני קשרים בלבד, "אם-אז" ו"לא"
=== הנחות יסוד (אקסיומות) וכללי היסק ===
שורה 74 ⟵ 73:
# <math>((p \to (q \to r)) \to ((p \to q) \to (p \to r)))</math>
# <math>((\neg p \to \neg q) \to (q \to p))</math>
[[כלל היסק]] אחד, [[מודוס פוננס]] (קיומו של תנאי ונביעת טענה מקיומו של התנאי), המוגדר כך:
שורה 80 ⟵ 78:
:ומ- <math>(p \to q)</math>
:הסק: <math>q</math>
במערכת זו הקשרים הקלאסיים האחרים, מלבד תנאי ושלילה, מוגדרים כך:
:<math>a \lor b</math> מוגדר כ- <math>\neg a \to b</math> (ובדומה, <math>\neg a \lor \neg b</math> מוגדר כ- <math>a \to \neg b</math>)
:<math>a \land b</math> מוגדר כ- <math>\neg(a \to \neg b)</math>
:<math>a \leftrightarrow b</math> מוגדר כ- <math>\neg((a \to b) \to \neg (b \to a))</math>
'''דוגמה להוכחה'''. ניתן להוכיח מהמערכת הזו בקלות ש <math>a \to a</math>, כך:
| |||