Булева алгебра

Матеріал з Вікіпедії — вільної енциклопедії.

Бу́лева а́лгебра (англ. boolean algebra. тж. алгебра логіки) в математиці та інформатиці — алгебраїчна структура, яка відображує певні логічні закономірності об’єктів та систем реального світу.

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

[ред.] Генеза

Засади алгебри логіки були сформульовані британцем Джорджем Булем в 1847 році. Пізніше її розвивали Чарлз Пірс, П. С. Порецький, Бертран Рассел, Давид Гільберт та ін.

Відтоді ця система застосовується для вирішення широкого спектру проблем математичної логіки та теорії множин, та особливо конструювання цифрової електроніки (початок використання булевої алгебри для синтезу перемикальних (релейних) схем був покладений в 1938 році роботами відомого американського вченого Клода Шеннона).

[ред.] Предмет вивчення

Спочатку А. л. досліджувала класи (обсяги понять), відношення між ними за обсягом і операції над класами: додавання, множення, віднімання. Проте з виникненням множин теорії (70-і pp. 19 ст.), яка частково поглинула проблематику А. л. (теоретико-множинні операції), і дальшим розвитком математичної логіки предмет А. л. значно змінився.

Сучасна А. л. досліджує операції над висловлюваннями, які розглядають як об'єкти лише з однією властивістю — бути істинними або хибними. Див. Алгебра висловлювань.

[ред.] Формальне визначення булевої алгебри

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

булеве додавання, яке співставляє будь-яким двом елементам a та b множини A елемент $a \lor b$ з цієї ж множини (булеву суму елементів а та b)
булеве множення, яке співставляє будь-яким двом елементам a та b множини A елемент $a \land b$ з цієї ж множини (булевий добуток елементів а та b)
булеве доповнення, яке співставляє кожному елементу a множини A деякий елемент $\bar{a}$ або $\lnot a$ (булеве доповнення до елемента а)

При цьому виконуються наступні аксіоми:

$a \lor b = b \lor a; a \land b = b \land a$ (комутативність)
$(a \lor b) \lor c = a \lor (b \lor c); (a \land b) \land c = a \land (b \land c)$ (асоціативність)
$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 b) \land b = b; (a \land b) \lor b = b;$ (поглинання-1)
$(a \lor a) \land b = b; (a \land \bar{a}) \lor b = b;$ (поглинання-2)

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

$a \lor a = a, a \land a = a$ (ідемпотентність)
$a \lor \bar{a} = b \lor \bar{b}; a \land \bar{a} = b \land \bar{b}$ для довільних а, b з множини A

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

$a \lor 0 = a; a \land 0 = 0; a \lor 1 = 1; a \land 1 = a$ для будь-якого a з А
$a=a \quad$ для будь-якого a з А
$\lnot(a \lor b)=\lnot a \land \lnot b; \lnot (a \land b)=\lnot a \lor \lnot b$ (правила де-Моргана)

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

x≤x (рефлективність)
якщо x≤y та y≤x, то x=y (антисиметричність)
якщо 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 \land b$ , точна нижня границя є $a \lor b$ .

Строго математично, булевою алгеброю називається ґратка A в якій зазначені операції дистрибутивні, кожний елемент з множини A має доповнення, а також існують нульовий та одиничний елементи.

[ред.] Двійкова алгебра

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