רקע תיאורטי

הצרנה

נחזור על דוגמת הים מן הסעיף הקודם:

צבענו בצבעים נפרדים את הטענות החוזרות בהיסק ואת המילים רק אם, ו- ו.
כעת, נשאיר את "שלד ההיסק" ללא שינוי ונחליף את תוכן ההנחות והמסקנה:

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

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

נשתמש בשפה חדשה לייצוג היסקים. האלף-בית של השפה החדשה מכיל את האותיות הלטיניות הקטנות (p, q, r, …) ואת ששת הסמלים לא, וגם, או, אם-אז, (, ).

הסמלים לא, וגם, או, אם-אז נקראים קשרים לוגיים (logical connectives). לא הוא קשר השלילה, המקביל לביטויים הבאים משפת הדיבור: לא, זה לא נכון ש. וגם נקרא קשר הגימום (מלשון "גם"), והוא מקביל לו' החיבור ולמילה וגם. או הוא קשר האיווי (מלשון "או"). אם-אז הוא קשר האימוז (מלשון "אם...אז...") והוא מקביל בין היתר לביטויים כמו ...אם...., אם... אז....

הסמלים המקובלים לציון הקשרים הלוגיים הם רבים:
שלילה: ~ , !
גימום: ^ , &
איווי: |
אם-אז: -->

בשפה החדשה נוכל להצרין גם טענות פשוטות וגם טענות מורכבות. טענות מורכבות מכילות טענה אחת או שתיים אשר מחוברות אל אחד הקשרים הלוגיים. למשל: לא נכון שהיום יום שלישי, אני אוהב שוקולד ועוגות גבינה, בוא אלי או שאבוא אליך, אם תרצו אין זו אגדה. טענות פשוטות הן טענות שלא ניתן לפרק אותן לטענות המחוברות על ידי קשרים.

נצרין טענות פשוטות באמצעות האותיות הלטיניות:

p – היום יום שלישי
q – בוא אלי
r – אבוא אליך

נצרין טענות מורכבות בעזרת הקשרים הלוגיים:

לא p – לא נכון שהיום יום שלישי
q או r – בוא אלי או שאבוא אליך

נשתמש בסוגריים לציון טווח ההפעלה של הקשרים אם הטענה איננה חד-משמעית אחרת. למשל, את הטענה המורכבת לא p או q אפשר להבין בשתי דרכים שונות:

לא (p או q)
(לא p) או q

נזדקק לסוגריים בהצרנות עם יותר מקשר לוגי אחד על מנת להצרין בדיוק את טענותינו.

על מנת לבדוק תקפות של היסקים עלינו לדעת את ערכי האמת של ההנחות ושל המסקנה. ערך האמת של טענה פשוטה יכול להיות T או F. אך מהו ערך האמת של טענה מורכבת?
הקשרים הלוגיים שהצגנו הם קשרי ערכי אמת: הם קובעים את ערך האמת של הטענה המורכבת על סמך ערכי האמת של הטענות המרכיבות אותה. כל אחד מהקשרים מגדיר מהו ערך האמת של הטענה המורכבת בעזרתו עבור כל צירוף של ערכי אמת למרכיביה. הטבלה הבאה מציגה את ההגדרות של כל הקשרים שלמדנו:

שאלה: מה מספר השורות בטבלת האמת של טענה המורכבת מ-N טענות פשוטות?
תשובה: 2^N (2 בחזקת N). זאת מכיוון שלכל טענה פשוטה יתכנו שני ערכי אמת (T או F), וזאת לכל אחת מ-N הטענות הפשוטות המרכיבות את הטענה המורכבת.
כל שורה בטבלה מייצגת אפשרות אחת, מצב עניינים אחד, עולם אפשרי אחד.

דרך אחת לבדוק תקפות היא להשתמש בטבלת אמת. אחרי שמצרינים את ההנחות ואת המסקנה, בונים טבלת אמת עבור כל האפשרויות של ערכי אמת לטענות הפשוטות,להנחות ולמסקנות. בודקים את כל השורות שבהן כל ההנחות יחד אמיתיות. בשורות אלה בודקים את ערך האמת של המסקנה. אם מוצאים אפילו שורה אחת שבה ההנחות כולן T והמסקנה היא F, ההיסק הוא היסק בטל. אחרת, ההיסק תקף.

בדיקת תקפות בעזרת טבלאות אמת היא שיטה טובה ובטוחה, אך מסורבלת. ככל שיש יותר טענות פשוטות קשה לבנות את הטבלה ולמלא את כל האפשרויות (מספיק שיש 6 טענות פשוטות ובטבלה תהיינה 64 שורות!).
בסעיף הבא נלמד דרך אחרת: הוכחת תקפות בעזרת כללי היסק.

מבוא

נושאים בסיסיים

נושאים מתקדמים

סיכום