73
АЛГЕБРА ЛОГИКИ которые имеют место для операций над высказываниями. Эти законы чаще всего имеют вид тождеств, т.е. равенств, верных при вех значениях переменных. Важную роль играют тождества: 1. AB = ВА, AvB = BvA (законы коммутативности); II. (АВ)С = А(ВС), (AvB)vC=Av(BvQ (законы ассоциативности); III. A (AvB) =Л, AvAB =A (законы поглощения); IV. A(BvQ = ABvAC(закон дистрибутивности); V. А-Л = Л (закон противоречия); VI. /lv-i/1 = И (закон исключенного третьего). Эти тождества, устанавливаемые, напр., с помощью таблиц, позволяют получать другие тождества. Тождеств 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, и) медиана, эквивалента и сложение. Иногда совершают еще один важный дальнейший шаг абстракции. Отвлекаются от табличного задания операций и оттого, что значениями буквенных переменных являются высказывания. Вместо этого допускаются различные интерпретации рассматриваемого «языка», состоящие из той или иной совокупности объектов (служащих значе-