Матеріал з Вікіпедії - вільної енциклопедії Ця стаття про алгебраїчній системі .Про розділ математичної логіки, що вивчає висловлювання і операції над ними, см. алгебра логіки .

булевой алгеброю [1] [2] [3] називається непорожня безліч A з двома бінарними операціями ∧ {\ displaystyle \ land} (аналог кон'юнкції ), ∨ {\ displaystyle \ lor} (аналог диз'юнкції ), Однієї унарною операцією ¬ {\ displaystyle \ lnot} (аналог заперечення ) І двома виділеними елементами: 0 (або Брехня) і 1 (або Істина) такими, що для будь-яких a, b і c з безлічі A вірні такі аксіоми :

Перші три аксіоми означають, що (A, ∧ {\ displaystyle \ land} , ∨ {\ displaystyle \ lor} ) є гратами . Таким чином, булева алгебра може бути визначена як дистрибутивная решітка , В якій виконані дві останні аксіоми. Структура, в якій виконуються всі аксіоми, крім передостанній, називається псевдобулевой алгеброю . Названа на честь Джорджа Буля .

З аксіом видно, що найменшим елементом є 0, найбільшим є 1, а доповнення ¬ a будь-якого елементу a однозначно визначено. Для всіх a і b з A вірні також наступні рівності:

В даному розділі повторюються властивості і аксіоми, описані вище з додаванням ще декількох.

Зведена таблиця властивостей і аксіом, описаних вище:

• Найпростіша нетривіальна булева алгебра містить всього два елементи, 0 і 1, а дії в ній визначаються наступною таблицею:

Ця булева алгебра найбільш часто використовується в логіці , Так як є точною моделлю класичного обчислення висловлювань . В цьому випадку 0 називають брехнею, 1 - істиною. Вирази, що містять булеві операції та змінні, представляють собою висказивательной форми.

У булевих алгебрах існують подвійні твердження, вони або одночасно вірні, або одночасно хибні. Саме, якщо у формулі, яка вірна в деякій булевої алгебри, поміняти все кон'юнкції на диз'юнкції, 0 на 1, ≤ на> і навпаки або <на ≥ і навпаки, то вийде формула, також справжня в цій булевої алгебри. Це випливає з симетричності аксіом щодо таких замін.

Можна довести, що будь-яка кінцева булева алгебра ізоморфна булевої алгебри всіх підмножин якогось множини. Звідси випливає, що кількість елементів в будь-якій кінцевій булевої алгебри буде ступенем двійки.

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

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

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.

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

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