Блог Басараби Марії Михайлівни: Алгебра логіки

четвер, 18 лютого 2016 р.

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

Матеріал з Вікіпедії — вільної енциклопедії.

Алгебра логіки (Булева логіка, двійкова логіка, двійкова алгебра) — розділ математичної логіки, що вивчає систему логічних операцій над висловлюваннями.^[1] Найчастіше передбачається, що висловлювання можуть бути тільки істинними або помилковими, тобто використовується так звана бінарна або двійкова логіка, на відміну від, наприклад, тризначної логіки.

Алгебра логіки як алгебраїчна структура наряду з алгеброю множин є частковими випадками булевої алгебри.

Визначення

Базовими елементами, якими оперує алгебра логіки, є висловлювання.
Висловлювання будуються над множиною {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

), що компактніше, але в цілому менш помітно.

Аксіоми

$\bar {\bar x}=x$ , інволютивність заперечення, закон зняття подвійного заперечення
$x\lor\bar x=1$
$\ x\lor1=1$
$\ x\lor x=x$
$\ x\lor0=x$
$\ x\land\bar x=0$
$\ x\land x=x$
$\ x\land0=0$
$\ 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).
Згодом булеву алгебру було узагальнено від логіки висловлювань шляхом введення характерних для логіки висловлювань аксіом. Це дозволило розглядати, наприклад, логіку кубітів, потрійну логіку (коли є три варіанти істинності висловлювання: «істина», «хибність» і «невизначено») тощо.

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

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