В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 55
Текст из файла (страница 55)
«с1 д», В,: «а = Ь», В;. «с = Н». Одна обратная теорема: (В, л Вз) -+ -+ (А, л Аз). Теорема, противоположная обратной: (-~В, ~ -зВз) -+ -+ (-зА, ~ -зА,); б) теорема имеет ту же форму, что и теорема из предыдущего пункта, где А,: «а л 'р = Ь», Аг. '«а (! Ь», В,: «а 1 а», Вз.' «а 1 р». Одна обратная теорема: (А, л В, л В,) -+ А„в) теорема имеет форму (А~ л А~) -+ В, где А~'. «-~(а ~ а)», А~. '«(ЛЬН(Ь ~ а) л л (Ь Ц а))», В: «а ~! а». 16. а) «Если А, то В»; б) «Если В, то А»; в) «Если В, то А»; г) «Если А, то В». 17. а) «Если функция дифференцируема в точке, то она непрерывна в этой точке»; б) «Если четырехугольник является прямоугольником, то его диагонали равны»; в) «Если многочлен г(х) делится на двучлен х — а, то а — корень многочленаЯх)»; г) «Если целое число оканчивается цифрой О или цифрой 5, то оно делится на 5»; д) «Если две прямые на плоскости перпендикулярны одной и той же прямой, то они параллельны»; е) «Если комплексные числа равны, то равны, соответственно их действительные и мнимые части»; ж) «Если коэффициенты квадратного уравнения— 269 действительные числа, то оно имеет не более двух действительных корней»; и) «Если каждое слагаемое четно, то и сумма четна»; к) «Если треугольники равны, то они равновелики».
18. Истинны высказывания б), г), е), з), к); остальные— ложны. 19. а) Необходимо и достаточно; б) достаточно, но не необходимо; в) достаточно, но не необходимо; г) достаточно, но не необходимо; д) достаточно, но не необходимо; е) необходимо и достаточно; ж) достаточно, но не необходимо; з) необходимо, но не достаточно; и) необходимо и достаточно; к) необходимо и достаточно; л) необходимо и достаточно.
20. а)А++ В, С«-»А,А++ Р, Е»»А, К вЂ” »А, С-э В, В«»Р, В»+Е, К-+ В, С » Р, С-+ Е, С ++ К, Р ++ Е, К-+ Р, К-+ Е (А +» Р обозначает А-+ В и В-+А); б) для А достаточны В, С, 1), Е, К, необходимы В, Р, Е, необходимы и достаточны одновременно В, Р, Е.
21. а) А -+ В, А — » С, А -э 1), А -+ Е, С»+ Р, С++ Е, Р «-» Е; б) для Е достаточны А, С, Р, необходимы С, Р, необходимы и достаточны одновременно С, Р. 22. а) 1) «Всякие вертикальные углы равны»; 2) «Если углы вертикальные, то они равны»; 3) «Углы вертикальные, только если они равны»; 4) «Для того чтобы углы были вертикальными, необходимо, чтобы они были равны»; 5) «То, что углы вертикальные, достаточно для их равенства»; 6) «Те углы, которые вертикальны, равны»; 7) «Вертикальными могут быль только те углы, которые равны»; 8) «Углы равны тогда, когда они вертикальные»; 9) «Углы могут быть вертикальными только тогда, когда они равны»; 10) «Если углы не равны, то они не вертикальные»; 11) «Вертикальные углы содержатся среди равных углов».
23. б) «Окружности одного и того же радиуса г касаются данной прямой в данной плоскости тогда и только тогда, когда их центры лежат на прямых той же плоскости, параллельных данной и находящихся по обе стороны от нее на расстоянии г»; в) «Число будет корнем уравнениями(х) = я(х) тогда и только тогда, когда оно будет корнем уравнения, получающегося из данного прибавлением к обеим его частям одного и того же числа т». 24. а) «Для того чтобы импликация была истинной, достаточно, чтобы ее посылка была ложной»; б) «Для того чтобы импликация была ложной, необходимо, чтобы ее следствие было ложным»; в) «Для того чтобы импликация была ложной, необходимо и достаточно, чтобы ее посылка была истинна, а следствие ложно»; г) «Для того чтобы импликация была истинна, необходимо и достаточно, чтобы ее посылка была ложна или следствие истинно».
25. Следуют высказывания а), в). 26. Истинны высказывания а), б), г), е). 27. б) Воспользуйтесь тавтологией ((Р л Д) -+ Я) -+ ((Р л л ~В) -+ -~Д); в) воспользуйтесь законом противоположности 270 (задача 1.28, ж); г) воспользуйтесь тавтологией задачи 1.28, Р и законом де Моргана (задача 1.28, 9)); д) воспользуйтесь тавтологией задачи 1.28, р. 29. Если капитан получает специальное указание, то должен покинуть порт; если капитан либо получает специальное указание, либо покидает порт, то он лишается впредь возможности захода в этот порт.
30. Нам удастся получить продовольствие в том и только в том случае, если нам будет угрожать смерть от голода; Если нам удастся получить продовольствие или нам будет угрожать смерть от голода, то мы попытаемся прорвать кольцо окружения. 31. Восьмой класс пойдет в поход в том и только в том случае, если будут приобретены новые палатки. 33. Да. 34. Да. 37. Нет. 38. Нет; нет. 39. Да. 40. Да. 41. Нет.
42. Нет. 43. Да. 46. «Число не делится на 2 или не делится на 5, или делится на 10»; «Число делится на 2 или не делится на 5, или делится на 10»; «Число делится на 2 или не делится на 5, или не делится на 10»; «Если число делится на 5, то оно делится на 10»; «Число не делится на 5 или делится на 2 тогда и только тогда, когда оно делится на 10»; «Если число делится на 5, то оно делится на 2»; «Если число делится на 5, то оно делится на 2 и на 10». 49. «Данный четырехугольник не ромб, но его можно вписать в окружность».
50. «Если целое число больше 2 и четное, то оно является составным». 51. а) «Данный четырехугольник не ромб»; б) «Четырехугольник не ромб, но его диагонали равны». 53. «Если целое число делится на 5, то оно оканчивается цифрой 0 или цифрой 5». 55. Кляксу на скатерть поставил Витя. 56. Нет, условиям задачи удовлетворяет как Витя, так и Коля.
58. Ершов, Дронов, Глебов, Ветров, Белов, Адамов. 59.А,Е, С,Р. 60. Есть две возможности составления расписания: 1) математика, литература, история; 2) история, математика, литература. 61. В экспедицшо следует взять: Š— биологом,  — гидрологом, С вЂ” радистом, Р— врачом, Р— синоптиком, Н вЂ” механиком.
271 1. 4. 2. 16. 3. 2". б. 2. 7. з) Это есть частный случай предыдущей задачи при й = 3. Ответ: 2" з+ б; к) (1/3)(2" — 1), если а — четное; (2/3)(2" '+ 1), если и — нечетное; м) 2ь+ 2" "— 1. 8. а) 11111011; б) 00100001; в) 11001111; г) 00000010; д) 01111110; е) 11100001; ж) 00111001; з) 00010011; и) 11100111; к) 11111111. 9.
Не равны функции из в), ж), и), к); в остальных парах— равны. 11. Нет. 12. Нет. 13. Да. 14. Нет. 20. а) х~ у= (х'. у')', б) х-+у= (х у')', в) х ++ у = (х у')' . (х'. у)', г) х+у=((х у')' (х' у)')'; д) х ~ у = (х у)'; е) х4 у =х'. у'; ж) х-/~ у = х у'. 23. а)х'=х[х; б) х у = (х 4 х) 4 (у 1 у); в)хну=(х ьу) 4(х ьу); г) х -+ у = ((х 4 х) 4 у) 4 ((х 4 х) 4 у); д) х/» у = [((х [ х) 4 у) 4 ((х 4 х) 4 уй 4 [((х 4 х) 4 у) 4 Их 4 4 х) 4 у)[; е) х ! у = ((х 4 х) 4 (у 4 у)) 4 ((х' 4 у) 4 (х 4 у')); ж) [((х 4 х) 4 у) 4 (х 1 (у 4 у))[ 4 [((х 4 х) [ у) 4 (х 4 (у 4 у))[. 24.
а) х ~ у = х" ч у = х' -+ у; б) х у=(х-+у')'; в) х ++ у = ((х-+ у) -+ (у -+ х)')', г) х + у = (х -+ у) -+ (у -+ х)', д) х [ у = х -+ у', е) х4 у= (х'-+у)'. б. а) ху+ х~+ у+ ~; б) уа+ х+ у+ 1; в) ху~+ ху+х~+ х+у+ г+ 1; г) у~+ х+ ~+ 1; 272 д) «у2+у1+«+ ц е) ху~+ у~+ х+ ~+ 1; ж) у~+ х+ у; з) «у~+ х~+ 1; и) ху~+ ху+у~+ х+ г+ 1; к) ху + у~ + х + 1. 7. а) Верно; б) верно; в) неверно; г) верно; д) верно; е) не- верно; ж) верно; з) неверно; и) неверно; к) верно. 8. а) 1; б) 1; в) 1; г) 1; д) О; е) 1; ж) 1; з) О; и) 1; к) О. 10. Восемь: О, 1, х, у, х', у', х + у, х ~-» у.
13. а) Нелинейна: у~ + х + у + 1; б) линейна: х + у + 1; в) нелинейна: ху + ~ + 1; г) нелинейна: ху~ + ху + х~ + у~; д) линейка: х+ 1; е) нелинейна: «у~+ «~+у«+ ~+ 1; ж) нелиней- на: «у~+ ху+ «~; з) нелинейна: ху~+ ху+ х~+ у~+ х+ у+ ~+ 1; и) линейна: х+у+ ц к) линейна: 1. 14. Например, если г(х, у, ~) = ху + у~ + у + 1, я(х, у) = ху, то Ь(х, у) = г(х, у, я (х, у)) = ху + у(ху) + у + 1 = у + 1. 18. «у+у«+ ~,«.
21. а) х'у'г ч х'у2' ч ху'2 ч ху~'ч ху~; б) х'у'~'ч«'у'г,чху~'ч«уч„' в) хуг,"чху~ч«уг,'чху~; г) х'у'~'чх'уг.ч «у'~'чху'~ чхук д) х'у '~'ч х'уг' ч «у'г.' ч х'ут. ч «ук, е) х'у '~'ч х'у'~ ч х'у~' ч х'уг. ч хуц ж) х'у'г'ч х'у~' ч х'у~ з) х'у'~' ч х'у~', и) х'у'~чху г ч ху к) х'у'~ ч х'у~' ч ху'Г.
27. Самодвойственны функции а), в), е), к); двойственные функции для остальных таковы: б) ху~ ч х'у~ ч ху'~ ч ху~' ч х'у'~; Г) х'у'~' ч «'у~; д) х'у'~' ч «'у ~ ч ху ~ ч ху'~ ч «у~ ч худ; Ж) х у~ ч ч ху~' ч хуг' з) ху~ ч ху~' ч «у~ ч ху~', и)«у~ ч хуг.'ч х~у' ч «у~'. 31. Таких функций шестнадцать: х; х'ут ч ху'г', ~'(х'у ч ху') ч х~ У; Х'У'т Ч ХУ~ ч ХУ', ~; Х'У 'т„Ч Х'У~' Ч ХУ'Г.' Ч ХУ~; Х'У '~ Ч «Уа ч Х'У; У '~' Ч ч «'у'~ ч ху~'; у'(х'~' ч !ф ч у(х'2 ч «Е '); ~'; х'~' ч х'у~ ч ху~', у', «'у' ч ч х'у«ч ху'г; х'у' ч х'у~' ч ху'~'; х'. Существенно зависят от всех своих аргументов десять. 32. Например, 7(х, у, ~, г) = х'~'!' ч х'у Оч уО'ч ху'г' ч ху~'в 44.
Ими будут такие линейные функции ар + а,х, + ... + а„х„, у которых нечетное число коэффициентов а;(!' ~ О) равно единице. 47. Не сравнимы: а), б), д), и); первый меньше второго: в), е), ж), з); в остальных — первый больше второго. 52. Монотонны функции а), в), е), к). 60. Такими функциями являются лишь функции О, 1, х. 61.
Нет, примером может служить функция ху ч у~ ч хг 62. Например, функции х, ху ч у~ ч х~. !О агоанн 273 63. х. 68. а) О, х; б) х, 1; в) О, ху, (х -+ у)', х, (у -+ х)', у, х+ у, х ч у; г) ху, х, у, х ч у, х++ у, у -+ х, х -+у, 1; д) х; е) ху, х, у, х ч у; ж) О, (х -+ у)', (у -+ х)', х + у; з) х ++ у, у -+ х, ху -+ у, 1. 17. а), в), г), д), е), з), и), к). 24.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
