Алгебра логіки (Булева алгебра, Булева логіка, двійкова логіка, двійкова алгебра, ) — розділ математичної логіки, що вивчає систему логічних операцій над висловлюваннями. В алгебрі логіки значенням змінних є значення істинності істина або хиба, які зазвичай визначаються як 1 і 0 відповідно. На відміну від елементарної алгебри, у якій значеннями змінних є числа, а основними операціями є додавання і множення, основними операціями булевої алгебри є кон'юнкція операція І () позначається як ∧, диз'юнкція АБО () позначається як ∨, і заперечення НІ () позначається як ¬. Таким чином, формалізм для описання логічних відношень є аналогічним тому, як описуються числові відношення в елементарній алгебрі.
Булеву алгебру запропонував Джордж Буль у своїй книзі Математичний аналіз логіки (1847), і більш детально в наступній книзі (1854). Відповідно до , термін «Булева алгебра» вперше запропонував Шеффер у 1913,«The name Boolean algebra (or Boolean 'algebras') for the calculus originated by Boole, extended by Schröder, and perfected by Whitehead seems to have been first suggested by Sheffer, in 1913.» E. V. Huntington, «New sets of independent postulates for the algebra of logic, with special reference to Whitehead and Russell's Principia mathematica », in Trans. Amer. Math. Soc. 35 (1933), 274—304; footnote, page 278. хоча Чарлз Сандерс Пірс у 1880 дав назву «Булева алгебра з однією сталою» першій главі своєї книги «Найпростіша математика». Булева алгебра є фундаментальною основою для розвитку цифрової електроніки, і втілена в усіх мовах програмування. Вона також використовується в теорії множин і статистиці.
Визначення Базовими елементами, якими оперує алгебра логіки, є висловлювання.
Висловлювання будуються над множиною {B, , , , 0, 1}, де B — непорожня множина, над елементами якої визначені три операції: заперечення (унарна операція), кон'юнкція (бінарна), диз'юнкція (бінарна), а логічний нуль 0 і логічна одиниця 1 — константи.
Так само використовуються назви диз'юнкт — пропозиціональна формула, що є диз'юнкцією одного або більше літералів (наприклад ). кон'юнктив — пропозиціональна формула, що є кон'юнкцією одного або більше літералів (наприклад ).
Унарна операція заперечення в тексті формул оформляється або у вигляді значка перед операндом (), або у вигляді риски над операндом (), що компактніше, але загалом менш помітно.
Значення Тоді як в елементарній алгебрі вирази зазвичай виражаються в числах, в алгебрі логіки вони виражають значення істинності істина і хиба. Ці значення задають за допомогою бітів (або двійкових чисел), а саме 0 та 1. Вони не поводять себе так само як цілі числа 0 та 1, для яких 1 + 1 = 2, а можуть визначатися як елементи , що є цілочисельною арифметикою за модулем 2, для якої 1 + 1 = 0. Алгебра логіки також вивчає функції, що приймають значення в множині {0, 1}.
Предмет вивчення Спочатку проблематика алгебри логіки перетиналася з проблематикою алгебри множин (теоретико-множинні операції).
Проте із закінченням формування теорії множин (70-і роки 19 ст.), до складу якої входила алгебра множин, і подальшим розвитком математичної логіки, предмет алгебри логіки значно змінився.
Сучасна алгебра логіки розглядає операції над висловлюваннями (див. Числення висловлень) як булеву функцію і вивчає відносно них такі питання, як: таблиці істинності; функціональна повнота; замкнені класи; представлення у вигляді: ДНФ, КНФ, полінома Жегалкіна.
Операції
Базові операції Як уже зазначалося, базовими операціями булевої алгебри (алгебри логіки) є такі логічні операції: І (кон'юнкція), позначається x∧y (іноді x І y), задовольняє x∧y = 1, якщо x = y = 1 та x∧y = 0 в інших випадках. АБО (диз'юнкція), позначається x∨y (іноді x АБО y), задовольняє x∨y = 0, якщо x = y = 0 та x∨y = 1 в інших випадках. НІ (заперечення), позначається ¬x (іноді НЕ x або !x), задовольняє ¬x = 0, якщо x = 1 та ¬x = 1, якщо x = 0.
Альтернативним способом значення x∧y, x∨y, та ¬x можна представити в табличному вигляді для всіх можливих значень за допомогою таблиць істинності таким способом.
00 0 010 0 101 0 111 1 1
0110
Якщо значення істинності 0 та 1 інтерпретувати як цілі числа, ці операції можна було задати як звичайні операції арифметики (де x + y використовує додавання, а xy використовує множення), або як функції мінімуму/максимуму:
Можна вважати, що лише заперечення і одна з двох операцій, що залишилися, є базовими, оскільки наступні рівняння дозволяють визначити кон'юнкцію через операції заперечення та диз'юнкцію, і навпаки:
Вторинні операції Три булеві операції описані вище називають базовими або первинними, що означає, що вони можуть бути базисом для всіх інших булевих операцій, оскільки всі інші операції можна виразити через них за допомогою композиції. Серед операцій, які можна побудувати з базових операцій є такі:
Ці визначення дають такі таблиці істинності, у яких показані значення цих операцій для всіх можливих вхідних значень.
{| class="wikitable" style="text-align: center" |- ! ! ! ! ! |- !0 !0 | 1 || 0 || 1 |- !1 !0 |0 || 1 || 0 |- !0 !1 |1 || 1 || 0 |- !1 !1 | 1 || 0 || 1
Перша операція, x → y, називається імплікацією. Якщо x є істинним, тоді за значення виразу x → y приймається значення y. Але якщо x приймає хибне значення, то значення y можна було б ігнорувати; однак ця операція повинна повернути деяке логічне значення, і існує лише два варіанти вибору. То ж за визначенням, x → y є істиною коли x є хибним.
Друга операція, x ⊕ y, називається виключною диз'юнкцією (часто задається як абревіатура XOR), аби відрізнити її від диз'юнкції. Вона є істиною, лише коли x та y різні.
Третя операція, обернена до виключної диз'юнкції, називається еквівалентність або булева рівність: x ≡ y буде істиною, лише коли x та y мають однакове значення.
Для двох даних операндів, кожен з яких має 22 = 4 можливих комбінації входів. Оскільки кожен вихід може мати два можливих значення, існує загалом 24 = 16 можливих булевих операцій.
Закони Законом у булевій алгебрі може виступати тотожність між двома булевими виразами такого вигляду як x∨(y∨z) = (x∨y)∨z, де булевий вираз (або логічне висловлювання) визначається як вираз, що побудований зі змінних та констант 0 та 1 та операцій між ними ∧, ∨, та ¬. Це поняття можна поширити й до виразів, що містять інші булеві операції, такі як ⊕, →, та ≡, але для формулювання законів таке розширення операцій не є необхідним. Для таких цілей додають визначення булевої алгебри як будь-якої моделі булевих законів, і як засіб для виведення нових законів з наявних, як наприклад доведення, що x∨(y∧z) = x∨(z∧y) з y∧z = z∧y.
Закони монотонності Булева алгебра задовольняє багатьом відповідним законам звичайної алгебри, якщо зіставити операції ∨ з додаванням, а ∧ з множенням. Зокрема такі закони є спільними для обох типів алгебр:
| Асоціативність операції : ||style="width:2em"| ||style="text-align: right"| || |- | Асоціативність операції : || ||style="text-align: right"| || |- | Комутативність операції : || ||style="text-align: right"| || |- | Комутативність операції : || ||style="text-align: right"| || |- | Дистрибутивність операції over : || ||style="text-align: right"| || |- | Ідентичність для : || ||style="text-align: right"| || |- | Ідентичність для : || ||style="text-align: right"| || |- | Анігілятор для : || ||style="text-align: right"| ||
Такі закони є дійсними в булевій алгебрі, але не дійсні у звичайній алгебрі: {| |- Анігілятор для : || ||style="text-align: right"| || |- | Анігілятор для : || ||style="text-align: right"|
| Ідемпотентність : || ||style="text-align: right"| || |- | Ідемпотентність : || ||style="text-align: right"| || |- | Абсорбція 1: || ||style="text-align: right"| || |- | Абсорбція 2: || ||style="text-align: right"| || |- | Дистрибутивність операції над :
| Дистрибутивність операції над : |
Якщо прийняти x = 2 в третьому наведеному вище законі, ми бачимо, що це не закон зі звичайної алгебри, оскільки 2 × 2 = 4. Решта п'ять законів можна фальсифікувати у звичайній алгебрі, якщо прийняти, що значення всіх змінних буде 1, наприклад, у законі абсорбції 1 ліва сторона відношення була б 1(1 + 1) = 2, а права частина рівняння була 1, і так далі.
Усі ці закони, що розглядалися досі, були для кон'юнкції та диз'юнкції. Ці дві операції мають властивість, що за зміни будь-якого з аргументів вихід залишиться або незмінним, або змінить своє значення так само як вхід. Аналогічно, зміна значення будь-якої змінної з 0 на 1 ніколи не призведе до того, що вихід змінить своє значення з 1 на 0. Операції з такою властивістю називають монотонними. Таким робом, усі аксіоми досі були для монотонної булевої логіки. Немонотонність з'являється через операцію доповнення ¬, що наведено далі.
Закони немонотонності Операція доповнення (заперечення) визначається такими двома законами.
Усі властивості заперечення, зокрема закони, що наведені нижче, випливають з двох вищенаведених законів.
Як у звичайній, так і в булевій алгебрі, операція заперечення працює як обмін пари елементів, тому в обох алгебрах вона задовольняє закону подвійного заперечення (також називається законом інволюції).
Але тоді як «звичайна алгебра» задовольняє таким двом законам:
булева алгебра задовольняє законам де Моргана:
Повнота Закони, описані вище, визначають булеву алгебру в тому сенсі, що з них випливають усі інші наслідки. Для цього достатньо законів доповнення 1 та 2, разом із законами монотонності. Отже, їх можна вважати повною множиною законів або однією з можливих систем аксіоматизації булевої алгебри. Кожен закон булевої алгебри випливає логічним чином із цих аксіом. Крім того, булеві алгебри можна визначити як моделі з цих аксіом.
Принцип двоїстості
Принцип: Якщо {X, R} — частково впорядкована множина, тоді {X, R(обернена)} також частково впорядкована множина.
Ніякої магії у виборі символів для позначення логічних значень булевої алгебри не існує. Замість 0 і 1 можна було б використовувати, наприклад, α та β, доки ми робимо це послідовним чином повсюди, це досі залишатиметься булевою алгеброю, але з явними зовнішніми відмінностями.
Припустимо також, що ми переназвали 0 та 1 відповідно на 1 та 0. Тоді це також залишатиметься булевою алгеброю, що навіть оперує з тими самими значеннями. Однак вона не буде ідентичною до нашої початкової булевої алгебри, оскільки тепер операція ∨ поводитиметься так, як поводила себе операція ∧ і навпаки. Тож, вони також матимуть зовнішні відмінності, які показують, що ми змінили позначення, не дивлячись на те, що ми досі використовуємо 0-і та 1-і.
Але якщо в додаток до того, що ми замінили місцями імена змінних, ми замінимо місцями імена двох двійкових операцій, тепер немає ніякого сліду від того, що ми зробили. Кінцевий результат повністю не відрізняється від того, з чого ми почали. Ми помітимо, що колонки для операцій x∧y та x∨y у таблицях істинності змінили свої місця, але ця відмінність є незначною.
Коли існує така пара операцій, для яких усе залишається незмінним, якщо всі пари були одночасно взаємно змінені, ми називаємо такі елементи кожної пари двоїстими один з одним. У такий спосіб, 0 та 1 є двоїстими, і операції ∧ та ∨ також є двоїстими. Принцип двоїстості, також називають двоїстістю де Моргана, за якою стверджують, що булева алгебра залишається незмінною, якщо взаємно замінити всі двоїсті пари.
Аксіоми , інволютивність заперечення, закон зняття подвійного заперечення
Логічні операції Простим і найширше вживаним прикладом такої алгебричної системи є множина B, що складається всього з двох елементів: B = { Хиба (0), Істина (1) } Зазвичай у математичних виразах Хиба ототожнюється з логічним нулем, а Істина — з логічною одиницею, а операції заперечення (НІ), кон'юнкції (І) та диз'юнкції (АБО) визначаються у звичному нам розумінні. Легко показати, що на цій множині B можна задати чотири унарні та шістнадцять бінарних відношень і всі їх може бути отримано через суперпозицію трьох обраних операцій.