В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 34
Текст из файла (страница 34)
Точку Х, можно брать в любом месте отрез- 169 ка [АВ[. Таким образом, Р' = [А,В [ — отрезок, симметричный отрезку [АВ[ относительно прямой 1 9.11. Изобразите на координатной прямой или на координатной плоскости множества истинности следующих предикатов: а) (х > 2) л (х < 2); б) (х > 2) ~ (х < 2); в) (х > 2) «+ (х < 2); г) (х > О) л (у < О); д) (х > О) г (у < О); е) (х.> О) -+ (у < О); ж) ([х / < 3) л (х > 2); з) (з[п х > О) л ([х — 2 [ < 5) л (!ах > 1); и) (х2 + у2 > 1) «-» (ху < О); к) ([ х [ > 2) -+ ([ х / < 3); л) (х > 2) -+ (х < 2); м) (х>0) ++(у < О).
Решение. л) Ясно, что предикат «(х > 2) -+ (х < 2)» будет обращаться в истинное высказывание только при тех значениях х, при которых посылка «х > 2» обращается в ложное высказывание. Следовательно, множеством истинности импликации будет полуинтервал [-ео, 21. м) (х > О) ++ (у < О).
Координаты х и у каждой точки первой четверти, включая положительную часть оси Оу, удовлетворяют первому соотношению, а второму — не удовлетворяют. Следовательно, весь предикат в этой области обращается в ложное высказывание. Во второй четверти координаты х и у каждой точки обращают оба предиката, стоящие в левой и правой частях эквивалентности, в ложные высказывания. Следовательно, весь предикат превращается в истинное высказывание. Исключение составляют точки полуосей Оу' и Ох .
Координаты х и у каждой точки третьей четверти не удовлетворяют первому соотношению, а второму — удовлепюряют. Следовательно, предикат превращается в ложное высказывание. В четвертой четверти координаты х и у каждой точки обращают и посылку, и следствие в истинные высказывания. Следовательно, предикат превращается в истинное высказывание. Итак, множеством истинности предиката является множество точек второй и четвертой четвертей плоскости, за исключением полуосей Оу' и Ох . 9.12. Найдите множества истинности следующих предикатов, заданных над множеством М = [1, 2, 3, 4, 5, ..., 19, 20): а) х — четное число; б) х — нечетное число; в) х<10; г) 3/х; д) (х — четное число) -+ (х — квадрат натурального числа); е) (х — квадрат натурального числа) -+ (х — четное число); ж) (х [ 16) л (х > 15); 170 з) (х — квадрат натурального числа) ~ (х < 10); и) (х> 14) л(4~х); к) (х — нечетное число) +» (2 не делит х); л) (х — четное число) +«(х не делит 8).
Решение. л) Данный предикат представляет собой эквивалентность двух предикатов. Поэтому найдем сначала те натуральные числа из М, которые превращают в истинные высказывания одновременно оба эти предиката. Первый предикат превращается в истинное высказывание элементами из множества М,' = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20), второй — элементами из М~з = (3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20). Значит, оба эти предиката превращаются одновременно в истинные высказывания на множестве М' = М,' г~ М1 = (6, 10, 12, 14, 16, 18, 20). Далее, найдем числа из М, которые превращают в ложные высказывания одновременно оба предиката «х — четное число» и «х не делит 8».
Первый предикат превращается в ложное высказывание элементами из множества М~ = (1, 3, 5, 7, 9, 11, 13, 15, 17, 19), а второй — элементами из М1 = (1, 2, 4, 8). Значит, оба эти предиката превращаются одновременно в ложные высказывания на множестве М'= М~ г М1'= (1). Таким образом весь данный предикат превращается в истинное высказывание при подстановке вместо х как элементов из М', так и элементов из М~.
Следовательно, множеством истинности данного предиката является объединение этих множеств М' ~г М» = =(6, 10, 12, 14, 16, 18, 20) н (Ц = (1, 6, 10, 12, 14, 16, 18, 20). 9.13. Зная множества Р' и Д' истинности предикатов Р(х„ х,, ..., х„) и Д(хп х„..., х„) соответственно, заданных над одними и теми же множествами, найдите множества истинности: а) предиката зР(хь хъ..., х„); б) конъюнкции; в) дизъюнкции; г) импликации; д) эквивалентности предикатов Р(хь хъ ..., х„) и Д(хп х„..., х„). Указание. г), д).
Выразите импликацию через отрицание и дизъюнкцию, а эквивалентность — через отрицание, конъюнкцию и дизъюнкцию, и затем примените результаты задач а), б) и в). 9.14. Зная множества Р'и Р' истинности предикатов Р(х„х„ ..., х„) и -з Р (х„х„..., х„) соответственно, заданных над одними н теми же множествами, найдите множество истинности следующего предиката: а) Р(х) ~ -~Р(х); б) Р(х) -+ -зР(х); в) (Р(х) -+ -юР(х)) -+ -юР(х); г) (Р(х) -+ -зР(х)) -+ Р(х); д) (Р(х) ~ -юР(х) ++ (Р(х) -+ -зР(х)); е) (Р(х) -+ (зР(х) ~ Р(х))) -+ -зР(х); ж) -юР(х) -+ (Р(х) л -зР(х)); з) (Р(х) ++ -зР(х)) -+ Р(х); 171 и) (Р(х) ++ -зР(х)) ч (-зР(х) -+ Р(х)); к) (-зР(х) л Р(х)) -+ (-зР(х) ч Р(х)); л) (-чР(х) ++ Р(х)) -+ Р(х).
Р е ш е н и е. л) Для нахождения множества истинности данного предиката сначала выразим операции ++ и -+ через з, л, ч, затем воспользуемся результатами задачи 9.13: [(-зР(х) ++ Р(х)) -+ Р(х)]' = [((-~Р(х) -+ Р(х)) л (Р(х) -+ ~Р(х))) -+ -+ Р(х)]' = [~((~~Р(х) ч Р(х)) л (-зР(х) ч -чР(х))) ч Р(х)]'= =((Р' иР')гь(Р' оР')) иР' = (РР'г Р')иР' = (Р' и Р') и Р' = =(Р' иР')иР' = У иР' = У. 9.15. Выразите множества истинности следующих предикатов через множества истинности входящих в них элементарных предикатов: а) ((-зР(х) ч -ю Д(х)) л Я(х)) ч (зЯ(х) л ~Р(х)); б) (Р(х) -+ Я(х)) л (Д(х) -+ -тЯ(х)) л (Р(х) -+ зЯ(х)); в) -ю(Р(х) ч Д(х)) ++ (-иР(х) ч Д(х)); г) (зР(х) -+ Д(х)) л (~Р(х) ч Д(х)); д) (Р(х) -+ Д(х)) л (Д(х) -+ Я(х)) л (Д(х) -+ -зЯ(х)); е) ~(Р(х) л -зЯ(х)) л ~(Р(х) л Д(х)) л (Р(х) -+ Д(х)); ж) (-юР(х) ++ Д(х)) л з(Р(х) -+ -зЯ(х)) л (-зР(х) -+ зД(х)); з) ((Р(х) ч ~Я(х)) ч ~(-зД(х) -+ Р(х))) -+ (Д(х) -+ Р(х)); и) (Д(х) ++ -чЯ(х)) л з(-юЯ(х) -+ Д(х)) л (зД(х) ч Я(х)); к) ((-зР(х) л Д(х)) -+ (Р(х) л -зД(х))) ч -з(Р(х) ч Д(х)); л) [((зЯ(х) -э -чР(х)) -+ (Д(х) ч -зР(х))) ч (-ч Д(х) ч -зР(х)) л л Я(х).
Р е ш е н и е. л) Для того чтобы выразить множества истинности Д данного предиката через множество истинности входящих в него элементарных предикатов, сначала выразим операции++ и -+ через -~, л, ч, а затем воспользуемся результатами задачи 9.13: [(((-з Я(х) -+ -зР(х)) -+ (Д(х)ч -з Р(х)))ч (з Д(х)ч -зР(х))) л Я(х)]'= = [((-ч(Я(х) ч зР(х)) ч (Д(х) ч -зР(х))) ч (з Д(х) ч ~Р(х))) л Я(х)]' = = ((Я'(х) и Р'(х)) и (Д+(х) и Р'(х))) и (Д'(х) и Р'(х))) г~ Я' = = ((( Я' о Р' ) о (Д' о Р')) о ( Д' и Р" )) г~ Я' = ((( Я' л Р') о о (Д' о Р')) о (Д' и Р')) л Я'= ((((Я' и Р') г~ 0) о Д') и и ( Д' о Р')) о Я" = (( Я' и Р' о Д') и ( Д" о Р')) о Я ' = ( Я' и о Р' о Д' о Д' о Р') и Я' = ( Я' о Р' о У) о Я' = Уг~ Я' = Я'.
9.16. Выясните, равны ли. множества истинности следующих предикатов: а) Р(х) -+ (Д(х) -+ Я(х)) и (Р(х) -+ Д(х)) -+ Я(х); б) зР(х) ч (Я(х) -+ -зД(х)) и (Р(х) л Я(х)) -+ -чД(х); 172 в) (Р(х) -+ Д(х)) л (Д(х) -+ Я(х)) и Д(х) -+ (Р(х) л Я(х)); г) (-1Р(х) — э Д(х)) -+ (-1Р(х) л -1Я(х)) и -зР(х) л (Д(х) -+ -+ -1Я(х)); д) -1(-1Р(х) л (Д(х) -+ -|Я(х)) и Р(х) ч (Д(х) л Я(х)))„' е) (Р(х) л -юД(х)) -+ (Р(х) ч Я(х)) и (Р(х) л (-|Д(х) -+ Р(х))) ч ч Я(х); ж) (Р(х) +.+ ~ Д(х)) л (~ Д(х) ч Р(х)) и ((-1 Д(х) ч -юР(х)) -+ (-1Р(х) л л Я(х))) ч (-1Р(х) л -1Я(х)); з) Р(х) -+ (Р(х) ч Д(х)) и -1Р(х) л (Р(х) ч Д(х)); и) ((Р(х) ч Д(х)) -+ Я(х)) ч -1Я(х) и (-1Р(х) -+ -1Я(х)) ч (Д(х) -+ -+ Я(х)); к) Р(х) ч ((~ Д(х) ++ Я(х)) л Д(х)) и ~Р(х) -+ ((-1 Д(х) -+ Я(х)) л л (Д(х) ч Я(х))); л) ((Р(х) -+ (Д(х)ч -тЯ(х))) -+ Д(х)) и -1 Д(х) л (Р(х) -+ -1Я(х)); м) -1(-1 Д(х) -+ Р(х)) л ((Р(х) ч -1 Д(х)) ++ Д(х)) и (Р(х)ч Д(х)) л л ((Д(х) -+ -1Р(х)) -+ -1Д(х)).
Р е ш е н и е. л) Чтобы выяснить, равны ли множества истинности данных предикатов, сначала найдем множества истинности каждого из них, а затем сравним их. Для нахождения множеств истинности сначала выразим -+ и ++ через ~, л, ч, а потом воспользуемся результатами задачи 9.13. Первый предикат: [-ч((Р(х) — ~ (Д(х) ч -зЯ(х))) -+ Д(х))]' = [.з((~Р(х) ч Д(х) ч ч -1Я(х)) -+ Д(х))]' = [-1(-1(-1Р(х) ч Д(х) ч -1Я(х)) ч Д(х))]' = = [-ю((Р(х) л -1Д(х) л Я(х)) ч Д(х))]' = [-1(Р(х) л -1Д(х) л Я(х)) л л -зКх)]' = [(-1Р(х) ч Д(х) ч -|Я(х)) л -1Д(х)]' = (Р+ и Д' и и Я') г1 Д' = ( Р' г Д') и (Д+ о Д') и ( Я' л Д') = ( Р' л Д') и и (Я' г1 Д') = (Р" и Я') г1 Д'. Второй предикат: [-1 Д(х) л (Р(х) -+ -1Я(х))]' = [~ Д(х) л ( 1Р(х) ч ч-1Я(х))]'= Д'+г1 (Р' и Я" ).
Сравнивая полученные множества истинности предикатов, делаем вывод, что они равны. м) Решаем аналогично. Первый предикат: [-ю(-зД(х) -+ Р(х)) л ((Р(х) ч -1Д(х)) ++ Д(х))]' = [-1(Д(х) ч ч (Р(х)) л ((Р(х) ч ~Д(х)) -+ Д(х)) л (Д(х) -+ (Р(х) ч -зД(х)))]' = = [(-1 Д(х) л -1Р(х)) л (-1(Р(х) ч -ю Д(х)) ч Д(х)) л (-з Д(х) ч (Р(х) ч ч -1 Д(х)))]* = [(~ Д(х) л -1(Р(х)) л ((-1Р(х) л Д(х)) ч Д(х)) л ( 1Д(х) ч ч (Р(х) ч -1 Д(х)))]' = [-зД(х) л -1(Р(х) л Д(х) л (-1Д(х) ч Р(х))]' = = [-юД(х) л -1Р(х) л Д(х)]' = И. Второй предикат: [(Р(х) ч Д(х)) л ((Д(х) -э -1Р(х)) -+ -1 Д(х))]' = [(Р(х)ч Д(х)) л л(-1(-1Д(х) ч -|Р(х)) ч -1Д(х))]' = КР(х) ч Д(х)) л ((Д(х) л Р(х)) ч ч .з Д(х))]'= (Р' и Д') г1 ((Д' г1 Р ) и Д ) = (Р' и Д') г1 (Д' и и Д ) г (Р'и Д ) =(Р'и(Д+г Д )) г1 У=(Р'иИ)г, У=Р г1 л У= Р'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
