В.Н. Нефедов, В.А. Осипова - Курс дискретной математики, страница 6

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

ПрнмеР 12 Формулы (Х,юХз) тг (Хг~(ХзаХг)) н (Х, юХе) тг' 'Хз нмеют соответственно таблицы нстпнностн 1.б Я 1.7. Упорядоченный набор еысказывательнмх переменных (Хг„,..., Хц ~ назовем списком переменных формулы Л, еслк зсе переменные формулы Л содержатся и этом наборе. В спнскс 27 переменных формула А часть переменнмх может быть финтнвмой, т. с. нс вкодпть явно в формулу А. Оценкой списка переменных назовем сопостаалеяие каждой переменной списка некоторого нспинсстного значения. Прн этом, еслн спнсок переменных формулы А солержнт й переменных, то вмеется 2" разлнчнык оценок, н, следовательно, таблнца нспщносгн этой фор. мулы содержит 2" строк.

Врнмер 1.3. Список переменных первой нз формул, прим- денных в примере 1.2, есть <Хь Хг> нлн <Хь Хь Хз>, <Ль Хь Ль> п т. л, (здесь Хз. Хь — фнктнвные переменные). Для формул, зависящих ст фнкснрованнсго списка <Хгр... Хц>. овределим нндуктявно нх значение нв данной оценке сайска (нлн, иначе, прн данном распределения встинпсстнмк значений переменвмк)г 1) формула есть одна нз переменных Х,, ...

Хц, например, Х,А тогда значение ее ва данной оценке есть то встнннссгное зваченне, коюрое сожютавлено переменной Хг,', 2) формула имеет внд:( )А), а значение А на данной опенке есть з; тогда значение ( )А) на данной опенке определяется как -)э, где )з вмчнсляегсв во табл. 1.1; 3) формула вмеет внд (АЙВ), млн (Ат)В) нлн (АщВ], плн (А — В), а значения А, В на данной сценке есть з.

!. Тогла аначенпе (АЙВ) будет зйй где ей1 вычнсвяетс» по табл. 1.2, а значения остальных формул определякчся аналогнчно. Ясгщ что значение формулм валяется фуякцнсй сценок. Теперь можно сформулировать основные понятия. 1.1.2. Равноснльнссть йюрмул Пусть А н  — две формулы, завпсящне от одного п того же списка перемепнык <Хгг ..., Хь >. Буден называть нх равносильпмми, если на любой опенке списка <Хг,,..., Хц> опп принимают одннаковмс значенвя. На первый щгляп, это определенно кзжеюя неоднозначным, так как А н В могут зависеть от бесконечного чнсза списков псременнмь. Однако эта неоднозначность только кажущаяся.

Т Ез нз 16 таа аца Гг Любой нз возможных спнсков должен содержать все переменные А н В, прячем зпачення А я В на любык оценках списка будут зависеть только от значсннй переменнмх, входяшнх в формулм А н В. Равносильность формул имеет свой алгебрапческнй аналог в тождественном равенстве алгебраических вмраженяй. Равносильность формул Л н В будем обозначать через А=В (так же, как в алгебре; папрнмер, а(Ь + с) ю аЬ+ ас). Нужно разлнчать самволы н =— .

Так, является символом формального языка, с помощью которого строятся формулы, а символ ии заменяет слова равносильно». Отношение равноснльностн есть отношение зквнвалентпостн. Действительно, оно рефлекснвно, так как для любой формулы А А А; симметрично, так как для любмх формул А н В, еслн Яви В, то В Я; трап»к»явно, так как для любмх фор. мул А, В, С, если А аа В в В С, то А юг С. ()оскальку в определения равноснльностн формул А, В безразлнчно, какой спнсок яеремсннмх берюся (лншь бм он включал в себя переменвме А н В), то в качестве <Кг,..., Кг»> возьмем список всех переменных формул А, В, С. На любой оценке зтого списка формулы А. В, а равно н В, С принимают одни н те же значения.

Следовательно, в формулы Я, С па всех оценках принимают одинаковые зваченкя. Основные равноспльностн. Для юабмл формул А. В, С спраеедлиаи следующие рааиосилыюсги 1) А А  — В ВЛ (поммуштиеиссть й); 2) А й А — А (идемпотептиосгь й); 3) Ай (ВВС) за (АВВ) ЬС (ассоциатиаиосгь й)г 4) АК/В из В)/А (комиутагиаиость ~/)г б) А з/А = Л (идемпогсягносгь К/)г 6) А З/ (В»/С) юг (А т/В) т/С (ассоциагиапосгь т/)/ 7) А~/ (ВАС) ва (А т/В) й (АК/С) (дистрибутиеиосгь К/ отиасигельио й) Г 8) Ай(Вт/С) (ЛВВ) ~/(АВС) (дисуРЫугиаиосгь огиасигельло )/)Г 9) А й (А К/ В)аа А (аврама аакаи паглащриия)г зв 10] АТ( (А йВ) м А (ам!род эиюж ломал(ения)7 11) 1 ! А ии А (спягие двойлозо отрибаиия)! 12) )(А йВ) (А Т( (В (лажяиб зяюж де Мараини)! 13) ) (А т('В) )Ай (В (второй зэков де Моргана); 14] А м (АЬВ] (('(Ад ]В) (лераия Формула расщеллелил); (б) А мч (А ((' В] 6~(А () ] В) (егория формула рисщаллеяия).

Любая из этих раввоснльвсстей легко мажет быть доказана с помощью таблиц истинности. Рассмотрим, например, равно. сильность 7. Пусть (К(Н..., Хн> — «акой-либо спиаж переменных, от которого зависят А, В, С. Тогда кл» значений А В, С иа какой-нибудь оценке списка переменных имеется восемь вариантов. Длн «аждого варианта по таблицам истинности нетруЛно подсчитать эяаченвя левай м правой частей равносильности 7 н убедиться в том, что в любом вз восьми случаев зтм значение совпадают (см. табл.

1.0). таа ива !8 (Аъ/В]а (АНС! А1гс А туп пас АМ(пдс! Однако часто равносильность экономнее доказывать беа составления полной таблицы, а лишь с помощью некоторого рассуждения. Рассмотрим, например. первый заков де Моргана (равносильность 12). Докажем, по если на каков-то сценке списка переменных, от которого зависят А и В, левая ча«ть рав. посильности !2 получает значение Л, то и правая сс часть по.

пучит значение Л, и, наоборот, если ва какой-то оценке списка переменных правая часть рашкюильно«тн принимает значение Л, то и левая часть примет значение Л. Это и будет означать равносильность. Итап, пусть на некоторой оценке опаска переменных формула П (ААВ) принимает значение Л. Тогда формула АЬВ прикипает значение И, а поэгому обе формулы А, В принимают эаачепие И. Но в этом случае, ачевпдпо, и правая часть равносильности 12 примет значение Л. И наоборот, пусть формула(АТ/ ! В принимает значение Л. Тогда формулы -(А, ПВ принимают значеяие Л, а формулы А,  — значение И. Очеэидно, что н леван часть равносильности 12 привет значение Л. зо Следующая грузна раввоснльностей показывает, что однц связки могут быть выражены через другие: 16) А В (АшВ) й (В=~А) я (ААВ) ~т (-! Ай-!В); 17) А ш В ") А'4 В м -! (А й -! В); 18) А~ГВии -!ЯШВ -1-)АВ-1 В); 19) ЯАВз-)(А~-)В) ги( ~(!А тг' -)В).

В снлу транзвтнвнсстн отношения равносильности, если А,ниАь Азиадь. ° °, Аьч' Аь то А~ — Аь В таком случае для простоты будем записывать цепочку А, = Азия ... гдг-1= — Аь Правы!ем правило, с помощью которого можно яереходнть от одних равноснльностей к другнм. Лемма 1.1.Пусть А В и С вЂ” лроизеогьная фюрмумт. Тогда -!А=-!В, АЙСинВВС, СЙА САВ, А~/С ниВтгС, С)/А=СтгВ, АшСжВшС, СшА СшВ, А С В СС АьяС В, Докажем, например, равносильность А ~ С и В ~ С. На произвольной оценке списка переменных, от которого зависят А, В, С, формулы А н В нрпвнмают одннаковос значение (ска- жем, з). Пусть ! — эначепне С на этой оценке.

Обе часты рас- сматрнваеной равноспльностн прннвмают одно я то же значе- ннс з ш г. Лемма 1.2. Пусть А ш В я С вЂ” формула, е нагорай еыде- лено одно вхождение переменной Хь Пусть Сл получается из С заменой этого вхождения Хг на А, а Св — из С заменой того же вхождения Кг на В. Тоеда Сл Си. Докажем это вндукцвей по чпслу л логическнх снмволов С. Есин н О, то формула С должна совпадать с Х~ (так как в ней ямеется вхождение переменной Хг). В этом случае Сг есть Я, Си есть В, а С» =— Сэ — нс что нное, как А == В.

Пусть лемма доказана для чпсна лопшескнх символов мень- ше н п пусть С вЂ” формула с н логнческамн сямаоламп. Она имеет вяд П О, нлн ОЬТП нлп ОгтЕ, нлн ОшЕ, нлн О Е, причем в первом случае выделенное вхождение Хг содержится в О. а в остальных случаях — лабо в О, либо в Е,но нс в О н Е сразу. Рассмотрнм, например, случай, когда С имеет внд Ош Е, а выделенное вхождение Х, содержите» в Р. Замення Кг в этом вхожденнн в О на А я В, получаем соответственно формулы О.з н О .

Ясна, «то Сл есть О* ш Е, а Сэ есть Рз шЕ. Так нак в формуле Р меньше логнчеекпх символов чем в С, то О» Ов. ПРнменнм тепеРь лсммУ 1.1 в слУчае АшСгм нн В ш С, где в ропп А выступает О.ь в ролн  — Он, в роли С вЂ” Е. В результате получаем Слив Сэ. Другие случал ргс- сматрнваются аналогично. Утвержденне 1.1 (нрава ю рааносильниг преобразований). Пусть С,с — формула, содержащая А е качестве своей лод- фармулм. Пусть Си нолучается иэ Сл заменой А е етом егюж- дении на В, Тогда, если А мг В, га С» пн Са з! Рассмотрим пра»»вольную переменную Хг к получим формулу С нз С» заменой А на Хь Будем счвтать это вхождение Х, в С выделенным.

Тогда С, А, В, Сч, Св удовлетворяют условя»м леммы 1.2, а эначнт, С,г = С». Заметим, что алгебраический аналог этого правила достаточно очевиден (впрочем, как в само правило) и обычно прнменяетс» без особого обоснованп». Напрнмср, пользуясь гож. деством х + х = 2х, получают у(х + х) = у(2х). Утверждение 1.2 (правило устра ения лосичсски» сииаолоа ю и -). Дл» каждой формулы можно уюмагь равносильную ей формулу, на содергкащую логичгсяах симоолоа и ю. В самом деле, опираясь на правнло равносильных преобразований, можно в походной формуле каждую подформулу внаа А В «вменять на (АВВ)фт/( )Ай Р)), а каждую подфорыулу вида А ю — аа -)А~/В (см.

равносвльностн 16 н !7). Можно дать в более строгое доказательство, нрнменнв яндукцню по числу лгамческнх символов. Пример 1 4. Формула (Х~ з (Хт юХз)) "1 (Кз зХ~) лра. образуется следуюцпгм образом: (К~ю (КэюКв)) -1 (Хз~ юХг)=(Х1ю( )ХзЧХз)) -( 1( ХаЧК)) = ( ~ХгЪ'( )Х Ч ЧХ)) -1(-)Х УК) ((ЗХ)/ (-)Х Чх))й)()к Чк))ту Ч ( )( )К,(l ( ЗХ"4 К,))д ) 1() Х ЧХ)).