В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 7
Текст из файла (страница 7)
Формулы Ги 6 называются равносильными, или эквивалентными (обозначение: Ггв 6), если при любых значениях переменных логические значения получающихся из формул Г и 6 высказываний совпадают. 1.54. Докажите, что формулы Ги 6 равносильны тогда и только тогда, когда формула Г++ 6 является тавтологией, т.е. Гьт ьт 6 с~ ~ Г++ 6. 1.55.
Используя утверждение предыдущей задачи и тавтологии из задачи 1.28, установите следующие равносильности: а) Рч~Р— = 1, Рн-зРг— в О; б) Рчбж Р, Рч 1= — 1; в) Раб= — О, Рн 1 от Р; г) Р= Р', д) РлОмДлР; е) Рч Д= — 0ч Р; ж) (Рн Ц) н Я— = Рн(Дл Я); 3) (Рч О)ч Я =— Рч (Дч Я); и) Рн (Дч Я) — = (Р н Д) ч (Рн Я); к) Р ч Ял Я) = (Рч Д) л (Рч Я); л) Рн Р= — Р; м) Рч Р= — Р; н) Рн (Цч Р) = — Р; о) Рч (Ц л Р) ьт Р; п) Р— э 0 в = -зРч Ц; р) Р~+ О= (Р— ь Ц) л(Д-+ Р); с) з(Рн Д)— : зРч-зо; т) з(Рч Ц) =-зРл-зД; у) Рч Д=-зР— ь О. 1.56. Следующие формулы преобразуйте равносильным образом так, чтобы они содержали только логические связки -з, н, чт а) ((Х-+ У) л (У-+ Х)) -+ (Хч У); б) ((Х-+ У) л ( У-+ зХ)) -+ (У-+ Х); в) ((Х-+ У) л (зХ-+ -з У)) -+ ((Хч У) л (зХч -з У)); г) ((Х++ з У) -+ Е) -+ (Х++ зЕ); д) (Х-+ (У++ У)) ++ ((Х-+ У) <-> Е); е) (Х-+ У) -+ ((Х-ь У) -+-зХ); ж) ((Хн.з У) -+ У) -+ (Х-+ з У); з) ((Х-+ У)-+ У)-+ У; и) (Х-+ У) -+ ((Х-+ з У) -+ (Хл У)); к) (Х-+У)-+((Хч У)-+(зУч У)); л) Х-ь-и(У++Я).
Решение. л) Проделаем требуемые равносильные преобразования: Х-+ з(У++ 2!) =-зХ ч -з(У++ Е) = — зХч((У-+2) н(У-ь - У))=' Хч ((-Учг),(-г У)). 2 нтшии 33 1.57. Следующие формулы преобразуйте равносильным образом так, чтобы отрицание бьио отнесено только к пропозициональным переменным и не стояло перед скобками: а) -ч((Хл (-ч Уч -чУ)) ч Я); б) -ч((Хл У) ~ -чУ) -+ ч(Хл Х); в) ~(о'-+ ~(Ул 'ч(Ул -чХ))); г) ч(ч(ч(Хл У) -+ У) -+ (-чХл У)); д) -ч(-ч(Хч (-чУл Я)ч чУ) ~(Ул У)); е) ч((чХл -ч У) -+ (Хч (Хл -ч Т)); ж) ч((Х++(чУмЯ)) л У); з) ч((чХ++ -ч У) м Я) л У; и) -ч((Х-+ У) -+ Х) -+ У; к) ч((Хч -чу) -+ У) л (чХ~ У)); л) (Х-+ У) -+ -ч(Х++ чЯ).
Р е ш е н и е. л) Проделаем требуемые равносильные преобразования: (Х-+ У) -+ -ч(Х++ чУ) — = (-чХ~ У) -+ ч(Х+» -чУ) = ч(-чХ~ У) ч ч-чЦХ вЂ” » тХ) л (чХ-» Х)) — = (-ч-чХл У) ъ -ч((чХч чХ) л (тчХн чХ)) (Хл-чУ) ч(~(чХч'чУ) ч -ч(ХчХ)) =-(Хл-чУ) ч(-ч-чХл л-ч-чЯ) я(-чУл чХ) =(Хл-чУ) н(Хл2) ч(-чХл чУ). 1.58. Следующие формулы преобразуйте равносильным образом так, чтобы они содержали только логические связки ч и»с а) (Х ~ У) -+ (~Х-+ Я); б) (-чХ-+ У) ч ч(Х-» У); в) ((Хч УчЯ)-+Х) ч У; г) ((Х-» У) -+ 2) ».чХ; д) (Х~ ( У-+ Я)) -+ Х е) (Х-+ У) -+ ( Ул У) „ ж) (чХл -ч У) -+ (Хл У); з) ((-чХл -ч У) ~ 2) -+ (Ул -ч У); и) ((Х-+ (Ул У)) -+ (-чУ-».чХ)) -+-чУ; к) ((Х-+ У) л ( У-+ с)) -+ (Х-+ Х); л) ('Х У)- г Р е ш е н и е.
л) Проделаем равносильные преобразования: (-чХ++ У) — » У= — .ч(-чХ++ У) ч У= ч((чХ вЂ” » У) л ( У-+ чХ)) ~ У=— — = -ч((ч чХч У) л (-ч Уч -чХ)) и У=— -ч(Хч У) и ч(чХн -ч У) и У— = (чХл л ч У) и (ч чХл -ч чУ) и У— = (-чХл чУ) ч (Хл У) ч У— = -ч(ч(чХл л -ч У) л -ч(Хл У) л чЯ). 1.59.
Каждую из формул предыдущей задачи преобразуйте равносильным образом так, чтобы она содержала только логические связки -ч и ч~. Р е ш е н и е. л) Воспользуемся результатом равносильных преобразований данной формулы, выполненных в предыдущей задаче,и продолжим преобразования для решения данной задачи: (-чХ+» У) -+ У = (-чХ л -ч У) ~ (Х л У) ч У: — -ч(ч.чХч .ч.чУ) ~~ ч ч(чХч чу) ч У= -ч(Х ~ У)ч ч(чХч -чу)ч Л 34 1.60. Производя равносильные преобразования с использованием равносильностей из задачи 1.55, докажите, что все формулы из задачи 1.29 являются тавтологиями.
Р е ш е н и е. е) Покажем„что левая часть эквивалентности равносильна правой. Для этого равносильным образом преобразуем левую часть (используем равносильности из задачи 1.55, л, к): Р-+ (О л Я) — = ~~Рч (Дл Я) =— ( чРч Ц) л (~Рч Я) = (Р— ~ Ц) л л (Р-ь Я). Тогда на основании утверждения задачи 1.54 заключаем, что данная формула действительно является тавтологией. н) Покажем, что эта формула равносильна 1 (истинному высказыванию): ((Р-+ Д) -+ Р) -+ Р = -з(-ч(-чР ч Д) ч Р) ч Р— = -з((-г~Р л л -з Д) ч Р) ч Р— = -т((Р л -ч Ц) ч Р) ч Р = — (-ч(Р л -за) л -чР) ч Р = =- ((~Рч Ц) л-~Р) чР~ -~Рч Р= 1. В процессе преобразований использованы равносильности и, т, с, д, е, и, а из задачи 1.55. 1.61. С помощью равносильных преобразований установите тождественную истинность формул из задачи 1.30.
1.62. Применяя равносильные преобразования, приведите следующие формулы к возможно более простой форме: а) -ч(-чР ч Д) -+ ((Р ч Д) -+ Р); б) -ч(~Рл-чД)ч ((Р-ь О) л Р); в) (Р— ь Д) л(Д-+Р) л(Рч Д); г) (Р— + Д) л(Д-+-зР) л(Я вЂ” эР); д) (Рл Я) ч(Рл-зЯ)ч (Ол Я)ч(-~Рл ОлЯ); е) (Р -ь О) -+ ((Р— ъ -з Д) -+ -зР); ж) -з((Р++ -ч Д) ч Я) л Д; з) (Р<-+ О) -+ (-зР-+ Ц); и) (Р— ь-зД) л((Р— ь Ц)ч (Я-+ Р)); к) ~((Р-+ Д) л Р) л (зРч -зД); л) (Р+э Д) л(Рч Ц).
Ре ш е н и е. л) Проделаем необходимые равносильные преобразования (проанализируйте их самостоятельно, выявив на каждом шаге ту равносильность, которая там применена): (Р+э Д) л (Рч Д) =— (Р— + Д) л (Д-+ Р) л (Рч Д) = (~Рч Ц) л л (-з Д ч Р) л (Рч Ц) = (~Рч О) л ((Рч -ч Д) л (Рч Д)) = (зРч Д) л л (Р ч (з О л О)) и (~Р ч Ц) л (Р ч 0) (ъР ч Ц) л Р (зР л Р) ч (О л л Р)) — = 0 ч (Р л Д):— Рл Д. 1.63. С помощью равносильных преобразований докажите, что следующие формулы являются тождественно ложными: а) ((Р -э Д) -+ Р) л -ьР; б) (-з((Хч У) -+ ~(Х-+ У)) ч -з(Ул У)) -+ -ч((У-+ -з2!) ч Я); в) ~(((Х-+ У) л ( У-+ с)) -+ (Х- У)); г) ((Х-+-зУ) -+-з(Х-+ 2)) л-з(У-+ У); д) (У-+-з(Хл ~Я))-+(-з(ХчЯ) лХл У); е) ((-зР-+ -з Ц) -+ ((-зР-+ Д) -+ Р)) -+ -з((-зР-+ Р) -+ Р)'„ ж) -и Ц л Р л (Р -+ Д); з) (Рч О) ++~-ъРл Я-+-чЦ)); 35 и) (Р— «(Д-+ Я)) л (Р— «Д) л Рл -~Я; к) ((Хл -ч У) ч (Хл -зУ)) ++ ((Х-+ У) л (Х-+ Я)); л) ((Р— « -ю Д) -+ ((~Я-« ~Х) -+ (Р л Д))) л -ч(Я-«Р).
Р е ш е н и е. л) Выполним равносильные преобразования: ((Р -+ ~ Д) -+ ((-зЯ -+ -ьУ) -+ (Р л Д))) «, ~(Я -«Р) = — (-з( зР ч ч -ч Д) ч (-з(Я ч -зо ) ч (Р л Д))) л -з(-юЯ ч Р) — = ((Р л Д) ч (-~Я л о ) ч ч (Рл Д)) л (-~Рл Я) = ((Рл Д) ч (-чЯ л «)) л (зРл Я) = — (Рл Дл л зР л Я) ч (-зЯ л о л -ьР л Я) = — 0 ч 0 = О. 1.64. С помощью равносильных преобразований установите, какие из следующих равносильностей действительно выполняются: а) Р-«Яч Я) а(Р-«Д) ч(Р-+ Я); б) Р-«(Дл Я) — = (Р-«Д) л (Р— + Я); в) Р-«Я++ Я) ге (Р-«Д)++(Р-+ Я); г) Р л (Д+«Я) = (Р л 0) ++ (Р л Я); д) Рч(Д<«Я) = (Рч Д)+«1Рч Я); е) Рл(0-«Я) — = (Рл 0)-+(Рл Я); ж) Рч (Д -«Я) =(Р ч Д) -«(Рч Р); з) (Р— «Ц) л Я =— (Рл Я) -+ (Ц л Я); и) (Р— «Д) ч Я = (Р ч Я) -+ (Дч Я); к) Р-«(Р+«Д) = Р— «О; л) Р— «(Рл Д) = — Р— «Д; м) Р— «(Рч Д) = Р— «Д.
Рещение. л) Р— «(Р л м) = — ~Р ч (Р л Д) — = ( зРч Р) л(~Рч ч Д) — = 1 л (Р-«Д) — = Р-«Д. м) Данная равносильность не выполняется, так как для формулы слева имеем Р-«(Рч Д) -=-~Рч(Рч Д) и~;~Рч Р) ч Д= — 1ч ч Д = — 1, т.е. формула Р-«(Рч Д) является тавтологией, в то время как формула справа Р-«Д, очевидно, тавтологией не является.
1.65. Чему равносильны следующие выражения (формулы): а) Р-«О; г) 1-+Р; ж)0-«-зР; к) О+«~Р; б) Р†« 1; д) Р+« 1; з) -зР-« 0; л) 1 -« -зР; в) 0-+Р; е) ~Р-«1; и) 1++зР; м) Р+«О. Решение. л) По определению импликации имеем 1-+0=0, 1 — «1= 1, т.е. при значении посылки, равном 1, значение всей импликации совпадает со значением следствия. Значит, 1 -+ -зР -= — = -зР. м) Для эквивалентности имеем 0++0=1, 1++0=0, т.е. при ложном одном высказывании логическое значение эквивалентности двух высказываний противоположно логическому значению второго высказывания.
Следовательно, Р++ 0 = — ~Р. 1.66. Докажите, что для нахождения отрицания произвольной формулы, составленной из пропозициональных переменных и логических связок л, ч, -з, достаточно всюду заменить знак л на знак ч, знак ч заменить на знак л, всякую переменную, входящую в формулу без знака отрицания, заменить на ту же переменную со знаком отрицания, а все имевшиеся знаки отрицания уничтожить. 36 1.67. Найдите отрицание каждой из следующих формул: а) (Хл ( Уч~ -чУ)) ч (-чХл У); б) ((-чХл-чУл-чУ)ч Я) л-чо'л-чр'л-чу; в) (((-чХл (-ч Уч У) ) ч Р) л -ч О) ч (чЯ л (Б ч -ч Т)); г) -ч(Хм -ч У) и ((-чХч -ч Уч У) л Хл Ул -чУ); д) (Хч -ч(~Хч У) м (-ч Ул ~2')) л -ч(Хл У); е) Хл ((Хл-чу)ч -ч(-чХч~ -чу У)); ж) (((-чХл УлчУ) ч (Хл-чулУ)) л(Уч У))ч (Хл Ул2); з) ч(Хн-чу) л(чХн Уч-чУ) л(-чУч-чУ); и) (-чХл ( Уч~ У)) ч (Хл -чУ); к) Х г ч((-чХч -чуя-ч2) л(Хч Уч У)); л) ((Х (-чУн (-чУл Р))) Д) л Я.
Р е ш е н и е. л) Руководствуясь правилом, сформулированным в задаче 1.66, выписываем отрицание данной формулы: ((-чХ~ (Ул л (Уч -чР))) л Д) ч -ч Я. Отметим, что для упрощения формулы иногда бывает удобно сначала найти ее отрицание, упростить его, а затем снова взять отрицание полученного результата. 1.68. Сколько существует неравносильных между собой формул б(Р, Д, Я) от трех переменных, являющихся логическими следствиями формулы: а) (Р-+ Д)-+ Я; ж) (Р++ Д)лчЯ; б) РчДнЯ; 3) РлДлЯ; в) (Р~Я)-+(Рл Ц); и) (-чРл О)++-чЯ; г) (Р л О) -+ -чЯ; к) (Р— ь (Д-+ Я)) -+ ((Р-ь Д) -+ д) Рч-ч (Д-+ Я); -+ (Р-+ Я)); е) (Р-+ О) г(Р-+Я); л) -чРч~(ЦлЯ). Р е ш е н и е.
л) Составим таблицу истинности данной формулы: Вспоминая определение логического следствия, постараемся понять теперь, как может выглядеть столбец значений формулы 37 6(Р, 0, Я), являющейся логическим следствием данной формулы зРч (0 л Я). В тех строках, где данная формула принимает значение 1 (у нас это строки 1, 2, 3, 4 и 8), формула 6, являющаяся ее логическим следствием, может также принимать лишь значение 1 (см. столбец значений формулы 6. В тех же строках, где данная формула принимает значение О (у нас это строки 5, 6 и 7), ее логическое следствие 6 может принимать любое значение (в столбце 6 таблицы эти места отмечены знаком *).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
