1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 43
Текст из файла (страница 43)
е. преобразований, сохрвкяющих эквивалент- ность, являются тождественные соотношения между формулами. Уже наш школьный багаж содержит большой запас тождеств для арифметических операций: а+Ь= Ь+а, а(Ь+с) =аЬ+ас, а(Ьс) = (аЬ)с, алгебраических тождеств: (а + Ь)а = аг + 2аЬ + Ь", (ав — Ь«) = (а + Ь)(а — Ь), тригонометрических соотношений: з)пах+ соз'х = 1, з(п (а + Ь) = з1п а.соэ Ь + сова з)п Ь (1) (2) (3) (4) (5) ") В последующем изложении мы оставим в стороне сравнительно реже употребляемую операцию альтернативы + (ясюпочающее «нлн«). ит. п. Непосредственное рассмотрение простейших логических фор- мул и основных логических операций позволяет найти немало важных соотношений, отражающих свойства булевых функций. Одни из них тривиальны, а другие выглядят неожиданно и ин- тересно, и их обнаружение в свое время вносило существенный вклад в развитие логики е). Первая группа соотношений выражает, так сказать, внутрен- ние свойства логических операций ") ~х=х, х )/ у = у ~/ х, х~/(у~/г) =(х~/у) ~/г, х б«у у 8«х, х б«(у й г) (х б«у) б«г, % ЪФ.
АЛГЕБРА ЛОГИКИ 20! х:» (у ~ х) = у ~ (х =» г), х=у=у=х, (6) (7) (8) х = (у — = в) = (х =— у) = — х. Заметим, что импликация не обладает ни коммутативностью, ни ассоциативностью. Следующая группа соотношений демонстрирует некоторые комбинированные свойства операпий: х Й (у ~/ з) = х 8с у ~/ х Й х. Интересно ааметить, что конъюнкция идизъюнкция взаимнодист- рибутявны: х ~/ (у Й з) = (х ~/ у) Й (х ~/ г). (10) Импликация также взаимно дистрибутивпа с диаыонкцией: х:» (у ~ в) = (х:» у) )/ (х:» в), (11) х ~ (у ~ г) = (х Ч у);» (х ~ а), (12) (х Ч у):» з = (х ~ г) )/ (у ~ з), (! 3) Следующая группа соотношений раскрывает свойства опера- ций при наложении некоторых свяаей на их аргументы: х )/ х = х, х~/ ~х=Ф, х )/1= х, ' х~/1=1, хйх= х, х л 1х=1, х 8~1=1, х бс 1 = х, х:»х = 1, х:» (у ~ х) = 1, $=»х= х, (~х= Ф, х:»$1, (16) (17) (18) (19) (20) (21) (22) (гз) (24) (25) (26) (27) (28) однако для импликапии и конъюнкции имеет место только одна дистрибутивность х .:» (у А а) = (х =» у) й (х ~ а).
хан у = ~х = ~у. х~$= 1х, (29) (39) (3Ц (32) х=х=й, 1— = х=х, Последняя группа соотношений вРзра>кает одни операции через другие: Каким бы внушительным этот перечень тождеств ни казался, он оставит критического читателя неудовлетворенным из-за сво- ей произвольности. Действительно, этот список в равной степени легко как пополнить, так и сократить. Е1апример, добавить такое интересное тождество, как х :э (у :з 'х) = (х :э у) :э (х :э з), Возникают также вопросы и с менее очевидным ответом: например, выводится ли из этих 39 соотношений таков тождество, как 1$ = 0 'Таким образом, найдя какую-то систему равносильных преобрааований, мы постоянно должны спрашивать себя, достаточна ли эта система, чтобы в ней вывести любую формулу, эквивалентную данной, и нет ли в этой системе лишних соотношений, т. е.
выводимых из других соотношений системы. Конечно, «лишними» мы их полагаем только в теоретическом смысле, так как оказавшись выводимыми из других, базовых соотношений, они остаются сами по себе весьма полезными. эа ГЛ. З. КРАТКОЕ ПОВТОРЕНИЕ МАТЕЫАТИЧЕСКОИ ЛОГИКИ х~/у= ~( ~хх ~у), х ~/ у = (х:> у) ~ у, х8у= ~(1 Ч 1у), х:~у- ~у:э )х, х~у= ~х~/у, х:~у= ~(х8с ~у), х = — у = (х:» у) 8с (у:з х). или исключить, скажем, тождество х~у= ~(хй ~у), потому что оно с легкостью выводится из соотношений х~у== )х~/у, х~/у= ~( ~хл ~у), ~х=х. (33) (34) (35) (39) (37) (38) (39) % «Л. АЛГЕБРА ЛОГИКИ . Возвращаясь к нашим задачам о выяснении эквивалентности и нахождении алгебры логических формул, мы можем наперед заметить, что если бы мы яашли полную систему тождеств в логических формулах, то получили бы еще один способ распознавания эквивалентности.
Действительно, пусть А и  — дзе логические формулы, задающие булевы функц>(и (А и Ь. Для )А и Ь существуют их совершенные нормальныд> формы К(~А) и КУБ). По построению А эквивалентна ККД й В эквивалентна К((в). Поскольку наша система тождеств полна, мы можем систематически «вывести» К(~А) из А и К(1Б) из В. Если в результате этих двух выводов получатся одинаковые совершенные нормальные формы, то это значит, что А и В эквивалентны (в силу теоремы 5).
Схемы формул. Поставим теперь точно задачу нахождения алгебры логических формул. Добавим к алфавиту языка логических формул буквы А, В, С,..., обозначающие метапеременнме. Значениями метапеременкых являются логические формулы. Применяя к расширенному алфавиту переменных правила формальной грамматики, мы получим, кроме обычных логических формул, еще н такие формулы, в которых фигурируют метапеременные. Каждую такую формулу мы для отличия будем называть схемой (логической формулы). Схема обозначает не одну формулу„ а множество(как правило, даже бесконечное) формул,' которые получаются.в результате замены каждой метаперемениой во всех ее вхождениях на любое (но одно и то же) ее значение.
Использование схем вместо конкретных конструкций является обычным математическим приемом формулирования обших утверждений: говоря, что схема обладает некоторым свойством, мы тем самым делаем общее утверждение обо всех 'получаемых из нее конкретных конструкциях. Конструкция С получается из схемы Я, если существуют значения метапеременных из Я, такие, что прн их замене на эти значения Я превращается в С. Например, говоря, что схема А )/ ~А является тождественно истинной, мы на самом деле высказываем общее суждение о бесконечном списке.
формул вида Х~/ ~Х, ((А ~/ В) =» С) Ч 1((А ~/ В) =з С), ~А~/ ) ~А, ит. д., состошцее в том, что все подобного рода формулы задают тождественно истинную функцию. В ряде случаев, говоря о схемах, мы фиксируем ограничения, налагаемые на метапеременные. оба Рл. е. кРАткОе повтОРение ИАтемАтической логики Например, сделанное утверждение о схеме А ~/ ~А справедливо только, если А — это одночлен "). Уточним далее, что мы имеем в виду, когда говорим, что логическая формула задает булеву функцию.
Пусть дано несколько логических формул Ф„Фз,..., Ф,. Зададимся любым количеством логических переменных х„..., х„, лишь бы их было не меньше, чем разных переменных в этих формулах, и сопоставим калы дой переменной из формул одну из логических переменных хи Зто сделано для того, чтобы мы формально могли бы считать в равносильном преобразовании, например, х:э (у:э х) = $ стоящую справа тождественно истинную величину $ функцией двух переменных, х и у. После такого сопоставления определим, как это было сделано выше, индуктивный процесс вычисления вначеинй истинности как функции )г переменных хг,..., х„для каждой из формул Фы Полученные булевы функции у„..., ~, называются (совместной) интерпретацией формул Ф„..., Ф,. Пояятие исчисления.
Назовем равносильностью слово вида А В, где А и  — логические формулы. Равносильность называется лгоакдвствснной, а формулы — вкв в лвнтными друг другу, если в любой совместной интерпретации соответствующие булевы функции )А и 1в тождественно равны друг другу. Допуская вместо логических формул их схемы, получим схему равносильности, для которой уже объясненным выше способом также можно определить свойство тождественности. Заменив в тождествах (1) — (39) знак равенства (который мы зареаервировали для содержательного использования) на —, мы,очевидно, получим серию тождественных равносильностей. Для того чтобы обобщить эти равносильности до схем, нужно зйменить символы х, у и х на метапеременные, например, А, В и С, и для каждой схемы указать, какие формулы допустимы в качестве их значений.
Например, равносильность (34) х ')/ у = (х:э у):э у переходит в схему А ~/ В (А:э В):э В, где А и  — конъюнкции. з) На всякий случай предупредим читателя, чтобы оя не смешивал только что введенные метаперемеикые А, В, С с обоапачеквямк прокзвольвых, ко фиксированных формул вида А, В и т. к., веформальво используемыми в тексте. Оки тоже являются своего рода метаперемеккыми, яо в другом мета- арыке, каковым является русский язык, ма котором написана зта кввга. 2 6.2. АЛГЕБРА ЛОГИКИ Назовем, далее, правилом вывода составную конструкцию, имеющую две части — посылку и заключение: посылка — это совокупность схем логических формул и равносильностей, заключение— равносильность или схема равносильности «). Текстуально правило вывода выглядит как дробь, в числителе которой пишется посылка, а в анаменателе — заключение, например, Хлу 1Х~/У,Х~/У )( ) Хв~ ) У),~~Х Х Х=>У 1(ХЖ 1У), Исчислением называется некоторый список правил вывода и равносильностей (или их схем).
Последние в качестве составной части исчисления называются аксиомами (схемами аксиом). Дадим теперь вах'нос индуктивное определение. Некоторая равносильность нли схема равносильности 21 называется выводимой в исчислении Т, если она: 1) или получается иа выводимой в Т схемы равносильности; 2) или является аксиомой в Т; 3) или получается из схемы аксиомы в Т; 4) или, если в Т есть правило вывода, для которого существуют такие выводимые посылки, которые задают 11 в качестве заключения этого правила.
Это определение раскрывает смысл исчисления, которое является одним из самых фундаментальных математических понятий. В общем случае исчисление — это механизм систематического получения некоторого множества конструктивных объектов путем отправления от некоторого изначального, заданного множества. Этим изначальным множеством являются аксиомы. Каждое правило вывода — это некоторое индуктивное определение новой конструкции (заключения) через конструкции, заданные в его посылке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
