Шукати в цьому блозі

понеділок, 15 лютого 2016 р.

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


Матеріал з Вікіпедії — вільної енциклопедії.
Булева алгебра утворена
підмножинами множини {x,y,z}
Не слід плутати з Алгеброю логіки — яка є частковим випадком Булевої алгебри, але в математичній логіці замість неї вживають термін «Булева алгебра».
Бу́лева а́лгебра — це алгебраїчна структура, що є доповненою дистрибутивною ґраткою, та частина математики яка вивчає подібні структури.
Алгебра логіки — застосування алгебраїчних методів і символіки для вивчення логічних відношень і розв'язання логічних задач.

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

Булева алгебра — алгебраїчна структура з двома бінарними операціями:
  • \land («meet», «булеве множення») — узагальнення кон'юнкції,
  • \lor («join», «булеве додавання») — узагальнення диз'юнкції,
та унарною операцією:
що задовільняють такі аксіоми:
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 b = b, (a \land b) \lor b = b (закон поглинання)
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 \bar{a}) \land b = b, (a \land \bar{a}) \lor b = b (доповнення)
Аксіоми 1,2,3 визначають ґратку.
Аксіоми 1,2,3,4 визначають дистрибутивну ґратку.
Аксіоми 1,2,3,5 визначають доповнену ґратку.
З аксіом випливають такі теореми:
a \lor a = a, a \land a = a (ідемпотентність)
a \lor \bar{a} = b \lor \bar{b}, a \land \bar{a} = b \land \bar{b}
Тобто вирази a \lor \bar{a} та a \land \bar{a} не залежать від вибору елемента.
Елемент a \lor \bar{a} називається булевою одиницею 1, елемент a \land \bar{a} називається булевим нулем 0.
a \lor 0 = a, a \land 0 = 0
a \lor 1 = 1, a \land 1 = a
\lnot 0 = 1, \lnot 1 = 0
\lnot (a \lor b) = \lnot a \land \lnot b, \lnot (a \land b) = \lnot a \lor \lnot b (правила де Моргана)
\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), то така множина називається структурою або решіткою. Точна верхня границя такої множини є a \land b, точна нижня границя є a \lor b.

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

Докладніше: Теорема Стоуна про представлення булевих алгебр
Кожна булева алгебра еквівалентна булевому кільцю і навпаки:
Операції булевого кільця:
a + b = (a \land {\neg}b) \lor (b \land {\neg}a)
a b = a \land b
Кожна скінченна булева алгебра ізоморфна алгебрі всіх підмножин скінченної множини (полю множин). Тому число елементів булевої алгебри завжди є ступенем 2.

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

В 1933 американський математик Едвард Хантінгтон запропонував наступну аксіоматизацію для булевих алгебр:
  • комутативність: a \lor b = b \lor a
  • асоціативність: a \lor \left(b \lor c\right) = \left(a \lor b\right) \lor c
  • аксіома Хантінгтона: \neg \left( \neg a \lor b \right) \lor \neg \left( \neg a \lor \neg b \right) = a.
Герберт Робінс задав питання: чи можна скоротити третю аксіому так, як подано нижче
  • аксіома Робінса: \neg \left( \neg \left(a \lor b \right) \lor \neg \left(a \lor \neg b \right) \right) = a.

Приклади

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

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

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

Немає коментарів:

Дописати коментар

Примітка: лише член цього блогу може опублікувати коментар.

Підписатися на: Дописати коментарі (Atom)