Алгебра логіки, розділ математичної логіки, що вивчає вислови, що розглядаються з боку їх логічних значень (істинності або помилковості), і логічні операції над ними. А. л. виникла в середині 19 ст в працях Дж. Буля і розвивалася потім в роботах Ч. Пірсу, П. С. Порецкого, Би. Рассела, Д. Гильберта і ін. Створення А. л. було спробою вирішувати традиційні логічні завдання методами алгебри. З появою теорії безлічі (70-і рр. 19 ст), що поглинула частину первинного предмету А. л., і подальшим розвитком математичної логіки (остання чверть 19 ст — 1-я половина 20 ст) предмет А. л. значно змінився. Основним предметом А. л. стали вислови . Під висловом розуміється кожна пропозиція, відносно якої має сенс стверджувати, істинно воно або помилково. Приклади висловів: «кит — тварина», «всі кути — прямі» і тому подібне Перше з цих висловів є, очевидно, достеменним, а друге — помилковим. Що вживаються в звичайній мові логічні в'язки «і», «або», «якщо..., то...», «еквівалентно», частка «не» і так далі дозволяють з вже заданих висловів будувати нові, «складніші» вислови. Так, з висловів «х > 2», «х £ 3» за допомогою в'язки «і» можна отримати вислів «x>2 і х £ 3», за допомогою в'язки «або» — вислів «x>2 або х £ 3», за допомогою в'язки «якщо..., то...» — вислів «якщо x > 2, то х £ 3» і так далі Істинність або помилковість отримуваних таким образом висловів залежить від істинності і помилковості вихідних висловів і відповідного трактування в'язок як операцій над висловами.
В'язки. Формули. У А. л. для позначення істинності вводиться символ і для позначення помилковості — символ Л. Часто замість цих символів уживаються числа 1 і 0. В'язки «і», «або», «якщо..., то...», «еквівалентно» позначаються відповідно знаками & (кон'юнкція), Ú (диз'юнкція), ® (імплікація), ~ (еквівалентність); для заперечення вводиться знак - (риска зверху). Поряд з індивідуальними висловами, приклади яких наводилися вище, в А. л. використовуються також т.з. змінні вислови, тобто такі змінні, значеннями яких можуть бути будь-які наперед задані індивідуальні вислови. Далі індуктивно вводиться поняття формули, що є формалізацією поняття «складного» вислови; через А, В З... позначаються індивідуальні, а через X, Y, Z... — змінні вислови. Кожна з цих букв називаються формулою. Якщо знаком * позначити будь-яку з перерахованих вище в'язок, а Á і Â суть формули, то (Á* Â) і суть формули. Приклад формули:
В'язки і частка «не» розглядаються в А. л. як операції над величинами, що набувають значень 0 і 1, і результатом вживання цих операцій також є числа 0 або 1. Кон'юнкція X&Y рівна 1 тоді і лише тоді, коли і Х і Y дорівнюють 1; диз'юнкція XúY рівна 0 т. і т. т., коли і Х і Y дорівнюють 0; імплікація Х®y дорівнює 0 т. і т. т., коли Х рівне 1, а Y дорівнює 0; еквівалентність Х~У дорівнює 1 т. і т. т., коли значення Х і Y збігаються; заперечення дорівнює 1 т. і т. т., коли Х рівне 0. Введені операції дозволяють кожній формулі при заданих значеннях вхідних в неї висловів приписати одне з двох значень 0 або 1. Тим самим кожна формула може одночасно розглядатися як деякий спосіб завдання або реалізації т.з. функцій А. л., тобто таких функцій, на наборах нулів і як значення 0 або 1. Для завдання функцій А. л. інколи використовуються таблиці, що містять всі набори значень змінних і значення функцій на цих наборах. Так, наприклад, звідна таблиця, задаюча функції `, X&Y, XúY, X®y і X~y має вигляд:
XY
X&Y
X\/y
X®У
Х~y
00
1
0
0
1
1
01
1
0
1
1
0
10
0
0
1
0
0
11
0
1
1
1
1
Аналогічно влаштовані таблиці для довільних функцій А. л. Це — т.з. табличний спосіб завдання функцій А. л. Самі ж таблиці інколи називають істиннісними таблицями.
Для перетворень формул в рівні формули важливу роль в А. л. грає наступна рівність:
Ця рівність, що встановлюється, наприклад, за допомогою істиннісних таблиць, дозволяють вже без допомоги таблиць отримувати ін. рівності. Методом здобуття останніх є т.з. тотожні перетворення, які міняють, взагалі кажучи, вираження, але не функцію, що реалізовується цим виразом. Наприклад, за допомогою законів поглинання виходить закон ідемпотентності ХúХ = X. Згадана рівність у ряді випадків дозволяє істотно спростити запис формул звільненням від «зайвих дужок». Так, співвідношення (1) і (2) дають можливість замість формул (...(Á 1 &Á 2 )&...)& Á s і (...( 1 Ú 2 )Ú...)Ú Â s використовувати компактніший запис Á 1 &Á 2 &...&Á s і  1 Ú 2 Ú... s Перше з цих виразів називається кон'юнкцією співмножників Á 1 ..., Á s , а друге — диз'юнкцією доданків  1 ...,  s . Рівність (5), (6), (7) показує також, що константи 0 і 1, імплікацію і еквівалентність, розглядаючи їх як функції, можна виразити через кон'юнкцію, диз'юнкцію і заперечення. Більш того, всяка функція А. л. може бути реалізована формулою, записуваною за допомогою символів
Нормальні форми. Безліч всіх формул, в побудові яких беруть участь змінні вислови, деякі з символів &, Ú,®, ~, - і констант 0 і 1, називаються мовою над даними символами і константами. Рівність (1) — (7) показують, що для всякої формули в мові над &, Ú,®, ~, - ,0, 1 знайдеться рівна нею формула в мові над &, Ú, - ,0, 1, наприклад
Особливу роль в останній мові грає клас формул, які можуть бути записані у вигляді Á 1 ÚÁ 2 Ú...ÚÁ s , 0 або 1, де s ³ 1, і кожне Á i — або змінний вислів, або його заперечення, або кон'юнкція таких, при цьому кожне Á i не містить однакових співмножників і не містить співмножників вигляду Х і одночасно і все Á i — попарно різні. Тут дужки опускаються, оскільки передбачається, що операція кон'юнкції зв'язує «сильнішим», ніж диз'юнкція, тобто при обчисленні по заданих значеннях змінних слід спочатку обчислити значення Á i .Еті вирази називаються диз'юнктивними нормальними формами (днф). Кожну формулу Á, реалізовуючу функцію, відмінну від константи, в мові над &, Ú, ®, ~, - , 0 1 за допомогою рівності (1) — (7) можна привести до рівної їй днф, що містить всі змінні формули Á і будь-яке число інших змінних, причому кожне Á у цій днф містить одні і ті ж змінні. Така днф називається досконалої днф формули Á. Можливість приведення до досконалої днф лежить в основі алгоритму, що встановлює рівність або нерівність двох наперед заданих формул.
Важливу роль в А. л. і її застосуваннях грає т. н. скорочена днф. Днф називається скороченою, якщо виконані наступні умови: 1) у ній немає таких пар доданків Á i і Á j , що всякий співмножник з Á i є і в Á I ; 2) для всяких два таких доданків Á i і Á i ,із яких один містить співмножником деяке змінне, а інший — заперечення це змінне (за умови, що в даній парі доданків немає іншого змінного, для якого це ж має місце), є (у цій же днф) доданок Á i , рівне кон'юнкції останніх співмножників цих два доданків. Всяка днф за допомогою рівності (1) — (7) може бути приведена до рівної нею скороченою днф. Наприклад, скороченою днф для формули ((X ~ (Y®z)) ® (X&Z)) є
Окрім днф, уживаються також кон'юнктивні нормальні форми (кнф). Так називають вирази, які можна отримати з днф шляхом заміни в них знаків Ú на &, а & на Ú. Наприклад, з днф
виходить кнф
Операція (або функція) f називається подвійною для операції в, якщо таблиця, задаюча f виходить з таблиці, задаючої в, шляхом заміни в ній усюди 0 на 1 і 1 на 0 (включаючи заміну значень функцій). Наприклад, кон'юнкція і диз'юнкція подвійні між собою, заперечення подвійне самому собі, константи 1 і 0 подвійні один одному і так далі Перетворенням формул, при якому знаки всіх операцій у вираженні замінюються на знаки подвійних ним операцій, константа 0 замінюється на 1, а 1 — на 0, називаються перетворенням подвійності. Якщо вірна рівність Á = Â і Á* подвійно Á, а Â* подвійно Â, те вірне Á* = Â*, зване подвійним попередньому. Це т.з. принцип подвійності. Прикладами подвійної рівності є пари законів (1) (2) (3); рівність (5) подвійна рівності (6), кожна кнф подвійна деякій днф. Досконалі кнф і скорочена кнф визначаються як такі кнф, що подвійні ним вирази є відповідно досконалій днф і скороченою днф.
Следствія. Гіпотези. Мінімізація. Досконалі і скорочені днф і кнф використовуються для вирішення завдання огляду всіх гіпотез і всіх следствій заданої формули. Під гіпотезою формули Á розуміється така формула Â, що (®Á) = 1, а під слідством формули Á — така формула Â, що (Á®Â) = 1. Гіпотеза формули Á називається простий, якщо вона є кон'юнкція змінних або їх заперечень і після відкидання будь-якого з її співмножників перестає бути гіпотезою формули Á. Аналогічно, наслідок формули називається простим, якщо воно є диз'юнкція змінних або їх заперечень і після відкидання будь-якого з її доданків перестає бути наслідком формули Á. Рішення задачі огляду гіпотез і следствій засноване на вказівці алгоритму, що будує всі прості гіпотези і следствія для заданої формули і в здобутті з них за допомогою законів (2) — (7) всіх останніх гіпотез і следствій.
Скорочена днф має важливі застосування. Слід зазначити перш за все завдання мінімізації функцій А. л., що є частиною т.з. завдання синтезу систем, що управляють. Мінімізація функцій А. л. полягає в побудові такої днф для заданої функції А. л., яка реалізує цю функцію і має найменше сумарне число співмножників в своїх доданках, тобто має мінімальну «складність». Такі днф називаються мінімальними. Кожна мінімальна днф для заданої відмінної від константи функції А. л. виходить із скороченої днф будь-якої формули, що реалізовує цю функцію, викиданням деяких доданків Á i , з цієї скороченою днф.
Мови. Інтерпретації. В мові над &, Ú, ®, ~, 0, 1 +, де знак + інтерпретується як складання по модулю два, встановлюються наступні співвідношення:
Ця рівність дозволяє переводити формули в мові над &, Ú, ®, ~, - , 0, 1 в рівні їм формули в мові над &,+, 1 і назад. Тотожні перетворення в останній мові здійснюються за допомогою рівності, встановленої для кон'юнкції і додаткової:
(11) Х +Y=Y+ X;
(12) (Х+y) + Z = Х+(Y + Z);
(13) Х&(Y + Z) = X&Y + X&Z;
(14) Х&Х = Х, X + (Y + Y) = X, X&1 = X,
тут як і раніше вважається, що кон'юнкція зв'язує «сильнішим», ніж знак +. Цієї рівності вистачає для того, щоб з них за допомогою тотожних перетворень, так само як і при розгляді мови над &, Ú, ®, ~, - , 0, 1, можна було вивести будь-яку вірну рівність в мові над &, +, 1. Вираження у цій мові називається приведеним поліномом (п.п.), якщо воно або має вигляд Á 1 +Á 2 + ... Á s , де кожне Á i є або 1, або змінне, або кон'юнкція різних змінних без заперечень Á i ¹Á j при i¹ j і s³1, або рівне 1 + 1. Наприклад, вираження X&Y&Z + X&Y+1 є п. п. Всяку формулу А. л. можна привести до п. п.
Окрім розглянутих мов, існують і ін. мови, рівносильні їм (дві мови називаються рівносильними, якщо за допомогою деяких правил перетворення кожна формула однієї з цих мов переводиться в деяку рівну нею формулу в іншій мові і назад). У основу такої мови досить покласти будь-яку систему операцій (і констант), що володіє тією властивістю, що через операції (і константи) цієї системи можна представити всяку функцію А. л. Такі системи називаються функціонально повними. Прикладами повних систем є
і тому подібне Існує алгоритм, який по довільній кінцевій системі функцій А. л. встановлює її повноту або неповноту. Розглядаються і такі мови, в основі яких лежать системи операцій, що немає функціонально повними, і такі мов нескінченно багато. Серед них є нескінченно багато попарно нерівносильних мов (у сенсі відсутності тієї, що переводиться за допомогою тотожних перетворень з однієї мови на іншій). Проте для всякої мови, побудованої на основі тих або інших операцій А. л., існує така кінцева система рівності цієї мови, що всяка рівність цієї мови виводиться за допомогою тотожних перетворень з рівності цієї системи. Така система рівності називається дедуктивно повною системою рівності (п. с. р.) мови.
Розглядаючи той або інший із згаданих вище мов разом з деякою п. с. р. цієї мови, інколи відволікаються від табличного завдання операцій, лежачих в основі цієї мови, і від того, що значеннями його змінних є вислови. Замість цього допускаються різні інтерпретації мови, що складаються з тієї або іншої сукупності об'єктів (службовців значеннями змінних) і системи операцій над об'єктами цієї безлічі що задовольняють рівності з п. с. р. цієї мови. Так, мова над &, Ú, - , 0, 1 в результаті такого кроку перетворюється на мову т.з. булевої алгебри, мова над &, +, 1 перетворюється на мову т.з. булевого кільця (з одиницею), мова над &, Ú у мову дистрибутивної структури і тому подібне
А. л. розвивається головним чином під впливом завдань, що встають в області її застосувань. З них найважливішу роль грають додатки А. л. у теорії електричних схем. Для опису останніх в деяких випадках доводиться відмовлятися від користування лише звичайною двозначною А. л. і розглядати ті або інші її багатозначні узагальнення (див. Багатозначна логіка ) .
Літ.: Гільберт Д. і Аккерман Би., Основи теоретичної логіки, пер.(переведення) з йому.(німецький), М., 1947; Тарський А., Введення в логіку і методологію дедуктивних наук, пер.(переведення) з англ.(англійський), М., 1948; Кліні С. До., Введення в метаматематику, пер.(переведення) з англ.(англійський), М., 1957; Новіков П. С., Елементи математичної логіки, М., 1959.
