קשר לוגי
ערך מחפש מקורות | |
קַשָּׁר לוגי הוא פונקציה המייצרת מקבוצה של פסוקים לוגיים, או תבניות לוגיות פסוק חדש או תבנית חדשה בהתאמה. קשרים משמשים בתחשיב הפסוקים ובתחשיב הפרדיקטים כדי לייצג פעולות לוגיות כגון "וגם", "לא" ו"אם-אז".
פסוק אמיתי תמיד נקרא טאוטולוגיה (למשל ), ופסוק שקרי תמיד נקרא סתירה (למשל ).
כל קַשָּׁר לוגי מייצג פעולה בוליאנית על ערכי האמת של האיברים המתקבלים כקלט, ומקושרת אליו טבלת אמת ספציפית. כדי לחשב את ערך האמת של הפסוק, או התבנית הנוצרים על ידי הקשר, משתמשים בערכי האמת של הפסוקים, או התבניות המתקבלים כקלט, ובטבלת האמת המשויכת לקשר.
קשרים לוגיים מסווגים על פי מספר הפסוקים/תבניות שהם מקבלים כקלט. הקשרים השימושיים הם אונאריים (דהיינו, מקבלים כקלט פסוק יחיד/ תבנית אחת), או בינאריים (דהיינו, מקבלים כקלט 2 פסוקים/תבניות). קשרים טרנאריים (המקבלים 3 פסוקים/תבניות) ומורכבים יותר אינם מקובלים בלוגיקה הפורמלית.
באופן מסורתי, מוגדרים בלוגיקה מתמטית חמישה קשרים "בסיסיים":
את כל חמשת הקשרים ניתן לבטא בעזרת NAND בלבד וכן בעזרת NOR בלבד. עם זאת, כל טבלת אמת מייצגת קשר לוגי, כך שישנם ארבעה קשרים אונאריים ו־16 קשרים בינאריים, ובתחומים כגון האלגברה הבוליאנית נעשה שימוש גם בקשרים נוספים, בהם XNOR ו-XOR.
לכל אחד מן הקשרים קיים סימון מקובל במתמטיקה:
- לא a:
- a וגם b:
- a או b:
- אם a אז b:
- a אם ורק אם b:
טבלת אמת של כל אחד מהקשרים:
T | T | T | T | F | F | T | T |
F | F | T | F | T | F | F | T |
F | T | T | F | F | T | T | F |
T | T | F | F | T | T | F | F |