В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 38
Текст из файла (страница 38)
Возьмем любой а я М. Тогда высказывание В(а) = -зА(а) л (чу)(А(у)) истинно, как мы только что установили. Следовательно, истинны высказывания -зА(а) и (чу)(А(у)). Из истинности второго высказывания заключаем, что высказывание А(а) истинно. Это противоречит истинности первого высказывания зА(а). Равносильность формул логики предикатов. Две формулы логики предикатов Г и Нс одноименными предикатными переменными назывит равносильными, если при всякой подстановке вместо предикатных переменных любых конкретных предикатов, заданных над одними и теми же множествами, эти формулы превращаются в равносильные предикаты. Обозначение равносильных формул: У=в Н.
9.36. Докажите, что формулы в каждой из следующих пар равносильны между собой на одноэлементном множестве: 188 а) -з('ФхНР(х)) и (~хН-зР(х)); б) -1(ЭхНР(х)) и (ЭхН-1Р(х)); в) (~гхНР(х) -+ Р(у)) и (~гх)(Р(х)) -+ Р(у); г) (ЭхНР(у) -+ Р(х)) и Р(у) -+ (~хНР(х)); д) (ЭхНР(х) -+ Р(у)) и (ЭхНР(х)) -+ Р(у); е) ('ФхНР(х) -+ Р(у)) и Р(у) -+ (ЭхНР(х)); ж) (ЭхНР(х) л(Д(х)) и (ЭхНР(х)) л (ЭхНД(х)); з) (чхНР(х)ч(Д(х)) и ('ФхНР(х)) ч(чхНД(х)); и) ('ФхНЭуНГ(х, у)) и (ЭуН~гхНГ(х, у)); к) (ЪхНЭуНГ(х, у) л б(х, у)) и ('Фх) НЭуНГ(х, у)) л (ЭуН 6(х, у))]; л) (тхНР(х)-+ Ц(х)) и (чхНР(х)) -+ (тхНО(х)).
Р е ш е н и е. На одноэлементном множестве (а) существуют лишь два одноместных предиката А0(х) и А,(х), характеризующихся тем, что Л(Аа(а)) = О, Х (А~(а)) = 1. в) Данные формулы открытые: в них имеется свободная предметная переменная у.
Составим таблицу значений для этих формул: Для первой формулы в первой строке получаем высказывание (тхНА0(х) -+ А0(а)), которое истинно, поскольку предикат А,(х) -+ -э А0(а) тождественно истинен на одноэлементном множестве (а]. Во второй строке получим высказывание ('ФхНА,(х) -+ А,(а)), которое также истинно. Для второй формулы сначала вычисляем столбец (чхНР(х)). В первой его строке получаем высказывание (тхНА0(х)), которое ложно, поскольку предикат А0(х) опровержим.
Во второй строке получаем истинное высказывание (т~хНА,(х)), поскольку предикат А,(х) тождественно истинен. Затем вычисляем столбец Р(у): Х(А0(а)) = О (1-я строка), Х(А,(а)) = 1 (2-я строка). Наконец вычисляем столбец значений самой формулы как импликацию соответствующих значений первого и второго столбцов.
Мы видим, что столбцы значений обеих формул одинаковы. (Более того, обе формулы тождественно истинны на одноэлементном множестве.) Следовательно, эти формулы равносильны на одноэлементном множестве. л) Данные формулы замкнутые: в них нет свободных предметных переменных. Поэтому достаточно обозначить только предикатные переменные Р и 9 Составим таблицы значений этих формул..Одинаковые столбцы значений обеих формул показывают, что формулы равносильны. 189 9.37. Докажите, что формулы в каждой из пар в предыдущей задаче 9.36 не равносильны между собой на двухэлементном множестве.
Решение. На двухэлементном множестве (а, Ь» существуют уже четыре одноместных предиката А«(х), А~(х), Ат(х), Аз(х) (см. задачу 9.31). в) Придадим предикатной переменной Р значение Ан а свободной предметной переменной у значение Ь. Тогда первая формула превратится в ложное высказывание (~х)(Аз(х) -» А~(Ь)), так как предикат Аз(х) -+ А,(Ь) опровержим (превращается в ложное высказывание при х = а). В то же время вторая формула превратится в истинное высказывание (~х)(Аз(х)) -+ А~(Ь): посылка ('с/х)(Аг(х)) ложна (так как предикат Аг(х) опровержим: превращается в ложное высказывание при х = Ь), и следствие А~(Ь) ложно.
Следовательно, формулы не равносильны на двухэлементном множестве. л) У к а з а н и е. Проверьте„что при подстановке в данные формулы вместо предикатной переменной Р(х) предиката А,(х) и вместо предикатной переменной Д(х) предиката Аз(х) первая формула превратится в ложное высказывание, а вторая — в истинное.
9.38. Докажите, что в каждой из следующих пар формулы не равносильны между собой: а) (Зх)(Р(х) -+ Д(х)) и (Зх)(Р(х)) -+ (Эх)(о(х)); б) (Зх)(Р(х) «-» Д(х)) и (Эх)(Р(х)) «+ (Бх)(Д(х)); в) (»х)(Р(х) -+ (Д(х) -+ Я(х))) и ('Фх)(Р(х) -+ (Я(х) -» Д(х)); г) (Бх)(Чу)(Л~)(Г(х, у, ~) и (3~)('Фу)(Лх)(Г(х, у, ~)); д) (чх)((Р(х) -+ Д(х)) ч (Д(х) -+ Р(х))) и ('Фх)(Р(х) -+ Д(х)) ч ч (»х)(о(х) -+ Р(х)); е) (»х)(Р(х) -+ Д(у)) и (»х)(Р(х)) -+ Ц(у); ж) (Бх)(Р(х) -+ Д(у)) и (Зх)(Р(х)) -+ Д(у); з) (чх)(Р(у) -+ Д(х)) и Р(у) -+ (Зх)(о(х)); и) (Лх)(Р(у) -+ Д(х)) и Р(у) -+ (Ъх)(Д(х)); к) (чх)(Р(х) ««Д(х)) и (чхКР(х))++(чх)(Д(х)).
Решение. а) Если М= (1, 2) и Р(х): «х < 3», Ц(х): «3 / х», то формула Р(х) -+ Д(х) превращается в тождественно ложный 190 предикат, «х < 3 -+ 3 ~ х», а значит, высказывание (Эх)(х < 3 -+ -+ 3 ~ х) ложно. С другой стороны, оба высказывания (3х)(х < 3) и (3х)(3 ~ х) истинны и, значит, истинна их импликация (Эх)(х < 3) -+ -+ (Лх)(3 ~ х). Таким образом, данные формулы неравносильны. ж) Можно использовать и «безымянные» предикаты (см. задачу 9.31) для обозначения предикатных переменных данных формул.
Достаточно вместо предикатных переменных Р и Д подставить предикат А,(х), а вместо предметной переменной у — элемент а. Тогда первая формула превратится в истинное высказывание, а вторая — в ложное. 9.39. Докажите, что если в формуле логики предикатов поменять местами два рядом стоящих одноименных квантора, то полученная формула будет равносильна исходной. 9.40. Останется ли справедливым утверждение предыдущей задачи, если поменять местами одноименные кванторы, не стоящие в формуле рядом? 9.41.
Докажите, что если две формулы равносильны на некотором множестве М, то они будут равносильны и на всяком непустом множестве М„мощность которого не превосходит мощности М 9.42. Докажите, что если две формулы неравносильны на непустом множестве М, то они будут неравносильны и на всяком таком множестве М„мощность которого не меньше мощности М Тавтологии логики предикатов. Формулу логики предикатов называют общезначимой, или тавтологией (тождественно ложной, или противоречием), если при всякой подстановке вместо предикатных переменных любых конкретных предикатов, заданных на каких угодно множествах, она превращается в тождественно истинный (тождественно ложный) предикат.
Для обозначения тавтологии используется символ ~=К 9.43. Докажите, что следующие формулы являются тавтологиями логики предикатов: а) (чх)(Р(х) л Д(х)) +» ((Ъх)(Р(х)) л (Чх)(Д(х))); б) (ЛхКР(х) ч Ц(х)) «+ ((Лх)(Р(х)) ч (Лх)(1г(х))); в) (Лх)(Р(х) л Д(х)) -+ ((Лх)(Р(х)) л (Лх)(Д(х))); г) ((чх)(Р(х)) ч (Ъх)(Д(х))) -+ ('чх)(Р(х) ч Д(х)); д) (Чх)(Р(х) ч (г) «+ ((Ъ'х)(Р(х)) ч Ц); е) (Эх)(Р(х) л Ц) +» ((Лх)(Р(х)) л Ц); ж) -з(чх)(Р(х)) ++ (Зх)(-зР(х))„' з) ~(Зх)(Р(х)) ++ (чх)(~Р(х)); и) (Чх)(Р(х) -+ зо(х)) -+ ~((чх)(Р(х)) л (Лх)(Д(х))); к) (Лх)(Р(х) -+ Д(х)) ++ ((Вх)(Р(х)) -+ (3х)(о(х))); л) (чх)(Р(х) -+ Д) «+ ((Лх)(Р(х)) -+ Д); м) (~~х)(Р(х)) -+ (Ъ'х)(Р(х) ч Д(х); н) (Зх)(Р(х)) -+ (Зх)(Р(х) ч Д(х)); о) (чх)(Р(х)) -+ (Лх)(Р(х) г Д(х)); п) ('чх)(Р(х) л Д(х)) -+ (чх)(Р(х)); 191 р) (3х)(Р(х) л Ц(х)) -+ (3хКР(х)); с) (Ъх)(Р(х) л Д(х)) -+ (Зх)(Р(х)).
Р е ш е н и е. л) Отметим, что предикатная переменная Д в этой формуле может быть не только О-местной, но и любой и-местной, важно лишь, чтобы в нее не входила предметная переменная х. Итак, пусть Д есть Д(уп ..., у„). Будем считать для краткости, что Ц есть предикатная переменная Я(у). Предположим, что данная формула не является тавтологией. Тогда существуют такие конкретные предикаты А(х) и В(у), определенные на множествах М и М, соответственно, что предикат (от у)(~х)(А(х) -+ В(у)) ++ (3х)(А(х) -+ В(у)) опровержим, т.е.
обращается в ложное высказывание при подстановке вместо предметной переменной у некоторого конкретного предмета Ь из М,: Л[(~х)(А(х) -+ В(Ь)) ++ ((3х)(А(х)) -+ В(Ь))] = О. Эквивалентность ложна, если ее члены принимают разные значения истинности, т.е. могут представиться две возможности: первая — Л[(~х) (А(х) -э -+ В(Ь))] = 1 (1), Л[(3х)(А(х)) -+ В(Ь)] = О (2) и вторая — Л[('Фх)(А(х) -+ -+ В(Ь))] = О (3), Л[(3х)(А(х)) -+ В(Ь)] = 1 (4). Рассмотрим первую возможность. Из (2) по определению импликации имеем Л[(3х)(А(х))] = 1 (5) и Л[В(Ь)] = О (6). Далее, из (5) по определению квантора существования заключаем, что предикат А(х) выполним, т.е. Л[А(а)] = 1 (7) для некоторого а из М. Вернемся к соотношению (1).
По определению квантора общности предикат А(х) -э В(Ь) — тождественно истинен. В частности, если вместо предметной переменной х подставить а из М, то получим истинное высказывание Л[А(а) -+ В(Ь)] = 1. Но, учитывая (6) и (7), получаем Л[А(а) -+ В(Ь)] = Л[А(а)] -+ Л[В(Ь)] = 1 -+ О = = Π— противоречие. Рассмотрим вторую возможность, выраженную в соотношениях (3), (4).
Из (3), на основании определения квантора общности, следует, что предикат А(х) -+ В(Ь) опровержим, т.е. Л[А(а)-+ -+ В(Ь)] = О для некоторого а е М. Тогда по определению импликации Л[А (а)] = 1, ЦВ (Ь)] = О (8). Ввиду последнего соотношения из соотношения (4) заключаем, что Л[(3х)(А(х))] = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
