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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Булева алгебра утворена
підмножинами множини {x,y,z}

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

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

Формальне визначення[ред.ред. код]

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

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

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

  • чи («булеве доповнення») — узагальнення заперечення;

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

(комутативність)
(асоціативність)
(закон поглинання)
(дистрибутивність)
(доповнення)

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

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

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

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

(ідемпотентність)

Тобто вирази та не залежать від вибору елемента.

Елемент називається булевою одиницею 1, елемент називається булевим нулем 0.

(правила де Моргана)
. (інволюція заперечення)

Над множиною 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), то така множина називається структурою або решіткою. Точна верхня границя такої множини є , точна нижня границя є .

Зв'язок з булевим кільцем[ред.ред. код]

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

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

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

Аксіоматизація[ред.ред. код]

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

  • комутативність:
  • асоціативність:
  • аксіома Хантінгтона:

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

  • аксіома Робінса:

Приклади[ред.ред. код]

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

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

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

0 1
0 0 1
1 1 1
0 1
0 0 0
1 0 1

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

Див. також[ред.ред. код]

Література[ред.ред. код]