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

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

מבוא

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

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

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

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

היות שלכל פונקציה בוליאנית–לוגית ישנו מספר קומבינציות מבוא סופי, נתן לרכז את כל צירופי המבואות האפשריים ומוצאי הפונקציה התואמים להם בטבלה אשר נקראת טבלת אמת, וזאת בניגוד לרב הפונקציות האחרות במתמטיקה, בהן כדי להציג את כל צירופי המבואות והמוצאים האפשריים יש להיעזר בביטויים אלגבריים (ברם, זוהי תכונה כללית של שדות שלמים מודולריים, אך קיומם של שני אברים בלבד ב־ ${\mathbb{\mathbb{Z}}}_2$ מפשטת מאד את הניתוח במקרה זה).

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

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

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

נוכיח בדרך זו את הזהות $A\cdot \overline{A}=0$ .

$A\cdot \overline{A}$	$A$
$1\cdot \overline{1}=0$	1
$0\cdot \overline{0}=0$	0

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

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

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

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

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

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

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

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

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

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

$\begin{array}{r}A\cdot \overline{A}=0\\ A+\overline{A}=1\\ A\cdot A=A+A=A\\ A\oplus B=A\cdot \overline{B}+B\cdot \overline{A}\\ \overline{A\oplus B}=A\cdot B+\overline{A}\cdot \overline{B}\end{array}$

חוקי פילוג

$\begin{array}{r}A\cdot (B+C)=A\cdot B+A\cdot C\\ A+(B\cdot C)=(A+B)\cdot (A+C)\end{array}$

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

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

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

$\begin{array}{r}\overline{p+q}=\overline{p}\cdot \overline{q}\\ \overline{p\cdot q}=\overline{p}+\overline{q}\end{array}$

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

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

מפת קרנו

מפת קרנו

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

יישומים

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

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0