לוגיקה בוליאנית

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

לוגיקה בוליאנית הוא ענף בלוגיקה מתמטית ובאלגברה הבוליאנית. ענף זה עוסק בפסוקים אלגבריים שערכי איבריהם אמת או שקר בלבד. הערכים מיוצגים על ידי הסימונים  '1'\ ו-  '0'\ בהתאמה. לענף שימוש רב בתחשיב פסוקים, באלקטרוניקה ובמדעי המחשב.

מבוא[עריכת קוד מקור | עריכה]

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

תכונה חשובה בלוגיקה בוליאנית היא תכונת הדואליות. לדוגמה: הפעולה הדואלית של (A+B) היא '('A'B). כלומר אם A = 1 ו B = 0 אזי התוצאה היא 1 בשני הביטויים ובהתאמה לשאר הפעולות.

היחוד לפונקציה בוליאנית[עריכת קוד מקור | עריכה]

בעוד ופונקציות אחרות המוגדרות מעל קבוצות כגון הטבעיים, השלמים, הראציונליים, הממשיים או המרוכבים ויכולות לקבל מספר ערכים אינסופי, פונקציות בוליאניות-לוגיות מוגדרות, כאמור, רק מעל הקבוצה \left\{ 0,1 \right\} (שהיא, הלכה למעשה, שדה השלמים המודולריים \mathbb{Z}_2), כמו כן המשתנים המרכיבים אותן, מכאן נובע כי לכל פונקציה שכזו יש רק מספר אפשרויות סופי של "הצבות", כלומר- ישנו מספר קבוע של צירופים אפשריים במבוא הפונקציה. לפונקציה עם משתנה אחד יש רק שני צירופי מבואות אפשריים, לפונקציה עם שני משתנים ישנם רק ארבעה צירופי מבואות אפשריים ולפונקציה עם שלושה מבואות רק שמונה צירופי מבואות אפשריים, כאשר באופן כללי אם ישנה פונקציה בוליאנית-לוגית עם מספר משתנים  n\ יהא מספר צירופי המבואות האפשריים שלה  2^n\ (לא במקרה, זוהי גם נוסחה בסיסית לרוחב פס נתונים במחשב כאשר  n\ מבטא מספר סיביות המידע). היות ולכל פונקציה בוליאנית-לוגית ישנו מספר קומבינציות מבוא סופי, נתן לרכז את כל צירופי המבואות האפשריים ומוצאי הפונקציה התואמים להם בטבלה אשר נקראת טבלת אמת, וזאת בניגוד לרב הפונקציות האחרות במתמטיקה, בהן כדי להציג את כל צירופי המבואות והמוצאים האפשריים יש להיעזר בביטויים אלגבריים (ברם, זוהי תכונה כללית של שדות שלמים מודולריים, אך קיומם של שני איברים בלבד ב- \mathbb{Z}_2 מפשטת מאוד את הניתוח במקרה זה).

הוכחת ביטויים באינדוקציה שלמה[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – אינדוקציה מתמטית

למספר הצירופים הסופי השלכה נוספת: בעוד וברב ענפי המתמטיקה האחרים יש להוכיח טענה על ידי הצגת ביטויים המיצגים את כל המצבים האפשריים, דבר שהוא באופן יחסי אבסטרקטי משהו, כאשר מספר המבואות הוא סופי נתן להוכיח טענה בוליאנית-לוגית על ידי אינדוקציה שלמה, כלומר הצבת כל הצירופים האפשריים ובדיקה כי הטענה אכן מתקימת בנוגע אליהם. נוכיח בדרך זו את הזהות הבאה:  A\ \cdot  \bar{A} = 0.

נציב: A\ = 1:

 1\ \cdot  \bar{1} = 0


נציב:  A\ = 0:

 0\ \cdot  \bar{0} = 0

בכך הוכחנו את נכונות הזהות עבור כל  A\ לוגי כלשהו: '0', '1', או ביטוי בוליאני-לוגי. באופן דומה, ניתן להוכיח זהויות גם עבור יותר ממשתנה בוליאני-לוגי אחד.

רשימת פעולות נפוצות[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – פעולה בוליאנית

בנוסף לשלושת הפעילויות הבסיסיות, ישנן עוד מספר פעולות בוליאניות שימושיות נוספות אשר את כולן נתן "לבנות" מן הפעולות הבסיסיות יותר, והן:

שם הפעולה סוג הפעולה סימון הפעולה
NOR פעולה בינארית \overline{A + B}
NAND פעולה בינארית \overline{A \cdot B}
XOR פעולה בינארית  A\ \oplus B\
XNOR פעולה בינארית \overline{ A\ \oplus B\ }

נתן להוכיח כי בעזרת כללי דה-מורגן והזהות עבור \overline{\overline{A}}
 = A\ , נתן להרכיב את כל הביטויים הבוליאניים-לוגיים על ידי שימוש ב- NAND לוגי בלבד או NOR לוגי בלבד.

פישוט ביטויים בוליאניים- לוגיים[עריכת קוד מקור | עריכה]

לעתים, ביטויים בוליאניים לוגיים עשויים להיות ארוכים מאוד ומסורבלים מאוד. ישנן מספר שיטות בהן נעשה שימוש על מנת לאפשר צמצום של ביטויים בולאיניים.

זהויות חשובות[עריכת קוד מקור | עריכה]

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

 A\ \cdot  \bar{A} = 0

 A\ +  \bar{A} = 1

 A\ \cdot  A\ =  A\ +  A\ =  A\

 A\ \oplus B\ = A \cdot  \bar{B} + \ B \cdot  \bar{A}

\overline{ A\ \oplus B\ }= \overline{A \cdot  \bar{B} + \ B \cdot  \bar{A}}=  A\ \cdot B\ + \bar{A} \cdot \bar{B}\


כללי דה-מורגן[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – כללי דה-מורגן

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

\overline{p + q}=\bar{p}\cdot \bar{q}

\overline{p \cdot q}=\bar{p} + \bar{q}

בעזרת פעולות אלה נתן להמיר כל ביטוי כך שיתבסס על פעולות NAND ו- NOR בלבד על ידי הפעלת שלילה כפולה (שאיננה משנה את ערך הביטוי) על כל הביטוי ושימוש בזהויות אלה עבור אחת מפעולות השלילה.

כלל דה-מורגן הוא המחשה של מושג ה'דואליות' שהוזכר במבוא לעיל.

מפת קרנו[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – מפת קרנו
מפת קרנו

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

יישומים[עריכת קוד מקור | עריכה]

לתורת הלוגיקה הבוליאנית מספר ישומים חשובים, ביניהם:

  • תחשיב פסוקים - נתן לערוך שימוש במשתנים בוליאניים כתוצאות של טענות ופסוקים מתמטיים ובכך לפשט עבודות שונות בתורת הלוגיקה המתמטית.
  • מיתוג ואלקטרוניקה ספרתית - שימוש נרחב מאוד בתורת הלוגיקה הבוליאנית נעשה בתחומי המיתוג והאלקטרוניקה הספרתית. נהוג לעשות שימוש ב- '1' כמיצג עבור "מתח גבוה" וב-'0' עבור "מתח נמוך" (לרב 5 וולט ו- 0 וולט או מעט יותר, בהתאמה). בעזרת כלים מתחום הלוגיקה הבוליאנית נעשה שימוש על מנת לתאר, לתכנן ולפשט מבנה של מערכות אלקטרונית-לוגיות רבות, בעיקר מבוססות שערים לוגיים, ביניהן מונים, דלגלגים ו-מרבבים.
  • מחשבים - נתן לעשות שימוש בכללי הלוגיקה הבוליאנית על מנת לפשט תנאים ולולאות.