Перегляд вихідного коду сторінки Алгебра логіки

{{не плутати|Булева алгебра (структура)|Булевою алгеброю (структурою)|яка також вживається для означення загальнішої [[алгебрична структура|алгебричної структури]]}}
{{unibox}}
'''Алгебра логіки''' (''Булева алгебра'', ''Булева логіка'', ''двійкова логіка'', ''двійкова алгебра'', {{lang-en|Boolean algebra}})&nbsp;— розділ [[математична логіка|математичної логіки]], що вивчає [[формальна система|систему]] [[логічний сполучник|логічних операцій]] над [[числення висловлень|висловлюваннями]].<ref>{{БСЭ|010299|Алгебра логіки}}</ref> В алгебрі логіки значенням [[Змінна|змінних]] є [[значення істинності]] ''істина'' або ''хиба'', які зазвичай визначаються як 1 і 0 відповідно. На відміну від [[Елементарна алгебра|елементарної алгебри]], у якій значеннями змінних є числа, а основними операціями є додавання і множення, основними операціями булевої алгебри є [[кон'юнкція]] ''операція <u>І</u>'' ({{lang-en|AND}}) позначається як ∧, [[Диз'юнкція (логіка)|диз'юнкція]] ''<u>АБО</u>'' ({{lang-en|OR}}) позначається як ∨, і [[заперечення]] ''<u>НІ</u>'' ({{lang-en|NOT}}) позначається як ¬. Таким чином, формалізм для описання логічних відношень є аналогічним тому, як описуються числові відношення в елементарній алгебрі.

<!--{{Увага|'''Алгебра логіки''' як [[алгебрична структура]] поряд з [[алгебра множин|алгеброю множин]] є частковими випадками більш загальної [[булева алгебра (структура)|булевої алгебри]].}}-->
Булеву алгебру запропонував [[Джордж Буль]] у своїй книзі ''Математичний аналіз логіки'' (1847), і більш детально в наступній книзі ''{{нп|The Laws of Thought|Дослідження законів думки|en|The Laws of Thought}}'' (1854).<ref>{{Cite book
  | last = Boole
  | first = George
  | authorlink = George Boole
  | title = An Investigation of the Laws of Thought
  | url = https://archive.org/details/lawsofthought0000bool
  | publisher = Prometheus Books
  | origyear = 1854
  | year = 2003
  | isbn = 978-1-59102-089-9 }}</ref>
Відповідно до {{нп|Едуард Верміле Гантінгтон|Гантінгтона|en|Edward Vermilye Huntington}}, термін «Булева алгебра» вперше запропонував [[Генрі Шеффер|Шеффер]] у 1913,<ref>«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, «[http://www.ams.org/journals/tran/1933-035-01/S0002-9947-1933-1501684-X/S0002-9947-1933-1501684-X.pdf New sets of independent postulates for the algebra of logic, with special reference to Whitehead and Russell's ''Principia mathematica''] {{Webarchive|url=https://web.archive.org/web/20170908084210/http://www.ams.org/journals/tran/1933-035-01/S0002-9947-1933-1501684-X/S0002-9947-1933-1501684-X.pdf |date=8 вересня 2017 }}», in
''Trans. Amer. Math. Soc.'' '''35''' (1933), 274—304; footnote, page 278.</ref>
хоча [[Чарлз Сандерс Пірс]] у 1880 дав назву «Булева алгебра з однією сталою» першій главі своєї книги «Найпростіша математика».<ref name="Peirce1931">{{cite book|first=Charles S.|last=Peirce|author-link=Charles Sanders Peirce|title=Collected Papers|url=https://books.google.com/books?id=3JJgOkGmnjEC&pg=RA1-PA13|volume=3|year=1931|publisher=Harvard University Press|isbn=978-0-674-13801-8|page=13|accessdate=7 лютого 2019|archive-date=27 липня 2020|archive-url=https://web.archive.org/web/20200727125021/https://books.google.com/books?id=3JJgOkGmnjEC&pg=RA1-PA13}}</ref>
Булева алгебра є фундаментальною основою для розвитку [[Цифрова електроніка|цифрової електроніки]], і втілена в усіх мовах програмування. Вона також використовується в [[Теорія множин|теорії множин]] і [[Статистика|статистиці]].<ref name="givhal">{{Cite book
 | last1 = Givant
 | first1 = Steven
 | first2 = Paul
 | last2 = Halmos
 | year = 2009
 | title = Introduction to Boolean Algebras
 | url = https://archive.org/details/introductiontobo0000giva
 | publisher = Undergraduate Texts in Mathematics, [[Springer Science+Business Media|Springer]]
 | isbn = 978-0-387-40293-2}}</ref>

== Визначення ==
Базовими елементами, якими оперує алгебра логіки, є [[Висловлювання (логіка)|висловлювання]].

Висловлювання будуються над [[множина|множиною]] {B, <math>\lnot</math>, <math>\land</math>, <math>\lor</math>, 0, 1}, де B&nbsp;— непорожня множина, над елементами якої визначені три [[операція (математика)|операції]]:
: '''<math>\lnot</math>''' ''[[заперечення]]'' ([[унарна операція]]),
: '''<math>\land</math>''' ''[[кон'юнкція]]'' ([[бінарна операція|бінарна]]),
: '''<math>\lor</math>''' ''[[диз'юнкція (логіка)|диз'юнкція]]'' ([[бінарна операція|бінарна]]),
: а логічний нуль '''0''' і логічна одиниця '''1'''&nbsp;— [[константа|константи]].

Так само використовуються назви
* ''диз'юнкт''&nbsp;— пропозиціональна формула, що є [[диз'юнкція (логіка)|диз'юнкцією]] одного або більше [[Літерал (математична логіка)|літералів]] (наприклад <math>x_1 \lor \neg x_2 \lor x_4</math>).
* ''кон'юнктив''&nbsp;— пропозиціональна формула, що є [[кон'юнкція|кон'юнкцією]] одного або більше літералів (наприклад <math>x_1 \land \neg x_2 \land x_4</math>).

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

=== Значення ===
Тоді як в елементарній алгебрі вирази зазвичай виражаються в [[Число|числах]], в алгебрі логіки вони виражають [[значення істинності]] ''істина'' і ''хиба''. Ці значення задають за допомогою [[біт]]ів (або двійкових чисел), а саме 0 та 1. Вони не поводять себе так само як [[цілі числа]] 0 та 1, для яких 1 + 1 = 2, а можуть визначатися як елементи {{нп|Двоелементне поле GF(2)|двоелементного поля GF(2)|en|GF(2)}}, що є [[Модульна арифметика|цілочисельною арифметикою за модулем 2]], для якої 1 + 1 = 0. Алгебра логіки також вивчає [[Функція (математика)|функції]], що приймають значення в множині {0,&nbsp;1}.

=== Предмет вивчення ===
Спочатку проблематика алгебри логіки перетиналася з проблематикою [[алгебра множин|алгебри множин]] (теоретико-множинні операції).

Проте із закінченням формування [[теорія множин|теорії множин]] ([[1870-ті|70-і роки 19&nbsp;ст.]]), до складу якої входила алгебра множин, і подальшим розвитком [[математична логіка|математичної логіки]], предмет алгебри логіки значно змінився.

Сучасна алгебра логіки розглядає операції над висловлюваннями (див. [[Числення висловлень]]) як [[булева функція|булеву функцію]] і вивчає відносно них такі питання, як:
* [[таблиці істинності]];
* [[функціональна повнота]];
* [[замкнений клас функцій алгебри логіки|замкнені класи]];
* представлення у вигляді: [[Диз'юнктивна нормальна форма|ДНФ]], [[Кон'юнктивна нормальна форма|КНФ]], [[поліном Жегалкіна|полінома Жегалкіна]].

== Операції ==

=== Базові операції ===
Як уже зазначалося, базовими операціями булевої алгебри (алгебри логіки) є такі логічні операції:
* І ([[кон'юнкція]]), позначається ''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'' можна представити в табличному вигляді для всіх можливих значень за допомогою [[Таблиці істинності|таблиць істинності]] таким способом.

<dl>
<dd>
{{col-begin}}
{{col-break|width=9%}}
{| class="wikitable" style="text-align: center"
|-
!<math>x</math>
!<math>y</math>
!<math>x \wedge y</math>
!<math>x \vee y</math>
|-
!0
!0
| 0 || 0
|-
!1
!0
| 0 || 1
|-
!0
!1
| 0 || 1
|-
!1
!1
| 1 || 1
|}
{{col-break}}
{| class="wikitable" style="text-align: center"
|-
!<math>x</math>
!<math>\neg x</math>
|-
!0
|1
|-
!1
|0
|}
{{col-end}}
</dd>
</dl>

Якщо значення істинності 0 та 1 інтерпретувати як цілі числа, ці операції можна було задати як звичайні операції арифметики (де ''x'' + ''y'' використовує додавання, а ''xy'' використовує множення), або як функції мінімуму/максимуму:
: <math>
\begin{align}
x \wedge y & = xy = \min(x,y)\\ 
x \vee y & = x + y - xy = \max(x,y)\\ 
\neg x & = 1 - x
\end{align}
</math>

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

: <math>
\begin{align}
x \wedge y & = \neg(\neg x \vee \neg y) \\
x \vee y & = \neg(\neg x \wedge \neg y)
\end{align}
</math>

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

: <math>x \rightarrow y = \neg{x} \vee y</math>
: <math>x \oplus y = (x \vee y) \wedge \neg{(x \wedge y)} = (x \wedge \neg y) \vee (\neg x \wedge y)</math>
: <math>x \equiv y = \neg{(x \oplus y)} = (x \wedge y) \vee (\neg x \wedge \neg y)</math>

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

: {| class="wikitable" style="text-align: center"
|-
!<math>x</math>
!<math>y</math>
!<math>x \rightarrow y</math>
!<math>x \oplus y</math>
!<math>x \equiv y</math>
|-
!0
!0
| 1 || 0 || 1
|-
!1
!0
|0 || 1 || 0
|-
!0
!1
|1 || 1 || 0
|-
!1
!1
| 1 || 0 || 1
|}

Перша операція, ''x''&nbsp;→&nbsp;''y'', називається '''імплікацією'''. Якщо ''x'' є істинним, тоді за значення виразу ''x''&nbsp;→&nbsp;''y'' приймається значення ''y''. Але якщо ''x'' приймає хибне значення, то значення ''y'' можна було б ігнорувати; однак ця операція повинна повернути ''деяке'' логічне значення, і існує лише два варіанти вибору. То ж за визначенням, ''x''&nbsp;→&nbsp;''y'' є ''істиною'' коли x є хибним.

Друга операція, ''x''&nbsp;⊕&nbsp;''y'', називається '''[[Виключна диз'юнкція|виключною диз'юнкцією]]''' (часто задається як абревіатура XOR), аби відрізнити її від диз'юнкції. Вона є істиною, лише коли ''x'' та ''y'' різні.

Третя операція, обернена до виключної диз'юнкції, називається '''еквівалентність''' або булева рівність: ''x''&nbsp;≡&nbsp;''y'' буде істиною, лише коли ''x'' та ''y'' мають однакове значення.

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

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

=== Закони монотонності ===
Булева алгебра задовольняє багатьом відповідним законам звичайної алгебри, якщо зіставити операції ∨ з додаванням, а ∧ з множенням. Зокрема такі закони є спільними для обох типів алгебр:<ref name="O'Regan_p33">{{cite book|author=O'Regan, Gerard|title=A brief history of computing|publisher=Springer|year=2008|isbn=978-1-84800-083-4|page=33|url=https://books.google.com/books?id=081H96F1enMC&pg=PA33|accessdate=7 лютого 2019|archive-date=27 липня 2020|archive-url=https://web.archive.org/web/20200727124324/https://books.google.com/books?id=081H96F1enMC&pg=PA33}}</ref>

:{|
|-
| Асоціативність операції <math>\vee</math>: ||style="width:2em"| ||style="text-align: right"| <math>x \vee (y \vee z)</math> || <math>= (x \vee y) \vee z</math>
|-
| Асоціативність операції <math>\wedge</math>: || ||style="text-align: right"| <math>x \wedge (y \wedge z)</math> || <math>= (x \wedge y) \wedge z</math>
|-
| Комутативність операції <math>\vee</math>: || ||style="text-align: right"| <math>x \vee y</math> || <math>= y \vee x</math>
|-
| Комутативність операції <math>\wedge</math>: || ||style="text-align: right"| <math>x \wedge y</math> || <math>= y \wedge x</math>
|-
| Дистрибутивність операції <math>\wedge</math> over <math>\vee</math>: || ||style="text-align: right"| <math>x \wedge (y \vee z)</math> || <math>= (x \wedge y) \vee (x \wedge z)</math>
|-
| Ідентичність для <math>\vee</math>: || ||style="text-align: right"| <math>x \vee 0</math> || <math>= x</math>
|-
| Ідентичність для <math>\wedge</math>: || ||style="text-align: right"| <math>x \wedge 1</math> || <math>= x</math>
|-
| Анігілятор для <math>\wedge</math>: || ||style="text-align: right"| <math>x \wedge 0</math> || <math>= 0</math>
|-
|}

Такі закони є дійсними в булевій алгебрі, але не дійсні у звичайній алгебрі:
:{|
|- Анігілятор для <math>\vee</math>: || ||style="text-align: right"| <math>x \vee 1</math> || <math>= 1</math>
|-
| Анігілятор для <math>\vee</math>: || ||style="text-align: right"| <math>x \vee 1</math>
|<math>= 1</math>
|-
| Ідемпотентність <math>\vee</math>: || ||style="text-align: right"| <math>x \vee x</math> || <math>= x</math>
|-
| Ідемпотентність <math>\wedge</math>: || ||style="text-align: right"| <math>x \wedge x</math> || <math>= x</math>
|-
| Абсорбція 1: || ||style="text-align: right"| <math>x \wedge (x \vee y)</math> || <math>= x</math>
|-
| Абсорбція 2: || ||style="text-align: right"| <math>x \vee (x \wedge y)</math> || <math>= x</math>
|-
| Дистрибутивність операції <math>\vee</math> над <math>\wedge</math>:
|
|<math>x \vee (y \wedge z)</math>
|<math>=(x \vee y) \wedge (x \vee z)</math>
|-
| Дистрибутивність операції <math>\vee</math> над <math>\wedge</math>: |
|}

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

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

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

: <math>
\begin{align}
&\text{Доповнення 1} & x \wedge \neg x & = 0 \\
&\text{Доповнення 2} & x \vee \neg x   & = 1
\end{align}
</math>

Усі властивості заперечення, зокрема закони, що наведені нижче, випливають з двох вищенаведених законів.<ref name="givhal"/>

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

: <math>
\begin{align}
&\text{Подвійне заперечення} & \neg{(\neg{x})} & = x
\end{align}
</math>

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

: <math>
\begin{align}
(-x)(-y) & = xy \\
(-x) + (-y) & = -(x + y)
\end{align}
</math>

булева алгебра задовольняє [[Правила де Моргана|законам де Моргана]]:

: <math>
\begin{align}
&\text{де Моргана 1} & \neg x \wedge \neg y & = \neg{(x \vee y)} \\
&\text{де Моргана 2} & \neg x \vee \neg y & = \neg{(x \wedge y)}
\end{align}
</math>

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

=== Принцип двоїстості ===
Принцип: Якщо {X, R}&nbsp;— [[частково впорядкована множина]], тоді {X, R(обернена)} також частково впорядкована множина.

Ніякої магії у виборі символів для позначення логічних значень булевої алгебри не існує. Замість 0 і 1 можна було б використовувати, наприклад, α та β, доки ми робимо це послідовним чином повсюди, це досі залишатиметься булевою алгеброю, але з явними зовнішніми відмінностями.

Припустимо також, що ми переназвали 0 та 1 відповідно на 1 та 0. Тоді це також залишатиметься булевою алгеброю, що навіть оперує з тими самими значеннями. Однак вона не буде ідентичною до нашої початкової булевої алгебри, оскільки тепер операція ∨ поводитиметься так, як поводила себе операція ∧ і навпаки. Тож, вони також матимуть зовнішні відмінності, які показують, що ми змінили позначення, не дивлячись на те, що ми досі використовуємо 0-і та 1-і.

Але якщо в додаток до того, що ми замінили місцями імена змінних, ми замінимо місцями імена двох двійкових операцій, ''тепер'' немає ніякого сліду від того, що ми зробили. Кінцевий результат повністю не відрізняється від того, з чого ми почали. Ми помітимо, що колонки для операцій ''x''∧''y'' та ''x''∨''y'' у таблицях істинності змінили свої місця, але ця відмінність є незначною.

Коли існує така пара операцій, для яких усе залишається незмінним, якщо всі пари були одночасно взаємно змінені, ми називаємо такі елементи кожної пари '''двоїстими''' один з одним. У такий спосіб, 0 та 1 є двоїстими, і операції ∧ та ∨ також є двоїстими. '''Принцип двоїстості''', також називають [[Правила де Моргана|двоїстістю де Моргана]], за якою стверджують, що булева алгебра залишається незмінною, якщо взаємно замінити всі двоїсті пари.

== Аксіоми ==
# <math>\bar {\bar x}=x</math>, [[Інволюція (математика)|інволютивність заперечення]], [[Закон подвійного заперечення|закон зняття подвійного заперечення]]
# <math>x\lor\bar x=1</math>
# <math>\ x\lor1=1</math>
# <math>\ x\lor x=x</math>
# <math>\ x\lor0=x</math>
# <math>\ x\land\bar x=0</math>
# <math>\ x\land x=x</math>
# <math>\ x\land0=0</math>
# <math>\ x\land1=x</math>

== Логічні операції ==
Простим і найширше вживаним прикладом такої алгебричної системи є множина B, що складається всього з двох елементів:
: B = { Хиба (0), Істина (1) }
Зазвичай у математичних виразах '''Хиба''' ототожнюється з логічним нулем, а '''Істина'''&nbsp;— з логічною одиницею, а операції заперечення (НІ), кон'юнкції (І) та диз'юнкції (АБО) визначаються у звичному нам розумінні. Легко показати, що на цій множині B можна задати чотири унарні та шістнадцять бінарних відношень і всі їх може бути отримано через суперпозицію трьох обраних операцій.

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

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

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

== Властивості логічних операцій ==
# [[Комутативність]]: x<math>\circ</math>y = y<math>\circ</math>x, <math>\circ\in</math>{&, <math>\lor, \oplus, \sim, \mid, \downarrow</math>}.
# [[Ідемпотентність]]: x<math>\circ</math>x = x, <math>\circ\in</math>{&, <math>\lor</math>}.
# [[Асоціативність]]: (x<math>\circ</math>y)<math>\circ</math>z = x<math>\circ</math>(y<math>\circ</math>z), <math>\circ\in</math>{&, <math>\lor, \oplus, \sim</math>}.
# [[Дистрибутивність]] кон'юнкцій і диз'юнкції відносно диз'юнкції, кон'юнкції і суми за модулем два відповідно:
#* <math>x\land  (y\lor z) = x\land y\lor x\land z</math>,
#* <math>x\lor y\land  z = (x\lor y)\land (x\lor z)</math>,
#* <math>x\land (y\oplus z) = x\land y\oplus x\land z</math>.
# [[Правила де Моргана|Закони де Мо́ргана]]:
#* <math>\overline{x\land y} = \bar x \lor  \bar y</math>,
#* <math>\overline{x\lor y} = \bar x\land \bar y</math>.
# Закони поглинання :
#* <math>x\land (x\lor y) = x</math>,
#* <math>x\lor x\land y = x</math>.
# Інші (1):
#* <math>x\land \bar x = x\land 0 = x\oplus x = 0</math>.
#* <math>x\lor \bar x = x\lor 1 = x\sim x = x\rightarrow x = 1</math>.
#* <math>x\lor x = x\land x = x\land 1 = x\lor 0 = x\oplus 0 = x</math>.
#* <math>x\oplus 1 = x\rightarrow 0 = x\sim 0 = x\mid x = x\downarrow x = \bar x</math>.
#* <math>\bar{\bar x} = x</math>, [[Інволюція (математика) |інволютивність заперечення]], [[Закон подвійного заперечення|закон зняття подвійного заперечення]].
# Інші(2) :
#* <math>x\oplus y = x\land \bar y \lor  \bar x\land y = (x\lor y)\land (\bar x\lor \bar y)</math>.
#* <math>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)</math>.
#* <math>x\rightarrow y = \bar x \lor  y = x\land y\oplus x\oplus 1</math>.
#* <math>x \lor  y = x \oplus y \oplus x\land y</math>.
# Інші(3) (Доповнення законів де Мо́ргана) :
#* <math>x\mid y = \overline {x\land y} = \bar x \lor  \bar y</math>.
#* <math>x\downarrow y = \overline {x\lor y}= \bar x\land \bar y</math>.

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

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

=== Діаграма Венна ===
[[Діаграма Венна]]<ref>{{cite journal |author-last=Venn |author-first=John |author-link=John Venn |title=I. On the Diagrammatic and Mechanical Representation of Propositions and Reasonings |journal=[[The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science]] |volume=10 |issue=59 |date=July 1880 |series=5 |doi=10.1080/14786448008626877 |pages=1–18 |url=https://www.cis.upenn.edu/~bhusnur4/cit592_fall2014/venn%20diagrams.pdf |dead-url=no |archive-url=https://web.archive.org/web/20170516204620/https://www.cis.upenn.edu/~bhusnur4/cit592_fall2014/venn%20diagrams.pdf |archive-date=2017-05-16 }} [http://www.tandfonline.com/doi/abs/10.1080/14786448008626877] {{Webarchive|url=https://web.archive.org/web/20200602173056/https://www.tandfonline.com/doi/abs/10.1080/14786448008626877 |date=2 червня 2020 }} [https://books.google.com/books?id=k68vAQAAIAAJ&pg=PA1] {{Webarchive|url=https://web.archive.org/web/20210803060608/https://books.google.com/books?id=k68vAQAAIAAJ&pg=PA1 |date=3 серпня 2021 }}</ref>&nbsp;— це графічне представлення булевих операцій за допомогою зафарбованих областей, що перекриваються. По одній області для кожної змінної, всі області круглі, як показано на прикладах. Внутрішня й зовнішня частина області ''x'' відповідає значенням 1 (істина) та 0 (хиба) відповідно для змінної ''x''. Зафарбована область показує значення операції для кожної комбінації цих областей, де зафарбована область означає 1, а не зафарбована&nbsp;— 0 (але в деяких книжках може зустрітися і навпаки).

Діаграми Венна на малюнку знизу показують операції кон'юнкції ''x''∧''y'', диз'юнкції ''x''∨''y'', та доповнення ¬''x''.
[[Файл:Vennandornot.svg|center|500px|thumb|Діаграми Венна для кон'юнкції, диз'юнкції та доповнення]]
Для кон'юнкції, регіон у середині двох кругів зафарбований, що означає, що вираз ''x''∧''y'' дорівнює 1, коли обидві змінні мають значення 1. Інші області лишилися не зафарбованими, аби зазначити, що ''x''∧''y'' дорівнює 0 для всіх інших комбінацій.

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

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

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

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

=== Цифрові логічні кола ===
Цифрова логіка застосовує булеву алгебру для 0 та 1 до електронної апаратури, що складається із з'єднаних між собою [[Логічний вентиль|логічних елементів]], і які утворюють [[Електрична схема|електричну схему]]. Кожний елемент виконує булеву операцію, і в різних системах позначень позначається так, що його вигляд ідентифікує певну операцію. Форми позначень для елементів, що позначають кон'юнкцію (І-вентиль), диз'юнкцію (АБО-вентиль), і доповнення (інвертори) виглядають так.<ref>{{Cite journal
  | last = Shannon
  | first = Claude
  | authorlink = Claude Shannon
  | title = The Synthesis of Two-Terminal Switching Circuits
  | journal = Bell System Technical Journal
  | volume = 28
  | pages = 59–98
  | year = 1949
  | id =
  | doi=10.1002/j.1538-7305.1949.tb03624.x}}</ref>

[[Файл:LogicGates.svg|center|400px|thumb]]
Лінії по лівій стороні кожного елемента позначають вхідні з'єднання або ''порти''. Значення на вході задається напругою. Для так званої логіки з «активним високим рівнем», 0 задається значенням напруги близьким до нуля або «землі», тоді як 1 задається значенням напруги близьким до джерела напруги; за активного низького рівня все буде навпаки. Лінія по правій стороні від кожного елемента задає вихідний порт, який переважно має ті самі узгодження щодо напруги, що й вхідні порти.

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

[[Алгебра_логіки#Принцип_двоїстості|Принцип двоїстості]], або [[правила де Моргана]], можна розуміти як твердження: що доповнення всіх трьох портів вентиля І перетворює його на вентиль АБО і навпаки, як показано на рисунку нижче. Доповнення обох портів інвертора залишає операцію незмінною.
[[Файл:DeMorganGates.GIF|center|400px|thumb]]

== Застосування ==
Алгебра логіки як числення двох логічних значень є основою для комп'ютерних схем, програмування комп'ютерів і математичної логіки, а також вона використовується в інших галузях математики, таких як теорія множин та статистика.<ref name="givhal"/>

=== Комп'ютери ===
На початку 20-го століття, декілька електротехніків інтуїтивним способом зрозуміли, що булева алгебра аналогічна поведінці певних електричних схем. [[Клод Шеннон]] формально довів, що така поведінка логічно еквівалентна булевій алгебрі в 1937 році.

Сьогодні всі сучасні комп'ютери загального призначення виконують свої функції за допомогою булевої логіки двох значень; таким чином, їхні електричні кола є фізичним втіленням булевої алгебри для двох значень. Вони досягають це багатьма способами: за допомогою напруги на з'єднаннях у високочастотних схемах і ємнісних пристроях зберігання даних, за допомогою орієнтації магнітного поля у феромагнітних пристроях зберігання інформації, за допомогою перфорації в перфокартах або паперових стрічках, і так далі. (деякі перші комп'ютери використовували десяткові кола або механізми замість двозначної логіки в електричних колах.)

Звісно, можна закодувати більше ніж два символи. Наприклад, можна використати відповідні значення в 0, 1, 2, і 3 вольта, аби закодувати алфавіт із чотирьох символів, або робити отвори різного розміру в перфокартах. На практиці, обмеження щодо швидкодії, малими розмірами, низьким енергоспоживанням об'єднуються так, що вирішальним фактором стають шуми. І стає важче відрізняти символи, коли в одному місці можуть виникнути декілька можливих символів. Замість того, щоб намагатися розрізнити чотири різні напруги на дроті, інженери цифрових схем зупинилися на двох значеннях напруги, високе і низьке.

Комп'ютери використовують булеві схеми для двох значень з описаних вище причин. Самі типові архітектури комп'ютерів використовують упорядковані послідовності булевих значень, наприклад, у 32 або 64 значень, які називають бітами. 01101000110101100101010101001011. Під час програмування на [[Машинний код|машинному коді]], [[Мова асемблера|мові асемблера]], і певних інших [[Мова програмування|мовах програмування]], програмісти працюють з низькорівневою цифровою структурою з [[Машинне слово|регістрів даних]]. Ці регістри працюють з рівнями напруги, за яких близьке до нуля значення напруги представляє булеве значення 0, і опорна напруга (часто +5V, +3.3V, +1.8V) задає булеве значення 1. Такі мови підтримують числові операції та логічні операції. У контексті, «числові» означає, що комп'ютер розглядатиме послідовність бітів як [[Двійкова система числення|двійкові числа]] (числа з основою два) і виконуватиме арифметичні операції такі як додавання, віднімання, множення або ділення. «Логічні» відноситься до логічних булевих операцій диз'юнкції, кон'юнкції і заперечення між двома послідовностями біт, за яких кожен біт однієї послідовності простим способом порівнюється з відповідним бітом в іншій послідовності. Таким способом, програмісти мають можливість обирати як працювати, застосовуючи правила числової алгебри чи булевої алгебри залежно від потреби. Основною відмінною функцією між родинами операцій є існування операції {{нп|Перенос (арифметика)|переносу|en|Carry (arithmetic)}} в першій алгебрі, і відсутність в останній.

== Історія ==
Засади алгебри логіки сформулював британський математик [[Джордж Буль]] у [[1847]] році. Алгебра Буля передувала сучасному розвитку [[Абстрактна алгебра|абстрактної алгебри]] і математичної логіки; і вважають, що вона пов'язана з появою обох цих галузей.<ref name="DunnHardegree2001">{{cite book|author1=J. Michael Dunn|author2=Gary M. Hardegree|title=Algebraic methods in philosophical logic|url=https://books.google.com/books?id=-AokWhbILUIC&pg=PA2|year=2001|publisher=Oxford University Press US|isbn=978-0-19-853192-0|page=2|accessdate=8 лютого 2019|archive-date=6 липня 2019|archive-url=https://web.archive.org/web/20190706150018/https://books.google.com/books?id=-AokWhbILUIC&pg=PA2}}</ref> В абстрактному тлумаченні, булева алгебра була розвинена в кінці 19-го століття, чому значно приклали зусилля математики [[Вільям Стенлі Джевонс|Вільям Джевонс]], [[Ернст Шредер]], {{нп|Едвард Верміле Гантінгтон|Едвард Гантінгтон|en|Edward Vermilye Huntington}} та інші, доки вона не досягла сучасного поняття (абстрактної) [[Математичні структури|математичної структури]].<ref name="DunnHardegree2001"/> Наприклад, емпіричні спостереження про те, що можливо маніпулювати виразами в [[Алгебра множин|алгебрі множин]], якщо перевести їх у вирази булевої алгебри пояснюються в сучасних термінах, що алгебра множин це [[Булева алгебра (структура)|Булева алгебра]]. Насправді, [[Маршалл Гарві Стоун|М.&nbsp;Г.&nbsp;Стоун]] [[Теорема Стоуна про представлення булевих алгебр|у 1936 довів]], що кожна булева алгебра є [[Ізоморфізм|ізоморфною]] [[Алгебра (теорія множин)|полю множин]].

У 1930-х, під час вивчення {{нп|Теорія перемикання кіл|перемикання електричних кіл|en|Switching circuit theory}}, [[Клод Шеннон]] помітив, що в цій темі також можна використовувати закони булевої алгебри, і запропонував '''комутаційну алгебру''', що дозволяє аналізувати та проєктувати схеми за допомогою алгебричних методів у термінах [[логічний вентиль|логічних елементів]]. Під час розробки схемотехніки сьогодні, немає великої потреби розглядати інші булеві алгебри, тому поняття «комутаційна алгебра» і «булева алгебра» часто використовуються як взаємозамінні.<ref name="BalabanianCarlson2001">{{cite book|author1=Norman Balabanian|author2=Bradley Carlson|title=Digital logic design principles|url=https://archive.org/details/digitallogicdesi0000bala|year=2001|publisher=John Wiley|isbn=978-0-471-29351-4|pages=[https://archive.org/details/digitallogicdesi0000bala/page/39 39]–40}}, [http://www.wiley.com/college/engin/balabanian293512/pdf/ch02.pdf online sample] {{Webarchive|url=https://web.archive.org/web/20200729122747/https://www.wiley.com/college/engin/balabanian293512/pdf/ch02.pdf |date=29 липня 2020 }}</ref><ref name="Radhakrishnan">{{cite book|author=Rajaraman & Radhakrishnan|title=Introduction To Digital Computer Design|url=https://books.google.com/books?id=-8MvcOgsSjcC&pg=PA65|publisher=PHI Learning Pvt. Ltd.|isbn=978-81-203-3409-0|page=65|date=2008-03-01|accessdate=8 лютого 2019|archive-date=27 липня 2020|archive-url=https://web.archive.org/web/20200727124657/https://books.google.com/books?id=-8MvcOgsSjcC&pg=PA65}}</ref><ref name="Camara2010">{{cite book|author=John A. Camara|title=Electrical and Electronics Reference Manual for the Electrical and Computer PE Exam|url=https://books.google.com/books?id=rfHWHeU0jfsC&pg=SA41-PA3|year=2010|publisher=www.ppi2pass.com|isbn=978-1-59126-166-7|page=41|accessdate=8 лютого 2019|archive-date=27 липня 2020|archive-url=https://web.archive.org/web/20200727131456/https://books.google.com/books?id=rfHWHeU0jfsC&pg=SA41-PA3}}</ref> Під час [[Синтез логіки|розробки]] схем [[Комбінаційна логіка|комбінаційної логіки]] фундаментальною задачею є {{нп|Оптимізація логіки|ефективна реалізація|en|Logic optimization}} [[Булева функція|булевих функцій]]. Сучасні засоби [[Програми проєктування електронних систем|автоматизації проєктування електронних систем]] для [[Схеми надвеликого рівня інтеграції|інтегральних схем надвеликого рівня інтеграції]] часто покладаються на ефективне представлення булевих функцій, що називають (скороченими впорядкованими) [[Бінарна діаграма рішень|двійковими діаграмами рішень]] для [[Синтез логіки|синтезу логіки]] та [[Формальна верифікація|формальної верифікації]].<ref name="Chen2007">{{cite book|editor=Wai-Kai Chen|title=The VLSI handbook|url=https://archive.org/details/vlsihandbook002edunse_g6s3|year=2007|publisher=CRC Press|isbn=978-0-8493-4199-1|edition=2nd|author=Shin-ichi Minato, Saburo Muroga|chapter=Binary Decision Diagrams|id=chapter 29}}</ref>

Логічні вирази, які можна представити в класичному [[Числення висловлень|численні висловлювань]] мають {{нп|алгебрична семантика (математична логіка)|еквівалентні вирази|en|algebraic semantics (mathematical logic)}} в булевій алгебрі. Так, термін '''булева логіка''' іноді використовується для зазначення числення висловлювань, що здійснюється в такий спосіб.<ref name="Parkes2002">{{cite book|author=Alan Parkes|title=Introduction to languages, machines and logic: computable languages, abstract machines and formal logic|url=https://books.google.com/books?id=sUQXKy8KPcQC&pg=PA276|year=2002|publisher=Springer|isbn=978-1-85233-464-2|page=276|accessdate=8 лютого 2019|archive-date=27 липня 2020|archive-url=https://web.archive.org/web/20200727130428/https://books.google.com/books?id=sUQXKy8KPcQC&pg=PA276}}</ref><ref name="BarwiseEtchemendy1999">{{cite book|author1=[[Jon Barwise]]|author2=[[John Etchemendy]]|author3=Gerard Allwein|author4=Dave Barker-Plummer|author5=Albert Liu|title=Language, proof, and logic|year=1999|publisher=CSLI Publications|isbn=978-1-889119-08-3|url-access=registration|url=https://archive.org/details/languageprooflog00barw}}</ref><ref name="Goertzel1994">{{cite book|author=Ben Goertzel|title=Chaotic logic: language, thought, and reality from the perspective of complex systems science|url=https://books.google.com/books?id=zVOWoXDunp8C&pg=PA48|year=1994|publisher=Springer|isbn=978-0-306-44690-0|page=48|accessdate=8 лютого 2019|archive-date=27 липня 2020|archive-url=https://web.archive.org/web/20200727131849/https://books.google.com/books?id=zVOWoXDunp8C&pg=PA48}}</ref> Булевої алгебри не достатньо для роботи з логічними формулами, у яких використовують [[квантор]]и, таких як у [[Логіка першого порядку|логіці першого порядку]]. Хоча розвиток математичної логіки не відповідає булевій, зв'язок між його алгеброю і логікою пізніше був закладений в основу [[Алгебраїчна логіка|алгебричної логіки]], що також вивчає алгебричні системи багатьох інших логік.<ref name="DunnHardegree2001"/> [[Задача вибору|Задача про ухвалення рішень]] про те, чи можуть змінні даної булевої формули (висловлювання) приймати такі значення, що формула буде розрахована як істина, називається [[Задача здійсненності булевих формул|задачею здійсненності булевих формул]], і є дуже вадливою для [[Теоретична інформатика|теоретичної інформатики]], що є першою задачею для якої було показано, що вона має складність [[NP-повна задача|NP-повної задачі]]. Тісно пов'язана з цим [[модель обчислення]], що відома як {{нп|булева схема||en|Boolean circuit}} співвідносить [[Часова складність|часову складність]] ([[алгоритм]]у) зі {{нп|складність схем|складністю схем|en|circuit complexity}}.

== Див. також ==
* [[Булева множина]]
* [[Булева функція]]
* [[Таблиці істинності]]
* [[Правила де Моргана]]
* [[Карта Карно]]
* [[Метод Куайна — Мак-Класкі]]
* [[Реляційна алгебра]]
* [[Булеві операції над многокутниками]]

== Примітки ==
{{примітки}}

== Література ==
* {{Винберг.Курс алгебры}}

== Посилання ==
* [http://esu.com.ua/search_articles.php?id=43596  А́ЛГЕБРА ЛО́ГІКИ ] {{Webarchive|url=https://web.archive.org/web/20160421162350/http://esu.com.ua/search_articles.php?id=43596 |date=21 квітня 2016 }} //[[ЕСУ]]
{{Логічні операції}}
{{Класична логіка}}
{{Математична логіка}}

[[Категорія:Алгебра логіки|*]]
[[Категорія:Булева алгебра]]
[[Категорія:Алгебраїчна логіка]]