Математическая энциклопедия - алгебра логики

раздел математической логики, изучающий высказывания, рассматриваемые со стороны их логич. значений (истинности пли'ложности), и логич. операций над ними.

А. л. возникла в сер. 19 в. в трудах Дж. Буля (см. [1], [2]) и развилась затем в работах Ч. Пирса (С. S. Реirs), П. С. Порецкого, Б. Рассела (В. Russel), Д. Гильберта (D. Hilbert) и др. Создание А. л. представляло собой попытку решать традиционные логич. задачи алгебраич. методами. С появлением теории множеств (70-е гг. 19 в.) основным предметом А. л. стали высказывания и логич. операции над ними. Под высказываниями понимаются предложения, относительно к-рых имеет смысл утверждать, истинны они или ложны; напр., высказывание "кит животное" истинно, в то время как высказывание "все углы прямые" ложно. Употребляемые в обычной речи логич. связки "и", "или", "если..., то", "эквивалентно", частица "не" и т. д. позволяют из уже заданных высказываний строить новые, более "сложные" высказывания. Так, из высказываний при помощи связки "и" можно получить высказывание при помощи связки "или" высказывание и т. д.

Истинность или ложность получаемых таким образом высказываний зависит от истинности или ложности исходных высказываний и соответствующей трактовки связок как операций над высказываниями. Для обозначения истинности вводится символ "И" и для обозначения ложности -символ "Л". Затем вместо этих символов стали употреблять числа 1 и 0. Связки "и", "или", "если..., то", "эквивалентно" обозначаются соответственно знаками (конъюнкция), (дизъюнкция), (импликация), (эквивалентность); для отрицания вводится знак (черточка сверху). Наряду с индивидуальными высказываниями, примеры к-рых приводились выше, стали использоваться также переменные высказывания, т. е. такие переменные, значениями к-рых могут быть любые наперед заданные индивидуальные высказывания. Далее индуктивно вводится понятие формулы, являющееся формализацией понятия сложного высказывания. Пусть А, В, С,... обозначают индивидуальные, а переменные высказывания. Каждая из этих букв наз. формулой. Если знак * обозначает любую из перечисленных выше связок, а суть формулы, то суть формулы, напр. Связки и частица "не" стали рассматриваться как операции над величинами, принимающими значения 0 и 1, и результатом применения этих операций также являются числа 0 и 1. Конъюнкция равна 1 тогда и только тогда, когда и х, и уравны 1; дизъюнкция равна 0 тогда и только тогда, когда и х, и уравны 0; импликация равна 0 тогда и только тогда, когда хравен 1, а уравен 0; эквивалентность равна 1 тогда и только тогда, когда значения хи усовпадают; отрицание равно 1 тогда и только тогда, когда хравен 0. Введенные операции позволяют каждой формуле при заданных значениях входящих в нее высказываний приписать одно из двух значений 0 или 1. Тем самым каждая формула может одновременно рассматриваться как нек-рый способ задания, или реализации, функций А. л., т. е. таких функций, к-рые определены на наборах из нулей и единиц и к-рые в качестве значений принимают также 0 или 1. При этом формулы наз. равными (обозначение ), если они реализуют равные функции. Объектом изучения А. л. стали функции А. л. и различные операции над ними. В последующем класс функций А. л. был расширен до класса функций, аргументы к-рых и сами функции принимают в качестве значений элементы фиксированного конечного множества Е;расширился также запас операций над функциями. Иногда под А. л. понимается как раз последняя концепция. Для приложений, однако, наибольшее значение имеет все-таки тот случай, когда мощность указанного множества Еравна двум, поэтому он будет рассмотрен особенно подробно. Излагаемые здесь результаты также тесно связаны с другим подходом в изучении высказываний так наз. высказываний исчислением.

Для задания функций А. л. иногда используют таблицы, содержащие все наборы значений переменных и значения функций на этих наборах. Так, напр., сводная таблица, задающая функции имеет вид:

Аналогично устроены таблицы для произвольных функций А. л. Это так наз. табличный способ задания .функций А. л. Сами таблицы иногда наз. истинностными таблицами. Для преобразования формул в равные формулы важную роль играют следующие равенства:

(закон коммутативности),

(закон ассоциативности),

(закон поглощения),

(закон дистрибутивности),

(закон противоречия),

(закон исключенного третьего),

Эти равенства позволяют уже без помощи таблиц получать другие равенства. Методом получения последних являются так наз. тождественные преобразования, к-рые меняют, вообще говоря, выражение, но не функцию, реализуемую этим выражением. Напр., при помощи законов поглощения получается закон идемпотентности Упомянутые равенства в ряде случаев позволяют существенно упростить запись формул освобождением от "лишних скобок". Так, соотношения (1) и (2) дают возможность вместо формул и использовать более компактную запись

Первое из этих соотношений наз. конъюнкцией сомножителей а второе дизъюнкцией слагаемых Равенства (5), (6), (7) показывают также, что константы 0 и 1, импликацию и эквивалентность, рассматривая их как функции, можно выразить через конъюнкцию, дизъюнкцию и отрицание. Более того, всякая функция А. л. может быть реализована формулой, записываемой с помощью символов

Множество всех формул, в построении к-рых участвуют переменные высказывания и нек-рые из символов и констант 0 и 1, наз. языком над данными символами и константами. Равенства (1)(7) показывают, что для всякой формулы в языке над найдется равная ей формула в языке над напр.:

Особую роль в последнем языке играет класс формул, к-рые могут быть записаны в виде 0 или 1, где и каждое либо переменное высказывание, либо его отрицание, либо конъюнкция таковых, при этом каждое не содержит одинаковых сомножителей и не содержит сомножителей вида одновременно и все попарно не равны. Здесь скобки опускаются, т. к. предполагается, что операция конъюнкции связывает "сильнее", чем дизъюнкция, т. е. при вычислении по заданным значениям переменных следует сначала вычислять значения Эти выражения наз. дизъюнктивными нормальными формами (д. н. ф.). Каждую формулу ив языке над реализующую функцию А. л., отличную от 0, при помощи равенств (1) (7), можно привести к равной ей д. н. ф., содержащей все переменные формулы и и любое число других переменных, причем каждое в этой д. н. ф. содержит одни и те же переменные. Такая д. н. ф. наз. севершенной д. н. ф. формулы и;для. 0 совершенной д. н. ф. является сама формула 0. Возможность приведения к совершенной д. н. ф. лежит в основе алгоритма, устанавливающего равенство или неравенство двух наперед заданных формул. Алгоритм этот состоит в следующем: приводят исследуемые формулы и 1 и и 2 к совершенным д. н. ф., содержащим все те переменные, к-рые есть как в так и в и смотрят, совпадают полученные выражения или нет; если совпадают, то если нет, то Важную роль в А. л. и ее приложениях играет сокращенная д. н. ф., т. е. такая, для к-рой выполнены следующие условия: 1) в ней нет таких пар слагаемых что всякий сомножитель из имеется и в ; 2.) для всяких двух слагаемых из к-рых одно содержит сомножителем нек-рое переменное, а другое отрицание этого переменного (при условии, что другого переменного, для к-рого это же имеет место, в данной паре слагаемых нет), имеется (в этой же д. н. ф.) слагаемое равное конъюнкции остальных сомножителей этих двух слагаемых. Всякая д. н. ф. при помощи равенств (1) (7) может быть приведена к равной ей сокращенной д. н. ф. Напр., сокращенной д. н. ф. для формулы является Формулы равны тогда и только тогда, когда их сокращенные д. н. ф. совпадают. Кроме д. н. ф., употребляются также конъюнктивные нормальные формы (к. н. ф.), т. е. выражения, к-рые можно получить из д. н. ф. путем замены в них знаков а на 1. Напр., из д. н. ф. получается к. н. ф. Операция (или функция) f наз. двойственной для операции если таблица, задающая f, получается из таблицы, задающей путем замены в ней всюду 0 на 1 и 1 на 0 (включая замену значений функций). Напр., конъюнкция и дизъюнкция двойственны между собой, отрицание двойственно самому себе, константы 1 и 0 двойственны друг другу и т. д. Преобразование формул, при к-ром знаки всех операций в выражении заменяются на знаки двойственных им операций, константа 0 заменяется на 1, а 1 на 0, наз. преобразованием двойственности. Если верно равенство двойственно двойственно то верно равенство наз. двойственным предыдущему; это так. наз. принцип двойственности. Примерами двойственных равенств являются пары законов (1), (2), (3); равенство (5) двойственно равенству (6), каждая к. н. ф. двойственна нек-рой д. н. ф. Совершенная к. н. ф. и сокращенная к. в. ф. определяются как такие к. н. ф., что двойственные им выражения являются соответственно совершенной д. н. ф. и сокращенной д. н. ф. Совершенные и сокращенные д. н. ф. и к. н. ф. используются для решения задачи обзора всех гипотез и всех следствий заданной формулы. Под гипотезой формулы понимается такая формула а под следствием формулы такая формула