Булеви алгебри, Дискретна математика
Булева алгебра: симетричне півкільце з унарною операцією доповнення x → x з аксіомами x + x = 1, x x = 0. Єдиність доповнення. Булеві алгебри та булеві кільця. Булева алгебра як грати. Решітка — алгебра (L, ∨, ∧) в якій операції (hешеткові об'єднання та перетин) асоціативні, комутативні, ідемпотентні та пов'язані тотожностями поглинання a ∨ (a ∧ b) = a, a ∧ (a ∨ b) = a. Будь-яке симетричне півкільце є ґратами, а дистрибутивні грати (кожна операція дистрибутивна щодо іншої) з нулем і одиницею — симетричним півкільцем. Приклад булевої алгебри - булев куб Bn. Теорема: будь-яка кінцева алгебра булева ізоморфна булеву кубу деякої розмірності.
Нагадаємо, що за визначенням булева алгебра - це симетричне півкільце, в якому введено ще одну унарну операцію - доповнення. Доповнення елемента x, що позначається x , задовольняє аксіомам x + x = 1, x x = 0. Зазначимо, що ці рівність для будь-якого x визначають елемент x однозначно, тобто. Існування доповнення визначається властивостями двох бінарних операцій.
Докладніше можна сказати, що булева алгебра - універсальна алгебра виду (L, ), що задовольняє умовам:
а) кожна бінарна операція є комутативною, асоціативною, ідемпотентною і має нейтральний елемент;
б) кожна бінарна операція дистрибутивна щодо іншої;
в) нейтральний елемент кожної бінарної операції є анулюючою іншої бінарної операції;
г) доповнення пов'язане з бінарними операціями аксіомами x+x=1, xx=0.
Обидві операції породжують два відносини порядку, що є взаємно зворотними. Так, відношення x y, рівносильне рівності x + y = y також визначається рівністю xy = x.
Якщо в булевій алгебрі B ввестиоперацію x ⊕ y = x y + x y, то отримаємо систему алгебри (L, ), яка є кільцем з одиницею, в якому операція множення ідемпотентна (бульовим кільцем). Коротше кажучи, алгебра булева є булевим кільцем. Навпаки, у будь-якому булевом кільці (L, ) множення комутативно, а додавання задовольняє умові x⊕x=0. Поклавши x+y=x⊕y⊕xy, x =x+1,отримував гебраїчну систему (L, ), що являє собою булеву алгебру.
До поняття булевої алгебри можна підійти і з іншого боку. Комутативна ідемпотентна напівгрупа називаєтьсянапіврешіткою. У напіврешітці (як і півкільці) можна запровадити відношення природного порядку відповідно до правила x y ⇔ x+y = y. Навпаки, будь-яка впорядкована множина, в якій будь-яка двоелементна множина має точну верхню грань, можна інтерпретувати як напіврешітку з операцією x + y = sup . Якщо в упорядкованому множині кожна двоелементна множина має і точну верхню, і точну нижню грані, то на цій множині можна ввести структуру напіврешітки двома способами: з операцією sup і з операцією inf . Першу структуру називають верхньою напіврешіткою, а другу — нижньою. Дві граткові операції пов'язані тотожностями
Алгебра (R, ), для якої (R, ∨) і (R, ∧) є напіврешітки, причому операції пов'язані тотожності поглинання a ∨ (a ∧ b) = a, a ∧ (a ∨ b) = a, називається ґратами. Бінарні операції називаються ґратовими (решіткове об'єднання та ґратове перетинання). Граткові операції входять до структури решітки симетрично. Тому будь-яку з них можна назвати об'єднанням, тоді друга буде перетином. Структуру грат має будь-яке впорядковане безліч, в якому для будь-якого двоелементного безлічі існує точна верхня і точна нижня грані. У цьому випадку гратовими операціями будуть a∨b=sup та a∧b=inf.
Структуру грат має будь-яке симетричне півкільце. Грати в загальному випадку може і не бути симетричним півкільцем. Наприклад, пентагон — впорядкована множина із ставленням порядку, заданим діаграмою Хассе* на рис. 1.1 — є ґратами, але в цій решітці операції не є дистрибутивними один щодо одного, як має бути в симетричному півкільці. Однак будь-яка дистрибутивна решітка (тобто решітка, в якій кожна операція дистрибутивна щодо іншої) з нулем та одиницею (нейтральними елементами об'єднання та перетину) є симетричним півкільцем.
Найпростіший приклад булевої алгебри - двоелементна булева алгебра
з операціями x + y = max xy = min, x = x +1. Узагальненням цього прикладу є булева алгебра B n з покомпонентним виконанням операцій алгебри B на кортежах. Алгебру B n називають n-й декартовим ступенем B або n-мірним булевим кубом. Виявляється, що будь-яка кінцева алгебра булева ізоморфна деякому булеву кубу. Простіше кажучи, інших прикладів кінцевих алгебр, відмінних від булева куба, немає.
Інший важливий приклад булевої алгебри - алгебра SA = 2 A , тобто. безліч всіх підмножин множини A з теоретико-множинними операціями об'єднання, перетину та доповнення. Відзначимо, що всі практично значущі приклади булевих алгебр можна інтерпретувати в рамках алгебри SA або будь-якої подалгебри. Наприклад, елементи булевої алгебри B n (n-вимірні булеви вектори) можна розглядати як запис характеристичної функції підмножини у множині n елементів. А тоді операції в B n будуть відповідати теоретико-множинним операціям. Симетричне півкільце ([a, b], ) можна перетворити на алгебру множин, поставивши у відповідність кожному x ∈ [a, b] відрізок [a, x]. Безлічтаких відрізків замкнуто щодо операцій об'єднання та перетину, тобто. утворює подалгебру в 2 [a, b]. Правда це півкільце не є булевою алгеброю, тому що в ньому не можна запровадити операцію доповнення.