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

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

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

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

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

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

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

בהינתן אלגברה בוליאנית (A, , , ) ניתן להגדיר חוג (A, +, *) על ידי כך שמגדירים  (פעולה זו נקראת הפרש סימטרי במקרה של קבוצות, או XOR במקרה של לוגיקה) ו-. איבר ה-0 של החוג מתלכד עם איבר ה0 של האלגברה הבוליאנית, ואיבר היחידה של החוג שווה לאיבר 1 באלגברה הבוליאנית.
בדרך זו מתקבל חוג A שמקיים שלכל x בA מתקיים . חוג המקיים שוויון זה נקרא חוג בוליאני. בחוג בוליאני, לכל a מתקיים ש-.
להפך, בהינתן חוג בוליאני A, נוכל להפוך את A לאלגברה בוליאנית על ידי כך שנגדיר ,  ו-. מכיוון ששתי פעולות אלה הופכיות אחת של השנייה, הרי שנוכל לומר כי כל אלגברה בוליאנית נוצרת מחוג בוליאני, ולהפך. יתר על כן, העתקה f בין אלגבראות בוליאניות היא הומומורפיזם של אלגבראות בוליאניות אם ורק אם היא הומומורפיזם של חוגים עבור החוגים הבוליאנים המתאימים. במילים אחרות, הקטגוריה של אלגבראות בוליאניות שקולה לקטגוריה של חוגים בוליאנים.
אידיאל I באלגברה בוליאנית A הוא תת-קבוצה של A כך שלכל x ו-y בI מתקיים ש , וכן לכל x בI ולכל a בA מתקיים ש . מושג זה מתלכד עם המושג אידיאל בתורת החוגים כאשר A מתייחסים אל A כאל חוג בוליאני. אידיאל I השונה מA נקרא ראשוני אם כל פעם שמתקיים  אז לפחות אחד מבין x ו-y שייך לI. אידיאל I השונה מA נקרא מקסימלי אם A הוא האידיאל היחיד המכיל את I. גם מושגים אלו מתלכדים עם המושגים המקבילים של אידיאל ראשוני ואידיאל מקסימלי מתורת החוגים.
המונח הדואלי למושג האידיאל נקרא מסנן (או פילטר). לפיכך, תת-קבוצה F של אלגברה בוליאנית A נקראת מסנן אם לכל זוג x ו-y בF מתקיים ש  ולכל x בF ולכל a בA מתקיים ש .

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

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

היסטוריה

המונח אלגברה בוליאנית נקרא על שמו של המתמטיקאי האנגלי ג'ורג' בול (1815-1864). המערכת האלגברית הלוגית שהוא ניסח ב-1854 במאמרו The Laws of Thought שונה מהמערכת שתוארה בערך זה במספר היבטים חשובים. לדוגמה, בול לא התייחס לפעולות או ווגם כפעולות דואליות. תחום האלגבראות הבוליאניות נולד בשנות ה-60 של המאה ה-19 במספר מאמרים שפרסמו ויליאם ג'בונס ו-צ'ארלס פאריס. ב-1890 הגדיר לראשונה ארנסט שרודר את המושגים אלגברה בוליאנית וסריג הדיסטריבוטיבי במאמרו Vorlesungen.
החיבור המקיף הראשון בנוגע לאלגבראות בוליאניות שנכתב באנגלית הוא Universal Algebra שנכתב ב-1898 על ידי אלפרד נורת' וייטהד. ההתייחסות לאלגבראות בוליאניות כמבנה אלגברי במובן האקסיומטי המודרני החלה ב-1904 במאמר של אדוארד ורמיל האנטינגטון. עבודות חשובות נוספות בתחום בוצעו על ידי מרשל סטון בשנות ה-30 של המאה ה-20, וכן במאמרו של גארט בירקהוף Lattice Theory משנות ה-40 של המאה ה-20. בשנות ה-60 של המאה ה-20 השתמשו פול כהן, דנה סקוט ואחרים בכלים של אלגבראות בוליאניות על מנת להוכיח תוצאות עמוקות בתחום הלוגיקה ובתורת הקבוצות האקסיומטית, בעיקר בתחום הכפייה.