позволяют получать другие тождества. Тождеств I - IV достаточно для того, чтобы из них по методу тождественных преобразований можно было вывести всякое (верное, конечно) тождество, левая и правая части которого - выражения алгебры логики, состоящие из переменных А, В, .., констант И, Л и знаков «•», «v», «-i» (не обязательно включая все из них). Добавление же тождеств VII А~~В = -лАчВ, А~В - ABv-тА-пВ дает возможность выводить и любые тождества, содержащие также знаки «—>», «~». Тождества V, VI, VII показывают, что константы И и Л, импликацию и эквиваленцию, рассматривая их как функции, можно выразить через конъюнкцию, дизъюнкцию и отрицание. Имеет место теорема, гласящая, что всякая функция алгебры логики может быть представлена через эти три операции, т.е. записана в виде выражения, содержащего лишь знаки этих операций и буквенные переменные. Именно, любую функцию можно записать как дизъюнкцию ФЦ, 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 в.), теорию релейно-контактных схем. Вопросы, касающиеся понятий самой алгебры логики, приводят к проникновению в алгебру логики неалгебраических методов (таких,