В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 35
Текст из файла (страница 35)
173 Следовательно, множества истинности данных предикатов не равны, если предикат Р(х) не является тождественно ложным. 9.17. Каким условиям удовлетворяют множества истинности одноместных предикатов Р(х) и Д(х), заданных на множестве М, если: а) конъюнкция их тождественно истинна; б) конъюнкция их тождественно ложна; в) конъюнкция превращается в истинное высказывание при подстановке любого из элементов множества Р' истинности предиката Р(х) и только таких элементов; г) дизъюнкция их тождественно истинна; д) дизъюнкция их тождественно ложна; е) дизъюнкция превращается в ложное высказывание при подстановке любого элемента из множества Р' истинности предиката Р(х) и только таких элементов; ж) импликация их тождественно истинна; з) импликация их тождественно ложна; и) эквивалентность их тождественно ложна; к) эквивалентность их тождественно истинна; л) эквивалентность превращается в истинное высказывание при подстановке любого из элементов множества Р' истинности предиката Р(х) и только таких элементов.
Решение. л) По условию задачи [Р(х) ++ Д(х)]' = Р'(х), т.е. [(Р(х) -+ 0(х)) л (Д(х) -+ Р(х))]' = Р'(х), т.е. [(~Р(х) ~~ 0(х)) л л (Р(х)ч -» 0(х))]' = Р'(х), т.е. ( Р' ~.г Д') гь( Р' н Д') = Р'. Следовательно, Р' ~ Р' и Д+ и Р' с Р' ~г Д'. Второе включение не накладывает никаких ограничений на множества Р' и Д', а вот первое — накладывает. Поскольку Р'ф Р' инто же время Р" а Р' з о 0', поэтому Р'с 0'. 9.18.
Считая одноместный предикат Р(х) заданным на множестве М, докажите что: а) Л[(ч'х)(Р(х))] = 1 «» Р' = М; б) Л[(Эх)(Р(х))] = 1 «» Р' ~ И; в) Л[(Лх)(Р(х))] = О «» Р' = И; г) Л[(~хН-»Р(х))] = 1 <=» Р' = И; д) Л[(Бх)(-зР(х))] = 1 «» Р' ~ М; е) Л[(Зх)(-чР(х))] = О «» Р' = М; ж) Л[-з(~~х)(Р(х))] = 1 «» Р' ~ М; з) Л[-з('»х)(Р(х))] = О «» Р' = М; и) Л[-»(Зх)(Р(х))] = 1 «» Р' = И; к) Л[-ч(Зх)(Р(х))] = О «» Р' ~ И; л) Л[(~Гх)(Р(х))] = О «» Р' ~ М; м) Л[(чхН-зР(х))] = О «» Р' ~ И.
Р е ш е н и е. л) По определению квантора общности, высказывание (~х)(Р(х)) ложно тогда и только тогда, когда предикат Р(х) опровержим, т.е. когда он не на всех элементах из Мпревращается 174 в истинное высказывание. Это и означает, что не все элементы из М входят в множество истинности предиката Р(х), т.е. Р' ~ М. м) Ложность высказывания (~х)(-зР(х)) означает опровержимость предиката -зР(х), что в свою очередь на основании предыдущей задачи означает, что (-чР)' ~ М. Вспоминая, что (зР)' = = Р', получаем Р+ ~ М Это означает, что Р' ~ И (ибо в противном случае, еслибы Р'= И, то Р' = Й = М). 9.19.
Пусть Р(х) и 0(х) — такие одноместные предикаты, заданные над одним и тем же множеством М, что высказывание: а) (Зх)[Р(х) -+ (-зР(х) ~ -з(-з 0(х) -+ Р(х)))] истинно; докажите, что высказывание (~х)(Р(х)) ложно; б) (Фх)Н-зД(х) л Р(х)) -+ (Р(х) -+ 0(х))] ложно; докажите, что высказывание (Зх)(Р(х)) истинно, а высказывание (~х)(Щх)) ложно; в) (Фх)[(Д(х) -+ -чР(х)) ~ (Р(х) -+ зД(х))] ложно; докажите, что тогда каждое из высказываний (Эх)(Р(х)) и (Зх)(Д(х)) истинно; г) (Зх)[-юР(х) -+ (Д(х) л Р(х))] ложно; докажите, что тогда будет ложным высказывание (Лх)(Р(х)); д) (Нх)Щх) л (Р(х) ~ (Д(х) ++ Р(х)))] истинно; докажите, что тогда истинно и следующее высказывание (Эх)(Р(х) л Д(х)); е) ('с~х)[Р(х) ~ (0(х) -+ Р(х))] ложно; докажите, что высказывание (Ъх)(Р(х)) ложно, а (Лх)(Д(х)) истинно; ж) Ях)[Р(х) л (Р(х) ++ (0(х) ~ -~Р(х)))] истинно; доказать, что высказывание (Лх)(Р(х) л Д(х)) также тогда будет истинным; з) (Лх)[((Р(х) -+ 0(х)) ++ -чР(х)) л Р(х)] истинно; доказать, что высказывание ('с~х)(Р(х) -+ 0(х)) ложно; и) (~х)[(Р(х) -+ ((Р(х) л 0(х)) -+ -зР(х))] ложно; проверьте, что тогда высказывание (Зх)(Р(х) л 0 (х)) истинно; к) (~х)[Р(х) -+ (Р(х) л -з(фх) -+ -зР(х)))] ложно; проверьте, что тогда будет ложным и высказывание (чх)(Р(х) -+ Д(х)); л) (~х)[~Р(х) -+ (Р(х) ~~ -ю(-з Д(х) -+ Р(х)))] ложно; докажите, что первое из высказываний (Чх)(Р(х)) и (Бх)(0(х)) ложно, а второе истинно; м) (Эх)[~Р(х) л (Р(х) ч (0(х) -+ Р(х)))] истинно; проверьте, что тогда высказывание (~х)(Р(х) ч Д(х)) ложно.
Р е ш е н и е. л) Из условия по определению квантора общности следует, что Л[-зР(а) -+ (Р(а) ~ -~(-з0(а) -+ Р(а)))] = О для некоторого элемента а а М Отсюда по определению импликации, заключаем, что Л[-~Р(а)] = 1 и Л[Р(а) ч -~(-зД(а) -+ Р(а))] = О.
По определению отрицания из первого из двух последних равенств следует, что Л[Р(а)] = О, а из второго — Л[-з(-зД(а) -+ -+ Р(а))] = О, т.е. Л[-з Д(а) -+ Р(а)] = 1. Поскольку, кроме того, Л[Р(а)] = О, то из последнего соотношения по определению импликации заключаем, что Л[-з Д(а)] = О, т.е. Л[Д(а)] = 1. Итак, Л[Р(а)] = О для некоторого а е М. Следовательно, по определению квантора общности заключаем, что высказывание 175 (~'х)(Р(х)) ложно. Так как Л[Д(а)] = 1, то отсюда по определению квантора существования следует, что высказывание (3х)(0(х)) истинно.
м) Из условия по определению квантора существования следует, что Л[-зР(а) л (Р(а) ~ (Д(а) -+ Р(а)))] = 1 для некоторого предмета а а М. Отсюда по определению конъюнкции заключаем, что Л[-зР(а)] = 1 и Л[Р(а) ~ (0(а) -+ Р(а))] = 1. Тогда Л[Р(а)] = = О, и из последнего соотношения с учетом только что установленного получим Л[Д(а) — ~ Р(а)] = 1. Снова, учитывая, что Л[Р(а)] = О, из последнего соотношения заключаем: Л[0(а)] = О.
Итак, Л[Р(а)] = О и Л[0(а)] = О. Тогда по определению дизъюнкции отсюда заключаем: Л[Р(а) ~ Д(а)] = О для некоторого а е М. По определению квантора общности отсюда следует, что высказывание (чх)(Р(х) ~ Д(х)) ложно. 9.20. Какими могут быль множества Р' и 0' истинности предикатов Р(х) и Д(х) соответственно, заданных над непустым множеством М, если известно, что следующее высказывание истинно: а) (3х)(Р(х) -+ Д(х)) л (тх)(~Р(х) л 12(х)); б) (~ х)(-зР(х) -+ ~0(х)) л -з(Зх)(Р(х) л 0(х)); в) -ч(Бх)(Р(х) -+ 0(х)) л -з(Ъх)(-зР(х) л 0(х)); г) -ю('с~х)(Р(х) л 0(х)) л (Зх)(Р(х) л 0(х)); д) (Эх)(Р(х) а Д(х)) л -ч(тх)(Р(х) -+ Д(х)); е) (тх)(Р(х) л -ч(2(х)) ++ (3х)(Р(х) -+ 0(х)); ж) -з(Чх)(зР(х) л 0(х)) ++ (3х)(Р(х) ч 0(х)); з) з('о'х)(Р(х) л 0(х)) ++ (Зх)(Р(х) л 0(х)); и) (Зх)(-зР(х) -+ з0(х)) ++ з(3х)(Р(х) л Д(х)); к) (чх)(зР(х) л 0(х)) ++ -з(ЗхКР(х) -+ 0(х)); л) -з(тх)(Р(х) ~~ з0(х)) л (Зх)(Р(х) -+ 0(х)); м) ('с~х)(-зР(х) л 0(х)) ++ -ч(3х)(Р(х) -+ Д(х)).
Р е ш е н и е. л) По определению конъюнкции двух высказываний из условия следует, что Л[-з(Ъх)(Р(х) и ~ 0(х))] = 1; Л[(Зх)(Р(х) -+ Д(х))] =1. (2) Далее, из (1) по определению отрицания заключаем, что Л[(чх)(Р(х) ч -чД(х))] = О. (3) По определению квантора общности (3) означает, что предикат Р(х) ~ ~Д(х) не является тождественно истинным, т.е. что его множество истинности не есть все множество М, т.е. (Р(х) ~ ч ~ 0(х))' ~ М, т.е. Р' н 0' и М. Последнее условие, как нетрудно понять, равносильно следующему: Д' 4 Р'.
Из (2) по определению квантора существования следует, что предикат Р(х) -+ 0(х) выполним, т.е. его множество истинности 176 ц ч(Лх)(Р(х) -+ 0(х))] = 1, либо два следующих условия: Х[('Фх)(-чР(х) л Д(х))] = О, (2) (3) Х[-ю(Зх)(Р(х) -+ Д(х))] = О. (4) Из (1) следует, что предикат -~Р(х) л Д(х) тождественно истинный, т.е.
его множество истинности совпадает с М: Р+ г~ 0' = М Поскольку Р' и 0" суть части множества М, то из последнего равенства следует Р' = М (т.е. Р' = И) и Д' = М. (5) Условие (2) эквивалентно следующему: ) [(Зх)(Р(х) -+ Д(х))] = = О, откуда заключаем, что предикат Р(х) -+ Ях) тождественно ложный, т.е. его множество истинности пусто: Р' ~ Д' = И.
Следовательно, Р' = И (т.е. Р' = М) и 0' = И. (6) Сравнивая полученные условия (5) и (6), ввиду того, что М~ И, заключаем, что условия (1) и (2) не могут выполняться. Рассмотрим условия (3) и (4). Из первого следует, что предикат ~Р(х) л Д(х) опровержим, т.е. не является тождественно истинным, а значит, его множество истинности Р' л Д' ~ М. Отсюда следует, что Р' ~ М или Д'~ М (так как Р' и Д' сугь части множества М), т.е. (7) Наконец из (4) следует, что Ц(Эх)(Р(х) -+ 0(х))] = 1, т.е.
предикат Р(х) -+ 0(х) выполним, и, значит„его множество истинности не пусто: Р' н Д' ~ И. Отсюда заключаем, что Р' ~ И или 0' ~ И, т.е. (8) 177 Р' ~ М или Д' ~ И. не пусто: (Р(х) -+ 0(х))' ~ И, т.е. (-зР(х) ~ Д(х))' ~ И, или Р' ~г н 0+ ~ И. Отсюда следует, что Р' ~ И (т.е. Р' ~ М) или Д' ~ И. Итак, окончательно мы получаем, что множества Р' и Д' должны удовлетворять следующим условиям: Д+ ф Р", причем либо Р'~ М, либо Д'~ И.
м) Из условия задачи по определению эквивалентности двух высказываний заключаем, что должны выполняться либо два следующих условия: Ч(~ х)(-зР(х) л 0(х))] = 1, (1) Итак, условия (7) и (8) должны выполняться одновременно: (Р' ~ И или Д' ~ М) и (Р' ~ Мили Д' ~ И). Это условие можно записать следующим образом (воспользовавшись дистрибутивностью конъюнкции относительно дизъюнкции): Р' ~ И и Р' ~ М (т.е. И ~ Р" с М), или Д' , -И и Д' ~ М (т.е. И ~ Д с М), или Р'~ И и Д'~И, или Р'~ Ми Д'з М.
9.21. Какими могут быть множества Р' и Д' истинности предикатов Р(х) и Д(х) соответственно, заданных над непустым множеством М, если известно, что следующее высказывание ложно: а) ('ФхН~Р(х) л Д(х)) -+ (ЗхН-зР(х) -+ Д(х))); б) (чхНР(х) -+ Д(х)) л (3хН~Р(х) л Д(х)); в) (~хН-зР(х) -+ Д(х)) ч -з(3хНР(х) л Д(х)); г) -з(ЗхНР(х) л Д(х)) -+ ~('ФхНР(х) ч ~Д(х)); д) (3х) з(Р(х) ч Д(х)) ++ (чхН-чР(х) л Д(х)); е) (ЧхНР(х) ч Д(х)) л (ЗхНР(х) -+ Д(х)); ж) (чхНР(х) ++ Д(х)) ч (чхНР(х) л Д(х)); з) (чхН зР(х) л Д(х)) — э (3хНР(х) -+ -зД(х)); и) (жхНР(х) ч Д(х)) -+ (3хН-зР(х) л -юД(х)); к) (ЭхН зР(х) л Д(х)) ч -з(чхНР(х) ++ зД(х); л) (3хНР(х) л Д(х)) -+ з(ЧхНР(х) -+ Д(х)); м) (~хНР(х) ++ Д(х)) ч ЯхНД(х) л Р(х)).
Решение. л) По определению импликации двух высказываний из условия задачи следует, что Л[(3хНР(х) л Д(х))) = 1, Л(-ч(чхНР(х) -+ Д(х))) = О. (2) Далее, из (1) по задаче 9.5, в заключаем, что (Р(х) л Д(х))' ~ ~ И, т.е. Р'о Д'~ И. Из (2) по определению операции отрицания следует, что л[(вхНР(х) -+ Д(х))1 = 1, откуда, в свою очередь, в силу задачи 9.5, а следует, что (Р(х) -+ Д(х))' = М. Следовательно, Р' ~ Д' = = М.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
