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

АЛГЕБРА ЛОГИКИ, раздел математической логики, изучающий высказывания с точки зрения их логических значений (истинности или ложности) и логические операции над высказываниями.

Алгебра логики возникла в середине 19 века в трудах Дж. Буля. Создание алгебры логики преследовало цель решать традиционные логические задачи алгебраическими методами. В алгебре логики под высказываниями понимаются предложения, относительно которых имеет смысл утверждать, истинны они или ложны. Употребляемые в обычной речи логические связки, такие, как «и», «или», «если..., то...», «эквивалентно», частица «не», позволяют из уже заданных высказываний строить новые, более сложные высказывания. Истинность или ложность получаемых таким образом высказываний зависит от истинности или ложности исходных высказываний и соответствующей трактовки связок как операций над высказываниями. Для обозначения истинности использовался символ «И», а для ложности - символ «Л». Затем вместо этих символов стали употреблять числа 1 и 0. Связки «и», «или», «если..., то...», «эквивалентно» обозначаются соответственно знаками & (конъюнкция), v (дизъюнкция), → (импликация), ~ (эквивалентность); отрицание (частица «не») обозначается знаком или чертой сверху. Наряду с индивидуальными высказываниями стали использоваться также переменные высказывания, значениями которых могут быть любые наперёд заданные индивидуальные высказывания. Понятие формулы, являющееся формализацией понятия сложного высказывания, вводится индуктивно. Пусть А, В, С,... - индивидуальные, а х, у, z,... - переменные высказывания. Каждая из этих букв называется формулой. Если знак * обозначает любую из перечисленных выше связок, а _U и V суть формулы, то (U*V) и U суть формулы, например ((х&у)→z). Связки (в том числе и отрицание) рассматриваются как операции над величинами, принимающими значения 0 и 1, результатом применения этих операций также являются числа 0 и 1. Конъюнкция х & у равна 1 точно тогда, когда и х, и у равны 1; дизъюнкция xvy равна 0 точно тогда, когда и х, и у равны 0; импликация х → у равна 0 точно тогда, когда х равен 1, а у равен 0; эквивалентность х ~ у равна 1 точно тогда, когда значения х и у совпадают; отрицание х равно 1 точно тогда, когда х равен 0. Введённые операции позволяют каждой формуле при заданных значениях входящих в неё высказываний приписать одно из двух значений 0 или 1. Тем самым каждая формула может одновременно рассматриваться как некоторый способ задания (реализации) функций алгебры логики, то есть таких функций, которые определены на наборах из нулей и единиц и значениями которых являются также 0 или 1. При этом формулы U и V называются равными, если они реализуют равные функции, в этом случае пишут U=V. Вначале объектом изучения алгебры логики были функции алгебры логики и различных операций над ними. В последующем класс функций алгебры логики был расширен до класса функций, аргументы которых и сами функции принимают в качестве значений элементы некоторого фиксированного конечного множества Е; расширился также запас операций над функциями. Иногда под алгебры логикой понимается именно последняя концепция. Для приложений наибольшее значение имеет случай, когда множество Е состоит из двух элементов.

Множество всех формул, в построении которых участвуют переменные высказывания и некоторые из символов &, v, →, ~ и констант 0 и 1, называется языком над данными символами и константами. Для всякой формулы в языке над {&, v, → , ~, } найдётся равная ей формула в языке над {&, v, , 0, 1}. Особую роль в последнем языке играет класс формул, которые могут быть записаны в виде U1vL2v...vUs, 0 или 1, где s≥1 и каждое U_i - либо переменное высказывание, либо его отрицание, либо конъюнкция переменных высказываний и отрицаний переменных высказываний; при этом каждое U_i не содержит одинаковых сомножителей и не содержит сомножителей вида х и х? одновременно и все U_i попарно не равны. В этой записи скобки опускаются, т.к. предполагается, что операция конъюнкции сильнее дизъюнкции, то есть при вычислении по заданным значениям переменных следует сначала вычислять значения U₁, ..., U_s. Эти выражения называются дизъюнктивными нормальными формами. Каждую формулу U в языке над {&, ν, →, ~,¬ , 0, 1}, реализующую функцию алгебры логики, отличную от 0, можно привести к равной ей дизъюнктивной нормальной форме, содержащей все переменные формулы и любое число других переменных, причём каждое  U_i в этой дизъюнктивной нормальной форме содержит одни и те же переменные. Такая дизъюнктивная нормальная форма называется совершенной дизъюнктивной нормальной формой формулы U; для 0 совершенной дизъюнктивной нормальной формой является сама формула 0. Возможность приведения к совершенной дизъюнктивной нормальной форме лежит в основе алгоритма, устанавливающего равенство или неравенство двух заданных формул.

Важную роль в алгебры логики и её приложениях играет сокращённая дизъюнктивная нормальная форма, то есть такая, для которой выполнены следующие условия: в ней нет пар слагаемых  U_i и U_j таких, что всякий сомножитель из  U_i имеется и в U_j; для всяких двух слагаемых  U_i и U_j, из которых одно содержит сомножителем некоторое переменное, а другое - отрицание этого переменного (при условии, что другого переменного, для которого это же имеет место, в данной паре слагаемых нет), имеется (в этой же дизъюнктивной нормальной форме) слагаемое  U_k равное конъюнкции остальных сомножителей этих двух слагаемых. Всякая дизъюнктивная нормальная форма может быть приведена к равной ей сокращённой дизъюнктивной нормальной форме. Кроме дизъюнктивных нормальных форм употребляются также конъюнктивные нормальные формы, т. е. выражения, которые можно получить из дизъюнктивных нормальных форм путём замены в них знаков v на &, а & на v и 0 на 1. Операция (или функция) f* называется двойственной для операции f, если таблица, задающая функцию f*, получается из таблицы для f заменой в ней 0 на 1, а 1 на 0 (включая замену значений функций). Например, конъюнкция и дизъюнкция двойственны между собой, отрицание двойственно самому себе, константы 1 и 0 двойственны друг другу. Преобразование формул, при котором знаки всех операций в выражении заменяются на знаки двойственных им операций, константа 0 заменяется на 1, а 1 на 0, называется преобразованием двойственности. Так называемый принцип двойственности формулируется следующим образом: если U = V и U* двойственно U, а V* двойственно V, то U* = V*.

Совершенные и сокращённые дизъюнктивные нормальные формы и конъюнктивные нормальные формы используются для решения задачи обзора всех гипотез и всех следствий заданной формулы. Под гипотезой формулы U понимается такая формула V, что (V → U) = 1, а под следствием формулы U - такая формула V , что (U→ V ) = 1. Гипотеза формулы U называется простой, если она есть конъюнкция переменных или их отрицаний и после отбрасывания любого из её сомножителей перестаёт быть гипотезой формулы U. Аналогично, следствие формулы U называется простым, если оно есть дизъюнкция переменных или их отрицаний и после отбрасывания любого из её слагаемых перестаёт быть следствием формулы U. Решение задачи обзора гипотез и следствий можно получить, указав алгоритм, строящий все простые гипотезы и следствия для заданной формулы, из которых затем получаются все остальные гипотезы и следствия.

В языке над {&, + , 0, 1}, где + обозначает сложение по модулю 2, выражение называется приведённым полиномом, если оно либо имеет вид U₁ +  U₂ + ... + U_s, где U₁ есть или 0, или 1, или переменное, или конъюнкция различных переменных без отрицаний,  U_i≠U_j при i≠j, i, j = 1, ..., s,s ≥1. Всякую формулу алгебры логики можно представить и единственным образом в виде приведённого полинома, называемого также полиномом Жегалкина (изучался И. И. Жегалкиным в 1927 году).

Кроме рассмотренных языков, существуют и другие языки, равносильные им (два языка называются равносильными, если при помощи некоторых правил преобразования каждая формула одного из этих языков переводится в равную ей формулу в другом языке и обратно). В основу такого языка достаточно положить любую систему операций и констант, обладающую тем свойством, что через операции и константы этой системы можно представить всякую функцию алгебры логики. Такие системы называются функционально полными. Примерами полных систем являются {хх?vх?у), {xvy, хх?), {х + у, 1, х&у) и т.п. Существует алгоритм, который по произвольной конечной системе функций алгебры логики устанавливает её полноту или неполноту. Система функций алгебры логики является полной точно тогда, когда она содержит функции f₁, ..., f₅ такие, что f₁(0, 0, ..., 0) = 1, f₂(1, 1, ..., 1) = 0, f₃ ≠ f₃*, f₄ - не монотонна, а для f₅ приведённый полином содержит слагаемое U, в котором больше одного сомножителя. При этом набор (а₁, ..., a_n) не превосходит набора (b₁ ..., b_n), если всегда    а    функция f(х₁, ..., x_n) монотонна, если её значения а и b на таких наборах всегда связаны так, что а ≤ b. Рассматриваются и такие языки, в основе которых лежат системы операций, не являющиеся функционально полными. Среди них имеется бесконечно много попарно несравнимых языков, т. е. нет переводимости с одного языка на другой при помощи тождественных преобразований. Для всякого языка, построенного на основе тех или иных операций алгебры логики, существует такая конечная система равенств этого языка, что всякое равенство выводимо при помощи тождественных преобразований из равенств этой системы. Такая система называется дедуктивно полной системой равенств данного языка.

Рассматривая тот или иной из упомянутых выше языков вместе с некоторой полной системой равенств этого языка, иногда отвлекаются от табличного задания операций, лежащих в основе языка, и от того, что значениями его переменных являются высказывания. Вместо этого допускаются различные интерпретации языка, состоящие из той или иной совокупности объектов (служащих значениями переменных) и системы операций над объектами этого множества, удовлетворяющих равенствам из полной системы равенств языка. Так, язык над {&, v,¬ , 0, 1} в результате такого шага превращается в язык булевой алгебры; язык над {&, +, 1} превращается в язык булева кольца (с единицей), язык над {&, v, ¬} превращается в язык дистрибутивной решётки.

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

Лит.: Boole G. The mathematical analysis of logic; being an essay towards а calculus of deductive reasoning. Camb., 1847. Oxf., 1998; idem. An investigation of the laws of thought, on which are founded the mathematical theories of logic and probabilities. L., 1854. N. Y., 1958; idem. The laws of thought. Amherst (N. Y.), 2003; Яблонский С.В., Гаврилов Г.П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. М., 1964; Новиков П. С. Элементы математической логики. 2-е изд. М., 1973.