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

Алгебра логіки (Булева логіка, двійкова логіка, двійкова алгебра) — розділ математичної логіки, що вивчає систему логічних операцій над висловлюваннями. Тобто, представлення логіки у вигляді алгебраїчної структури.

Визначення

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

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

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

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

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

Аксіоми

1. $\bar {\bar x}=x$
2. $x\lor\bar x=1$
3. $\ x\lor1=1$
4. $\ x\lor x=x$
5. $\ x\lor0=x$
6. $\ x\land\bar x=0$
7. $\ x\land x=x$
8. $\ x\land0=0$
9. $\ x\land1=x$

Походження

Засади алгебри логіки були сформульовані британцем Джорджем Булем в 1847 році. Пізніше її розвивали Чарлз Пірс, Генрі Шеффер, П. С. Порецький, Бертран Рассел, Давид Гільберт та ін.

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

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

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

Проте з закінченням формування теорії множин (70-і роки 19 ст.), яка включила в себе алгебру множин, і подальшим розвитком математичної логіки, предмет алгебри логіки значно змінився.

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

• таблиці істинності;
• функціональна повнота;
• замкнені класи;
• представлення у вигляді: ДНФ, КНФ, полінома Жегалкіна.

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

Простим і найширше вживаним прикладом такої алгебраїчної системи є множина 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$.

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

Див. також

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