АЛГЕБРА ЛОГИКИ

— важнейший случай логик многозначных, в котором изучаются свойства функций, принимающих в качестве значений, как и их аргументы, элементы из заданного двухэлементного множества, а также семейства и алгебры таких функций, содержащие в качестве операций операции суперпозиции и некоторые их аналоги. Иногда вместо термина «А. л.» употребляют термин «двузначная логика». А. л. начала формироваться в 19 в. в трудах англ. математика Дж. Буля. А. л. создали гл. о. для решения традиционных логических задач алгебраическими методами.

С появлением множеств теории( 70-е гг. 19 в.) и развитием алгебры множеств, вобравшей в себя часть первоначального предмета А. л., а также в связи с дальнейшим развитием логики математической предмет А. л. значительно изменился. Объектом изучения стали ф-ции А. л. и различные операции над ними. В дальнейшем класс ф-ций А. л. был расширен до класса ф-ций, аргументы которых, как и сами ф-ции, принимают в качестве значений элементы фиксированного конечного мн-ва Е; расширился также набор операций над ф-циями. Иногда под А. л. понимают как раз последнюю концепцию. Но для приложений наибольшее значение имеет тот случай, когда мощность указанного мн-ва Е равна двум. Исследования в А. л. тесно связаны с другим подходом к изучению высказываний — т. н. исчислением высказываний. Под высказыванием понимают предложения, относительно которых можно утверщдать, истинны они или ложны. Напр., «Кит - животное», «Все углы — прямые» и т. п. Первое из этих высказываний является истинным, а второе — ложным.

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

Истинность или ложность получаемых т. о. высказываний зависит от истинности или ложности исходных высказываний и соответствующей трактовки связок как операций над высказываниями. Для обозначения истинности вводится символ и (или 1), а для обозначения ложности — символ Связки «и», «или», «если..., то», «эквивалентно» обозначаются соответственно знаками для отрицания вводится знак — (черточка сверху). Наряду с индивидуальными высказываниями стали использовать также переменные высказывания, т. е. такие переменные, значениями которых могут быть любые наперед заданные индивидуальные высказывания. Понятие ф-лы, являющееся формализацией понятия «сложного» высказывания вводится индуктивно. Пусть а, b, с, индивидуальные, а х, у, z, ...- переменные высказывания. Кащдая из этих букв наз. ф-лой. Если знаком обозначить любую из перечисленных выше связок, а а и b суть ф-лы, то (а b) и а также суть ф-лы. Пример ф-лы: . Связки и частицу «не» стали рассматривать как операции над величинами, принимающими значения «0» и «1», и результатом применения этих операций также являются числа «0» или «1» (см. Логические операции).

Введенные операции позволяют каждой ф-ле при заданных значениях входящих в нее высказываний приписать одно из двух значений — «0» или «1». Тем самым каждая ф-ла может одновременно рассматриваться как некоторый способ задания реализации ф-ций А. л., т. е. таких ф-ций, которые определены на наборах из нулей и единиц и которые принимают значения тоже «0» или «1». При этом формулы а и эквивалентными если они реализуют равные ф-ции. Для задания ф-ций А. л. иногда используют табл., содержащие все наборы значений переменных и значения ф-ций на этих наборах. Это т. н. табличный способ задания ф-ций. Сами же таблицы наз. истинностными таблица Так, напр., сводная таблица задающая ф-ции , имеет вид:

Аналогично строятся таблицы для произвольных ф-ций А. л.

Для преобразования ф-л в равные ф-лы важную роль играют следующие равенства:

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

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

КНФ определяются как такие КНФ, что двойственные им выражения являются соответственно совершенной ДНФ и сокращенной ДНФ.

Совершенные и сокращенные ДНФ и КНФ удобно использовать для решения задачи нахождения всех гипотез и следствий заданной ф-лы. Под гипотезой ф-лы а понимается такая что ; а под следствием ф-лы а — такая ф-ла, что . Гипотеза ф-лы а наз. простой, если она есть конъюнкция переменных или их отрицаний и после отбрасывания любого из ее сомножителей перестает быть гипотезой ф-лы а. Аналогично этому следствие ф-лы а наз. простым, если оно есть дизъюнкция переменных или их отрицаний и после отбрасывания любого из ее слагаемых перестает быть следствием ф-лы. Решение задачи нахождения гипотез и следствий состоит в указании алгоритма, строящего все простые гипотезы и следствия для заданной ф-лы, и в получении из них при помощи законов (2) — (7) всех остальных гипотез и следствий. Алгоритм опирается на следующие факты. Если , то а и b имеют одни и те же гипотезы и следствия соответственно. Слагаемое ДНФ является гипотезой этой ДНФ; сомножитель КНФ является следствием этой КНФ. Если а — гипотеза выражения b, то а & с — тоже гипотеза для b; если а — следствие выражения b, то а V с — также является следствием из b. Если а и с — гипотезы выражения b, то а V с также гипотеза для b; если а и с — следствия из а, то а & с также следствие из а. У совершенной ДНФ нет других гипотез (не содержащих букв, не входящих в эту ДНФ), кроме дизъюнкций некоторых ее слагаемых или ДНФ, равных им. У совершенной КНФ нет других следствий, кроме конъюнкций некоторых ее сомножителей или равных им выражений. Сокращенная ДНФ есть дизъюнкция всех ее простых гипотез; сокращенная КНФ есть конъюнкция всех ее простых следствий. Сокращенная ДНФ имеет важные приложения. Следует отметить прежде всего задачу минимизации ф-ций А. л., являющуюся частью задачи синтеза управляющих систем. Минимизация ф-ций А. л. состоит в построении такой ДНФ для заданной ф-ции, которая реализует ее и имеет наименьшее суммарное число сомножителей в своих слагаемых, т. е. имеет миним. сложность. Такие ДНФ наз. минимальными. Каждую минимальную ДНФ для заданной, отличной от константы, ф-ции А. л. можно получить из сокращенной ДНФ этой ф-ции путем выбрасывания некоторых слагаемых. Для отдельных ф-ций сокращенная ДНФ может совпадать с минимальной ДНФ. Это имеет место, напр., для монотонных ф-ций, т. е. таких ф-ций, которые реализуются ф-лами над и 1. В языке над , где знак + интерпретируется как сложение по модулю 2, устанавливаются следующие соотношения:

Эти ф-лы позволяют переводить ф-лы в языке над в эквивалентные им ф-лы в языке над и наоборот. Тождественные преобразования в таком языке осуществляются при помощи равенств, установленных для конъюнкции и таких дополнительных равенств:

(здесь тоже считается, что конъюнкция связывает сильнее, чем знак +). Этих равенств достаточно для того, чтобы из них при помощи тождественных преобразований, как и при рассмотрении языка над можно было вывести любое верное равенство в языке над Выражение в этом языке наз. приведенным полиномом, если оно либо имеет вид где есть «1» или переменная, или конъюнкция различных переменных без отрицаний при либо равно Напр., выражение является приведенным полиномом. Всякую формулу А. л. при помощи тождественных преобразований можно привести к приведенному полиному. Равенство имеет место тогда и только тогда, когда приведенный полином для а совпадает с приведенным полиномом для b.

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

Алгоритм основан на следующем факте. Система ф-ций А. является полной тогда и только тогда, когда она содержит ф-ции такие, что а также ф-ции где двойственная к не монотонная, а для приведенный полином содержит слагаемое а, в котором больше одного сомножителя (все эти ф-ции не обязательно должны быть разные). Рассматриваются и языки, в основе которых лежат системы операций, не являющиеся функционально

полными. Таких языков бесконечно много. Среди них имеется бесконечное мн-во попарно не сравнимых языков (т. е. при помощи тождественных преобразований нельзя переводить с одного языка на другой). Однако для всякого языка, построенного на основе тех или иных операций А. существует такая конечная система равенств этого языка, что всякое равенство этого языка выводимо при помощи тождественных преобразований из равенств этой системы. Такая система наз. дедуктивно полной системой равенств данного языка. Напр., равенства (1) — (6) составляют полную систему равенств языка над

Рассматривая тот или иной из упомянутых выше языков вместе с некоторой полной системой равенств этого языка, иногда отвлекаются от табличного задания операций, лежащих в основе этого языка, и от того, что значениями его переменных являются высказывания. Вместо этого возможны различные интерпретации языка, состоящие из той или иной совокупности объектов (служащих значениями переменных) и системы операций над объектами этого мн-ва, удовлетворяющих равенствам из полной системы равенств этого языка. Так, язык над в результате этого превращается в язык булевой алгебры, язык над язык булевого кольца (с единицей), язык над в язык дистрибутивной структуры и т. п. А. л. развивается гл. о. под влиянием задач, возникающих в области ее приложений. Из них самую важную роль играют приложения А. л. в теории электр. схем. Для описания последних в некоторых случаях приходится пользоваться не только обычной двузначной А. л., а рассматривать и те или другие ее многозначные обобщения.

Лит.: Порецкий П.С. О способах решения логических равенств и об обратном способе математической логики. «Протоколы секции физико-математических наук Общества естествоиспытателей при Казанском университете», 1884, т. 2, в. 4; Новиков П. С. Элементы математической логики. М., 1959; Гильберт Д., Аккерман В. Основы теоретической логики. Пер. с нем. М., 1947 [библиогр. с. 297—298]; Яблонский С. В., Таврило в Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. М., 1966 [библиогр. с. 113—115]. В. Б. Кудрявцев.