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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Алгебра логіки (Булева логіка, двійкова логіка, двійкова алгебра) — розділ математичної логіки, що вивчає систему логічних операцій над висловлюваннями.[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), що компактніше, але в цілому менш помітно.

Аксіоми[ред.ред. код]

  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 році. Пізніше її розвивали Чарлз Пірс, Генрі Шеффер(ru), П. С. Порецький, Бертран Рассел, Давид Гільберт та ін.

Відтоді ця система застосовується для вирішення широкого спектру проблем математичної логіки та теорії множин, та особливо конструювання цифрової електроніки (початок використання алгебри логіки для синтезу перемикальних (релейних) схем був покладений в 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\circy = y\circx, \circ\in{&, \lor, \oplus, \sim, \mid, \downarrow}.
  2. Ідемпотентність: x\circx = x, \circ\in{&, \lor}.
  3. Асоціативність: (x\circy)\circz = x\circ(y\circz), \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):
  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.

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

Див. також[ред.ред. код]

Примітки[ред.ред. код]