В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 40
Текст из файла (страница 40)
Получаем ... в (~у)[(Р(х) -+ Д(у)) — > ('с~!)(Р(г) ч ('с~г)(Д(~)))] и ... Далее, в оставшейся в квадратных скобках формуле квантор общности по переменной г относится к заключению импликации, в то время как посылка этой импликации не имеет свободной переменной ь Тогда на основании равносильности задачи 9.49, к (полученной из теоремы 21.12, в) квантор (~й) может быть без всяких изменений вынесен за знак импликации. Получаем 196 ...
и (»уНт~)[(Р(х) -+ Ц(у)) -+ (Р(г) м (ъ~НО(х)))» и ... Остается квантор общности по переменной ~. Сначала на основании равносильности задачи 9.49, з (теорема 21.11, в) выносим его за знак дизьюнкции (второй член дизъюнкции Р (г) не зависит от г свободно): ... и (туН'сЧ)[(Р(х) -+ О(у)) -+ (ь'~НР(г) ч О(г))» и ... Наконец, как и в случае с квантором (т'г), вынесем квантор (в~) за знак импликации (равносильность из задачи 9.49, к, теорема 21.12, в): ... и (ъуНв~Н'в~)[(Р(х) -+ Д(у)) -+ (Р(!) м Д(~))». Проблемы разрешимости для общезначимости и выполнимости формул. Проблема состоит в том, чтобы уметь выяснять, будет ли данная формула логики предикатов выполнимой или она будет общезначимой.
Алгоритмического решения данная проблема не имеет, т.е. единого алгоритма, применимого ко всем формулам и неизбежно дающего ответ на рассматриваемый вопрос, не существует. 9.53. Приведите пример формулы, тождественно истинной на области из одного элемента, но необщезначимой. 9.54. Приведите пример формулы, выполнимой на области из трех элементов, но невыполнимой на области из двух элементов. Р е ш е н и е. Рассмотрим формулу (3х, у, яНВ(х, у) л Я(х, я) л Я(у, х) л (тгН-зВ(Ф, г))). Покажем, что она выполнима на области из трех элементов. Пусть М= [а, Ь, с» — множество из трех элементов. Вместо двухместной предикатной переменной Я подставим предикат неравенства: Ф (х, у)»» х и у.
Тогда рассматриваемая формула превращается в следующий конкретный 0-местный предикат (высказывание): (Зх, у, ~Н))1(х, у) л Ф(х, ~) л Ф(у, х) л (чгН~Ф(б г))), или вдругих обозначениях: (Зх, у, ~Их мул х;» глу»» гл (ы1Н1= г)). Чтобы убедиться в том, что данный предикат выполним на М, т.е. что это высказывание истинно, нужно увидеть, что трехместный предикат от предметных переменных х, у, я х и у л х и ~ л у и е г л (~гН~ = г) выполним на М. Это действительно так.
Достаточно взятьх= а, у=Ь, ~= с. Покажем теперь, что рассматриваемая формула тождественно ложна на всякой области из двух элементов. Пусть М = [а, ܻ— произвольное двухэлементное множество. Выполнимость рассматриваемой формулы на М означает наличие такого конкретного предиката В(х, у), заданного на М что высказывание (Эх, у, гНВ(х, у) л л В(х, ~) л В(у, х) л (т'гН-зВ(с, г))) истинно. Истинность этого 197 высказывания, в свою очередь, означает, что найдутся три таких элемента Р„т~, т, а (а, Ь), что высказывание В(г„тт) л В(г„т,) л л В(т1, Г) л (~'т) (-тВ(б т)) истинно. Так как элементов Р„т1, т, три, а в множестве (а, Ь) лишь два различных элемента, то два из элементов ц, тт, Г, совпадут.
Пусть г, = т1 = а, Г, = Ь. Тогда истинно следующее высказывание: В(а, а) л В(а, Ь) л В(а, Ь) л ('ФгН-тВ(б г)), откуда следует, что истинны высказывания В(а, а) и (ттгН~В(б г)). Истинность последнего высказывания означает, что истинны оба высказывания ~В(а, а) и -тВ(Ь, Ь). Итак, мы показали, что высказывание В(а, а) и его отрицание тВ(а, а) истинны одновременно. Это противоречие. Следовательно, данная формула невыполнима на двухэлементном множестве. 9.55. Приведите пример формулы, выполнимой на области из четырех элементов, но невыполнимой на области из трех элементов.
9.56. Докажите, что каждая из двух следующих формул а) (чхНЗуН'Ф~НЯ(х, х) л -тЯ(у, х) л (Я(у, ~) -+ Я(х, ~))); б) (тгхН5уНУ[х, у)) л (ЧхНчГ(х, х)) л (т~хН~уНт1~)[(Г(х, у) л л г1у, ~)) -+ г1х, ~)1 выполнима на бесконечной области и невыполнима ни на какой конечной области. Р е ш е н и е. а) Эта замкнутая формула превращается в истинное высказывание, если вместо предикатной переменной Я(х, у) подставить двуместный предикат «х > у», заданный над У: ('О'ХНЗу)('Ф2) [х > х л х ) у л (у > ~ -Ф х > ~)1. Это означает, что формула выполнима на бесконечной области. Покажем, что допущение выполнимости этой формулы в конечном множестве приводит к противоречию.
Допустим, что А(х, у) — такой предикат, заданный на конечном множестве М, что высказывание (чхНЛуНтт~)[А(х, х) л -тА(у, х) л (А(у, ~) -+ А(х, х))1 истинно. На основании правил пронесения кванторов через конъюнкцию (теорема 21.11, а, г или задача 9.49, д, е) данное высказывание можно представить в виде (ттх)(А(х, х)) л л (ттхНЗу)[~А(у, х) л (»'~НА(у, ~) -+ А(х, ~))1. Следовательно, истинны высказывания (ттх)А(х, х)) и ('»'хну)[~А(у, х) л (т~«НА(у, «) -+ -+ А(х, г))).
Из истинности второго высказывания следует существование в М такой последовательности элементов а„а„а„..., что истинно каждое высказывание -тА(ат „, а~Ну = 1, 2, ...). Но в силу предположения конечности множества М найдутся такие! и Ь (Ь > т), что а; = аь Тогда из истинности первого высказывания (ттхНА(х, х)) следует истинность высказывания А(аь, ат). Возьмем теперь во втором высказывании х = аг ь Для него найдется такой у = аы то будут истинны высказывания ~А(аг,, а») и (~~НА(ам х) -+А(а«ь ~). Следовательно, истинно высказывание 198 А(аг» а;) -+ А(а„п а;), а значит, истинно и высказывание А(а« „а;). Беря теперь х = а«з, мы аналогично придем к истинности высказывания А(а«п а,) и т.д., и наконец — к истинности высказывания А(а; „, а;) (поскольку /с > 1). Но это противоречит истинности его отрицания ~А(аг «и а;), установленной выше.
9.57. Покажите, что формула (Зх)(~у)(Я(х, у) -+ (-1Я(у, х) -+ -+ (Я(х, х) ++ Я(у, у)))) тождественно истинна в области из трех элементов н не является тождественно истинной в области из четырех элементов. 9.58. Покажите, что формула (»'х, у, ~)(Я(х, х) и (Я(х, ~) -+ -+ (Я(х, у) «Я(у, ~)))) -+ (Зх)(ЧУ)(Я(х, у)) тождественно истинна на конечной области и не является таковой на бесконечной области. Р е ш е н и е. Во-первых, отметим, что предикат «х < у», заданный на бесконечном множестве У, превращает данную формулу в ложное высказывание: ('Фх, у, ~Ях < х и (х < ~ — » (х < у ~ у < ~))1 -» -+ (Зх)(~у)(х < у), ибо посылка этой импликации истинна, а следствие ложно.
Во-вторых, докажем, что данная формула тождественно истинна на любом конечном множестве. Доказательство будем вести индукцией по числу элементов в множестве. Если М = (а„а2), то истинным будут утверждения Я(а„а,), Я(ап аз) и Я(а„а,) -+ (Я(аь аз) «Я(ап а,)), а значит, и дизъюнкция Я(аь а2) ч Я(ап а,). Если при этом истинно Я(а„а,), то истинно (Чу)(Я(ап у)), т.е. истинно заключение (Зх)('Фу)(Я(х, у)) импликации данной формулы и вся данная формула. Аналогично, если истинно Я(а„а,), то истинно (~у)(Я(а„у)) и снова истинна вся данная формула. Предположим теперь, что данная формула тождественно истинна на всяком конечном множестве, содержащем не больше чем и элементов. Покажем тогда, что она будет тождественно истинна и на любом (и + 1)-элементном множестве. Пусть М = (а„..., а„, а„,1).
В силу тождественной истинности данной формулы на и-элементном подмножестве М' = (а„..., а„) и предположения истинности на М' посылки данной формулы имеем истинные высказывания: (Чх)(Я(х, х)) и (Чх)(Я(х, х) -+ -+ (~~у)(Я(х, у) ~ Я(у, х))). Тогда истинно заключение (Зх)(чу) (Я(х, у)).
Не нарушая общности, можно считать, что таким х будет элемент аь т.е. (~гу)(Я(ап у)), т.е. истинны все утверждения Я(ап а,), ..., Я(а„а„). Мы хотим доказать, что данная формула истинна на (и + 1)- элементном множестве М = (а„..., а„, а„,1). Для этого нужно показать, что на нем в предположении истинности посылки данной формулы верно ее заключение (Зх)(еу)(Я(х, у)). Если верно Я(ап а„„), то угверждение доказано. Если же Я(а„а„„) не верно, то, в силу истинности дизъюнкции Я(а„а„„) ~ Я(а„„, а,), заключаем, что истинно Я(а„„, а,).
199 Далее, в силу истинности в М посылки (Чх, у, е)(Я(х, я) -+ -+ (Я(х, у) ~ Я(у, е))) и утверждений Я(аь аг), ..., Я(аь а„), приходим к истинности всех следующих дизъюнкций: Я(а„а„,,) ~ ~ Я(а„, и аз), ..., Я(аь а„„) ч Я(а„,о а„). Поскольку первый член каждой дизъюнкции ложен, то истинны все вторые члены Я(а„, и а,), ..., Я(а„,ь а„). Учитывая еще и истинность Я(а„, и а,) и, кроме того, Я(а„,ь а„„), приходим к истинности утверждения (Ъу)(Я(а„, и у)) на М. Это означает истинность на Мзаключения данной формулы (Зх)(~Гу)(Я(х, у)) и всей данной формулы.
9.59. Относительно каждой из следующих формул: а) (Эх)(Р(х)) -+ (~Ух)(Р(х)); б) (Зх)(Чу)(Р(х, у)) ++ (чу)(Эх)(Р(х, у)) докажите, что если она тождественно истинна в некоторой области, то эта область состоит из одного элемента. 9.60. Покажите, что формула (('Фх)(Я(х, х)) л (Эу)(~х)(Я(х, у))) -+ -+ (Зх)(чу)(Я(х, у)) тождественно истинна на всяком не более чем двухэлементном множестве, но тавтологией не является. 9.61. Пусть формула логики предикатов общезначима.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
