Алгебра логіки

Алгебра логіки (Булева алгебра, Булева логіка, двійкова логіка, двійкова алгебра, англ. Boolean algebra) — розділ математичної логіки, що вивчає систему логічних операцій над висловлюваннями. В алгебрі логіки значенням змінних є значення істинності істина або хибність, які як правило визначаються як 1 і 0 відповідно. На відміну від елементарної алгебри, в якій значеннями змінних є числа, а основними операціями є додавання і множення, основними операціями Булевої алгебри є кон'юнкція операція І позначається як ∧, диз'юнкція АБО позначається як ∨, і заперечення НІ позначається як ¬. Таким чином формалізм для описання логічних відношень є аналогічним тому, як описуються числові відношення у елементарній алгебрі.

Булеву алгебру запропонував Джордж Буль у своїй книзі Математичний аналіз логіки (1847), і більш детально у наступній книзі Дослідження законів думки (1854). Відповідно до Гантінгтона, термін "Булева алгебра" вперше запропонував Шеффер в 1913, хоча Чарлз Сандерс Пірс в 1880 дав назву "Булева алгебра із однією сталою" першій главі своєї книги "Найпростіша математика". Булева алгебра є фундаментальною основою для розвитку цифрової електроніки, і втілена в усіх мовах програмування. Вона також використовується у теорії множин і статистиці.

Визначення

Базовими елементами, якими оперує алгебра логіки, є висловлювання.

Висловлювання будуються над множиною {B, $\lnot$, $\land$, $\lor$, 0, 1}, де B — непорожня множина, над елементами якої визначені три операції:

$\lnot$ заперечення (унарна операція),

$\land$ кон'юнкція (бінарна),

$\lor$ диз'юнкція (бінарна),

а логічний нуль 0 і логічна одиниця 1 — константи.

Так само використовуються назви

• диз'юнкт — пропозиціональна формула, що є диз'юнкцією одного або більше літералів (наприклад $x_{1}\lor \neg x_{2}\lor x_{4}$).
• кон'юнктив — пропозиціональна формула, що є кон'юнкцією одного або більше літералів (наприклад $x_{1}\land \neg x_{2}\land x_{4}$).

Унарна операція заперечення в тексті формул оформляється або у вигляді значка перед операндом ($\lnot x$) або у вигляді риси над операндом (${\bar {x}}$), що компактніше, але в цілому менш помітно.

Предмет вивчення

Спочатку проблематика алгебри логіки перетиналась з проблематикою алгебри множин (теоретико-множинні операції).

Проте із закінченням формування теорії множин (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 if x = 0.

Альтернативним способом значення x∧y, x∨y, та ¬x можна представити у табличному вигляді для всіх можливих значень за допомогою таблиць істинності наступним чином.

$x$ $y$ $x\wedge y$ $x\vee y$ 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1

$x$ $\neg x$ 0 1 1 0

Якщо значення істинності 0 та 1 інтерпретувати як цілі числа, ці операції можна було задати як звичайні операції арифметики (де x + y використовує додавання а xy використовує множення), або як функції мінімуму/максимуму:

${\begin{aligned}x\wedge y&=xy=\min(x,y)\\x\vee y&=x+y-xy=\max(x,y)\\\neg x&=1-x\end{aligned}}$

Можна вважати, що лише заперечення і одна із двох операцій, що залишилися, є базовими, оскільки наступні рівняння дозволяють визначити кон'юнкцію через операції заперечення та диз'юнкцію, і навпаки:

${\begin{aligned}x\wedge y&=\neg (\neg x\vee \neg y)\\x\vee y&=\neg (\neg x\wedge \neg y)\end{aligned}}$

Вторинні операції

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

$x\rightarrow y=\neg {x}\vee y$

$x\oplus y=(x\vee y)\wedge \neg {(x\wedge y)}=(x\wedge \neg y)\vee (\neg x\wedge y)$

$x\equiv y=\neg {(x\oplus y)}=(x\wedge y)\vee (\neg x\wedge \neg y)$

Ці визначення дають наступні таблиці істинності, в яких показані значення цих операцій для всіх можливих вхідних значень.

$x$	$y$	$x\rightarrow y$	$x\oplus y$	$x\equiv y$
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 мають однакове значення.

Для двох даних операндів, кожен з яких має 2² = 4 можливих комбінації входів. Оскільки кожен вихід може мати два можливих значення, існує загалом 2⁴ = 16 можливих булевих операцій.

Закони

Законом в булевій алгебрі може виступати тотожність між двома булевими виразами такого вигляду як x∨(y∨z) = (x∨y)∨z, де булевий вираз (або логічне висловлювання) визначається як вираз, що побудований із змінних та констант 0 та 1 та операцій між ними ∧, ∨, та ¬. Це поняття можна поширити і до виразів, що містять інші булеві операції, такі як ⊕, →, та ≡, але для формулювання законів, таке розширення операцій не є необхідним. Для таких цілей додають визначення булевої алгебри як будь-якої моделі булевих законів, і як засіб для виведення нових законів із існуючих, як наприклад доведення що x∨(y∧z) = x∨(z∧y) із y∧z = z∧y.

Закони монотонності

Булева алгебра задовольняє багатьом відповідним законам звичайної алгебри, якщо якщо співставити операції ∨ із додаванням, а ∧ із множенням. Зокрема наступні закони є спільними для обох типів алгебр:

Асоціативність операції $\vee$:		$x\vee (y\vee z)$	$=(x\vee y)\vee z$
Асоціативність операції $\wedge$:		$x\wedge (y\wedge z)$	$=(x\wedge y)\wedge z$
Комутативність операції $\vee$:		$x\vee y$	$=y\vee x$
Комутативність операції $\wedge$:		$x\wedge y$	$=y\wedge x$
Дистрибутивність операції $\wedge$ over $\vee$:		$x\wedge (y\vee z)$	$=(x\wedge y)\vee (x\wedge z)$
Ідентичність для $\vee$:		$x\vee 0$	$=x$
Ідентичність для $\wedge$:		$x\wedge 1$	$=x$
Анігілятор для $\wedge$:		$x\wedge 0$	$=0$

Наступні закони є дійсними в булевій алгебрі, але не дійсні в звичайній алгебрі:

Анігілятор для $\vee$:		$x\vee 1$	$=1$
Ідемпотентність $\vee$:		$x\vee x$	$=x$
Ідемпотентність $\wedge$:		$x\wedge x$	$=x$
Абсорбція 1:		$x\wedge (x\vee y)$	$=x$
Абсорбція 2:		$x\vee (x\wedge y)$	$=x$
Дистрибутивність операції $\vee$ над $\wedge$:		$x\vee (y\wedge z)$	$=(x\vee y)\wedge (x\vee z)$

Якщо прийняти x = 2 в третьому наведеному вище законі, ми бачимо що це не закон із звичайної алгебри, оскільки 2×2 = 4. Решта п'ять законів можна фальсифікувати у звичайні алгебрі, якщо прийняти що значення усіх змінних буде 1, наприклад, в законі абсорбції 1 ліва сторона відношення була б 1(1+1) = 2, а права частина рівняння була 1, і так далі.

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

Закони немонотонності

Операція доповнення (заперечення) визначається наступними двома законами.

${\begin{aligned}&{\text{Доповнення 1}}&x\wedge \neg x&=0\\&{\text{Доповнення 2}}&x\vee \neg x&=1\end{aligned}}$

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

Як у звичайній так і у булевій алгебрі, операція заперечення працює як обмін пари елементів, тому в обох алгебрах вона задовольняє закону подвійного заперечення (також називається законом інволюції)

${\begin{aligned}&{\text{Подвійне заперечення}}&\neg {(\neg {x})}&=x\end{aligned}}$

Але тоді як «звичайна алгебра» задовольняє наступним двом законам

${\begin{aligned}(-x)(-y)&=xy\\(-x)+(-y)&=-(x+y)\end{aligned}}$

Булева алгебра задовольняє Законам де Моргана:

${\begin{aligned}&{\text{де Моргана 1}}&\neg x\wedge \neg y&=\neg {(x\vee y)}\\&{\text{де Моргана 2}}&\neg x\vee \neg y&=\neg {(x\wedge y)}\end{aligned}}$

Повнота

Закони описані вище визначають булеву алгебру, в тому сенсі що з них випливають усі інші наслідки. Для цього достатньо законів доповнення 1 та 2, разом із законами монотонності. Таким чином їх можна вважати повною множиною законів або однією із можливих систем аксоіматизації булевої алгебри. Кожен закон булевою алгебри випливає логічним чином із цих аксіом. Крім того, булеві алгебри можна визначити як моделі із цих аксіом.

Аксіоми

1. ${\bar {\bar {x}}}=x$, інволютивність заперечення, закон зняття подвійного заперечення
2. $x\lor {\bar {x}}=1$
3. $\ x\lor 1=1$
4. $\ x\lor x=x$
5. $\ x\lor 0=x$
6. $\ x\land {\bar {x}}=0$
7. $\ x\land x=x$
8. $\ x\land 0=0$
9. $\ x\land 1=x$

Логічні операції

Простим і найширше вживаним прикладом такої алгебраїчної системи є множина B, що складається всього з двох елементів :

B = { Хибність (0), Істина (1) }

Як правило, в математичних виразах Хибність ототожнюється з логічним нулем, а Істина — з логічною одиницею, а операції заперечення (НІ), кон'юнкції (ТА) і диз'юнкції (АБО) визначаються у звичному нам розумінні. Легко показати, що на цій множині B можна задати чотири унарні та шістнадцять бінарних відношень і усі їх може бути отримано через суперпозицію трьох обраних операцій.

Спираючись на цей математичний інструментарій, логіка висловлювань вивчає висловлювання і предикати. Також вводяться додаткові операції, такі як еквівалентність $\leftrightarrow$ («тоді і тільки тоді, коли»), імплікація $\rightarrow$ («отже»), складання по модулю два $\oplus$ («виключна диз'юнкція»), штрих Шефера $\mid$, стрілка Пірса $\downarrow$ та інші.

Логіка висловлювань послужила основним математичним інструментом при створенні комп'ютерів. Вона легко перетворюється в бітову логіку: істинність висловлювання позначається одним бітом (0 — ХИБНІСТЬ, 1 — ІСТИНА); тоді операція $\neg$ набуває суті вирахування з одиниці; $\lor$ — немодульного додавання; & — множення; $\leftrightarrow$ — рівності; $\oplus$ — в буквальному розумінні сума за модулем 2 (виключне АБО — XOR); $\mid$ — сума не перевищує 1 (тобто A $\mid$ B = (A + B) <= 1).

Згодом булеву алгебру було узагальнено від логіки висловлювань шляхом введення характерних для логіки висловлювань аксіом. Це дозволило розглядати, наприклад, логіку кубітів, тризначну логіку (коли є три варіанти істинності висловлювання: «істина», «хибність» і «невизначено») тощо.

Властивості логічних операцій

1. Комутативність: x$\circ$y = y$\circ$x, $\circ \in${&, $\lor ,\oplus ,\sim ,\mid ,\downarrow$}.
2. Ідемпотентність: x$\circ$x = x, $\circ \in${&, $\lor$}.
3. Асоціативність: (x$\circ$y)$\circ$z = x$\circ$(y$\circ$z), $\circ \in${&, $\lor ,\oplus ,\sim$}.
4. Дистрибутивність кон'юнкцій і диз'юнкції відносно диз'юнкції, кон'юнкції і суми за модулем два відповідно:
   • $x\land (y\lor z)=x\land y\lor x\land z$,
   • $x\lor y\land z=(x\lor y)\land (x\lor z)$,
   • $x\land (y\oplus z)=x\land y\oplus x\land z$.
5. Закони де Мо́ргана:
   • ${\overline {x\land y}}={\bar {x}}\lor {\bar {y}}$,
   • ${\overline {x\lor y}}={\bar {x}}\land {\bar {y}}$.
6. Закони поглинання :
   • $x\land (x\lor y)=x$,
   • $x\lor x\land y=x$.
7. Інші (1):
   • $x\land {\bar {x}}=x\land 0=x\oplus x=0$.
   • $x\lor {\bar {x}}=x\lor 1=x\sim x=x\rightarrow x=1$.
   • $x\lor x=x\land x=x\land 1=x\lor 0=x\oplus 0=x$.
   • $x\oplus 1=x\rightarrow 0=x\sim 0=x\mid x=x\downarrow x={\bar {x}}$.
   • ${\bar {\bar {x}}}=x$, інволютивність заперечення, закон зняття подвійного заперечення.
8. Інші(2) :
   • $x\oplus y=x\land {\bar {y}}\lor {\bar {x}}\land y=(x\lor y)\land ({\bar {x}}\lor {\bar {y}})$.
   • $x\sim y={\overline {x\oplus y}}=1\oplus x\oplus y=x\land y\lor {\bar {x}}\land {\bar {y}}=(x\lor {\bar {y}})\land ({\bar {x}}\lor y)$.
   • $x\rightarrow y={\bar {x}}\lor y=x\land y\oplus x\oplus 1$.
   • $x\lor y=x\oplus y\oplus x\land y$.
9. Інші(3) (Доповнення законів де Мо́ргана) :
   • $x\mid y={\overline {x\land y}}={\bar {x}}\lor {\bar {y}}$.
   • $x\downarrow y={\overline {x\lor y}}={\bar {x}}\land {\bar {y}}$.

Існують методи спрощення логічної функції: наприклад, Карта Карно, метод Куайна — Мак-Класкі

Представлення у вигляді діаграм

Діаграма Венна

Діаграма Венна — це графічне представлення булевих операцій за допомогою зафарбованих областей, що перекриваються. По одній області для кожної змінної, всі області круглі як показано на прикладах. Внутрішня і зовнішня частина області x відповідає відповідно значенням 1 (істина) та 0 (хибність) для змінної x. Зафарбована область показує значення операції для кожної комбінації цих областей, де зафарбована область означає 1, а не зафарбована - 0 (але в деяких книжках може зустрітися і навпаки).

Діаграми Венна на малюнку знизу показують операції кон'юнкції x∧y, диз'юнкції x∨y, та доповнення ¬x.

Діаграми Венна для кон'юнкції, диз'юнкції та доповнення

Для кон'юнкції, регіон в середині двох кругів зафарбований, що означає що вираз x∧y дорівнює 1, коли обидві змінні мають значення 1. Інші області лишилися не зафарбованими, аби зазначити, що x∧y дорівнює 0 для всіх інших комбінацій.

На другій діаграмі, що показує диз'юнкцію x∨y зафарбована область, що знаходиться в середині двох кіл одночасно. Третя діаграма представляє доповнення ¬x, де зафарбована область не в середині кола.

Тут не показані діаграми для сталих 0 та 1, оскільки вони тривіальні, і представляються незафарбованим або зафарбованим прямокутником, без кіл в середині. Однак ми б могли розмістити коло для змінної x в цих прямокутниках, в такому випадку це б позначало функцію із одним аргументом, x, що позначає те саме значення, незалежно від x, що називається константною функцією. Що стосується результатів функцій, то константи і константні функції не відрізняються; їх відмінність полягає в тому, що константа не приймає ніяких аргументів, і називається нульовою операцією, в той час як константна функція приймає один аргумент, який ігнорується, і тому є унарною операцією.

Діаграми Венна є корисними для візуалізації законів. Закони комутативності для ∧ та ∨ можна побачити із симетричності діаграм: бінарна операція, що не є комутативною не мала б симетричної діаграми, оскільки заміна місцями x та y призвело до горизонтального віддзеркалення діаграми, і відсутність комутативності б відзначилася у не симетричності діаграми.

Ідемпотентність операцій ∧ та ∨ можна було б зобразити зсунувши два кола разом і зазначивши, що зафарбована область тоді стає цілим колом, як обох ∧ та ∨.

Цифрові логічні кола

Цифрова логіка застосовує булеву алгебру для 0 та 1 до електронної апаратури, що складається із логічних елементів з'єднаних між собою, і які утворюють електричну схему. Кожний елемент виконує булеву операцію, і в різних системах позначень позначається таким чином, що його вигляд ідентифікує певну операцію. Форми позначень для елементів, що позначають кон'юнкцію (І-вентиль), диз'юнкцію (АБО-вентиль), і доповнення (інвертори) виглядають наступним чином.

Лінії по лівій стороні кожного елементу позначають вхідні з'єднання або порти. Значення на вході задається напругою. Для так званої логіки з "активним високим рівнем", 0 задається значенням напруги близьким до нуля або "землі", в той час як 1 задається значенням напруги близьким до джерела напруги; при активному низькому рівні все буде навпаки. Лінія по правій стороні від кожного елемента задає вихідний порт, який як правило має ті самі узгодження щодо напруги, що і вхідні порти.

Доповнення виконується інвертуючим вентилем. Трикутник позначає операцію, яка просто копіює вхід на вихід; невелике коло на виході позначає фактичну дію доповнення до входу. У даній системі позначень розташування кола біля будь-якого порту означає, що сигнал проходячи через цей порт буде інвертований пройшовши крізь нього, не залежно від того це вхідний чи вихідний порт.

Історія

Засади алгебри логіки сформулював британський Джорджем Булем в 1847 році. Алгебра Буля передувала сучасному розвитку абстрактної алгебри і математичної логіки; і вважають, що вона пов'язана із появою обох цих областей. В абстрактному тлумаченні, булава алгебра була розвинена в кінці 19-му столітті, чому значно приклали зусилля математики Вільям Джевонс, Ернст Шредер, Едвард Гантінгтон та інші, доки вона не досягла сучасного поняття (абстрактної) математичної структури. Наприклад, імперичні спостереження про те, що можливо маніпулювати виразами у алгебрі множин, якщо перевести їх у вирази булевої алгебри пояснюються в сучасних термінах, що алгебра множин це Булева алгебра. Насправді, М. Г. Стоун в 1936 довів, що кожна булева алгебра є ізоморфною полю множин.

В 1930-их, під час вивчення перемиканні електричних кіл, Клод Шеннон помітив, що в даній темі також можна використовувати закони булевої алгебри, і запропонував комутаційну алгебру, що дозволяє аналізувати і проектувати схеми за допомогою алгебраїчних методів в термінах логічних елементів. При розробці схемотехніки сьогодні, немає великої необхідності розглядати інші булеві алгебри, тому поняття "комутаційна алгебра" і "булева алгебра" часто використовуються як взаємозамінні. При розробці схем комбінаційної логіки фундаментальною задачею є ефективна реалізація булевих функцій. Сучасні засоби автоматизації проектування електронних систем для інтегральних схем дуже великого масштабу часто покладаються на ефективне представлення булевих функцій, що називають (скороченими впорядкованими) двійковими діаграмами рішень для синтезу логіки та формальної верифікації.

Логічні вирази, які можна представити у класичному численні висловлювань мають еквівалентні вирази у булевій алгебрі. Таким чином, термін булева логіка іноді використовується для зазначення числення висловлювань, що здійснюється в такий спосіб. Булевої алгебри не достатньо для роботи із логічними формулами, в яких використовують квантори, таких як в логіці першого порядку. Хоча розвиток математичної логіки не відповідає Булевій, зв'язок між його алгеброю і логікою пізніше був закладений в основу алгебраїчної логіки, що також вивчає алгебраїчні системи багатьох інших логік. Задача прийняття рішень про те чи є змінні даної булевої формули (висловлювання) приймати такі значення, що формула буде розрахована як істина називається задачею здійсненності булевих формул, і є дуже вадливою для теоретичної інформатики, що є першою задачею для якої було показано, що вона має складність NP-повної задачі. Тісно пов'язана з цим модель обчислення, що відома як булева схема співвідносить часову складність (алгоритму) із складністю схем.

Див. також

• Булева множина
• Булева функція
• Таблиці істинності
• Закони де Моргана
• Карта Карно
• Метод Куайна — Мак-Класкі
• Алгебра Кодда

Література

• Винберг Э. Б. Курс алгебри. — 4-е изд. — Москва : МЦНМО, 2011. — 592 с. — ISBN 978-5-94057-685-3.(рос.)

Посилання

• А́ЛГЕБРА ЛО́ГІКИ //ЕСУ