Основы дискретной математики В.А. Осипова (552659), страница 8
Текст из файла (страница 8)
С точки зрения логики тождественноистиншяе формулы суть не что иное, как логические законы, ибо при любой подстановке вместо переменных тождественно- истинные формулы конкретных высказываний в результате 24. Логика высказываний получим истинные высказывания. Перечислим наиболее важные тождественно-истинные формулы (А, В, С вЂ” р С вЂ” п оизвольные формулы): 1) А )г ~А (закоп исключенного третьего или 1ет~гит попда1иг); 2) АзА; 3) Аэ(ВЗА); 4) (А Э В) ) ((В ~ С) З (А ) С)) (цепное рассуждение); 5) (А з (В э С)) з ((А э В) з (А э С)); 6) (А4гВ) з А, (АйВ) з В; 7) А З (В З (А4сВ)); 8) А э (А ч В), В з (А),' В); 9)( Вз А)З((-.ВзА)эВ); 10) ((А з В) З А) з А (закон Пирса).
Каждую из них можно обосновать, например, составив таблицу истинности и вычислив по ней значение формулы при произвольных значениях А, В, С. Проблемой разрешимости для логики высказываний называют следующую проблему: существует ли такая процедура, которая позволяла бы для произвольной формулы в конечное число шагов определить, является ли она тавтологией? Ясно что эта проблема разрешима, поскольку можно пере) брать все оценки списка переменных и вычислить на них значения формулы.
2.1.5. Двойственность. Закон двойственности Будем рассматривать формулы, содержащие только логические символы Й, Ч, —. Символы 4с, Ч называются двойственными друг другу. Формула А* называется двойственной формуле А, если она получена из А одновременной заменой всех символов 4с, у на двойственные. Например, формула Х1й(Х2 Н ~Х1) двойственна формуле Х1 )) (Хаас- Х1). Очевидно, что (А")' совпадает с А.
П, < Х Х ... Х, > — некоторый список переменных, усть < з з ... зь > — его оценка. Назовем оценку < 11, гг, ..., Ц > З1)З2)")Ь двойственной оценке < з1, зг, ..., зь >, если ( получается из ( з1, з2, ..., зь > заменой всех И на Л и всех Л на И.
47 2Л. Логика высказываний получ)эем равносильность 46 Глава 2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ Лемма 2.3. Пусть А — формула, а < Х;„Х;„..., Х;„> — список 'перелтенньтх, от котпорого 'она зависит. Тогда А принимает зпачение И на оценке < зь вг, ..., вв > в толт и только в твом случае, если А* ттринимает значение Л на оценке < 1ь 12, ..., ~ь >, двойстпвепной оценке < вь зв, ..., вт) >. Докажем лемму 2.3 для всех формул А, зависящих от списка переменных < Х;„Х;„..., Х;, >, индукцией по числу п логических силтволов А.
Если и = О, то А совпадает с одной из переменных Х;, (1 < 1 < й). В этом случае А* тоже совпадает с Х,, То, что Х;, пРинимаетзначение И на оценке < зь вг, ..., вь >, означает, что вт есть И. Но это равносильно тому, что Й есть Л, а также тому, что Х;, принимает значение Л на оценке < $ь 12, ..., 1ь >. Пусть утверждение леммы 2.3 справедливо при числе логических символов, меньшем п. Докажем, что оно остается справедливым и при числе символов, равном и. Тогда формула А должна иметь вид ~В, ВйС или В Ч С. В соответствии с этим утверждением различают три случая: 1.
Формула А есть -В. Тогда, очевидно, А* совпадает с — (В*). Пусть А истинна на оценке < вь зг, ..., вь >. Тогда В будет ложной на ней. В формуле В' число логических символов меньше п. Так как (В*)* есть В, то из ложности (В*)* на оценке < вь з2, ..., вь > следует истинность В* на оценке < 1ь 12, ..., Фв > (ибо < вь зв, ..., зь > и < 1ь 12, ..., 2ь > взаимно двойственны). Отсюда следует, что формула А* (или - (В*)) ложна на < ~ь ~2, ..., 2ь >. Аналогично из ложности А* на < 8т) 12) ..., 2ь > выводится истинность А на < вь з2, ..., вь >. 2.
Формула А есть ВйС, В этом случае А* есть В* Ч С'. Пусть А принимает значение И на оценке < вь в2, ..., зь >. Тогда и В, С будут истинны на < вь в2, ..., вв >. Так как в формулах В, С число логических символов меньше и, то В*, С* примут значение Л на < 1ь 22, ..., 1ь >, а значит, и В* )т С* принимает значение Л на этой оценке. И наоборот, если В' ч' С* принимает значение Л на < $ь 22, ..., ~ь >, то формулы В*, С* бУпУт ложны на < 2ь 12, ..., 1ь >, и, далее, в силУ индУктивного предположения В, С будут истинны на < зь вть ..., зь >, а значит, и ВйС будет истинна на этой оценке.
3. Формула А есть В'ч'С. В этом случае А* есть В'йС*. Пусть А принимает значение И на < вь ва, ..., вь >. Тогда либо В, либо С будет истинной на < зь зг, ..., вв >. Если это, например, будет В то поскольку в В логических символов меньше, чем ) п, В' будет ложной на < йь 12) ..., й, ). Но тогда и В йС будет ложной на < 1ь 12, ..., 1ь ).
Аналогично рассуждаем и в случае истинности С. Доказательство обратного утверждения также несложно. Теорема 2.1 (принцип двойственности). Если А = В, то А* = В". гт А В Если переменных от которого зависят формулы А, В (и, очевидно, ) А*, В*), а < 1м 12, ..., 2ь > — оценка этого списка, то принимает значение И на этой оценке в том и только в том случае, если (А*)* (т.
е. А) принимает значение Л на оценке < вь з2, ..., вь >, двойственной оценке < Фм 12, ..., ~ь >. Но последнее в силу равносильности А и В имеет место тогда и только тогда, когда В принимает значение Л на оценке < вь в2, ..., зь >. С другой стороны, В* принимает значение И на оценке < 1м 12, ..., 2ь > только тогда, когда (В")' (т. е. В) принимает значение Л на < вь з2, ..., вь ). Итак, видим, что истинность А* на < 2ь Ф2, ..., 1ь > равносильна истинности В* На < 1ь Ф2, ..., 1ь >.
ПОСКОЛЬКУ ОЦЕНКа < 1м 12, ..., 1ь > произвольна, получаем,что А* = В*. Принцип двойственности можно применить для нахождения новых равносильностей. Например, используя следующий частный случай дистрибутивности й относительно Ч Х;й(Х Ч Хь) = — (Х)йХд) У (Х;йХв), Х; у (Х йХь) = (Х; )т Х )й(Х; и Хь). Другие приложения принципа двойственности будут приведены ниже. 2.1.6. Нормальные формы формул Заметим, что в силу ассоциативности операций й и Ч (см.
теорему 1.1), как бы мы не расставляли скобки в выражениях А)йА2й йАь, Ат Ч А2 ')т )т' Аь (й > 3), всегда будем приходить к равносильным формулам. Допуская некоторую 48 Глава 2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ вольность, каждое из этих выражений будем считать формулой и называть соответственно многочленной конъюнкцией и дизьюнкцией формул А1, Аг, ..., Аь.
Для этих формул, используя, например, индукцию по шах(а, 1), нетрудно получить равносильности, выражающие обобщенную дистрнбутивностзя (АгйАгй ..йАь) в' (ВгйВгй ..йВг) ав = (А1 уВ)й(А1 МВ,)й й(А1 1~В,)й й(Аг'»'В1)й(Агчвг)й. й(А чвг)й .. " й(А,~В1)й(Аьчвг)й" й(А,чВ1) (А1 У Аг У . У Аь)й(В1 У Вг и . г/ Вг) вз = (Агйв,) м (А,йв,)1 "~ (Агйв,)у Ч (АгйВ1) У(АгйВг) У .
У(АгйВг) У ".1 (А„йвг)ч (Аьйвг) ч" ~ (Аьйв,). Определим теперь некоторые канонические виды формул. Формулу называют элементарной ког«ъюнкцией, если она является конъюнкцией (быть может, одночленной) переменных и отРицаний пеРеменных. НапРимеР, фоРмУлы Хг, . Хг, ХгйХз, Хгй ХгйХ«йХг являются элементарными конъюнкциями. Говорят, что формула находится в диэъюнктпивной нормальной форме (ДНФ), если она является днзъгонкцией (быть может, одночленной) элементарных конъюнкций. Например, формулы Хг Хз ХгйХгйХз, (ХгйХгй'"Хз) гг (Хгй ХгйХз) находятся в ДНФ.
Теорема 2.2 (о приведении к ДНФ). Для любой формулы А моэгсно найти такую формулу В, находящуюся в ДНФ, что А = В. Формула В называется диэъюнктивной нормальной формой формулы А. Доказательство теоремы распадается на три этапа: 1-й этап. Для формулы А строим такую формулу Аг, что А ив е А1 и в А1 не содержится символов, ~ (см. утверждение 2.2). 2-й этап. Докажем теперь, что для формулы А1 можно найти формулу Аг такую, что А1 = Аг и в Аг отрицание находится 2.1. Логика высказываний только перед переменными. Такая формула называется формулой с «тесными» отрицаниями. Докажем это утверждение индукцией по числу и логических символов формулы Аг. Если и = О, то А1 есть какая-то переменная Хо В качестве Аг нужно взять Хо Пусть утверждение выполняется для всех формул Аг с числом символов меньше и.
Пусть в формуле А1 содержится точно и логических символов. Рассмотрим следующие случаи: 1) А1 имеет вид В1 У С1. Тогда в В1, С1 логических символов меньше, чем п. Поэтому существуют формулы Вг, Сг такие, что В1 —= Вг, С1 = Сг и в Вг, Сг отрицание встречается только перед переменными. Ясно, что Вг г,г Сг равносильна А1 и является формулой с «тесными» отрицаниями; 2) А1 имеет вид ВгйС1, Доказательство аналогично предыдущему случаю; 3) А1 имеет вид В1. Тогда А1 = В1 и в В1 логических символов меньше, чем и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
