В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 39
Текст из файла (страница 39)
Последнее означает тождественную ложность предиката А(х). В частности, для предмета а е М имеем Л[А(а)] = О, что противоречит первому из соотношений (8). Итак, в каждом случае приходим к противоречию, доказывающему невозможность сделанного предположения. Следовательно, данная формула — тавтология. м) Предположим, что формула не является тавтологией. Тогда существуют такие предикаты А(х) и В(х), определенные на мно'жестве М, что высказывание (~хКА(х)) -+ (~хКА(х) ч В(х)) ложно. Импликация ложна, если и только если Л[(чх)(А(х))] = 1 (1) и Л[('Фх)(А(х) ч В(х))] = О (2). Из (2) по определению квантора общности следует, что предикат А(х) ч В(х) опровержим, т.е.
найдется 192 такой предмет а е М, для которого Х[А(а) ~ В(а)] = О, т.е. Х [А(а)] = = О и Х[В(а)] = О. Но утверждение ЦА(а)] = О противоречит (1), так как из него по определению квантора общности вытекает, что предикат А(х) тождественно истинный, т.е. ни при каком а а М не превращается в ложное высказывание. 9.44.
Докажите, что следующие формулы являются тавтологиями логики предикатов: а) (ФхКР(х)) -+ Р(у); б) Р(у) -+ (ЗхНР(х)); в) (~ФхКР(х)) -+ (Зх)(Р(х)); г) (ЗхКР(у) -+ Р(х)); д) (Фх)(ЧУ)(Р(х, у)) -э ('ФхКР(х, х)); е) (ЗхКР(х, х)) -+ (ЗхКЗУКР(х, у)); ж) ('ФхК'ФУКД(х, у)) ++ (ФУКЧхКД(х, у)); з) (ЗхКЗУКД(х, у)) ++ (ЗУКЗхКД(х, у)); и) ('ФхКзяКГ(х, у) ч ~Г(г, у)); к) (чхКзуК'Ф1К(Р(х) л 3Р(у)) — + Д(я)); л) (ЗУК'ФхКР(х, у)) -+ (ФхКЗУКР(х, у)).
Р е ш е н и е. л) Предположим, что эта формула не является тавтологией. Тогда существует такой предикат А(х, у), определенный на множествах М~ и Мп что высказывание (Зу)(ФхКА(х, у)) — ~ -+ (ФхКЗУ) (А(х, у)) ложно. Импликация ложна, если и только если Л[(ЗУ) (~Фх)(А(х, у))] = 1 (1), Х[(ъ'хКЗУКА(х, у))] = О (2).
Из (1) по определению квантора существования следует, что предикат (от у) (Фх) (А(х, у)) выполним, т.е. Л[(ФхКА (х, Ь))] = 1 для некоторого Ь а М,. Последнее по определению квантора общности означает, что предикат А (х, Ь) тождественно истинен на М,. Следовательно, тождественно истинным на М, будет и одноместный (от х) предикат (ЗУКА (х, у)). Ио тогда по определению квантора общности Х[('ФхКЗУКА(х, у))] = 1, что цротиворечит соотношению (2). Следовательно, данная формула — тавтология. 9.45. Являются ли тавтологиями следующие формулы логики предикатов: а) (ЗхКР(х)) -+ (ФхКР(х)); б) ~((ЗхКР(х)) -+ (ФхКР(х))); в) (ЗхК'ФУКД(х, у)) -+ ('ФУКЗхКД(х, у)); г) (чхКзуКД(х, у)) -+ (ЗУКчхКД(х, у)); д) ('ФхКР(х) -+ Д(х)) -+ [(ФхКР(х)) -+ (ФхКД(х))]; е) (ФхКР(х) -+ Д(х)) -+ [(ЗхКР(х)) -+ (ЗхКД(х))]; ж) (ЗхКР(х) -+ Д(х)) -э [(ЗхКР(х)) -+ (Зх)Д(х))]; з) (ЗхКР(х) -+ Д(х)) -+ [(ФхКР(х)) -+ (ЗхКД(х))]; и) (ЗхКЗУК(Р(х) л Р(у)) ч (-зР(х) л .зР(у))); к) (ЗхКФУКР(у) -+ Д(х, у)); л) (ФхКР(х) -+ Д(х)) ++ [(ЗхКР(х)) -+ ('ФхКД(х))]? Р е ш е н и е.
л) Увидим, что эта формула не является тавтологией. Для этого в качестве области, над которой будем рассматри- 7 агоаии 193 вать предикаты Р(х) и Д(х), возьмем множество натуральных чисел, а предикаты выберем следующие: Р(х) «х делится на 4», Д(х): «х четно». Тогда ясно, что из утверждения о том, что все числа, делящиеся на 4, четны, вовсе не следует, что если существует число, делящееся на 4, то все натуральные числа четны. Следовательно, данная формула не тождественно истинна.
9.46. Покажите, что: а) все тавтологии алгебры высказываний являются тавтологиями логики предикатов; б) правило модус поненс (МР) остается правилом для получения тавтологий и в логике предикатов; в) правило подстановки остается правилом получения тавтологий и в логике предикатов. 9.47. Докажите, что: а) если ~= (Ъ'х)(Г(х)), то ~= Г(х); б) если ~ 6 — э Г(х), то в= 6 -+ (чх)(Г(х)); в) если с= Г(х) -+ 6, то ~ (Лх)(Г(х)) -+ 6; г) если ~= Г(х) -+ Н(х), то ~= (чх)((Г(х)) -+ (чх)(Н(х)); д) если ~ Г(х) — э Н(х), то ь= (Лх)((Г(х)) -+ (Лх)(Н(х)); е) если ~= Г(х) «» Н(х) то ~ (чх)((Г(х)) ++ ('»х)(Н(х)); ж) если ~ Г(х) «+ Н(х), то ~= (Лх)(Г(х)) «+ (Лх)(Н(х)); з) если формула Г(х) содержит свободно лишь переменную х и в= Г(х), то ~= (Зх)(Г(х)); и) если ~ Г(х), то ~= (~хКГ(х)), где формула 6 не содержит свободных вхождений переменной х.
Решение. и) Дано: ~ Г(х). Это означает, что если в формулу логики предикатов Г(х) вместо всех входящих в нее предикатных переменных подставить конкретные предикаты, то формула превратится в тождественно истинный предикат А(х, у, ..., ~), зависящий не только от переменной х, но и, возможно, от каких-то еще переменных у, ..., ~. (Заметим, что исходная формула Г(х) может содержать и различные кванторы по каким-то переменным и, и, ..., и, стоящим в разных ее местах.) Обратимся теперь к формуле (чх)(Г(х)). Подставив в нее вместо всех входящих в нее предикатных переменных конкретные предикаты, мы также превратим ее в конкретный предикат ('Фх) (А(х, у, ..., 4)), который уже не будет зависеть от переменной х, но, возможно, будет зависеть от переменных у, ..., ~.
По определению операции взятия квантора общности предикат ('Фх)(А(х, у, ..., л)) таков, что для любых предметов Ь, ..., с из областей задания высказывание ('Фх)(А(х, Ь, ..., с)) будет истинным, если предикат (отх) А(х, Ь, ..., с) тождественно истинный. Согласно условию ~ Г(х), как мы выяснили вначале, так оно и есть. Значит, высказывание ('Фх)(А(х, Ь, ..., с)) будет истинным для любых предметов Ь, ..., с. Но зто и означает, что предикат (от у, ..., к) ('Фх)(А(х, у, ..., ~)) будет тождественно истинным. Это, в свою очередь, означает, что формула (~х)(Г(х)) есть тавтология логики предикатов.
194 Равносильные преобразования формул. Переход от формулы к равносильной ей формуле называется равносильным преобразованием исходной формулы. 9А8. Докажите, что формулы логики предикатов Ги Нравносильны тогда и только тогда, когда формула Г++ Н является тавтологией. 9.49. Докажите, что справедливы следующие равносильности (формула Н не содержит х свободно): а) -1(ЭхКР(х)) и (чхК-зР(х)); б) -з('ФхКР(х)) и (БхК-1Р(х)); в) ('ФхКР(х) л Д(х)) = (ЪхКР(х)) л ('ФхКД(х)); г) (БхКР(х) ~ Д(х)) и (ЭхКР(х)) ч (БхКД(х)); д) Н л (ЭхКР(х)) и (БхКН л Р(х)); е) Н л ('ФхКР(х)) и ('ех)(Н л Р(х)); ж) Нч (ЭхКР(х)) и (ЭхКН ч Р(х)); з) Н~ (вхКР(х)) и (мх)(Нч Р(х)); и) Н -+ (БхКР(х)) н (БхКН -+ Р(х)); к) Н-+ (~гхКР(х)) и (мх)(Н-+ Р(х)); л) (ЭхКР(х)) -+ Н и (чхКР(х) -+ Н); м) (чхКР(х)) -+ Н' и (БхКР(х) -+ Н). 9.50.
Подобрав интерпретацию, покажите, что если формула Н содержит свободные вхождения переменной х, то равносильности д) — м), кроме е), ж), задачи 9.49 не выполняются. 9.51. Для следующих формул логики предикатов найдите равносильную им приведенную форму, т.е. такую форму, в которой из операций алгебры высказываний имеются только операции -1, л, ~, а знаки отрицания относятся только к предикатным переменным и к высказываниям: а) (ЭхКР(х) -+ (ЧУКД(у))); б) з((чхКР(х)) -э (БУКД(у))); в) (вхКР(х)) -+ -з(Д(у) -э (ч~КЯ(~))) г) ((ЭхКР(х) -+ (чуКД(у))) -+ Я(~); д) -з((вхКР(х) -+ Д(х)) л (БУКСУЯ(у) л Я(~))); е) з(('ФхКЭУК(Р(х) -+ Р(у)) л (Р(у) -+ Р(х)))); ж) -з(чхКР(х, у) -+ (БУКД(у))); з) (ЭхК(ЧУКР(у)) -+ Д(х)) л ~('ФУКЭхКД(х) -+ Р(у)); и) -ю(ЭУКР(у) ++ (чхКД(х))); к) з(ЧхКЭУКЧ~КР(х, у, а) -+ (ЭгКД(х, !) л Д(у, 1) л Д(~, г))); л) ~(('чхКР(х)) ч (ЭхКД(х) — э Я(х))).
Р е ш е н и е. л) Используя равносильности алгебры высказываний и логики предикатов, преобразуем равносильным образом эту формулу: ~((чхКР(х) ч (БхКД(х) -+ Я(х))) и ~(('ФхКР(х)) л л -1(БхКД(х) -+ Я(х)) и (ЭхК~Р(х)) л (чх)~(-юД(х) ъ А(х)) и =- (Бх) (~Р(х)) л ('ч'хКД(х) л ~Я(х)). 9.52. Применяя равносильные преобразования, приведите следующие формулы к предваренной (пренексной) нормальной фор- 195 ме„т.е. к форме вида (О,х,) ... (Д„х„)(Г(хь ..., х )), где в ( л, каждый Я есть один из кванторов Ч или Л и формула Р(х„..., х„) не содержит кванторов: а) ('ох)(Р(х) -+ О(х)) -э ((Лх)(Р(х)) -+ (Зу)(о(у))); б) (~х)(Р(х)) -+ ('Фх)(Д(х)); В) ('Фх)(0(х~ у))" ((~х)(0(х» х)) -+ (Ъ'г)Щ~, е) -+ (зх)(0(х~ х))))' г) (ъу)(Д(у, ~) — э (Лх)(Я(х, г, я)); д) (Ъ'у)(о(х, у)) -+ Я(х, х); е) Р(у) -+ ~((Ъ'х)(о(х, у)) -+ Р(у); ж) (Зх)(Я(х, у, г)) — э -з(~х)(Д(х, у)); з) ((Зх)(Р(х)) ~ (~7х)(фх))) л (5(у) -+ (Ъх)(Я(х))); и) ('4х)(Р(х, у)) ч ((Эх)(Р(х, х)) -+ ('Фе)(-з(о(у, ~) -+ (Эх)(Р(х, 2))))); к) (Р(,у) л Д(х)) -+ 3('Фу)(А(у, я)); л) (Чх)(Лу)(Р(х, у)) -+ (Лг)('Фх)(Д(х, я)); м) (Лу)((Р(х) -+ О(у)) -+ (Фу)((Р(у) ч ('Ф~)(Ц(г))).
Р е ш е н и е. м) Данная формула представляет собой импликацию двух подформул, в каждой из которых имеется квантор по переменной у, так что и в первой подформуле, и во второй подформуле переменная у оказывается связанной. Это означает, что переменная у в первой подформуле и переменная у во второй подформуле никак не связаны между собой. Кроме того, в силу их связанности кванторами каждая из них может быть обозначена любой другой буквой.
Это обозначение не имеет значения для данной формулы, но имеет исключительно важное значение для ее равносильного преобразования, начинающегося с процесса вынесения кванторов (Зу) и (~гу) за знак импликации. Итак, начнем с того, что переменную у во второй подформуле данной формулы обозначим буквой и (Лу)((Р(х) -+ Д(у)) -+ (~ту)((Р(у) ~ (Ч~)((2(~))) = и (Эу)(Р(х) -+ Ц(у)) -+ (Мг)(Р(г) ч ('с~г)(Д(г))) и ... Теперь мы видим, что квантор существования по переменной у применяется к посылке импликации, в то время как следствие импликации не имеет свободной переменной у. Тогда на основании равносильности задачи 9.49, л (полученной из теоремы 21.12, а Учебника) квантор (Лу) может быть вынесен за знак импликации, но при этом он должен поменяться на квантор (чу).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
