В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 59
Текст из файла (страница 59)
Последняя формула и есть 6++ Н; н) (1) б, «Н, б ++ Н «- 6 -+ Н, (2) б, б -+ Н «- Н, (3) С, -~Н, 6++ Н «- Н, (4) 6, «Н, 6++ Н «- -«Н, (5) 6, ~Н «- -«(6++ +«Н); о) (1) б, Н, б «- Н, (2) б, Н «- б -+ Н, (3) Н, 6, Н «- 6, (4) Н, 6 «- Н -+ С, (5) 6, Н « — (6 -+ Н) л (Н -+ 6). Последняя формула и есть 6 ~+ Н. 22. Приведем обоснования этих выводимостей.
а) (1) Рл 6 «- Г, (2) Гл 6 «- 6, (3) 6, Г«- бл Г, (4) Р л 6«- « — бл Г; в) (1) Г л С «- 6 л Г, (2) « — (Гл 6) -+ (6 л Г), (3) 6 л Г«- Рл л 6, (4) «-(6 л Р) -«(Г л 6), (5) «-(Г л 6) ++ (6 л Г); г) (1) Р «- 6 ч Г, (2) 6 «- 6 ч Г, (3) Р ч б «- б ч Г, (4) «-(Рч ч 6) -+ (б ч Г), (5) б «- Г ч б, (б) Г «- Гч 6, (7) 6 ч Р « — Р ч 6, (8) «-(ба Г) -+ (Рч С), (9) «-(Гч 6) ++ (б з Р); е) (1) Г «- Р ч Г, (2) «-Г -+ (Р ч Р), (3) -чГ -+ Г, -зГ «- -«Г, (4) -зР-« Г, «Г «- Г, (5) -зГ -+ Г «- ч~Г, (6) -з-юГ «- Г, (7) -«Г -+ -+ Г «-Г1 Гч Г « — Г), (8) «-(Г ч Г) -+ Р, (9) «-(Гч Г) ++ Г; з) технология обоснования этой теоремы абсолютно аналогична технологии обоснования теоремы 8.22, ж.
При этом используются выводимости из задач 8.9, ф и 8.16, в и правило Клини удаления дизъюнкции (задача 8.20, д); 286 и) (1) Г «- Г, (2) Гл 6 «- Г, (3) Гч (Гл 6) « — Г, (4) * (Гч (Гл л 6)) -+ Г, (5) Г «- Рч (Г л 6), (6) «-Г-+ (Г ч (Гл 6)), (7) «- (Рч ч(Р л 6)) ++ Г; к) аналогично предыдущей теореме; л) (1) -ъ(Гч 6), Г«- Гч 6, (2) «(Гч 6), Г«- ~(Рч 6), (3) «(Гч ч 6) «- ~Г, (4) «(Гч 6), 6 «- Гч 6, (5)-й,Гч 6), 6 «- М(Гч 6), (6)«(Гч ч 6) « — -чб, (7) ~(Г ч С) «- ~Г л чб, (8) « — -«(Г ч С) -+ («Г л л ~6), (9) ~Г л -«б «- -з(Г ч 6), (10) «-(«Г л -чб) -+ -з(Г ч 6), (11) «--«(Г ч 6) ++ («Гл ~6); м) (1) ~Г, Гл б «--«Г, (2) «Г, Р л 6 «-Г, (3) -чГ «- -«(Г л 6), (4) -зб, Г л 6 «--зб, (5) ~6, Г л 6 «- 6, (6) ~6 «-~(Г л 6), (7)~Гч -зб «--з(Гл 6)„(8) «-(«Гч -зб) -+ -«(Гл 6), (9) продолжите вывод самостоятельно; н) (1) Г-+ 6, -з 6, Г «- Г-+ 6, (2) Г-« 6, ~ б, Г «- 6, (3) Г-+ 6, -зб, Г «- -зб, (4) б, -~б «- -з(Г -+ 6), (5) Г -+ б, «б, Г «- -«(Г -+ -+ 6), (6) Г -+ 6, «б « — -«Г, (7) Г -+ 6 «- -з б -+ -чГ, (8) «- (Г -+ -+ 6) -+ (~6 -+ -тГ), (9) продолжите вывод самостоятельно; о) (1) ~«Г «- Г, (2) Г, -чГ «- Г, (3) Г, -~Г «- -«Г, (4) Г «- ~-«Г, (5) «- -гзГ -+ Г, (6) «- Г -+ «~Г, (7) «- -«-«Г ++ Г.
1. Предикатами являются выражения а), б), г), д), е), з), и). 3. Истинны высказывания а), в), д), е), ж), и), к). 5. Высказывание (~х)(Р(х)) эквивалентно конъюнкции Р(а,) л л Р(а,) л ... л Р(а„), а высказывание (Зх)(Р(х)) — дизъюнкции Р(а,) ч Р(а~) ч ... ч Р(а„'). 6. а) (3, 6, 9); б) М; в) И; г) М; д) И; е) (-3, 2); ж) (О, О); з) ((1, 3), (1, 5), (1, 7), (2, 3), (2, 5), (2, 7), (3, 5), (3, 7), (4, 5), (4, 7), (5, 7)); и) ((2, 4), (2, 6), (3, 6), (2, 2), (3, 3), (4, 4), (6, 6)); к) ((-2, 11), (4, 9), (4, 11), (8, 7), (8, 9), (8, 11)). 7. а) Луч х < 3 с началом в точке 3 (без самой точки 3), уходящий в — е; б) две точки -4 и 4; в) открытый отрезок 1-2, 2[; г) два луча: х < -2 и х > 2, оба без начальных точек; д) два луча (оба с начальными точками): х < 3 и х > 5; е) открытый отрезок ] — 5, -11; ж) замкнутый отрезок 1-8, 2); з) вся числовая прямая; и) два луча х < -5 и х > -1; к) вся числовая прямая.
8. а) Биссектриса первого и третьего координатных углов; б) две взаимно-перпендикулярных биссектрисы координатных углов; в) окружность радиуса 3 с центром в начале координат; г) И; д) часть плоскости, заключенная внутри параболы (включая и саму параболу) с вершиной в начале координат, ветви которой направлены вверх; е) две ветви гиперболы в первой и третьей координатных четвертях; ж) полуплоскость, ограниченная прямой, проходящей через точки А(0, 2) и В(6, О), включая саму эту прямую; з) вся плоскость, за исключением биссектрисы вто- 287 рого и четвертого координатных углов; и) две оси координат; к) логарифмическая кривая, проходящая через начало координат.
9. Тождественно истинными являются предикаты 9.4, а, г, д, и, л, 9.6, б, г, 9.7, з; тождественно ложными являются предикаты 9.4, в, 9.6, в, д, 9.8, г. 10. а) Окружность (без точек А и В) с центром в середине отрезка [АВ[ радиуса, равного половине длины этого отрезка; б) полуплоскость, ограниченная прямой 1, содержащая точку А и не содержащая прямую 1; в) единственная точка, являющаяся точкой пересечения прямой ! с серединным перпендикуляром к отрезку [АВ[; г) отрезок [А,В,[, симметричный с отрезком [АВ[ относительно точки С; д) серединный перпендикуляр к отрезку [АВ[; е) окружность с центром в точке В данного радиуса; з) отрезок [АВ[; и) луч, лежащий на прямой (АВ), с началом в точке В, не содержащий точки А; к) парабола с фокусом А и директрисой !.
11. а) И; б) В~(2); в) (2); г) четвертая координатная четверть (замкнутая); д) все точки плоскости, кроме точек второй четверти„включая полуоси Оу' и Ох; е) все точки плоскости, кроме точек первой четверти, включая полуось Ох', исключая полуось Оу', ж) полуинтервал [-3, 2[ числовой прямой; з) И; и) нижняя полуплоскость, объединенная с верхней полуокружностью радиусом 1 с центром в начале координат; к) внутренность полосы, ограниченной прямыми х = -3 и х = 3.
12. д) (1, 3, 4, 5, 7, 9, 11, 13, 15, 16, 17, 19); е) (2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20); ж) (1, 2, 4, 8, 16, 17, 18, 19, 20); з) (1, 2, 3, 4, 5, 6, 7, 8, 9, 16); и) (16, 20); к) М. 13. а) Р; б) Р' гъ Д'; в) Р' и Д'; г) Р" о Д', д) ( Р' и Д') гь л (Д' и Р"). 14.а) У;б) Р';в) У;г)Р',д) Р',е) У;ж)Р',з) У; и) Р', к) У.
15. а) Р' и (Д' г~ В'); б) Р' г~ (Д' о В'); в) Д', г) Д', д) Р' и Д'; е) Р'; ж) Р' гь Д' л В'; з) Р' и Д' н Я'; и) Д' г~ лЯ', к) Р'и Д'. 16. Равны множества истинности предикатов б), г), д), ж), и). 17. а) Р' = Д' = М; б) Р+ г~ Д+ = И; в) Р' с Д', г) Р' о Д' = М; д) Р' = Д' = И; е) Р' = И, Д' = М; ж) Р" с Д', з) Р' = М, Д' = И; и) Р' г~ Д' = И и Р' и Д' = М т.е.
подмножества Р' и Д' множества М образуют разбиение множества М; к) Р' = Д'. 20. а) Р'= И, Д'= М; б) Д'= И; в) Р'= М, Д'= И; г) Р'~ М Д'~ М, Р'л Д'~И;д) Р'г~ Д'; И, Р'~ Д';е) Р'с. Д'либо Р' ~ М, либо Д' , -И; ж) Р' ~ И или И ~ Д' ~ М; з) Р' ~ И, Д'; ~И, Р'л Д"; И;и) Р'л Д"=И,причем Р'~Ияли Д'~М; к) Р'~И, Д'~МилиР', -М, Д'~И. 288 21.
а) Р'= И, Д'= М; б) Д' с Р' или Р' г~ Д'~ И, Р' 1ь Д'; в) Р'г Д'~И, Р'о Д'~М;г) Р'=И;д) Р'=И, Д'=Мили Р' = Ц' = И; е) Р' о Д' ~ М, Р' и Д' ~ И или Р' = М, Д' = И; ж) Р' и Ц' = М, Р' л Д' = И; з) Р' = Д' = И или Р' ~ И, Д+ ~ И; и) Р'н Д'=М;к) Р'= Д'. 22. а) Равносильны на У и )т"; б) на множестве Я не равносильны; на множествах Д, У, Фравносильны; в) равносильны на всех множествах; г) равносильны лишь на )т'; д) равносильны лишь на Ф; е) равносильны на всех множествах; ж) равносильны лишь на Ф; з) равносильны на всех множествах; и) равносильны лишь на )т'; к) равносильны на всех множествах.
23. а) Любое множество чисел, кратных одновременно 3 и 7, или не кратных ни 3, ни 7; б) всякое множество чисел, не содержащее следующих трех чисел: 2, (1+ Г31)/2, (1 — /31)/2; в) множество всех городов, располагающихся как на берегу Волги, так и на берегу Свияги (например, Ульяновск), или множество городов, не располагающихся ни на берегу Волги, ни на берегу Свияги; г) любое множество нечетных составных чисел или любое такое множество с добавленным числом 2 (если считать число 2 и простым, и четным); д) например, множество всех прямоугольников; е) например, множество всех ромбов или множество всех четырехугольников с неперпендикулярными диагоналями; ж) множество всех равнобедренных треугольников или любое его подмножество; з) множество всех чисел, делящихся на 9, или множество всех чисел, не делящихся на 3; и) множество всех кубов или множество геометрических тел, не являющихся параллелепипедами; к) множество геометрических тел, не являющихся ни цилиндрами, ни конусами.
25. а) Из первого следует второй; б) из второго следует первый; в) ни один из предикатов не является следствием другого; г) из первого предиката следует второй, а из второго — первый, т.е. предикаты равносильны; д) из первого предиката следует второй; е) из первого предиката следует второй, а из второго — первый, т.е. предикаты равносильны; ж) ни один из предикатов не является следствием другого; з) из второго следует первый; и) из первого следует второй; к) из первого следует второй. 26. а) Любое подмножество множества Ф, не содержащее нечетных чисел, делящихся на 3; б) любое множество чисел, не содержащее числа -1; в) любое подмножество множества Ф, все нечетные числа которого являются квадратами натуральных чисел; г) множество всех четырехугольников; д) объединение множества всех четырехугольников, не являющихся параллелограммами, с множеством всех ромбов; е) объединение множества всех русских ученьгх-математиков с множеством всех иностранных ученых, не являющихся математиками; ж) открытый беско- 289 нечный полуинтервал (-о», 5); з) множество всех натуральных чисел, делящихся на 9; и) множество всех параллелепипедов; к) любое множество геометрических тел, в котором нет ни одного цилиндра.
27. Не являются формулами в), ж). 28. а) х связана; б) х связана, у свободна; в) в первом вхождении х свободна, во втором — связана; г) х связана; д) в первом вхождении х связана, во втором — свободна, у связана; е) х и у связаны, ~ свободна; ж) и в первом вхождении связана, во втором — свободна, и и ~ связаны; з) х в первом вхождении связана, во втором — свободна, у в первом вхождении свободна, во втором — связана, ~ свободна; и) х связана, у в первом вхождении свободна, во втором — связана, ~ свободна; к) х связана, у в первом вхождении связана„во втором — свободна, ~ свободна. 29.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
