булева алгебра
- деякі властивості
- Основні тотожності
- приклади
- принцип подвійності
- Уявлення булевих алгебр
- аксіоматизації
булевой алгеброю [1] [2] [3] називається непорожня безліч A з двома бінарними операціями (аналог кон'юнкції ),
(аналог диз'юнкції ), унарною операцією
(аналог заперечення ) І двома виділеними елементами: 0 (або Брехня) і 1 (або Істина) такими, що для всіх a, b і c з безлічі A вірні такі аксіоми :
Перші три аксіоми означають, що (A, ,
) є гратами . Таким чином, булева алгебра може бути визначена як дистрибутивная решітка , В якій виконані дві останні аксіоми. Структура, в якій виконуються всі аксіоми, крім передостанній, називається псевдобулевой алгеброю.
деякі властивості
З аксіом видно, що найменшим елементом є 0, найбільшим є 1, а доповнення ¬ a будь-якого елементу a однозначно визначено. Для всіх a і b з A вірні також наступні рівності:
Основні тотожності
В даному розділі повторюються властивості і аксіоми, описані вище з додаванням ще декількох.
Зведена таблиця властивостей і аксіом, описаних вище:
Див. також алгебра логіки
приклади
- Найпростіша нетривіальна булева алгебра містить всього два елементи, 0 і 1, а дії в ній визначаються наступною таблицею:
- Ця булева алгебра найбільш часто використовується в логіці , Так як є точною моделлю класичного обчислення висловлювань . В цьому випадку 0 називають брехнею, 1 - істиною. Вирази, що містять булеві операції та змінні, представляють собою висказивательной форми.
- Алгебра Лінденбаума - Тарського ( фактормножество всіх тверджень стосовно равносильности в даному обчисленні з відповідними операціями) будь-якого обчислення висловлювань є булевої алгеброю. В цьому випадку істиннісне оцінка формул обчислення є гомоморфизмом алгебри Лінденбаума - Тарського в двоелементною булеву алгебру.
- Безліч всіх підмножин даної множини S утворює булеву алгебру щодо операцій ∨: = ∪ (об'єднання), ∧: = ∩ (перетин) і унарною операції доповнення. Найменший елемент тут - порожня множина , А найбільший - все S.
- Якщо R - довільне кільце , То на ньому можна визначити безліч центральних ідемпотентів так:
A = {e ∈ R: e ² = e, ex = xe, ∀ x ∈ R},
тоді безліч A буде булевої алгеброю з операціями e ∨ f: = e + f - ef і e ∧ f: = ef.
принцип подвійності
У булевих алгебрах існують подвійні твердження, вони або одночасно вірні, або одночасно хибні. Саме, якщо у формулі, яка вірна в деякій булевої алгебри, поміняти все кон'юнкції на диз'юнкції, 0 на 1, ≤ на ≥ і навпаки, то вийде формула, також справжня в цій булевої алгебри. Це випливає з симетричності аксіом щодо таких замін.
Уявлення булевих алгебр
Можна довести, що будь-яка кінцева булева алгебра ізоморфна булевої алгебри всіх підмножин якогось множини. Звідси випливає, що кількість елементів в будь-якій кінцевій булевої алгебри буде ступенем двійки.
Знаменита теорема Стоуна стверджує, що будь-яка булева алгебра ізоморфна булевої алгебри всіх відкрито-замкнутих множин якогось компактного цілком незв'язною хаусдорфова топологічного простору.
аксіоматизації
В 1933 м американський математик Хантінгтон запропонував наступну аксіоматизації для булевих алгебр:
- Аксіома коммутативности: x + y = y + x.
- Аксіома асоціативності: (x + y) + z = x + (y + z).
- Рівняння Хантінгтона: n (n (x) + y) + n (n (x) + n (y)) = x.
Тут використані позначення Хантінгтона: + означає диз'юнкцію, n - заперечення.
Герберт Роббінс поставив наступне питання: чи можна скоротити останню аксіому так, як написано нижче, тобто чи буде певна виписаними нижче аксіомами структура булевої алгеброю?
Аксіоматизації алгебри Роббінса:
- Аксіома коммутативности: x + y = y + x.
- Аксіома асоціативності: (x + y) + z = x + (y + z).
- Рівняння Роббінса: n (n (x + y ') + n (x + n (y))) = x.
Це питання залишалося відкритим з 30-х років і був улюбленим питанням Тарского і його учнів.
В 1996 м Вільям Маккьюн, використовуючи деякі отримані до нього результати, дав ствердну відповідь на це питання. Таким чином, будь-яка алгебра Роббінса є булевої алгеброю.