В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 54
Текст из файла (страница 54)
25. Выполнимы (и опровержимы) б), в), ж), з), и), к); тавтологии — а), г), е); противоречие — д). 26. Формула обратится в истинное высказывание, если сделать, например, следующую подстановку: а) Р = 1, б) Р = Д = 0; в) Р= = 1, Д = 0; г) Р = Д = 1, В = 0; д) Р = Д = 1; е) Р Д вЂ” любые; ж) В = 1; з) Р = 0; и) Р = 1; к) Р = Д = 1. 27. Формула обратится в ложное высказывание, если сделать, например, следующую подстановку: а) Х = У = 1; б) Х = У = О, У = 1; в) Х = У= 1, У = 0; г) У = У = К= Ж'= О, У = 1; д) Р, Д— любые; е) Р = 1, О = 0; ж) Р = Д = 1; з) Р = Л = 1; и) Р = Д = 1, В=О; к) Р=1, 0=5=0.
33. Справедливы утверждения а), в), з); достаточность выполняется для утверждений г), е), ж), и), к); для утверждений б), д) не выполняется ни необходимость, ни достаточность. 34. Являются: 2), 4), 6), 7), 9). 258 35. Все обратные следования неверны. Зб. Все обратные следования неверны. 37. а) Нет; б) первая следует из второй„в) первая следует из первая следует из следует из первой; второй; г) вторая следует из первой; д) нет; е) второй; ж) вторая следует из первой; з) вторая и) нет; к) первая следует из второй. 2, 1; и) 3, 5, 2, 4, 1; к) 1, 3, 5, 2, 4.
40. Верны следования в), г), е), ж), з), и), к) 41. Выполняются. 56. а)Хч У; е) -чХч-зУ; б) Хч-чУ; ж)~Хч-зУ; в) (Хч У) л (-~Хч -з У); з) -~Хч У; г) (Хч Уч2) л(~Хч ~У); и)Х; д) ХчУ; к) -чХч Уч-чУ 57. а) (-чХч (Ул Х)) л -чУ; б) -чХч Уч-чУ; в) о'л У л (-т Уч Х); г) -з 1"л (Хч -~Я); д) (Хч (-ч Ул Х) ч -ч2) л (-ч Уч -зЯ); е) -~Хл -~Ул (-зУч Т); ж) (Х л Ул -зЯ) ч (-зХ л (-П ч Я)) ч ~ У; з) Хл Ул-~У; и) ХчУ; к) .чХл -чУ.
58. а) -ч(-чХл Ул -зУ); б) ~(~Хл -зУ); в) -ч(-зХл Ул -чХ); г) -(Хл (Ул г)); д) (- Хл -(Ул .К)); е) -з(-з(Хл -зУ) л -ч(Ул У)); ж) -з(-ьХл -з У); з) -ч(-з(Хл -з(Ул -чУ) л -ч(-чУл У)); и)-(Хл-г) л У; к) -з(-чХл Х). 59. а) Хч-юУчУ; б) Хч У; в) Хч-зУчУ; г) -зХч-ч(-зУчУ); д) Х ( Учг); е) ~(тХч У) ч -з(ч Уч ~У); ж)хч У; з) ( ХчУ)ч ( УчУ)ч-з(Уч~У); и) -и(-ч(-зХч Х) ч -зУ); к) Х 259 38.
Справедливы а), б), е), з), к). 39. а) 2, 5, 4, 3, 1; б) 2, 5, 1, 4, 3; в) 2, 5, 3, 4, 1; г) 3, 2, 1, 5, 4; д) 3, 4, 2, 1, 5; е) 4, 1, 5, 2, 3; ж) 1, 5, 2, 4, 3; з) 4, 5, 3, ж) (-~Х ч У) л (Хч -з Уч -чЯ); з) (Хч У) л (-~Хч -~ Уч У); и) -чХч-чУ; к) Х 3. а) (-ч Х л ~ 1' л У л -з Т) ч (Х л У л У л -~ Т); б) (Хл Ул У) ч (Хл -зУл Я) ч (Хл Ул ~Я) ч (~Хл Ул ~У) ч ч (-чХл -~ 1'л Я) ч (Хл -~ У л -й!) ч (-чХ л -з Ул -чЯ); в) (Хл Ул Я) ч (-~Хл Ул У) ч (Хл -~Ул Я) ч (Хл Ул -зУ) ч (~Хл л -ч У л У) ч (-~Х л У л -чЯ) ч (Х л -з 1'л -~У) ч (-~Х л -ч Ул -~е); г) (Х л Ул Я) ч (Х л -з Ул У) ч (Хл Ул -зЯ) ч (Х л -ч Ул -зЯ) ч ч (-зХл Ул -зУ) ч (-чХ л -з 1'л -~Я); д) (Хл Ул Я)ч~тХл Ул У) ч (Хл -зУл У)ч (Хл Ул -~У) ч (-зХл л-чУл Я); е) (-чХл Ул 2) ч (Хл -з Ул е) ч (-~Хл -з Ул Я) ч (-~Хл Ул ~Я) ч ч (Хл ~ Ул ~Я) ч (-~Хл -~ Ул -~Я); ж) (Х л Ул У) ч (Хл -з Ул Я) ч (-чХ л ~ Ул Я) ч (чХ л Ул -~Я) ч ч (-~Хл -з Ул -чЯ); з) (Хл Ул Л) ч (-~Х л 1'л У) ч (Х л -ч Ул Л) ч (Х л -~ Ул ~У) ч ч (-~Х л Ул-~Я); и) (-зХл У) ч (-~Хл -~У) ч (Хл -~У); к) (Х л Ул У) ч (Х л Ул -~У) ч (Х л ~ Ул Я) ч (Хл -~ Ул ~Я).
4. б) Хч-~Уч-~У; в) не существует; г) (Хч Уч -чЯ) л (Хч -Лч -~Я); д) (Хч Уч У) л (Хч -М ч Я) л ~~Х ч -М ч Я); е) -~Хч -з Уч У; ж) (-ьХч Уч Я) л (-зХч -7 Уч Я) л (Хч -Л ч -ь2); з) (Хч Уч Я) л(Хч Уч ~2) лЛ;~Хч -~Уч 2); и) -~Хч-~У; к) (Хч Уч Я) лЛХч Уч -~Я) л (Хч ~ Уч 2) л (Хч -~ Уч -~Я). 5. а) ~Хл -~У; е) Хл -чУл -~Ел Т; б) -чХл У; ж)-чХл 1'л -зУл -~Т; в) Хл 1', з) -зХл -зУл -~Ел Т; г) Хл -~Ул -~У; и) Хл -~Ул У; д) ~Х л з У л У; к) Х л У л е л ~ Т.
6. а) (-чХл -чУ) ч (Хл У); б) Хл -~У; в) (-~Х л У л -~Я) ч (Х л -~ Ул У) ч (Х л Ул У); г) (-~Хл Ул Я) ч (Хл 1'л -~У); д) (Х л -~ Ул -~У) ч (-чХ л Ул ~Я) ч (~Х л -~ Ул Я); е) (-чХл У л Я) ч (Х л -~ Ул У) ч (Х л Ул -чУ) ч (Х л Ул Я); ж) (Хл ~Ул 2) ч (-~Хл Ул -~У) ч (-~Хл -зУл ~Я); з) (~Х л У) ч (Х л -~ У) ч (-~Х л -~ У); и) (Х л У л -~ У л -~ Т) ч (-~Х л ~ У л Х л Т); к) (~Хл Ул -~Ул Т) ч (Хл ~1 л Ул-~Т)ч(Хл-~Ул-чУл ~Т) ч ч (Хл Ул Ул-~Т). 261 д) Х++ У; е) -з(Х++ 2); ж) ((Х л У) ~ -1 У) л (-1(Х л 2) ~~ У); з) У; и) -1Х; к) (Хл ~У) и У. 20. а) Х; б) (Хл У) ч (Ул .2) ч (2'л Х); в) (-1Х л ~ Ул Я) и (-1Х л Ул -~Л) и (Х л -ч Ул -~Я); г) (-~Хл -1У) ~~ (-зУл -зЯ) ч(-зУл -1Х); д) Х г; е) =г); ж) =г); з) Х л -з(У++ Я); и) -ч(Х++ У); к) У++ У. 23.
Тождественно истинны формулы а), д), е); остальные— тождественно ложны. 26. Равносильны между собой формулы в задачах а), б), г), д), е), з), и); в остальных — не равносильны. 27. а) -1Х ч -1 У, любая тавтология; б) Х-+ У, любая тавтология; в) Х~ У, любая тавтология; г) -1Х, -1Х ~ У, -1Х ~ -1 У, любая тавтология; д) таких нет; е) Х-+ У; ж) любая формула; 3) ~Х У Хн У, -1Хл У, Х-+ У, -1(Хл У), ~(Х++ У), любая тавтология; и) -1 У, У-+ Х -1(Х л У), любая тавтология; к) любая формула.
28. а) (Х-+ У) л У; б) -тХ~ У, -~Х~ Уч У, -1Хч -1 Уч У, любая тавтология; в) Х- -У У-+-Х, У- (-Х~-а),Х- (У- -г),Х-+(У-+ Е), 2'-+ (У-+ Х), (Х -+ (У-+ Я)) а (У -+ (У вЂ” э Х)), любая тавтология; г) таких нет; д) (-~Хл -~Я) ч У, (Х++ 2) ч У, У-+ У, У-+ (Хч У), Х-~ У Х-+ -+ (Уч 2), Х-+ (У-+ У), любая тавтология; е) любая тавтология; ж) (Х ~ У) л ~У; з) Х-+ У, Х вЂ” ~ (У ч 2), Х-+ (У-+ У), любая тавтология; и) таких формул нет; к) любая формула. 29.
а) У, Х-+ У; б) Х++ У; 264 д) Хл У -~Хл -~У; е) таких нет; ж) -~Хл У, -~Хл -~У; з) Х У, Хл У, -з(Х-+ У),-~(У-+ Х), -~(Х++ У); и) таких нет; к)хл УХл-К 40. а) Таких нет; б) -~Х л -~ У л 2; -зХ л -~ У л -)У; в) Х Ул У, Хл Ул ~У; г) Хл Ул -~У, -~Хл Ул -~У; д) Х У У, Хл -~Ул -чУ; е) отсутствующие в СКН-форме совершенные дизъюнктивные одночлены:зХч Уч У, Хч Уч зУ, -зХч-зУч 2; Хч -П ч зУ; ж) отсутствующие в СКН-форме совершенные дизъюнктивные одночленък Хч Уч 2; Хч з Уч -зУ -зХч -~Уч -~У; з) чХл Ул ъе, Хл Ул -~У; и) отсутствующие в СКН-форме совершенные дизъюнктивные одночлены: Хч Уч У, Хч Уч -~У, зХч -Лч У, -~Хч -~Уч-зУ; к) Хл Ул У, -чХл Ул Е 41.
а) ~У, -~У л У, -ъс л -~ К; б) -~Х, -з У, -~Х л -з У, -~Х ч -~ У, -зХ л У, Х л ч У, -~(Х+~ У); в)ХлУ; г) -ч(Х-+ У), -з(Х-+ У), -з(Х++ У), -з(Хч У), -зУ, -зХ, -з(Хл У); д) Х л Ул У, Х л Ул -зУ, Хл У Хл з Ул У, Х л е, (Хл -з Ул 2) ч ч (Хл Ул-~У), Хл (Уч Я); е) -з(У -+ Х), -ч(Х ч 2), -зХ; ж) Хл — Ул г, Х.
У. -г, Х (У гК Хл — Ул — г, Хл .г, Х л -~ У (Х л -ч У) ч (Х л -~У); з) Х л У, ~(У-+ Х), У, -~(Х ч У), Х++ У -зХ, Х-+ У; и) У л У, -~ У л У, -~У л ~У, У, ~ 1; У++ У, У-+ У; к) Х л Ул У, Х л -з Ул У, Хл У, -~Хл Ул У, Ул У, (-~Хл Ул 2) ч ч (Х л -~ У л Я), (Х ч У) л У. 42. а) Хл Ул -~2; Хл Ул У, Хл У, любая тождественно ложная формула; б) Хл Ул У, ~Хл Ул У, -~Хл -~ Ул У, (-~Хл -~ Ул У) ч (Х л Ул л 2), -зХл У, Ул У, .с л (-~Хч У), любая тождественно ложная формула; в) (Хч У) л -ч У ((Хч У) л -~ У) ч (Х л У); г) таких формул нет; д) -~Хч -~ У, -~Хч -~ Уч У, -зХч -ч Уч ~У, любая тавтология; е) -~Хл )'л У, Хл -~Ул У, Хл Ул -~У, Хл (У++ 2), Ул (Х++ ++ Я), У л (Х++ У), (-~Х л У л г) ч (Х л -~ У л У) ч (Х л У л ~У), любая тождественно ложная формула; ж) Хл -) Ул -~У, -)Хл Ул У, (-)Хл Ул У) ч (Хл -~ Ул ~Я), любая тождественно ложная формула; 2б7 з) Х л Ул У, -|Х л Ул У, У л Х, -1Х л -1 Ул У, (-~Х л -1 Ул -зУ) ч ч (Хл Ул Я), (-зХл-~Ул.8) ч (~Хл Ул У), Ул (Х-+ Х), любая тождественно ложная формула; и) ~Хл У, -~Хл (У-+ 2); к) Хл Ул -~У, ~Хл Ул -~У, Ул ~У, ~Хл -~Ул ~У, (-зХл -~Ул л У) ч (Х л Ул .з2), -1 Ул -~У, (Х-» У) л -чУ любая тождественно ложная формула.
$3 3. б) «Если последовательность не ограничена, то она не сходится»; в) «Если углы при основании треугольника не равны, то треугольник не равнобедренный»; з) «Если последовательность не имеет предела, то она или не монотонна, или не ограничена», 5. 6) Теорема, противоположная обратной: «Если а не делится на с, то либо а не делится на Ь, либо Ь не делится на с»; г) обратная теорема: «Если одно из слагаемых делится на некоторое число и сумма делится на это число, то и второе слагаемое делится на это число», Противоположная теорема: «Если одно из слагаемых не делится на некоторое число, то либо другое слагаемое, либо их сумма на это число не делится».
Теорема, противоположная обратной: «Если сумма не делится на некоторое число, то одно из слагаемых не делится на это число»; д) обратная теорема: «Если два угла опираются на одну и ту же дугу и равны между собой, то они вписаны в окружность». Противоположная теорема: «Если два угла не вписаны в окружность, то они либо не опираются на одну и ту же дугу, либо не равны между собой». Теорема, противоположная обратной: «Если два угла не равны между собой, то они либо не вписаны в окружность, либо не опираются на одну и ту же дугу»; ж) две обратные теоремы: «Если хорды, принадлежащие равным кругам, одинаково удалены от центров этих кругов, то такие хорды равны», «Если равные хорды одинаково удалены от центров соответствующих кругов, то они принадлежат равным кругам»; з) две обратные теоремы: «Если две прямые перпендикулярны одной и той же плоскости, то они параллельны между собой».
Вторая обратная теорема формулируется так же, как исходная теорема; и) обратных и противоположных теорем нет. 6. У-+ (Х, л Хз) ~= (Х, л У) -+ Х~,' У-+ (Х, л Хз) ~ (Хг л У)-+ Х~', (Х~ -+ У) -+ Хз ~= (Х~ л У) -+ Х~', (Х~ -+ У) -+ Х~ ~= (Х~ л У) -+ Хн 7. а) Две теоремы, обратные данной, вида (А, л А, л В) -+ Аз и (А, л А, л В) -+ А, формулируются как одна: «Если одна из двух параллельных прямых перпендикулярна третьей, лежащей в той же плоскости, то и другая ей перпендикулярна», Две теоремы, противоположные данной, также формулируются как одна: «Если две прямые не перпендикулярны, то они не могут лежать в одной плоскости с третьей прямой, которая была бы параллельна одной 268 из них и перпендикулярна другой».
Теорема, противоположная обратной: «Если две прямые не параллельны, то они не могут лежать в одной плоскости с третьей прямой, перпендикулярной им обеим»; б) одна обратная теорема вида (В л А, л А,) -+ А„ где В: «а 1 а», Ар «-~(а ~ а)», не выражает ничего нового, так как сводится к утверждению В -+ А„которое непосредственно вытекает из определения параллельности прямой и плоскости; в) одна обратная теорема: «Если прямая, лежащая в одной из двух пересекающихся плоскостей, параллельна линии их пересечения, то она параллельна другой из этих плоскостей».
8. б) Обратная теорема: «Если диагонали прямоугольника взаимно-перпендикулярны или делят углы пополам, то этот прямоугольник — квадрат». Противоположная теорема: «Если прямоугольник не является квадратом, то его диагонали не перпендикулярны или не делят углы пополам». Теорема, противоположная обратной: «Если диагонали прямоугольника не перпендикулярны или не делят углы пополам, то четырехугольник не квадрат»; г) одна обратная теорема: «Если сечение пирамиды плоскостью делит боковые ребра и высоту на пропорциональнные части, то сечение параллельно основанию».
9. б) Обратная теорема «Если параллелограмм есть ромб или квадрат, то его диагонали взаимно-перпендикулярны». Противоположная теорема: «Если диагонали параллелограмма не взаимно- перпендикулярны, то он не ромб и не квадрат». Теорема, противоположная обратной: «Если параллелограмм не ромб и не квадрат, то его диагонали не взаимно-перпендикулярны»; в) одна обратная теорема формы (В, ~ Вз) -+ А. 10. а) Теорема имеет форму (А, л Аз) -+ (В, л Вз), где А,: «а 1 Ь», А~.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
