תחשיב פסוקים הוא מערכת פורמלית שמייצגת קשרים לוגיים בין ערכי אמת של פסוקים. המערכת בוחנת רק את תוקף הטיעון לפי ערכי האמת, ולא את התוכן או האמת הממשית של הפסוקים האטומיים.
בדוגמה פשוטה: "אם חרק הוא נמלה אזי הוא חי בתל נמלים" ו"החרק הוא נמלה" מובילים באופן מיידי למסקנה שהחרק חי בתל. תחשיב הפסוקים בוחן כשלים כאלה על פי ערכי אמת בלבד. אפשר גם להשאיר משתנים ללא פירוש ולבדוק תקפות עבור כל הצבה של ערכי אמת.
הצרנה היא המרת טענות למשפטים סימבוליים. כל משפט בסיסי מסומן באות קבועה, והאות מייצגת את הטענה בכל מקום בטיעון. הקשרים הלוגיים מיוצגים בסימנים מוסכמים.
הקשרים המרכזיים הם:
- שלילה (¬): מקשרת ליחידת פסוק אחת והופכת אמת לשקר ולהפך.
- ההלחם / וגם (∧): מחבר בין שני פסוקים, אומר ששניהם אמיתיים.
- ניתוק / או (∨): מחבר בין שני פסוקים, אומר שאחד מהם לפחות אמיתי.
- תנאי / אם-אז (→): אומר שאם הפסוק הראשון נכון אז השני גם נכון.
- תנאי כפול / אם ורק אם: אומר ששני הפסוקים נכונים יחד או שקריים יחד.
נוסחה בנויה היטב היא רצף סימנים שקורא אותו בצורה אחת בלבד. ההגדרה רקורסיבית מאפשרת לבדוק אם רצף הוא נוסחה. סוגריים בדרך כלל חיוניים כדי למנוע עמימות.
קבוצת קשרים שלמה יכולה לבטא כל פונקציה בוליאנית. הקשרים NAND ו-NOR (שפר) כל אחד מהם עצמאי ומהווה קבוצה שלמה. אפשר גם להסתמך על "אם-אז" ו"לא" בלבד ולהגדיר עמם את שאר הקשרים.
יש מערכות אקסיומטיות פשוטות עם שני קשרים בלבד. יאן לוקאסייביץ' הציע מערכת כזו עם שלוש אקסיומות וכלל היסק מודוס פוננס (אם P→Q ו-P אז Q). שאר הקשרים מוגדרים דרכן.
במסגרת הסמנטיקה כל פסוק יסודי מקבל ערך אמת אחיד בכל ההופעות שלו. כל קשר הוא פונקציית-אמת שמקבלת ערכי אמת ומחזירה ערך יחיד. טבלה שמציגה את כל ההצבות נקראת טבלת אמת.
מונחים חשובים:
- טאוטולוגיה: פסוק שאמיתי בכל הצבה.
- סתירה: פסוק ששקרי בכל הצבה.
- קונטינגנטי: פסוק שאינו טאוטולוגיה ואינו סתירה.
- עקיבות: קבוצה עקבית אם קיימת הצבה שכולם בה אמיתיים.
טבלאות אמת בודקות אם יש הצבה שבה ההנחות אמיתיות והמסקנה שקרית. דוגמה: טיעון עם הנחות "השמש זורחת" ו"אם השמש זורחת אז האגם לא קפוא" לא מוכיח בהכרח ש"הברווזים לא עפים"; טבלת אמת יכולה להראות שורה נגדית.
מערכות הוכחה מבוססות על כללים תחביריים בלבד. דדוקציה טבעית מכילה לכל קשר כלל הכנסה וכלל הוצאה. מערכת כזו היא נאותה (כל הניתן להוכיח אמת) ושלמה (כל אמת ניתנת להוכחה).
כלל הכנסה לתנאי: אם מתוך P ו-Q מסיקים P→Q. כלל סילוק להלחם: מתוך P∧Q מסיקים P.
מערכת הילברט משתמשת באלף-בית של משתנים פורמליים ובקשרים "לא" ו"אם-אז". היא כוללת שלוש אקסיומות וכלל היסק אחד, מודוס פוננס. גם מערכת זו נאותה ושלמה.
תחשיב פסוקים הוא דרך רשמית לבדוק טענות אמיתיות או שקריות. המערכת מסתכלת רק על "אמת" ו"שקר", לא על התוכן.
אם אומרים: "אם חרק הוא נמלה אז הוא חי בתל" ו"החרק הוא נמלה", אז המסקנה היא שהוא חי בתל. זהו סוג של חשיבה לוגית פשוטה.
משנים משפטים לאותיות קבועות. כל אות מייצגת טענה אחת.
קשרים חשובים:
- שלילה: אומר "לא".
- וגם (הלחם): אומר ששני דברים נכונים.
- או: אומר שאחד מהדברים נכון.
- אם-אז: אומר שאם האחד נכון אז השני נכון.
נוסחאות נכונות נכתבות כך שאי אפשר לקרוא אותן בשתי דרכים שונות.
טבלת אמת מראה לכל אפשרות של אמת ושקר מה יינתן במשפט המורכב. יש משפטים שאמיתיים תמיד, אלה נקראים טאוטולוגיות. יש משפטים ששקריים תמיד, אלה סתירות.
טבלאות אמת עוזרות לבדוק אם הנחות נכונות ובכל זאת המסקנה שגויה. זאת דרך טובה למצוא שגיאות בלוגיקה.
יש מערכות שמראות איך להוכיח דברים חוקית. לכל קשר יש כללים להכניסו ולהוציאו, וכך בונים הוכחות נכונות.
תגובות גולשים