эквиваленцию, рассматривая их как функции, можно выразить
через конъюнкцию, дизъюнкцию и отрицание. Имеет место
теорема, гласящая, что всякая функция алгебры логики может быть
представлена через эти три операции, т.е. записана в виде выражения,
содержащего лишь знаки этих операций и буквенные переменные.
Именно, любую функцию можно записать как дизъюнкцию ФЦ,
Av …, Ап) всех выражений вида
Ф(др av …, апУ(Ага}) Ц~а2)…(Лп~яп),
где flj, а2,…, ап — набор из значений И, Л. Заменяя в этой
дизъюнкции выражения Л,~И на Av а А~Л — на -vi, а также стирая
«коэффициенты» Ф(аг а2,…, дп), равные И (по закону WA-A) и
отбрасывая члены с «коэффициентами», равными Л (по законам (Л-Л=Л,
JlvA = A), мы и получим (если функция не есть константа) то
выражение, о котором говорится в теореме.
Дизъюнктивной нормальной формой (днф) называется выражение,
которое есть буква И или Л или имеет вид А^Ар …, vAn, где каждый
член А] является либо буквенной переменной, либо ее отрицанием,
либо конъюнкцией таковых, причем s не обязательно отлично от 1,
т.е. знаков «v» может и не быть. Днф называется совершенной, если
она есть И или Л или в каждом члене содержит ровно по одному
разу все имеющиеся в ней буквы (переменные) и не имеет
одинаковых членов. Всякое выражение алгебры логики можно привести
к днф. А всякую днф можно привести к совершенной днф, «домно-
жая» члены на недостающие буквы (по закону A=ABvA^B) и
ликвидируя повторения букв в членах (по закону АА-А, А-лА- Л, Л-Л=Л,
JlvA=A) и повторения членов (по закону AvA=A).
Приведение к совершенной днф позволяет по любым двум данным
выражениям А и В решить вопрос о том, одну ли и ту же функцию
они выражают, т.е. верно ли тождество А=В.
Важную роль играет т. н. сокращенная днф. Последнюю можно
определить как такую днф, в к-рой 1) нет повторений букв ни
в одном члене, 2) нет таких пар членов А. и А? что всякий
множитель из А. имеется и в А. и 3) для всех двух таких членов, из
к-рых один содержит множителем некоторую букву, а другой —
отрицание той же буквы (при условии, что другой буквы, для
которой это имеет место, в данной паре членов нет), имеется
(в этой же днф) член, равный конъюнкции остальных множителей
этих двух членов.
Кроме днф, употребляются также конъюнктивные нормальные
формы (кнф). Это такие выражения, к-рые можно получить из днф
путем замены в них знаков «v» на «•», а «¦» на «v».
Преобразованием двойственности называется такое преобразование
выражения алгебры логики, при котором в этом выражении знаки
всех операций заменяются на знаки двойственных им операций, а
константы: И на Л, Л на И; причем операция (или функция) Ф
называется двойственной для операции ?, если таблица, задающая Ф,
получается из таблицы, задающей ?, путем замены в ней всюду И
на Л, а Л на И (имеется в виду одновременная замена и значений
функции, и значений ее аргументов). Если Ф двойственная У, а ?
двойственная X, то Ф=Х. Напр., конъюнкция и дизъюнкция
двойственны между собой, отрицание двойственно самому себе,
константа И (как функция) двойственна константе Л. Функция ФЦ, Av …,
Ап) двойственна функции Ч!(А]УА71…, Ап), если, и только если, верно
-,Ф(4, А7, …,4,) = УЫ,, -42,…, -Ч).
Совершенную кнф и сокращенную кнф можно определить как
такие кнф, что двойственные им выражения есть соответственно
совершенная днф и сокращенная днф. Совершенные и сокращенные
днф и кнф можно использовать для решения задачи обзора всех
гипотез и вех следствий данного выражения алгебры логики. Причем
под гипотезой выражения А алгебры логики естественно понимать
такое выражение Д что В—А тождественно истинно, а под
следствием выражения А — такое выражение Д что А~В тождественно
истинно.
Еще один, часто употребляемый в алгебре логики шаг абстракции,
состоит в отождествлении И с числом 1, а Л — с числом 0. Вводится
операция А+ Д задаваемая таблицей: 0+0=0,0+1=1,1+0=1,1+1=0.
Она называется сложением (точнее сложением по модулю 2; другое
название: разделительная дизъюнкция; читается: «А плюс В», или «А
не эквивалентно В», или «Либо А, либо В»),
Всякую функцию алгебры логики можно представить через
умножение (т. е. конъюнкцию), сложение и константу 1 (теорема Жегал-
кина). В частности, верны следующие тождества:
VIII. AvB=AB+A+B,-v4=A+l
IX. А-В=АВ+А+\, А~В=А+В+\.
Обратные представления имеют вид
X. A+B=A-nBv^AB, l=Av^A.
Тождества VIII позволяют «переводить» выражения «языка»
конъюнкции, дизъюнкции и отрицания (КДО) на «язык» умножения,
сложения и единицы (УСЕ), а тождества X — осуществлять
Тождественные преобразования можно производить и на «языке»
УСЕ. В основе их лежат следующие законы:
XI. АВ=ВА, А+В+В+А (законы коммутативности);
XII. (АВ)С=А(ВС), (А+В)+С=А+(В+С) (ассоциативности);
XIII. А(В+С)=АВ+АС (закондистрибутивности);
XIV АА=А, А+(В+В)=А
XV. А1=А.
Этих тождеств достаточно для того, чтобы из них можно было
вывести любое (верное) тождество, обе части которого суть выражения
«языка» УСЕ. А добавив к ним тождества VIII, мы сможем выводить
и все тождества «языка» КДО.
Выражение «языка» УСЕ называется приведенным полиномом (п.
п.), если оно есть 1+1 (т. е. нуль) или имеет вид A^+A7+…+As, где
каждый член Ах есть либо 1, либо буквенная переменная, либо
произведение последних, причем ни в одном члене нет никаких
повторений букв, никакие два члена не одинаковы (в том же смысле,
что и выше), a s не обязательно больше 1 (т. е. знаков «+» может не
быть). Всякое выражение алгебры логики можно привести к п. п.
(теорема Жегалкина).
Кроме «языков» КДО и УСЕ существуют и другие «языки»,
обладающие тем свойством, что через операции (и константы) этих
«языков» можно представить всякую функцию алгебры логики. Такие
системы называются (функционально) полными. Примеры полных
систем: а) конъюнкция и отрицание, б) дизъюнкция и отрицание,
в) импликация и отрицание, г) импликация и 0, д) умножение, эк-
виваленция и 0, е) штрих Шеффера Л|Д ж) медиана (Л, Д С),
[определение: (А, Д Q=ABvACvBC\y отрицание и 1, и) медиана,
эквивалента и сложение.
Иногда совершают еще один важный дальнейший шаг абстракции.
Отвлекаются от табличного задания операций и оттого, что
значениями буквенных переменных являются высказывания. Вместо этого
допускаются различные интерпретации рассматриваемого «языка»,
состоящие из той или иной совокупности объектов (служащих значе-
74
АЛГЕБРА ЛОГИКИ
ниями буквенных переменных) и системы операций над объектами
этого множества, удовлетворяющих тождествам из полной системы
тождеств этого «языка». «Язык» КДО в результате такого шага
абстракции превращается в «язык» т. н. булевой алгебры, «язык» УСЕ —
в «язык» т. н. дистрибутивной структуры.
Важным примером булевой алгебры является алгебра классов,
в которой роль элементов играют подмножества (классы)
некоторого фиксированного множества (т. н. универсума) ?/, роль О
играет пустое множество 0, роль 1 — само U, роль AB, AvB
и -Л ~ теоретико-множеств. операции пересечения, объединения
и дополнения соответственно. Связь между алгеброй классов,
алгеброй предикатов и алгеброй высказываний, этими тремя
важнейшими интерпретациями абстрактной алгебры логики как «языка»
булевой алгебры, состоит в следующем: первая переходит во вторую
путем замены множеств (классов) их т. н. характеристическими
предикатами (т. е. множества А — предикатом хеА, гласящим: «х
принадлежит множеству А»), если при этом соответствующим
образом преобразуются также операции и константы 0 и 1, а вторая
переходит в третью при подстановке во все предикаты на место их
аргументов некоторого фиксированного их значения. Вернее, при
таком переходе от алгебры классов к алгебре предикатов получается
алгебра одноместных предикатов. Другим важным случаем является
алгебра двуместных предикатов, называемых чаще отношениями. С
ней тесно связана алгебра отношений, отличающаяся от нее только
тем, что в последней, кроме трех операций булевой алгебры,
имеются еще две.
Всякую булеву алгебру можно «переделать» в булево кольцо,
определив операцию А+Всогласно закону X (и отбросив операцию AvB).
Напр., в случае алгебры множеств роль А+В играет т. н.
симметрическая разность множеств А и В (состоящая из всех тех элементов
универсума, которые принадлежат одному и только одному из
множеств А или В). Обратно, всякое булево кольцо (с единицей) можно
«переделать» в булеву алгебру. Понятия булевой алгебры и булева
кольца связываются с именем Дж. Буля. Однако оформились эти
понятия (не говоря уже о терминах) значительно позже.
Первые работы по алгебре логики были посвящены задачам: а)
выражения логических соотношений между объемами понятий
(соответственно высказываниями) в виде уравнений (равенств), б)
построения алгоритмов решения логических уравнений и систем
уравнений с целью автоматизировать способы извлечения из
данных посылок содержащейся в них (неявно) информации (того или
иного рода).
В настоящее время алгебра логики развивается гл. о. под влиянием
задач, встающих в области ее приложений. Она находит широкое
применение в технике (особенно при решении задач, связанных с
построением автоматов) и, наоборот, развивается сама под
влиянием запросов техники (задач автоматизации программирования,
уменьшения числа элементов в устройствах релейного действия
и др.). Важную роль играют приложения в теории электрических
схем, включая первоначально, начиная с работ В. И. Шестакова и
К. Шеннона (30~40-е гг. 20 в.), теорию релейно-контактных схем.
Вопросы, касающиеся понятий самой алгебры логики, приводят к
проникновению в алгебру логики неалгебраических методов (таких,
как табличные, топологические, дескриптивные) и вследствие
этого к постепенному вьшелению из алгебры логики самостоятельной
области — теории функций алгебры логики (или иначе, теории
булевых функций).
В случае более сложных схем, чем контактные, приходится часто
отказываться от использования лишь обычной алгебры логики и
рассматривать те или иные ее многозначные обобщения, отличные от
булевых алгебр и булевых колец (см. Многозначные логики). Другим
направлением современного развития алгебры логики является
алгебраическая логика. Она интересна тем, что выдвигает и частично
решает задачу построения алгебр неклассических логик, т.е. таких
вариантов алгебры логики, которые соответствуют неклассическим
исчислениям высказываний.
Некоторые тенденции возможного дальнейшего развития алгебры
логики как совокупности алгебраических методов логики
намечаются в связи с бурным развитием ряда областей как современной
алгебры, так и математической логики. Одна из них связана с
мощным ростом теоретико-множественной алгебры, позволяя всякую
операцию рассматривать как алгебраическую операцию. Такое
рассмотрение дает возможность охватить алгебраическими методами
значительную часть современной математической логики (см.
Логика символическая).
Другая — связана с успехами теории алгоритмов, позволившей
уточнить ряд алгоритмических проблем алгебры, и последовавшим
решением некоторых из них. Тенденция эта состоит в объединении
алгоритмической алгебры с самой теорией алгоритмов м попытках
алгебраизации последней, т.е. построения алгебраической теории
алгоритмов.
Эта постепенная алгебраизация все большего числа сторон
математической логики будет, по-видимому, содействовать наилучшему
вьшелению и ее чисто логических сторон, для того чтобы изучать
последние уже иными методами.
А В. Кузнецов
Сокращенный вариант статьи: Алгебра логики. —
В кн.: Философская энциклопедия. Т. 1. М., 1960.
Как и предвидел А. Кузнецов, все большее прикладное
значение приобретает теория булевых функций как
самостоятельная область, выделившаяся из алгебры логики. В
результате пришли к понятию функциональной системы
(Рп, Q, где Рп есть множество всех функций л-значной
логики (или множество всех функций счетнозначной логики
PJ с заданной на нем операцией суперпозиции С. Рп
обычно рассматривается как обобщение множества всех булевых
функций Рт Известна содержательная трактовка понятия
функциональной системы ((Рп, Q выступает ее частным
случаем), в основе которой лежит рассмотрение таких пар (Р,
П), в которых Р есть множество отображений, реализуемых
управляющими системами из некоторого класса, a ? состоит
из операции, используемой при построении новых
управляющих систем из заданных. В свою очередь (Pv С) есть
эквивалент алгебры логики. Таким образом, от алгебры формул,
изучаемой в алгебре логики, перешли к алгебре функций. И
хотя именно алгебра логики, т.е. классическая логика
высказываний, лежит в основе проектирования микросхем для
современной цифровой электронной техники, в том числе и для
компьютеров, подобные работы ведутся и на основе
многозначных логик. В частности, для функционально полных
(и некоторых других) многозначных систем был построен
аналог совершенной днф.
Еще более важное предвидение А. Кузнецова связано
с выделением алгебраической логики в одно из
направлений современной алгебры логики. В первую очередь
имеется в виду построение алгебр, соответствующих
неклассическим логикам в том
