Алгебра логіки
А́лгебра ло́гіки — розділ математичної логіки, що вивчає властивості логічних операцій із висловлюваннями.
Висловлювання — це певні твердження, тобто розповідні речення, за змістом яких доречно ставити питання про їхню істинність чи хибність. Істинним висловлюванням присвоюють логічне значення 1 або t (англ. true), а хибним — логічне значення 0 або f (англ. false). При цьому жодне висловлювання не може бути одночасно й хибним, й істинним. Алгебра логіки вивчає лише ті операції, які можуть бути сформульовані в термінах істинності та хибності висловлювань і не апелюють до їхнього змісту.
Основи алгебри логіки заклав у серед. 19 ст. Дж. Буль. Пізніше її розвивали Ч. Пірс, Г. Шеффер, П. Порецький, Б. Рассел, Д. Гільберт, І. Жегалкін, Я. Лукасевич, Е. Пост, К. Шеннон та ін.
Основні логічні операції (їх ще називають логічними зв’язками або логічними функторами) утворилися як формалізації тих конструкцій живої мови, які використовуються для побудови складних речень із простих. До таких операцій належать заперечення [math]¬a[/math] (або [math]ā[/math]) висловлювання a, а також кон'юнкція [math]a ∨ b[/math], диз'юнкція [math]a ∧ b[/math], імплікація [math]a → b[/math] та еквівалентність [math]a ↔ b[/math] висловлювань [math]a і b[/math].
Використовуються також ін. позначення: для заперечення – N, ¯, ~, C; для кон’юнкції – C, &; для диз’юнкції – D, +; для імплікації – ⊃, ⇒; для еквівалентності – ~, ≡, ⇔. Ці операції задаються такою таблицею істинності:
Для операцій алгебри логіки виконуються такі закони:
- закон подвійного заперечення [math]¬ ¬A = A[/math];
- комутативні закони [math]A ∨ B = B ∨ A[/math], [math]A ∧ B = B ∧ A[/math], [math]A ↔ B = B ↔ A[/math];
- асоціативні закони [math](A ∨ B) ∨ C = A ∨ (B ∨ C)[/math], [math](A ∧ B) ∧ C = A ∧ (B ∧ C)[/math], [math](A ↔ B) ↔ C = A ↔ (B ↔ C)[/math];
- дистрибутивні закони [math]A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)[/math], [math]A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)[/math];
- закони ідемпотентності [math]A ∨ A = A[/math], [math]A ∧ A = A[/math];
- закони де Моргана [math]¬(A ∨ B) = ¬A ∧ ¬B[/math], [math]¬(A ∧ B) = ¬A ∨ ¬B[/math];
- закони поглинання константами [math]A ∨ 1 = 1[/math], [math]A ∧ 1 = A[/math], [math]A ∨ 0 = A[/math], [math]A ∧ 0 = 0[/math];
- закон виключення третьої можливості [math]A ∧ ¬A = 1[/math];
- закон суперечності [math]A ∨ ¬A = 0[/math].
Є також окрема група законів виключення логічних зв’язок:
Використовуючи ці закони, формули алгебри логіки можна зводити до різних канонічних форм: диз’юнктивної нормальної форми, кон’юнктивної нормальної форми, зображення у вигляді многочлена Жегалкіна.
У 19 — на поч. 20 ст. апарат алгебри логіки використовувався для формалізації та розв’язання різних задач логіки висловлювань. Від 1930-х апарат алгебри логіки застосовується для опису, аналізу і синтезу релейно-контактних схем у системах управління та для конструювання електронно-обчислювальної техніки. Розробляються також алгебри логіки для операцій із висловлюваннями, що набувають більше 2 значень істинності (першу систему тризначної логіки із значеннями «істинне», «хибне» й «невизначене» запропонував 1920 Я. Лукасевич). П. Порецький розробив алгоритм, який дає змогу ефективно отримувати з даних засновків усі наслідки певного вигляду. Алгоритм базується на законах Блейка–Порецького [math]a ∨ (¬a ∧ b) = a ∨ b[/math] та [math]a ∧ (¬a ∨ b) = a ∧ b[/math].
Г. Шеффер (нар. в Україні) 1913 відкрив логічну операцію (названа на його честь штрихом Шеффера), через яку можна виразити довільну операцію алгебри логіки.
Література
- Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. Москва, 1966.
- Гиндикин С. Г. Алгебра логики в задачах. Москва, 1972.
- Дрозд Ю. А. Основи математичної логіки. Київ, 2003.
- Матвієнко М. П., Шаповалов С. П. Математична логіка та теорія алгоритмів. Київ, 2015.
Автори ВУЕ
Покликання на цю статтю: О. Г. Ганюшкін Алгебра логіки // Велика українська енциклопедія. URL: https://vue.gov.ua/Алгебра логіки (дата звернення: 7.05.2024).
