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

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

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

Визначення[ред.ред. код]

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

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

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