מתמטיקה דיסקרטית/קשרים לוגיים

הקבועים הלוגים הם אמת (מסומן ב-T או 1) ושקר (מסומן ב-F וב-0).

משתנה בוליאני (פסוק בסיסי) הוא ביטוי (מסומן ב-P) אשר יכול לקבל אחד מהערכים הלוגיים אפס או אחד.

קשרים לוגיים בינארים

קשרים לוגיים בינארים מגדירות את התוצר של שני ערכיים לוגיים:

קשר או

בקשר "או" אם אחד מהביטויים אמת נקבל תוצאה "אמת"

קשר או
p q
T T T
T F T
F T T
F F F

קשר וגם

קשר "וגם" נקבל אמת אם שני הביטוים אמת.

קשר וגם ( )
p q
T T T
T F F
F T F
F F F

קשר גרירה

בקשר גרירה לא נקבל פסוק אמת אם"ם P הוא ביטוי שקר ו-Q פסוק אמת.

קשר גרירה (pq)
p q pq
T T T
T F F
F T T
F F T

קשר שקילות

בקשר שקילות נקבל פסוק אמת כאשר P ו-Q זהים בערכים הלוגיים שלהם

קשר שקילות ( pq)
p q pq
T T T
T F F
F T F
F F T

קשר קסור

בקשר קסור נקבל פסוק אמת כאשר P ו-Q בעלי ערכים לוגים שונים זה מזה.

קשר קסור (pq)
p q pq
T T F
T F T
F T T
F F F

שלילה

שלילה ()
p ¬p
T F
F T

פסוק מורכב

פסוק מורכב הוא פסוק המורכב ממספר קשריים לוגיים, למשל pqq

פסוקים מורכבים A ו-B נקראים שקולים כאשר טבלאות האמת שלהם זהות. בין הפסוקים השקולים החשובים:

  1. ¬

בנית טבלת אמת לפסוק מורכב

בכדי לבנות טבלת אמת לביטויים נפריד כל ביטוי לשלבים ונבנה כל שלב.

             
T T T F F F F
T F F T F T T
F T F T T F T
F F F T T T T

ראה גם