אלגברה בוליאנית (מבנה אלגברי)

במתמטיקה, ובמיוחד בתורת הקבוצות, אלגברה בּוּליאנית הוא סוג של מבנה אלגברי, הקרוי על-שמו של המתמטיקאי האנגלי ג'ורג' בול (1815–1864). זהו גם שמו של התחום "אלגברה בוליאנית" העוסק בחקר אלגברות בוליאניות.

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

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

אלגברה בוליאנית נקראת גם סריג בוליאני. ניתן לראות את הקשר עם תורת הסריגים באמצעות ההתייחסות ליחס ההכלה של קבוצות $\,A\subseteq B$ כיחס הסדר $\,A\leq B$. נתבונן למשל בסריג המכיל את כל תת-הקבוצות של הקבוצה $\{x,y,z\}$. קבוצה זו סדורה חלקית באמצעות יחס ההכלה. לכן, לדוגמה, מתקיים $\,\{x\}\leq \{x,y\}$. בנוסף לכך, לכל זוג איברים, לדוגמה $\,p=\{x,y\}\quad q=\{y,z\}$ קיים חסם עליון (במקרה זה $\,\{x,y,z\}$) וחסם תחתון (במקרה זה $\,\{y\}$). ניתן לראות בפעולות החסם העליון והתחתון את המקבילות של פעולות האיחוד והחיתוך בהתאמה.

הגדרה פורמלית

אלגברה בוליאנית היא קבוצה A ביחד עם 2 פעולות בינאריות $\,\land$ (הנקראת וגם) ו-$\,\lor$ (הנקראת או) ופעולה אונארית המסומנת ב-$\,\lnot$ (הנקראת שלילה). בנוסף קיים ב-A קבוע המסומן ב-0 וקבוע המסומן ב-1, כך שהאקסיומות הבאות מתקיימות: לכל שלושה איברים a, b ו-c ב-A,

$a\lor (b\lor c)=(a\lor b)\lor c$	$a\land (b\land c)=(a\land b)\land c$	אסוציאטיביות
$a\lor b=b\lor a$	$a\land b=b\land a$	קומוטטיביות
$a\lor (a\land b)=a$	$a\land (a\lor b)=a$	חוק הספיגה
$a\lor (b\land c)=(a\lor b)\land (a\lor c)$	$a\land (b\lor c)=(a\land b)\lor (a\land c)$	דיסטריבוטיביות
$a\lor \lnot a=1$	$a\land \lnot a=0$	משלים

משמעות האסוציאטיביות, הקומוטטיביות ואקסיומת הספיגה היא שהמבנה (A, $\land$, $\lor$) הוא סריג. בסריג ניתן להוכיח שאם אחד מחוקי הדיסטריבוטיביות מתקיים אז גם השני מתקיים. לפיכך, ניתן לומר שאלגברה בוליאנית היא פשוט סריג דיסטריבוטיבי עם השלמה. מאקסיומות האלגברה הבוליאנית ניתן להוכיח כי האיבר הקטן ביותר 0, האיבר הגדול ביותר 1 וכן המשלים a¬ של איבר a כלשהו נקבעים בצורה יחידה. בנוסף, ניתן להוכיח כי בכל אלגברה בוליאנית A, לכל a ו-b בA מתקיימות הזהויות הבאות:

$a\lor a=a$	$a\land a=a$	אידמפוטנטיות
$a\lor 0=a$	$a\land 1=a$	הסריג חסום
$a\lor 1=1$	$a\land 0=0$
$\lnot 0=1$	$\lnot 1=0$	0 ו-1 משלימים הדדית
$\lnot (a\lor b)=\lnot a\land \lnot b$	$\lnot (a\land b)=\lnot a\lor \lnot b$	כללי דה מורגן
$\lnot \lnot a=a$		המשלים הוא אינוולוציה

את הפעולות ניתן, כאמור, לפרש בשתי דרכים: מחד, אלו פעולות בין קבוצות, כאשר $\,\land$ היא פעולת החיתוך, $\,\lor$ היא פעולת האיחוד, ו-$\,\lnot$ היא פעולת המשלים. מאידך, אלו פעולות לוגיות, כאשר $\,\land$ היא הקשר 'וגם', $\,\lor$ היא הקשר 'או', ו-$\,\lnot$ היא קשר השלילה. במקרה הראשון 0 היא הקבוצה הריקה, ובמקרה השני – שקר. לדוגמה, הטענה הלוגית לפיה לא ייתכן שגם a וגם שלילתה יהיו נכונות, $a\land (\lnot a)={\mbox{FALSE}},$, מקבילה לטענה בתורת הקבוצות לפיה החיתוך של A עם משלימתה שווה לקבוצה הריקה: $A\cap (A^{C})=\varnothing$.

דוגמאות

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

∧ 0 1 0 0 0 1 0 1

∨ 0 1 0 0 1 1 1 1

a 0 1 a¬ 1 0

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

• • (a ∨ b) ∧ (¬a ∨ c) ∧ (b ∨ c) ≡ (a ∨ b) ∧ (¬a ∨ c)
  • (a ∧ b) ∨ (¬a ∧ c) ∨ (b ∧ c) ≡ (a ∧ b) ∨ (¬a ∧ c)

• אם מסתכלים על תחשיב הפסוקים עם κ פסוקים יסודיים, ויוצרים את האלגברה המתקבלת מהפעולות "או", "וגם" ו"שלילה", כאשר מזהים שני פסוקים כשווים אם ורק אם הם טאוטולוגים, מקבלים אלגברה בוליאנית. זוהי למעשה האלגברה הבוליאנית החופשית עם κ יוצרים.
• קבוצת החזקה (כלומר קבוצת כל תת-הקבוצות) של קבוצה לא ריקה S עם פעולות האיחוד החיתוך והמשלים ביחס ל-S היא אלגברה בוליאנית. איבר ה-0 הוא הקבוצה הריקה והאיבר 1 הוא הקבוצה S.
• קבוצת כל התת-קבוצות של קבוצה נתונה S שהן סופיות או קו-סופיות (כלומר משלימות של קבוצה סופית) היא אלגברה בוליאנית. זוהי למעשה תת-אלגברה של האלגברה מהדוגמה הקודמת.
• לכל מספר טבעי n, קבוצת כל המחלקים החיוביים של n היא סריג דיסטריבוטיבי אם מגדירים ש-a ≤ b אם ורק אם a | b. סריג זה הוא אלגברה בוליאנית אם ורק אם n הוא מספר חופשי מריבועים (כלומר אין אף ריבוע של מספר גדול מ-1 המחלק את n).
• בהינתן מרחב טופולוגי X, אוסף תת-הקבוצות של X שהן גם פתוחות וגם סגורות מהווה אלגברה בוליאנית ביחס לפעולות האיחוד, החיתוך, והמשלים.
• אם R הוא חוג כלשהו, אז קבוצת המרכז האידמפוטנטי של R המוגדרת על ידי:

$\,A=\{e\in R:e^{2}=e,ex=xe,\forall x\in R\}$

היא אלגברה בוליאנית ביחס לפעולות e ∨ f := e + f − ef ו e ∧ f := ef.

אלגברה בוליאנית כקבוצה סדורה חלקית

סריג בוליאני של תת-קבוצות

כמו כל סריג, אלגברה בוליאנית (A, $\land$, $\lor$) מגדירה סדר חלקי על A על ידי כך שמגדירים a ≤ b אם ורק אם $\,a=a\land b$ (או תנאי השקול לכך – $\,b=a\lor b$). קל להבין תנאי זה באלגברה הבוליאנית של קבוצת החזקה של קבוצה נתונה: באלגברה זו מתקיים a ≤ b אם ורק אם $\,a=a\cap b$, או במילים אחרות אם ורק אם $\,a\subseteq b$ (באלגברה זו, כזכור, a ו-b הן תת-קבוצות של קבוצה נתונה S). למעשה, ניתן להגדיר אלגברה בוליאנית כסריג דיסטריבוטיבי (A, ≤) (כאשר מתייחסים ל-A כקבוצה סדורה חלקית) עם איבר קטן ביותר 0 ואיבר גדול ביותר 1 כך שלכל איבר x קיים משלים x¬ כך ש

x $\,\land$ ¬x = 0 וכמו כן x $\,\lor$ ¬x = 1

כאשר $\,\land$ ו-$\,\lor$ מסמנים את האינפימום והסופרמום של שני איברים.

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

עיקרון הדואליות

האלגברה המתקבלת מהחלפה בין הפעולות $\,\land$ ו-$\,\lor$ ומהחלפת האיברים 0 ו-1 זה בזה אף היא אלגברה בוליאנית. יתר על כן, כל טענה אלגברית הנכונה באלגבראות בוליאניות ניתנת להתמרה לטענה דואלית על ידי החלפת $\,\land$ ו-$\,\lor$ זה בזה והחלפה של הופעות של האיברים 0 ו-1 זה בזה. טענה היא נכונה אם ורק אם הטענה הדואלית לה נכונה. לדוגמה, הטענה הדואלית לטענה $\,a\lor 1=1$ היא הטענה $\,a\land 0=0$.

שיטות סימון נוספות

לפעולות של האלגברה הבוליאנית יש מספר סימונים מקובלים. לעיתים הן מסומנות פשוט על ידי המילים האנגליות AND, OR ו-NOT. בתיאור מעגלים דיגיטליים רווח השימוש גם בסימונים NOR, NAND ו-XOR. מתמטיקאים, מהנדסים ומתכנתים נוהגים לעיתים קרובות להשתמש בסימון + בשביל OR, בסימון · בשביל AND, ובקו מעל הביטוי (מכונה לעיתים "גג") בשביל לסמן את שלילתו.

הומומורפיזמים ואיזומורפיזמים

הומומורפיזם בין האלגבראות הבוליאניות A ו-B הוא פונקציה $\,f:A\rightarrow B$ כך שלכל זוג איברים a ו-b בA מתקיים:

• $\,f(a\land b)=f(a)\land f(b)$
• $\,f(a\lor b)=f(a)\lor f(b)$
• $\,f(0)=0$
• $\,f(1)=1$

מתנאים אלו ומאקסיומות האלגברה הבוליאנית נובע כי, בנוסף, לכל a בA מתקיים:

• $\,f(\lnot a)=\lnot f(a)$.

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

חוגים בוליאניים, אידיאלים ומסננים

בהינתן אלגברה בוליאנית (A, $\land$, $\lor$, $\lnot$) ניתן להגדיר חוג (A, +, *) על ידי כך שמגדירים $\,a+b=(a\land \lnot b)\lor (b\land \lnot a)$ (פעולה זו נקראת הפרש סימטרי במקרה של קבוצות, או XOR במקרה של לוגיקה) ו-$\,a*b=a\land b$. איבר ה-0 של החוג מתלכד עם איבר ה-0 של האלגברה הבוליאנית, ואיבר היחידה של החוג שווה לאיבר 1 באלגברה הבוליאנית. בדרך זו מתקבל חוג A שמקיים שלכל x ב-A מתקיים $\,x^{2}=x$. חוג המקיים שוויון זה נקרא חוג בוליאני. בחוג בוליאני, לכל a מתקיים ש-$a+a=0$.

להפך, בהינתן חוג בוליאני A, נוכל להפוך את A לאלגברה בוליאנית על ידי כך שנגדיר $\,x\lor y=x+y+xy$, $\neg a=1+a$ ו-$\,x\land y=xy$. מכיוון ששתי פעולות אלה הופכיות אחת של השנייה, הרי שנוכל לומר כי כל אלגברה בוליאנית נוצרת מחוג בוליאני, ולהפך. יתר על כן, העתקה f בין אלגבראות בוליאניות היא הומומורפיזם של אלגבראות בוליאניות אם ורק אם היא הומומורפיזם של חוגים עבור החוגים הבוליאנים המתאימים. במילים אחרות, הקטגוריה של אלגבראות בוליאניות שקולה לקטגוריה של חוגים בוליאניים.

אידיאל I באלגברה בוליאנית A הוא תת-קבוצה של A כך שלכל x ו-y ב-I מתקיים ש-$\,x\lor y\in I$, וכן לכל x ב-I ולכל a ב-A מתקיים ש-$\,a\land x\in I$. מושג זה מתלכד עם המושג אידיאל בתורת החוגים כאשר A מתייחסים אל A כאל חוג בוליאני. אידיאל I השונה מ-A נקרא ראשוני אם כל פעם שמתקיים $\,x\land y\in I$ אז לפחות אחד מבין x ו-y שייך ל-I. אידיאל I השונה מ-A נקרא מקסימלי אם A הוא האידיאל היחיד המכיל את I. גם מושגים אלו מתלכדים עם המושגים המקבילים של אידיאל ראשוני ואידיאל מקסימלי מתורת החוגים.

המונח הדואלי למושג האידיאל נקרא מסנן (או פילטר). לפיכך, תת-קבוצה F של אלגברה בוליאנית A נקראת מסנן אם לכל זוג x ו-y ב-F מתקיים ש $\,x\land y\in F$ ולכל x ב-F ולכל a ב-A מתקיים ש-$\,a\lor x\in F$.

הצגות של אלגבראות בוליאניות

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

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

שלמות ודיסטריביוטיביות

אלגברה בוליאנית נקראת שלמה אם לכל תת-קבוצה שלה יש חסם תחתון מקסימלי (אינפימום) וחסם עליון מינימלי. המשמעות של השלמות היא שניתן להרחיב את הפעולות $\lor ,\land$ גם לקבוצות אינסופיות. למשל, אלגברת כל תת-הקבוצות של קבוצה S היא שלמה, בעוד שהאלגברה הבוליאנית של כל תת-הקבוצות הסופיות והקו-סופיות של קבוצה אינסופית איננה שלמה.

כל אלגברה בוליאנית ניתן להשלים באופן יחיד, עד כדי איזומורפיזם, לאלגברה בוליאנית שלמה, שנוצרת מתוך איברי האלגברה המקורית באמצעות הפעולות $\lor ,\land$, כאשר אנו מתירים להן לפעול גם על קבוצות אינסופיות.

נעיר כי אלגברה בוליאנית שלמה לא בהכרח מקיימת את כלל הדיסטריביוטיביות האינסופי:

$\bigwedge _{i\in A}\bigvee _{j\in B}a_{i,j}=\bigvee _{f\in B^{A}}\bigwedge _{i\in A}a_{i,f(i)}$

אם היא מקיימת אותו היא תקרא דיסטריביוטיבית. במקרים רבים היא מקיימת את הכלל עד כדי הגבלת העוצמה של A או של B. במקרים האלו היא תקרא $(\kappa ,\lambda )$-דיסטריביוטיבית, בהתאם לעוצמות של A ושל B בהן הכלל עובד.

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

היסטוריה

המונח "אלגברה בוליאנית" נקרא על שמו של המתמטיקאי האנגלי ג'ורג' בול (1815–1864). המערכת האלגברית הלוגית שהוא ניסח ב-1854 במאמרו The Laws of Thought שונה מהמערכת שתוארה בערך זה במספר היבטים חשובים. לדוגמה, בול לא התייחס לפעולות 'או" ו"וגם" כפעולות דואליות. תחום האלגבראות הבוליאניות נולד בשנות ה-60 של המאה ה-19 במספר מאמרים שפרסמו ויליאם ג'בונס וצ'ארלס פאריס. ב-1890 הגדיר לראשונה ארנסט שרודר את המושגים אלגברה בוליאנית וסריג הדיסטריבוטיבי במאמרו Vorlesungen.

החיבור המקיף הראשון בנוגע לאלגבראות בוליאניות שנכתב באנגלית הוא Universal Algebra שנכתב ב-1898 על ידי אלפרד נורת' וייטהד. ההתייחסות לאלגבראות בוליאניות כמבנה אלגברי במובן האקסיומטי המודרני החלה ב-1904 במאמר של אדוארד ורמיל האנטינגטון. עבודות חשובות נוספות בתחום בוצעו על ידי מרשל סטון בשנות ה-30 של המאה ה-20, וכן במאמרו של גארט בירקהוף Lattice Theory משנות ה-40 של המאה ה-20. בשנות ה-60 של המאה ה-20 השתמשו פול כהן, דנה סקוט ואחרים בכלים של אלגבראות בוליאניות על מנת להוכיח תוצאות עמוקות בתחום הלוגיקה ובתורת הקבוצות האקסיומטית, בעיקר בתחום הכפייה.

ראו גם

• אלגברה בוליאנית – תחום מתמטי
• לוגיקה בוליאנית
• אלגברה של קבוצות
• סיגמה אלגברה

לקריאה נוספת

• Cori, Rene, and Lascar, Daniel, 2000. Mathematical Logic: A Course with Exercises. Oxford Univ. Press. See Chapter 2.
• Dahn, B.I. (1998), "Robbins Algebras are Boolean: A Revision of McCune's Computer-Generated Solution of the Robbins Problem," Journal of Algebra 208: 526–532.
• Halmos, Paul, 1963. Lectures on Boolean Algebras, Van Nostrand.
• Halmos, Paul and Steven Givant, 1998. Logic as Algebra, Dolciani Mathematical Expositions No. 21, Mathematical Association of America.
• Mendelson, Elliott, 1970. Boolean Algebra and Switching Circuits, Schaum's Outline Series in Mathematics. McGraw–Hill.
• Monk, J. Donald, and R. Bonnet, eds., 1989. Handbook of Boolean Algebras, 3 vols. North-Holland.
• Stoll, R.R., 1979 (1963). Set Theory and Logic. Dover Publications.
• Huntington, E. V., 1933, "New sets of independent postulates for the algebra of logic," Trans. AMS 35: 274--304.
• Huntington, E. V., 1933, "Boolean algebra: A correction," Trans. AMS 35: 557--558.
• Brown, Stephen and Vranesic, Zvonko, 2002. Fundamentals of Digital Logic with VHDL Design, Second Edition. McGraw-Hill. See Section 2.5.

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

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

• רשומות קורס באלגבראות בוליאניות (בעברית)
• אלגברה בוליאנית (מבנה אלגברי), באתר אנציקלופדיה למתמטיקה (באנגלית)