В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 37
Текст из файла (страница 37)
л) Действие квантора их распространяется на всю формулу, стоящую в квадратных скобках. Поэтому переменная х всюду в данной формуле является связанной. Переменная д не стоит под знаком квантора, поэтому, без всякого сомнения, является свободной. Наконец переменная у стоит под знаком квантора Зу, но действие этого квантора распространяется лишь на выражение Р(х, у), и поэтому переменная у в этом выражении является связанной. Но переменная у входит еще и в выражение Д(х, у, ~), на которое действие квантора Зу не распространяется. В этом выражении переменная у свободна. Для окончательной ясности в этом вопросе данную формулу можно переписать (переобозначив связанную переменную любой другой буквой, не входящей в формулу, например буквой т) в следующем виде: (их)[(з(НР(х, т)) -+ Ц(х, у, ~)]. здесь уже отчетливо видно, что переменные х и г связанные, а у и х свободные.
9.29. Придайте следующим формулам указанные интерпретации и определите истинностные значения получающихся высказываний: а) (ихНР(х) — » Р(у)), М= [Петр, Павел), Р(х): «Имя х состоит из 5 букв», у = Петр; б) (йх)(Р(х)) -+ Р(у), интерпретация та же, что и для предыдущей формулы; в) (ихН-зГ(х, х)) л(ихН'иуНч~Н(Г(х, у) л Г(у, ~)) -+ Г(х, я)) л л (йхНЗуНГ(х, у)), М = [1, 2, 3), Г(х, у): «х < у»; г) предыдущая формула, М = )т', Р(х, у): «х < у»; д) (ЗхНР(х) л 0(х)), М = Ф, Р(х): «х < 5», Д(х): «х > 6»; е) (ЗхНР(х)) л (БхН О(х)), интерпретация та же, что и для предыдущей формулы; 183 ж) з(ЗхНР(х)), М = Ф, Р(х): «х ( 2»; з) (ЭхН-~Р(х)), интерпретация та же, что и для предыдущей формулы; и) ('ФхНР(х) «+ Д(х)), М= Ф, Р(х)' «3 ~ х», Д(х): «2 ~ х»; к) ('о'хНР(х)) ++ (ьх)(Д(х)), интерпретация та же, что и для предыдущей формулы; л) (ЛхНР(х) -+ Р(у)), М = (2, 3), Р(х): «2! хъ, у = 3; м) (ЗхНР(х)) -+ Р(у), М = (2, 3), Р(х); «2 / х», у = 3, Р е ш е н и е.
л) При подстановке вместо предикатной переменной Р конкретного одноместного предиката «2 ~ х» формула превращается в одноместный (зависящий от у) предикат: (ЭхН(2 ~ х -+ -+ 2 ~ у)). Подставив вместо предметной переменной у значение 3, получим высказывание (3хН(2 ~ х) -+ (2 ~ 3)). Руководствуясь определением квантора существования, выясним, каково его логическое значение. Поскольку одноместный предикат (2 ~ х) -+ (2 ~ 3) при х = 3 превращается в истинное высказывание (2 ~ 3) -+ (2 ! 3), то и высказывание (БхН(2 ~ х) -+ (2 ~ 3)) истинно. м) При указанной интерпретации данная формула превращается в высказывание (ЗхН2 ~ х) -+ 2 ( 3, представляющее собой импликацию двух высказываний.
При этом посылка (3хН2 ! х) есть истинное высказывание (так как предикат «2 ! х» превращается в истинное высказывание при х= 2), а следствие «2 ~ 3» — в ложное. Следовательно, получившееся при интерпретации высказывание ложно. 9.30. Покажите, что каждая интерпретация каждой из следующих формул на одноэлементном множестве дает истинное высказывание: а) Р(х) -» Р(у); б) Р(х) ««Р(у); в) (ЛхНР(х)) -+ Р(у); г) (ЗхНР(х)) -+ (чхНР(х)); д) Р(х) ч -ьР(у) е) (ЧхН'ФуНР(х) ч -1Р(у)); ж) Р(х) -+ (Р(х) л Р(у)); з) (Р(х) ч Р(у)) -+ Р(х); и) Р(у) -+ (чхНР(х)). Решение.
и) Как известно, предикат на множестве М есть некоторая функция, заданная на этом множестве и принимающая значения в двухэлементном множестве (О, Ц. Тогда, как легко понять, если М состоит из одного элемента а, т.е. М= (а), то на нем можно задать лишь два конкретных предиката (функции) А,(х) и А,(х) следующим образом: А,(а) = О, А,(а) = 1. При интерпретировании данной формулы нужно входящую в нее предикатную переменную Р назвать одним из конкретных предикатов А, или А„а свободную предметную переменную ув некоторым предметом из М (там их всего один — а).
184 Сведем в таблицу всевозможные интерпретации данной формулы: 9.31. Покажите, что при интерпретации формул предыдущей задачи на двухэлементном множестве не всегда получается истинное высказывание. Решение. ж) На двухэлементном множестве М= (а, Ь) имеются уже четыре различных одноместных предиката. Они представляют собой функции А,(х), А2(х), А~(х), А4(х), заданные на двухэлементном множестве М = (а, Ь) и принимающие значения в двухэлементном множестве (О, Ц в соответствии со следующей таблицей: Всевозможные интерпретации данной формулы в этом случае сведем в следующую таблицу: Из таблицы видно, что предикат А,(х) и предмет Ь в М(характеризующийся тем, что А,(Ь) = 1) превращают данную формулу в ложное высказывание А,(Ь) -+ (~гх)(А,(х)).
Руководствуясь этими соображениями, данную интерпретацию можно наполнить определенным содержанием, взяв, например, в качестве М множество (5, б) (5 и 6 — натуральные числа), а в качестве предиката 185 Аз(х) предикат «х < 5». Тогда высказывание «5 < 5» истинно, а «6 ~ < 5» — ложно (значит, в нашем случае-а = б и Ь = 5). Ложное высказывание, в которое превращается данная формула при этой интерпретации, выглядит так: 5 < 5 -+ (~хНх < 5). 9.32.
Придумайте такие конкретные двухместные предикаты А(х, у), чтобы высказывания (чхНЗУНА(х, у)) и (ЗУН~хНА(х, у)): а) были оба истинны; б) были оба ложны; в) первое было бы ложным, а второе истинным; г) первое бьио бы истинным, а второе — ложным. 9.33. Придумайте такие конкретные двухместные предикаты А(х, у), чтобы высказывания (чхНЗУНА(х,у)) и (зхН'ФУНА(х У)): а) были оба истинны; б) были оба ложны; в) первое было бы ложным, а второе — истинным; г) первое было бы истинным, а второе — ложным. Решение.
а) Рассмотрим предикатА(х, у): «х(у» на множестве всех натуральных чисел. При такой интерпретации первая формула превращается в истинное высказывание: «Для всякого натурального числа существует большее него натуральное число» и вторая формула превращается в истинное высказывание: «Существует наименьшее (т.е. меньшее всех остальных) натуральное число», 9.34. Составьте таблицу значений следующей (открытой или замкнутой) формулы, интерпретируя ее всевозможными способами на двухэлементном множестве: а) (3УНЧхНР(х, у)) ч -тР(и, и); б) ('ФхНР(х) -+ Р(у)) г ~Р(у); в) (мх)(Р ч Д(х)) -+ (Р «(ЪхН Д(х))).
Решение. а) Надвухэлементном множестве М= (а, Ь) имеются 16 различных двухместных предикатов (функции двух аргументов, заданных на Ми принимающих значения в двухэлементном множестве (О, 1)): Для интерпретации данной открытой формулы на множестве М = (а, Ь) нужно 2-местный предикатный символ Р заменить на конкретный 2-местный предикат, а каждую свободную предметную переменную (у нас их две — и и и) заменить на конкретный элемент из множества М= (а, Ь). Сделаем, например, следующую замену: Р=Ап, и = а, о= а. Получим высказывание 186 (Зу)(~гх)(Ац(х, у)) ~~ ~Ац(а, а). Определим его логическое значение.
Во-первых, ясно, что Ц-тАц(а, а)1 = -й[Ац(а, а)1 = -т1 = О. Теперь рассмотрим высказывание (Зу)( ~ х)(А„(х, у)). По определению квантора общности применение этой операции к двухместному предикату Ац(х, у) дает одноместный предикат (от у): Ац(а, у) л Ац(Ь, у). Далее, применение квантора существования к последнему предикату дает высказывание (О-местный предикат): (Ац(а, а) л Ац(Ь, а)) ~ (Ац(а, Ь) л Ац(Ь, Ь)), логическое значение которого равно: (1 л 1) ч (О л О) = 1 ч 0 = 1. Таким образом, логическое значение высказывания (*) равно 1 ч 0 = 1. Составим теперь таблицу значений данной формулы, когда предикатная переменная Р принимает всевозможные значения Ац Аь ..., Ам, а предметные переменные и и а принимают значение а (проверьте результаты, приведенные в этой таблице, проделав вычисления, как показано выше): 187 Составьте теперь самостоятельно еще три аналогичные таблицы, в которых предметные переменные и и и принимают следующие значения: в первой и = а, о = Ь, во второй и = Ь, » = а, в третьей и = Ь, а = Ь.
Соединение всех этих таблиц и даст требуемую таблицу значений данной формулы при всевозможных ее интерпретациях на двухэлементном множестве. 9.35. Определите, какие из следующих формул выполнимы, а какие нет (т.е. тождественно ложны): а) (3х)(Р(х)); б) (жх)(Р(х)); в) (Зх)(Чу)(Д(х, х) л -з0(х, у)); г) (Лх)('Фу)(Д(х, у) -+ ('Ф~)(Я(х, у, ~))); д) Р(х) -+ (~у)(Р(у)); е) ('Фх)(Р(х) ч Д(х)) -+ ((~х)(Р(х)) ч (чх)(Д(х))); ж) (Лх)(Р(х)) -+ (жх)(Р(х)); з) (~х)(Р(х) л -зР(х)); и) ('Фх)(Бу)(Р(х) л -чР(у)); к) (чх)('оу)(Р(х) ч -зР(у)); л) (3х)(Лу)(Р(х) л -зР(у)); м) зР(х) л (чу)(Р(у)). Р е ш е н и е. л) Пусть х и у пробегают множество Фнатуральных чисел и Р(х) означает, что «х — четное число».
Тогда данная формула (Лх)(Лу)(Р(х) л ~Р(у)) превращается в высказывание: «Среди натуральных чисел существуют как четные, так и нечетные числа», которое истинно. Следовательно, данная формула выполнима. м) Покажем, что эта формула невыполнима. Допустим противное. Это означает, что существует такое множество М и такой конкретный предикат А(х) над ним, что когда х, у я М, то данная формула превращается в конкретный одноместный предикат В(х) = -зА(х) л (чу)(А(у)). Этот предикат, в свою очередь, превращается в истинное высказывание при всякой подстановке вместо х элементов из множества М.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
