Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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



План:


Введення

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

Булевой алгеброю [1] [2] [3] називається непорожня безліч A з двома бінарними операціями \ Land (Аналог кон'юнкції), \ Lor (Аналог диз'юнкції), унарний операцією \ Lnot (Аналог заперечення) і двома виділеними елементами: 0 (або Брехня) і 1 (або Істина) такими, що для всіх a, b і c з безлічі A вірні наступні аксіоми :

a \ lor (b \ lor c) = (a \ lor b) \ lor ca \ land (b \ land c) = (a \ land b) \ land cасоціативність
a \ lor b = b \ lor aa \ land b = b \ land aкомутативність
a \ lor (a \ land b) = aa \ land (a \ lor b) = a закони поглинання
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 \ lnot a = 1a \ land \ lnot a = 0 додатковість
У нотації +

\ Begin {align} & a + (b + c) = (a + b) + c & a (bc) = (ab) c \ \ & a + b = b + a & ab = ba \ \ & a + ab = a & a (a + b) = a \ \ & a + bc = (a + b) (a + c) & a (b + c) = ab + ac \ \ & a + \ bar {a} = 1 & a \ bar {a} = 0 \ end {align}

Перші три аксіоми означають, що (A, \ Land , \ Lor ) Є гратами. Таким чином, булева алгебра може бути визначена як дистрибутивная решітка, в якій виконані дві останні аксіоми. Структура, в якій виконуються всі аксіоми, крім передостанній, називається псевдобулевой алгеброю.


1. Деякі властивості

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

a \ lor a = a ; a \ land a = a ;
a \ lor 0 = a ; a \ land 1 = a ;
a \ lor 1 = 1 ; a \ land 0 = 0 ;
\ Lnot 0 = 1 ; \ Lnot 1 = 0 ; додаток 0 є 1 і навпаки
\ Lnot (a \ lor b) = \ lnot a \ land \ lnot b ; \ Lnot (a \ land b) = \ lnot a \ lor \ lnot b ; закони де Моргана
\ Lnot \ lnot a = a . інволютивних заперечення

2. Основні тотожності

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

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

a \ lor b = b \ lor a ; a \ land b = b \ land a . 1 комутативність переместительному
a \ lor (b \ lor c) = (a \ lor b) \ lor c ; a \ land (b \ land c) = (a \ land b) \ land c . 2 асоціативність сочетательно
3.1 кон'юнкція щодо диз'юнкції a \ lor (b \ land c) = (a \ lor b) \ land (a \ lor c) 3.2 диз'юнкція щодо кон'юнкції a \ land (b \ lor c) = (a \ land b) \ lor (a \ land c) 3 дистрибутивність розподільного
a \ lor \ lnot a = 1 ; a \ land \ lnot a = 0 . 4 комплементность додатковість (властивості заперечень)
\ Lnot (a \ lor b) = \ lnot a \ land \ lnot b ; \ Lnot (a \ land b) = \ lnot a \ lor \ lnot b . 5 закони де Моргана
a \ lor (a \ land b) = a ; a \ land (a \ lor b) = a . 6 закону поглинання
a \ lor (\ lnot a \ land b) = a \ lor b ; a \ land (\ lnot a \ lor b) = a \ land b . 7 Блейка-Порецкого
a \ lor a = a ; a \ land a = a . 8 Ідемпотентность
\ Lnot \ lnot a = a . 9 інволютивних заперечення
a \ lor 0 = a ; a \ land 1 = a . 10 властивостей констант
a \ lor 1 = 1 ; a \ land 0 = 0 .
додаток 0 є 1 \ Lnot 0 = 1 ; додаток 1 є 0 \ Lnot 1 = 0 .
(A \ lor b) \ land (\ lnot a \ lor b) = b ; (A \ land b) \ lor (\ lnot a \ land b) = b . 11 Склеювання


3. Приклади

  • Найпростіша нетривіальна булева алгебра містить всього два елементи, 0 та 1, а дії в ній визначаються наступною таблицею:
0 1
0 0 0
1 0 1
0 1
0 0 1
1 1 1
a 0 1
a 1 0
  • Ця булева алгебра найбільш часто використовується в логіці, так як є точною моделлю класичного обчислення висловлювань. У цьому випадку 0 називають брехнею, 1 - істиною. Вирази, що містять булеві операції і змінні, є висказивательную форми.
  • Алгебра Лінденбаума - Тарського ( фактормножество всіх тверджень стосовно равносильности в даному вирахуванні з відповідними операціями) якого-небудь обчислення висловлювань є булевой алгеброю. У цьому випадку істиннісне оцінка формул обчислення є гомоморфізмом алгебри Лінденбаума - Тарського в двоелементний булеву алгебру.
  • Безліч всіх підмножин даної множини S утворює булеву алгебру щодо операцій ∨: = ∪ (об'єднання), ∧: = ∩ (перетин) і унарний операції доповнення. Найменший елемент тут - пусте безліч, а найбільший - всі S.
  • Якщо R - довільне кільце, то на ньому можна визначити безліч центральних ідемпотентов так:
    A = {eR: e = e, ex = xe,xR},
    тоді множина A буде булевой алгеброю з операціями ef: = e + f - ef та ef: = ef.

4. Принцип подвійності

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

5. Подання булевих алгебр

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

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


6. Аксіоматизації

В 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 р. Вільям МакКьюн, використовуючи деякі отримані до нього результати, дав ствердну відповідь на це питання. Таким чином, будь-яка алгебра Роббінса є булевой алгеброю.


Примітки

  1. DA Vladimirov Springer Online Reference Works - Boolean algebra - eom.springer.de/B/b016920.htm (Англ.) . Springer-Verlag (2002). Фотогалерея - www.webcitation.org/61IIIKl84 з першоджерела 29 серпня 2011.
  2. Владимиров Д. А. Булеві алгебри - eqworld.ipmnet.ru/ru/library/books/Vladimirov1969ru.djvu - М .: "Наука", 1969. - С. 19.
  3. Кузнецов О. П., Адельсон-Бєльський Г. М. Дискретна математика для інженера - М .: Вища школа, 1988. - С. 58.

Література


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Булева формула
Булева функція
Алгебра Лі
Алгебра
Алгебра Лі
Зовнішня алгебра
Сигнатура (алгебра)
Алгебра Келі
Альтернативна алгебра
© Усі права захищені
написати до нас
Рейтинг@Mail.ru