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

булевой алгеброю [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 м американський математик Хантінгтон запропонував наступну аксіоматизації для булевих алгебр:

1. Аксіома коммутативности: x + y = y + x.
2. Аксіома асоціативності: (x + y) + z = x + (y + z).
3. Рівняння Хантінгтона: n (n (x) + y) + n (n (x) + n (y)) = x.

Тут використані позначення Хантінгтона: + означає диз'юнкцію, n - заперечення.

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

Аксіоматизації алгебри Роббінса:

1. Аксіома коммутативности: x + y = y + x.
2. Аксіома асоціативності: (x + y) + z = x + (y + z).
3. Рівняння Роббінса: n (n (x + y ') + n (x + n (y))) = x.

Це питання залишалося відкритим з 30-х років і був улюбленим питанням Тарского і його учнів.

В 1996 м Вільям Маккьюн, використовуючи деякі отримані до нього результати, дав ствердну відповідь на це питання. Таким чином, будь-яка алгебра Роббінса є булевої алгеброю.

Див. також

Примітки

література