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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$a\vee a=a,$	$a\wedge a=a$	(ідемпотентність)
$a\vee \overline{a}=b\vee \overline{b},$	$a\wedge \overline{a}=b\wedge \overline{b}$

Тобто вирази $a\vee \overline{a}$ та $a\wedge \overline{a}$ не залежать від вибору елемента.

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

$a\vee 0=a,$	$a\wedge 0=0$
$a\vee 1=1,$	$a\wedge 1=a$
$\mathrm{\neg }0=1,$	$\mathrm{\neg }1=0$
$\mathrm{\neg }(a\vee b)=\mathrm{\neg }a\wedge \mathrm{\neg }b,$	$\mathrm{\neg }(a\wedge b)=\mathrm{\neg }a\vee \mathrm{\neg }b$	(правила де Моргана)
$\mathrm{\neg }\mathrm{\neg }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), то така множина називається структурою або решіткою. Точна верхня границя такої множини є $a\wedge b$, точна нижня границя є $a\vee b$.

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

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

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

$a+b=(a\wedge \mathrm{\neg }b)\vee (b\wedge \mathrm{\neg }a)$

$ab=a\wedge b$

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

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

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

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

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

• аксіома Робінса: $\mathrm{\neg }(\mathrm{\neg }(a\vee b)\vee \mathrm{\neg }(a\vee \mathrm{\neg }b))=a.$

Приклади

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

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

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

$\vee$ 0 1 0 0 1 1 1 1

$\wedge$ 0 1 0 0 0 1 0 1

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

Див. також

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

Література

• Шаблон:ФС