שינויים

טבלאות '''טבלת אמת. 8 אפשרויות ל''' מאפשרת לטפל בפסוק על-3 ידי בחינת כל האפשרויות לערכי אמת של האטומים המעורבים בו. טכנית, אם בפסוק יש n אטומים, הטבלה מורכבת מ-<math>\ 2^n</math> שורות, שבכל אחת מהן מקצים אפשרות אחרת לערכי האמת של האטומים. למשל, בטבלת האמת של <math>\ \varphi = ((A \vee B) \rightarrow A) \rightarrow \neg B</math> יש ארבע שורות, המתאימות לערכי האמת TT, TF, FT, FF עבור האטומים AB. בטבלה יש להוסיף גם את ערך האמת של כל תת-פסוק (במקרה דנן, <math>\ A \vee B</math> ו- <math>\ (A\vee B) \rightarrow A</math>), ובסופו של דבר את ערך האמת של הפסוק עצמו.  פסוק שערך האמת שלו הוא תמיד T, לכל הצבה של ערכי אמת באטומים, נקרא '''טאוטולוגיה'''. פסוק שערך האמת שלו הוא תמיד F נקרא '''סתירה'''.  לטאוטולוגיות חשיבות מיוחדת בלוגיקה, משום שהם מבטאות אמת צורנית אוניברסלית, שאינה תלויה בהצבת ערכי האמת. (ראו גם [http://xkcd.com/703/]). '''דוגמא'''. הפסוק <math>\ \varphi</math> שהוזכר לעיל הוא טאוטולוגיה. הוא קובע שאם מההנחה "A או B" אפשר להסיק את A, אז B מוכרח להיות שקרי. '''תרגיל'''. אם <math>\ \psi = \psi(A_1,\dots,A_n)</math> הוא פסוק טאוטולוגי התלוי באטומים <math>\ A_1,\dots,A_n</math>, אז כל פסוק המתקבל מהצבה של פסוקים כלשהם <math>\ \theta_1,\dots,\theta_n</math> במקום האטומים (באופן עקבי), גם הוא טאוטולוגי. חשוב להכיר טאוטולוגיות בסיסיות, ועוד יותר חשוב לדעת כיצד בודקים האם פסוק הוא טאוטולוגי, ולזהות פסוקים שאינם טאוטולוגיות. '''דוגמאות'''. להלן כמה טאוטולוגיות שקל לבדוק: * <math>\ (A \wedge B) \rightarrow A</math> (כלומר, אם A וגם B, אז בפרט A); * <math>\ A \rightarrow (A \vee B)</math> (אם A, אז בוודאי מתקיים A או B);* <math>\ A \vee \neg A</math> (זהו "כלל השלישי הנמנע": או שהתפוח אדום או שאינו אדום (כמובן, בתנאי שמגדירים היטב מתי תפוח הוא אדום));* <math>\ ((A\rightarrow B)\wedge (B\rightarrow C)) \rightarrow (A \rightarrow C)</math> (אם מ-A נובע B ומ-B נובע C, אז מ-A נובע C). אפשר להמציא עוד טאוטולוגיות כהנה וכהנה.'''תרגיל'''. הסבר מדוע פסוק שמופיעים בו רק הקשרים הלוגיים "או" ו"וגם" אינו יכול להיות טאוטולוגיה. הגדרתו של הקשר הלוגי "אם ורק אם" מובילה אותנו להגדרה שימושית:'''הגדרה'''. הפסוקים <math>\ \varphi, \varphi'</math> הם '''שקולים''' אם הפסוק <math>\ \varphi \leftrightarrow \varphi'</math> הוא טאוטולוגיה. במקרה כזה מסמנים <math>\ \varphi \equiv \varphi'</math>. '''דוגמאות'''. * <math>\ \neg\neg A \equiv A</math>* <math>\ (A\rightarrow B) \equiv ((\neg A) \vee B)</math>.* <math>\ (A \leftrightarrow B) \equiv ((A \wedge B)\vee((\neg A)\wedge (\neg B)</math>.* <math>\ (A \leftrightarrow B) \equiv (A \rightarrow B) \wedge (B \rightarrow A)</math>.* <math>\ (A \rightarrow B) \equiv ((\neg B) \rightarrow (\neg A))</math>. '''משפט'''. כל פסוק לוגי שקול לפסוק שבו מופיעים רק קשר השלילה והקשרים "או" ו"וגם".

=== שלילה ===חשוב לדעת לנסח במדוייק את השלילה של פסוק נתון. הדוגמאות הבסיסיות מסוג זה נקראות '''כללי דה-מורגן''': * <math>\ \neg (A \vee B) \equiv (\neg A) \wedge (\neg B)</math>.* <math>\ \neg (A \wedge B) \equiv (\neg A) \vee (\neg B)</math>. '''משפט'''. כל פסוק לוגי שקול להצבת האטומים <math>\ A_i</math> ושלילתם <math>\ \neg A_i</math>, בפסוק שבו מופיעים רק הקשרים "או" ו"וגם".