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

לוגיקה בּוּליאנית הוא ענף בלוגיקה מתמטית ובאלגברה בוליאנית המקבל את שמו ממפתחה הראשון, ג'ורג' בול. ענף זה עוסק בפסוקים אלגבריים שערכי איבריהם אמת או שקר בלבד. הערכים מיוצגים על ידי הסימונים ${\displaystyle '1'\ }$ ("אמת") ו- ${\displaystyle '0'\ }$ ("שקר") בהתאמה. לענף שימוש רב בתחשיב פסוקים, באלקטרוניקה ובמדעי המחשב.

מבוא

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

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

היחוד לפונקציה בוליאנית

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

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

ערך מורחב – אינדוקציה מתמטית

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

נציב ${\displaystyle A\ =1}$:

${\displaystyle 1\ \cdot {\bar {1}}=0}$

נציב ${\displaystyle A\ =0}$:

${\displaystyle 0\ \cdot {\bar {0}}=0}$

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

רשימת פעולות נפוצות

ערך מורחב – פעולה בוליאנית

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

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

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

באמצעות הפעלת שלילה על הזהות

${\displaystyle A\ \cdot A\ =A\ +A\ =A\ }$ ניתן להוכיח ש NOT A=A NOR A=A NAND A

נמצא שאפשר להשתמש בפונקציה אחת (NOR או NAND) בלבד לכל הפעולות

פישוט ביטויים בוליאניים - לוגיים

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

זהויות חשובות

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

${\displaystyle A\ \cdot {\bar {A}}=0}$

${\displaystyle A\ +{\bar {A}}=1}$

${\displaystyle A\ \cdot A\ =A\ +A\ =A\ }$

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

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

חוקי פילוג

${\displaystyle A\cdot (B+C)=A\cdot B+A\cdot C}$

${\displaystyle A+(B\cdot C)=(A+B)\cdot (A+C)}$

נשים לב כי החוק הראשון זהה לחוק באלגברה הליניארית המוכרת לנו ואילו החוק השני לא קיים בה.

כללי דה-מורגן

ערך מורחב – כללי דה-מורגן

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

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

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

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

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

מפת קרנו

ערך מורחב – מפת קרנו

מפת קרנו

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

יישומים

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

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

מחשבים

ניתן לעשות שימוש בכללי הלוגיקה הבוליאנית על מנת לפשט תנאים ולולאות. בתוכנות עריכה של שפות תכנות, ניתן להגדיר משתנה בוליאני שערכו אמת או שקר. פונקציה רווחת היא if הבודקת האם מתקיים שביטוי מסוים הוא אמת או שקר, ובהתאם מוציעה לפועל פקודה/ות מסוימת, אחרת (else) מוציאה לפועל פקודה/ות אחרת. למשל (בצורה של פסאודו קוד) :

if age > 18

print ("בגיר")

else

print ("קטין")

קישורים חיצוניים

• אלגברה בוליאנית, באנגלית