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

Аналогічно влаштовані таблиці для довільних функцій А. л. Це - т. Зв. табличний спосіб завдання функцій А. л. Самі ж таблиці іноді називають істиннісними таблицями.

Для перетворень формул в рівні формули важливу роль в А. л. грають такі рівності:

(1) X & Y = Y & X, X Ú Y = Y Ú X (закон коммутативности);

(2) (X & Y) & Z = X & (Y & Z), (X Ú Y) Ú Z = X Ú (Y Ú Z) (закон асоціативності);

(3) X & (X Ú Y) = X, X Ú (Х & У) = X (закон поглинання);

(4) X & (Y Ú Z) = (X & Y) Ú (X & Z) (закон дистрибутивности);

(5) X & = 0 (закон протиріччя);

(6) X Ú = 1 (закон виключеного третього);

(7) Х ® Y == Ú Y, Х ~ Y = (X & Y) Ú ( & ).

Ці рівності, що встановлюються, наприклад, за допомогою істиннісних таблиць, дозволяють вже без допомоги таблиць отримувати ін. Рівності. Методом отримання останніх є т. Н. тотожні перетворення, які змінюють, взагалі кажучи, вираз, але не функцію, реалізовану цим виразом. Наприклад, за допомогою законів поглинання виходить закон ідемпотентності Х Ú Х = 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 називається двоїстою для операції y, якщо таблиця, що задає f виходить з таблиці, яка задає y, шляхом заміни в ній усюди 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 & AMP; Y & AMP; Z + X & AMP; Y + 1 є п. п. Будь-яку формулу А. л. можна привести до п. п.

Крім розглянутих мов, існують і ін. Мови, рівносильні їм (дві мови називаються рівносильними, якщо за допомогою деяких правил перетворення кожна формула одного з цих мов перекладається в деяку рівну їй формулу в іншій мові і назад). В основу такої мови досить покласти будь-яку систему операцій (і констант), що володіє тим властивістю, що через операції (і константи) цієї системи можна уявити будь-яку функцію А. л. Такі системи називаються функціонально повними. Прикладами повних систем є

і т. п. Існує алгоритм , Який по довільній кінцевої системі функцій А. л. встановлює її повноту або неповноту. Розглядаються і такі мови, в основі яких лежать системи операцій, які не є функціонально повними, і таких мов нескінченно багато. Серед них є нескінченно багато попарно нерівносильні мов (в сенсі відсутності переводимости за допомогою тотожних перетворень з однієї мови на іншу). Однак для будь-якого мови, побудованого на основі тих чи інших операцій А. л., Існує така кінцева система рівності цієї мови, що будь-яке рівність цієї мови виводиться за допомогою тотожних перетворень з рівності цієї системи. Така система рівності називається дедуктивно повною системою рівностей (п. С. Р.) Мови.

Розглядаючи той чи інший із згаданих вище мов разом з деякою п. С. р. цієї мови, іноді відволікаються від табличного завдання операцій, що лежать в основі цієї мови, і від того, що значеннями його змінних є висловлювання. Замість цього допускаються різні інтерпретації мови, що складаються з тієї чи іншої сукупності об'єктів (службовців значеннями змінних) і системи операцій над об'єктами цього безлічі, що задовольняють равенствам з п. С. р. цієї мови. Так, мова над &, Ú, -, 0, 1 в результаті такого кроку перетворюється в мову т. Н. булевої алгебри, мова над &, +, 1 перетворюється в мову т. н. булевого кільця (з одиницею), мова над &, Ú в мову дистрибутивної структури і т. п.

А. л. розвивається головним чином під впливом завдань, що постають в області її додатків. З них найважливішу роль відіграють додатки А. л. в теорії електричних схем. Для опису останніх в деяких випадках доводиться відмовлятися від користування лише звичайної двозначної А. л. і розглядати ті чи інші її багатозначні узагальнення (див. багатозначна логіка ).

Літ .: Гільберт Д. і Аккерман Б., Основи теоретичної логіки, пер. з нім., М., 1947; Тарський А., Введення в логіку і методологію дедуктивних наук, пер. з англ., М., 1948; Кліні С. К., Введення в метаматематику, пров. з англ., М., 1957; Новіков П. С., Елементи математичної логіки, М., 1959.

В. Б. Кудрявцев.