В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 36
Текст из файла (страница 36)
Пересечем обе части этого равенства с Р'. Р' = Р' г~ М= Р' г~ л (Р' н Д') =(Р" г~ Р' ) ~АР'г~ Д') = И и (Р'г~ Д') = Р'г~ Д'. Это означает, что Р' с Д'. Кроме того, Р+ л Д' ~ И. Итак, И ~ ~ Р'с Д+, м) Из условия задачи следует, что Л[(тхНР(х) ++ Д(х)Ц = О, Л[(3х) (Д(х) л Р(х))[ = О. Из первого равенства следует, что предикат Р(х) ++ Д(х) тождественно ложен, т.е. (Р' н Д') г~ (Р' и Д' ) = И. (1) Из второго равенства следует, что предикат Д(х) л Р(х) тождественно ложен, т.е.
178 Р'г~ О'= И. (2) Преобразуем (1) с учетом (2): И =(Р' н Д') г~(Р'н К') = =(Р' г~(Р'о Д')) н (Д'а (Р'~э Д')) = (Р' с~ Д') и (О'л Р') = = Р' г~ Д'. Возьмем дополнения от обеих частей полученного равенства. Получим: Р' г~Д' = И, т.е. Р'~г Д'= М. Равносильность н следование нредикатов. Предикаты Р(хн х,, ..., х„) и Д(хо х„..., х„) над одними и теми же множествами называют равносильньаии, или эквивалентными, если Р' = Ц', т.е.
если один из них обращается в истинное высказывание на тех и только тех наборах значений переменных из соответствующих множеств, на которых в истинное высказывание обращается другой предикат. Предикат 0(х„х„..., х„) называют следствием предиката Р(х„хв ..., х„), заданного над теми же множествами, что и предикат Д(х„х,, ..., х„), если он обращается в истинное высказывание на всех тех наборах значений переменнь1х из соответствующих множеств, на которых в истинное высказывание обращается предикат Р(х„хь ..., х„), т.е. если О' ~ Р'.
9.22. Выясните, равносильны ли следующие предикаты, если их рассматривать над множеством действительных чисел Я, над множеством рациональных чисел Ц, над множеством целых чисел У и над множеством натуральных чисел Ф: а) 5х' — 11х+ 2 = О, (х' — 3)(Зх' — 7х+ 2) = О; б) х' — 3/х —.ГЗ =х+,/3, созх< 1; в) х'=О, ~х~ < О; г) Гх,/у =15,,/х у =15; д) )х) = ~ у), х= у; е) х<2,у<2; ж) 1а(х у) = 1, 1а х+ 1а у = 1; з) 2" 2» = 4, 2" + У = 4; и) 1й(х у) = 1й х + 1а у, 2' 2У = 2" + У; к) 1а(х у) = 1й х + 1а у, ,/х . у = Гх ,/у; л) хз = 1, (х — 1)(х + /2 )(х — 1,5)(х + 1) = О. Решение. л) Предикаты равносильны над множеством Ф (каждый из них имеет в этом случае множество истинности (Ц) и над множеством У (множество истинности каждого из них в этом случае (-1, Ц).
Над множествами Д и Я первый предикат имеет множество истинности (-1, Ц). Второй предикат над множеством Д обладает множеством истинности ( — 1 1, 3/2), а над множеством Я вЂ” множеством истинности ( — /2, — 1, 1, 3/2 ). Следовательно, над множествами Ц и Я предикаты не равносильны. 9.23. Задайте множество так, чтобы над ним следующие предикаты были равносильны: 179 а) «х кратно 3», «х кратно 7»; б) «хз — х — 2 = О», «хз + 1 = О»; в) «Город х находится на берегу реки Волги», «Город х находится на берегу реки Свияги»; г) «х — простое число»„«х — четное число»; д) «Диагонали в четырехугольнике х равны», «Четырехугольник х — параллелограмм»; е) «Диагонали в четырехугольнике х взаимно-перпендикулярны», «Четырехугольник х — ромб»; ж) «х — треугольник», «Биссектриса одного из внутренних углов треугольника х является его медианой»; з) «х делится на 3», «х делится на 9»; и) «х — куб», «х — параллелепипед»; к) «х — цилиндр», «х — конус»; л) «Треугольник х — равнобедренный», «Три высоты треугольника х равны между собой», Решение.
л) Ясно, что требуемое множество нужно искать среди подмножеств множества всех треугольников. Элементы этого множества должны быть одновременно и равнобедренными треугольниками, и такими треугольниками, у которых все три высоты равны между собой. Можно показать, что три высоты в треугольнике равны между собой тогда и только тогда, когда этот треугольник равносторонний. Поскольку, кроме того, всякий равносторонний треугольник является равнобедренным, то искомым множеством может быть, например, множество всех равносторонних треугольников. Другое множество, над которым два данных предиката равносильны, — множество всех неравнобедренных треугольников.
9.24. Докажите следующие утверждения, считая, что каждый из двух предикатов зависит от одних и тех же переменных, пробегающих одни и те же соответственные множества: а) Конъюнкция двух предикатов есть опровержимый предикат тогда и только тогда, когда по меньшей мере один из данных предикатов опровержим; б) Конъюнкция двух предикатов есть тождественно истинный предикат тогда и только тогда, когда оба данных предиката тождественно истинны; в) Дизъюнкция двух предикатов есть выполнимый предикат тогда и только тогда, когда по меньшей мере один из данных предикатов выполним; г) Дизъюнкция двух предикатов есть тождественно ложный предикат тогда и только тогда, когда оба данных предиката тождественно ложны; д) Конъюнкция тождественно ложного предиката и любого предиката есть тождественно ложный предикат: Р(х) л Р(х) «» Р(х); е) Конъюнкция тождественно истинного предиката и любого предиката есть предикат, равносильный последнему: Т(х) л Р(х) «» Р(х); 180 ж) Дизъюнкция тождественно ложного предиката и любого предиката есть предикат, равносильный последнему: Г(х) ч Р(х) «» «» Р(х); з) Дизъюнкция тождественно испппюго предиката и любого предиката есть тождественно истинный предикат: Т(х) ~ Р(х) «» Т(х); и) Импликация двух предикатов с тождественно ложным следствием равносильна отрицанию ее посылки; к) Импликация двух предикатов с тождественно истинной посылкой равносильна ее следствию; л) Эквивалентность двух предикатов с тождественно истинным одним членом равносильна ее второму члену; м) Эквивалентность двух предикатов с тождественно ложным одним членом равносильна отрицанию ее второго члена.
Решение. д) Вычислим множество истинности (Гл Р)'= Г'г~ г~ Р' = И г~ Р' = И. Следовательно, предикат Г(х) л Р(х) тождественно ложен. з) Аналогично вычислим множество истинности (Тч Р)' = Т' .з ~г Р' = М Р' = М. Следовательно, предикат Т(х) .«Р(х) тождественно истинен. 9.25. Определите, является ли один из следующих предикатов, заданных на множестве действительных чисел, следствием другого: а) «! х ~ < 3», «хз — Зх+ 2 = О»; б) «х4 = 16», «хз = — 2»; в) «х — 1 > О», «(х — 2)(х + 5) = О»; г) «яп х = 3», «хз + 5 = О»; д) х'+5х — 6 > О», «х+ 1 =1+х; е) «хз < О», «х = з(п я»; ж) «-5 < х», «х < 5»; з) «1я х < 1», «1 < х < 10»; и) «ха+у = 1», «хз+у < 1»; к) «х' < у», «у > О»; л) «хз — 2х~ — 5х + 6 = О», «~х — 2 ( = 1».
Решение. л) Второй предикат превращается в истинное высказывание лишь при двух подстановках: х = 1 и х = 3. Нетрудно проверить, что эти подстановки превращают и первый предикат в истинное высказывание (являются корнями кубического уравнения). Поэтому первый предикат является следствием второго. 9.26. Задайте множество М значений предметной переменной так, чтобы на этом множестве второй предикат был бы следствием первого: а) «х кратно 3», «хчетно»; б) «х'= 1», «х — 1=0»; в) «х нечетно», «х — квадрат натурального числа»; г) «х — ромб», «х — параллелограмме; д) «х — параллелограмм», «х — ромб»,. е) «х — русский ученый», «х — математик»; 181 ж)-5<х,х<5; з) «х делится на 3», «х делится на 9»; и) «х — куб», «х — прямоугольный параллелепипед»; к) «х — цилиндр», «х — конус»„ л) «х — квадрат, «х — параллелограмм», Решение.
л) Поскольку всякий квадрат является паралле- лограммом, в качестве множества, на котором второй предикат является следствием первого, может быть взято множество всех четырехугольников. Формулы логики предикатов, их интерпретация и классифика- ция. Понятие формулы логики предихатов вводится аналогично тому, как это было сделано в алгебре высказываний. Определение имеет индуктивный характер: а) всякий 0-местный предикатный символ (т.е. пропозициональная переменная) есть формула; б) вся- кий и-местный предикатный символ Р(х„хп ..., х„), где х„хг, ..., х„— свободные предметные переменные, есть формула; в) ес- ли Г~ и Гг — формулы, то -~Г, (Г, и Р;), (Г, «Р~), (Г, -+ Р;), (Г, ++ Р;) — формулы; г) если à — формула, в которую предмет- ная переменная х входит свободно, то (их)(Г) и (3х) (Г) — фор- мулы, в которых предметная переменная х связана, а те предмет- ные переменные, кроме х, которые были свободны в Г, свободны и в новых формулах, и те предметные переменные, которые были связаны в Г, связаны и в новых формулах; д) никаких других фор- мул, кроме тех, которые получаются по правилам а) — г), в логике предикатов нет.
Формула логики предикатов превращается в конкретный пре- дикат при подстановке вместо всех ее предикатных переменных конкретных предикатов. Формулу логики предикатов называют выполнимой (опровержи- мо4 на множестве М, если при некоторой подстановке вместо предикатных переменных конкретных предикатов, заданных на этом множестве, она обращается в выполнимый (опровержимый) предикат. Формулу логики предикатов называют тождественно истин- ной (тождественно ложной) на множестве М, если при всякой подстановке вместо предикатных переменных любых конкретных предикатов, заданных на этом множестве, она превращается в тождественно истинный (тождественно ложный) предикат. 9.27. Определите, какие из следующих выражений являются формулами логики предикатов, а какие нет, и объясните почему: а) (Зх)(В(х)) -+ (чх)(В(х)); б) (вх)(Р(х)) -+ Р(у); в) (Ъх)((Р(х) п Д(х)Я(х)) -+ (Лу)(зЮ(х)); г) (Ь'х)(Д(х) п -1Я(х)); д) (Зх)(Р(х) л Д(х) п -1Я(х)); е) (Лх)(Е(х) л 1)(х, у)); 182 ж) (ихНР(х) «Д(х)) -+ (ЗхНР(х) -+ Ц(х) и Я(х)); з) -1Р(х) л (иу)(Р(у)); и) (ЗхНЛуНх ~ у л Р(х) л Р(у)); к) ~[(3хНР(х)) -+ (йхНР(х))]; л) (их)[Е(х) -+ (иуН2)(х, у) -+ Е(у))]; м) (Эу)[Р(у) л (йхНД(х, у) и Я(х))].
9.28. Перечислите свободные и связанные вхождения каждой из переменных в каждой из следующих формул: а) (ихНР(х)); б) (ихНР(х)) -+ Р(у); в) Р(х) -+ (ЭхНД(х)); г) (ЗхНА(х) л В(х)); д) (ЭхНйуНР(х) л Д(у)) -+ (йуНЯ(х, у)); е) (ЗхНЭуНР(х, у) л О(~)); ж) (БиНииНВ(и, и)) -+ (зг)(В(т, и)); з) (ихНР(х) -+ Д(у)) л (ЗуНЯ(х, у, е)); и) (их)[( и 4)(Р(х, е) -» Д(у)) л (ЗуНЯ(х, у, ~))]; к) (ЗуН'ихНД(х, у, е) л Р(у)) -+ Я(у, е); л) (Чх)[(БУНР(х, у)) -+ Ц(х, у, е)]. Р е ш е н и е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
