В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 41
Текст из файла (страница 41)
Если уничтожить все кванторы и рассматривать оставшуюся часть как формулу алгебры высказываний, то будет ли она всегда тождественно истинной? Верно ли обратное утверждение? 9.62. Докажите, что если формула алгебры предикатов выполнима на области М, то она выполнима и на всякой области М', содержащей в себе М. 9.63. Докажите, что ~-формула, в которую входят п различных предметных переменных, общезначима (является тавтологией) тогда и только тогда, когда она тождественно истинна на л-элементном множестве.
9.64. Докажите, что З-формула общезначима (является тавтологией) тогда и только тогда, когда она тождественно истинна на одноэлементном множестве. Логическое следование формул логики предикатов. Понятие логического следования для формул логики предикатов соответствует понятию логического следования для формул алгебры высказываний. Формула С логики предикатов называется логическим следствием формулы Г, если при всякой интерпретации, при которой Г превращается в тождественно истинный предикат, формула 6 также превращается в тождественно истинный предикат.
Запись: Г ~ 6. Как и в алгебре высказываний, Г~= 6 ~~ ~ Г-+ 6. Также две формулы равносильны тогда и только тогда, когда каждая из них является логическим следствием другой. 9.65. Докажите, что в логике предикатов справедливы следующие логические следования: а) (Зу)(чх)(Г(х, у)) ~= (Чх)(Зу)(Г(х, у)); б) (чх)(Г(х)) ~= (Зх)(Г(х)); в) (Зх)(Р(х) л О(х)) ~ (Эх)(Р(х)) л (Зх)(Ц(х)); 200 г) (ФхНР(х)) ч ('ФхНО(х)) ~= ('ФхНР(х) ч Д(х)); д) (ЭхНР(х)) -+ (тх)Я(х)) ~= (чхНР(х) -+ Д(х)); е) (тхНР(х) -+ Д(х)) ~= (чхНР(х)) -+ (ЪхНО(х)); ж) (тхНР(х) -+ Д(х)) ~= (Лх,'(Р(х)) -+ (ЛхНД(х)).
Выясните, верны ли обратные логические следования. 9.66. Докажите, что в логике предикатов справедливы следующие логические следования: а) ('ФхНУ1х)) ~= Г(у) — правило удаления квантора общности (или правило универсальной конкретизации); б) Г(у) ~= (ЛхНГ(х)) — правило введения квантора существования (или правило экзистенциального обобщения).
Эти правила можно представить также в следующих видах: Г ~=Г(х) Г, Г(х) ~=6 Г ~=('ФхНГ(х)) Г, (ЗхНГ(х)) ~6 при условии, что ни в одну формулу из совокупности Г и в формулу 6 предметная переменная х не входит свободно. Решение. а) Обоснуем первое из этих правил. По условию, Г ~ Г(х), т.е. формула Г(х) превращается в тождественно истинный предикат при всякой такой интерпретации, при которой в тождественно истинные предикаты превращаются все формулы из совокупности Г.
Пусть мы имеем такую интерпретацию и при ней формула Г(х) превращается в тождественно истинный предикат Го(х, у„..., у„) от переменных х, у„..., у„. Тогда, по определению квантора общности, предикат ('ФхНГО(х, у„..., у„)) от переменных у„..., у„также будет тождественно истинным. Это и означает, что Г ~= ('ФхНГ(х)).
9.67. Выясните, будут ли выполняться в логике предикатов следую|цие логические следования: а) 0(у) -+ Р(х) ~ 0(у) -+ ('ФхНР(х)); б) Д(у) -+ (~хНР(х)) ~= Д(у) -+ Р(х); в) Р(х) -+ Д(у) ~ (ЛхНР(х)) -+ Д(у); г) (ЛхНР(х)) -+ 0(у) Ф= Р(х) -+ О(у)," д) Р(х) -+ Д(у) ~= (~хНР(х)) -+ Д(у); е) ('ФхНР(х)) -+ Д(у) ~ Р(х) -+ Д(у); ж) (БхНР(х, х)) ~ Ях)ЯуНР(х, у)); з) ('ФхНР(х) ++ Д(х)) ~= (тхНР(х) -+ Ц(х)); и) (ЛхНЯ(х) л ~Р(х)) ~ (чхНР(х) л ~Я(х)); к) (ЗхНХ(х) л Р(х)) ~= ЯхНЯ(х) ч Р(х)); л) ('о'хНЯ(х) -+ -1Р(х)) ~= (ЗхНР(х) л -тЯ(х)); м) (тхНР(х) ++ Д(х)) ~ (ЗхНЦ(х) -+ Р(х)). Решение. л) Предположим, что найдутся такие конкретные предикаты А(х) и В(х), заданные над конкретным множеством М, что Ц(тхНВ(х) -+ -зА(х))] = 1 (1)„а Ц(лхНА(х) л ~В(х))1 = 0 (2). Из (1) по определению квантора общности следует, что 201 Л[В(а) -+ ~А(а))] = 1 (3) для любого предмета а я М. Из (2) по определению квантора существования следует, что Л[А(Ь) л л -чВ(Ь))] = 0 (4) для некоторого предмета Ь е М.
Отсюда видно, что если предикаты А(х) и В(х) взять такими, что Л [В(х)] = О, если х е М ~(Ь] (ЦА(Ь)] = 0 и ЦА(х)] произвольно, если х ~ Ь), то противоречия не получится, соотношения (3) и (4) будут выполняться, вместе с ними будут выполняться соотношения (1) и (2), которые и будут говорить о том, что рассматриваемое следование неверно. м) Допустим, что найдутся такие конкретные предикаты А(х) и В(х), которые заданы над конкретным множеством М, что Л[(тх) (А(х) ++ В(х))] = 1 (1), а Л[(Зх)(А(х) -+ В(х))] = 0 (2). Из (1) по определению квантора общности следует, что Л[А(а) +~ ++ В(а))] = 1 (3) для любого предмета а е М.
Из (2) по определению квантора существования следует, что Л[А(Ь) -+ В(Ь)] = 0 (4) для некоторого предмета Ь е М. Тогда из (4) следует, что Л[А(Ь)] = 1, а Л[В(Ь)] = О. Два последних соотношения противоречат соотношению (3). Значит, сделанное допущение неверно и рассматриваемое следование справедливо. 9.68. Выясните, будут ли выполняться в логике предикатов следующие логические следования, выражающие на языке логики предикатов соответствующие законы аристотелевой силлогистики: а) (тх)(Я(х) -+ Р(х)) ~ (Бх)(Ю(х) л Р(х)) (1-й закон подчинения); б) (Зх)(Я(х) л Р(х)) с= (Бх)(Р(х) л Я(х)) (закон 1-обращения); в) (~!х)(Я(х) -+ Р(х)) ~= (Зх)(Р(х) л Я(х)) (закон а-обращения); г) (Чх)(Я(х) -э -зР(х)) ~= (Зх)(Ю(х) л -чР(х)) (2-й закон подчинения); д) (тх)(Я(х) -+ ~Р(х)) ~= ( т'х)(Р(х) -+ -зЯ(х)) (закон е-обращения).
9.69. Докажите, что в логике предикатов выполняются следующие логические следования, выражающие на языке логики предикатов пятнадцать правильных аристотелевых силлогизмов: а) (тх)(М(х) -+ Р(х)) л (Ъх)(Я(х) -+ М(х)) ~= (Ъх)(Я(х) -+ -+ Р(х)) (фигура 1, модус ВагЬага); б) ('Фх)(М(х) -+ чР(х)) л (Чх)(Я(х) -+ М(х)) ~= (~!х)(5(х) -+ -+ -чР(х)) (фигура 1, модус Се!агел!); в) (тх)(М(х) -+ Р(х)) л(Зх)(Я(х) л М(х)) ~= (Бх)(Я(х) л Р(х)) (фигура 1, модус Рат)' г) (тх)(М(х) -+ ~Р(х)) л (Зх)(Я(х) л М(х)) ~= (Бх)(Ю(х) л л ~Р(х)) (фигура 1, модус Гегго) д) (~!х)(Р(х) -+ М(х)) л (Зх)(Я(х) л -зМ(х)) ~ (Зх)(Я(х) л л ~Р(х)) (фигура 11, модус Ваго/со); 202 е) (ЧхНР(х) -+ ~М(х)) л (тхНХ(х) -+ М(х)) ~= ('ФхНВ(х) -+ -+ -|Р(х)) (фигура 11, модус Сезаге); ж) (тхНР(х) — э М(х)) л (~хНЮ(х) -+ ~М(х)) ~= (~гхНЮ(х) -+ -+ ~Р(х)) (фигура 11, модус Сатезггез); з) (тхНР(х) -+ -1М(х)) л (ЗхНЯ(х) л М(х)) ~= (БхНЯ(х) л л ~Р(х)) (фигура Н, модус Резйпо); и) (ЧхНМ(х) -+ Р(х)) л (ЛхНМ(х) л Я(х)) ~ (ЛхНЯ(х) л Р(х)) (фигура 111, модус 2)акЕл); к) (ЗхНМ(х) л -1Р(х)) л ('с'хНМ(х) -+ Я(х)) ~ (3хНЮ(х) л л ~Р(х)) (фигура !11, модус Во3сагйо)' л) (БхНМ(х) л Р(х)) л (~~хНМ(х) -+ Я(х)) ~= (3хНЯ(х) л Р(х)) (фигура 111, модус 1)1зати); м) ('ФхНМ(х) -+ ~Р(х)) л (ЛхНМ(х) л В(х)) ~ (ЗхНЮ(х) л л -1Р(х)) (фигура 111, модус Репюп); н) (ЗхНР(х) л М(х)) л (ЪхНМ(х) -+ Я(х)) ~= (ЗхНЯ(х) л Р(х)) (фигура %, модус Рптапз) о) (х'хНР(х) -+ М(х)) л (17хНМ(х) -+ -зя(х)) ~= (чхНВ(х) -+ -+ ~Р(х)) (фигура 1У, модус Сатепез); п) ('о'хНР(х) -+ -1М(х)) л (ЗхНМ(х) л В(х)) ~= (лхНЯ(х) л л ~Р(х)) (фигура 1У, модус Ргеизоп).
Р е ш е н и е. н) Допустим, что данное следование не выполняется. Это означает, что существуют такие конкретные предикаты А(х), В(х), С(х), заданные над конкретным множеством М, что ХНЗхНС(х) л В(х))] = 1, ХН'ФхНВ(х) -+ А(х))] = 1, а л[(ЗхНА(х) л л С(х))] = О. Тогда из первого соотношения получаем, что для некоторого аа е М ЦС(ае) л В(ае)] = 1 (1), а из второго и третьего — л[В(а) -+ А(а)] = 1, ЦА(а) л С(а)] = 0 для любого а е М (в частности, для а = а,: ЦВ(ае) -+ А(ае)] = 1 (2), 1[А(ае) л л С(ае)] =0 (3)).
Из (1) заключаем ЦС(ае)] = 1 (4) и ЦВ(ае)] = 1 (5). Наконец, из (2) и (5) следует, что Х[А(ае)] = 1, а из (3) и (4) следует, что л[А (ао)] = О. Два последних соотношения противоречат друг другу. Это и означает, что сделанное допущение неверно и данное следование выполняется. 9.70. Докажите, что в логике предикатов следующие логические следования не выполняются (хотя они выражают на языке логики предикатов еще четыре правильных аристотелевых силлогизма): а) (('ФхНМ(х) -+ Р(х)) л (тхНМ(х) -+ В(х))) -+ (ЗхНЯ(х) л л Р(х)) (фигура 111, модус Эагаргу) б) (~хНМ(х) -+ -1Р(х)) л (пхНМ(х) -+ Я(х)) ~ (ЛхНЯ(х) л л -зР(х)) (фигура Н1, модус Ре1арюоп); в) (тхНР(х) -+ М(х)) л (тхНМ(х) -+ Я(х)) ~= (ЛхНЯх) л Р(х)) (фигура ТУ, модус Вгатаппр); г) (тхНР(х) -+ ~М(х)) л (ЪхНМ(х) -+ Я(х)) ~ (ЗхНЯ(х) л л -|Р(х)) (фигура %, модус пезаро).
203 Решение. а) Покажем, что данное логическое следование не выполняется. Для этого нужно указать такие конкретные предикаты А(х), В(х), С(х), заданные над некоторым множеством М, что посылка силлогизма превратится в истинное высказывание («х)(В(х) -+ С(х)) л (~х)(В(х) -+ А(х)), а следствие — в ложное (Лх)(А(х) л С(х)). Для этого достаточно, чтобы предикат В(х) был тождественно ложен, а предикаты А(х) и С(х) обладали бы тем свойством, что для любого предмета а е Модно из высказываний А(а) или С(а) было бы ложным. Последнее возможно, если, например, один из предикатов А(х) или С(х) является отрицанием другого.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
