Булева алгебра (структура)

Бу́лева а́лгебра — це алгебраїчна структура, що є доповненою дистрибутивною ґраткою, та частина математики яка вивчає подібні структури.

Булева алгебра утворена
підмножинами множини {x,y,z}

Не плутати з Алгеброю логіки — яка є частковим випадком Булевої алгебри, але в математичній логіці замість неї вживають термін «Булева алгебра».

Алгебра логіки — застосування алгебраїчних методів і символіки для вивчення логічних відношень і розв'язання логічних задач.

Формальне визначення

Булева алгебра — алгебраїчна структура з двома бінарними операціями:

• ${\displaystyle \land }$ («meet», «булеве множення») — узагальнення кон'юнкції,
• ${\displaystyle \lor }$ («join», «булеве додавання») — узагальнення диз'юнкції,

та унарною операцією:

• ${\displaystyle \lnot a}$ чи ${\displaystyle \ {\bar {a}}\;}$(«булеве доповнення») — узагальнення заперечення;

що задовільняють такі аксіоми:

${\displaystyle a\lor b=b\lor a,}$	${\displaystyle a\land b=b\land a}$	(комутативність)
${\displaystyle a\lor (b\lor c)=(a\lor b)\lor c,}$	${\displaystyle a\land (b\land c)=(a\land b)\land c}$	(асоціативність)
${\displaystyle (a\lor b)\land b=b,}$	${\displaystyle (a\land b)\lor b=b}$	(закон поглинання)
${\displaystyle a\lor (b\land c)=(a\lor b)\land (a\lor c),}$	${\displaystyle a\land (b\lor c)=(a\land b)\lor (a\land c)}$	(дистрибутивність)
${\displaystyle (a\lor {\bar {a}})\land b=b,}$	${\displaystyle (a\land {\bar {a}})\lor b=b}$	(доповнення)

Аксіоми 1,2,3 визначають ґратку.

Аксіоми 1,2,3,4 визначають дистрибутивну ґратку.

Аксіоми 1,2,3,5 визначають доповнену ґратку.

З аксіом випливають такі теореми:

${\displaystyle a\lor a=a,}$	${\displaystyle a\land a=a}$	(ідемпотентність)
${\displaystyle a\lor {\bar {a}}=b\lor {\bar {b}},}$	${\displaystyle a\land {\bar {a}}=b\land {\bar {b}}}$

Тобто вирази ${\displaystyle a\lor {\bar {a}}}$ та ${\displaystyle a\land {\bar {a}}}$ не залежать від вибору елемента.

Елемент ${\displaystyle a\lor {\bar {a}}}$ називається булевою одиницею 1, елемент ${\displaystyle a\land {\bar {a}}}$ називається булевим нулем 0.

${\displaystyle a\lor 0=a,}$	${\displaystyle a\land 0=0}$
${\displaystyle a\lor 1=1,}$	${\displaystyle a\land 1=a}$
${\displaystyle \lnot 0=1,}$	${\displaystyle \lnot 1=0}$
${\displaystyle \lnot (a\lor b)=\lnot a\land \lnot b,}$	${\displaystyle \lnot (a\land b)=\lnot a\lor \lnot b}$	(правила де Моргана)
${\displaystyle \lnot \lnot a=a}$.		(інволюція заперечення)

Над множиною A також визначене бінарне відношення ≤, яке має назву відношення нестрогого порядку та відповідає умовам:

1. x≤x (рефлективність)
2. якщо x≤y та y≤x, то x=y (антисиметричність)
3. якщо x≤y та y≤z, то x≤z (транзитивність)

Замість x≤y можна писати у≥x. Множина з таким відношенням має назву впорядкованої.

Нехай S — підмножина елементів впорядкованої множини A. Елемент a' має назву верхньої (нижньої) границі S, якщо для будь-якого а з S справедливе a ≤ a' (a ≥ a'). Якщо множина усіх верхніх (нижніх) границь множини S містить найменший (найбільший) елемент, то він має назву точної верхньої (точної нижньої) границі і позначається sup S(inf S). Якщо для будь-яких a, b з множини A існують inf (a, b) та sup (a, b), то така множина називається структурою або решіткою. Точна верхня границя такої множини є ${\displaystyle a\land b}$, точна нижня границя є ${\displaystyle a\lor b}$.

Зв'язок з булевим кільцем

Докладніше: Теорема Стоуна про представлення булевих алгебр

Кожна булева алгебра еквівалентна булевому кільцю і навпаки:

Операції булевого кільця:

${\displaystyle a+b=(a\land {\neg }b)\lor (b\land {\neg }a)}$

${\displaystyle ab=a\land b}$

Кожна скінченна булева алгебра ізоморфна алгебрі всіх підмножин скінченної множини (полю множин). Тому число елементів булевої алгебри завжди є ступенем 2.

Аксіоматизація

В 1933 американський математик запропонував наступну аксіоматизацію для булевих алгебр:

• комутативність: ${\displaystyle a\lor b=b\lor a}$
• асоціативність: ${\displaystyle a\lor \left(b\lor c\right)=\left(a\lor b\right)\lor c}$
• аксіома Хантінгтона: ${\displaystyle \neg \left(\neg a\lor b\right)\lor \neg \left(\neg a\lor \neg b\right)=a.}$

Герберт Робінс задав питання: чи можна скоротити третю аксіому так, як подано нижче

• аксіома Робінса: ${\displaystyle \neg \left(\neg \left(a\lor b\right)\lor \neg \left(a\lor \neg b\right)\right)=a.}$

Приклади

Алгебра логіки та алгебра множин є загально-відомими прикладами булевої алгебри.

Алгебра логіки (двійкова алгебра)

Найважливішим прикладом булевої алгебри є булева алгебра з двома елементами — одиничний елемент 1 та нульовий елемент 0. Ця алгебра є фундаментом функціонування цифрових дискретних систем. Операція ${\displaystyle \lor }$ в такій алгебрі має назву "логічного АБО" (logical OR), операція ${\displaystyle \land }$ -- "логічного І" (logical AND), а елементам 1 та 0 ставляться у відповідність твердження "істина" (true) та "неправда" (false). Результати цих двох операцій можуть бути зведені в такі таблиці:

${\displaystyle \lor }$ 0 1 0 0 1 1 1 1

${\displaystyle \land }$ 0 1 0 0 0 1 0 1

Така двійкова алгебра відіграє ключову роль в описі цифрових схем (насамперед це стосується цифрових схем без зворотних зв'язків).

Див. також

• Булева алгебра з двома елементами
• Поле множин
• Вільна булева алгебра

Література

• Філософський словник / за ред. В. І. Шинкарука. — 2-ге вид., перероб. і доп. — К. : Головна ред. УРЕ, 1986.