Сборник задач по дискретке

12. Подобрать необходимую модель и записать следующие утвержде- ния и их отрицания:

1)xn – возрастающая последовательность;

2)xn – монотонная последовательность;

3)xn – ограниченная последовательность;

4)xn – ограниченная снизу последовательность;

5)xn – ограниченная сверху последовательность;

6)xn – сходящаяся последовательность;

7)xn – бесконечно малая последовательность;

8)xn – бесконечно большая последовательность.

13. В модели M = P (A); S(2) , где A – некоторое множество, S (x, y) Û " x Ì y", записать следующие утверждения:

1)x – пересечение y и z ;

2)x – объединение y и z ;

3)x = ;

4)x = A;

5)x – дополнение y .

14.Определить, являются ли следующие формулы истинными, ложны- ми, выполнимыми, опровержимыми в модели M = ¢+ ; S(3), P(3), E(2) , где

S (x, y, z) Û " x + y = z", P(x, y, z) Û " xy = z" , E (x, y) Û " x = y".

1)(S (x, y, z) Ù S (x, y,u)) É E (z,u);

2)"x"y "z"u((S (x, y, z) Ù S (x, y,u)) É E (z,u));

3)"x"y "z"u((P(x, y, z) Ù P(x, y,u)) É E (z,u));

4)$x S (x, y, y) É "x P(x, y, y);

5)$x S (x, y, y) É "x S (x, y, y);

6)$x S (x, y, y) É "x S (x, y, x);

7)$x S (x, x, y);

8)$y S (x, x, y);

9)$y (P(x, x, y) É S (x, x, y)).

51

15. Выполнимы ли следующие формулы :

1)	$xP (x);	6) P (x) É "yP ( y) ;
2) "xP (x);		7)	$xP (x) É P ( y) ;
3)	$x$y (P (x) Ù ¬ P ( y));	8) "x$y (P (x) É ¬ P ( y));
4)	$x"y (P (x, x) Ù ¬P (x, y));	9) "x$y ( ¬ P (x) É P ( y));
5)	$x"y (Q (x, y) É "zR (x, y, z));	10)	$y"x (P (x) É ¬ P ( y));
		11)	$y"x ( ¬ P (x) É P ( y))?
16. Будут ли общезначимы следующие формулы:
1) "xP (x) É P ( y) ;		4) ¬($xP (x) É "xP (x)) ;
2) P ( y) É "xP (x) ;		5)	$x"yQ (x, y) É "y$xQ (x, y) ;
3)	$xP (x) É "xP (x) ;	6) "x$yQ (x, y) É $y"xQ (x, y) ?
17. Доказать, что следующие формулы общезначимы:
1) ¬$xP (x) É ¬"xP (x);		2) "xP (x) É $xP (x) ;
3) "xP (x) É P ( y) ;		4) P ( y) É $xP (x) ;
5) "x"yP (x, y) : "y"xP (x, y) ;		6)	$x$yP (x, y) : $y$xP (x, y) ;
7) ("xA(x) ÙC) : "x (A(x) ÙC);		8) (C Ù"xA(x)) : "x (C Ù A(x));
9)	(C Ù $xA(x)) : $x (C Ù A(x)) ;	10)	($xA(x) ÙC) : $x (A(x) ÙC) ;
11)	(C Ú "xA(x)) : "x (C Ú A(x)) ;	12)	("xA(x) Ú C) : "x (A(x) Ú C) ;
13)	(C Ú $xA(x)) : $x (C Ú A(x)) ;	14)	($xA(x) Ú C) : $x (A(x) Ú C) ;
15)	(C É "xA(x)) : "x (C É A(x));	16) .("xA(x) É C) : $x (A(x) É C) ;
17)	($xA(x) É C) : "x (A(x) É C) ;	18)	(C É $xA(x)) : $x (C É A(x)) ;

19)("xA(x) Ù"xB (x)) : "x (A(x) Ù B (x));

20)($xB (x) Ú $xA(x)) : $x (B (x) Ú A(x));

21)"x (A(x) É ¬ B (x)) É ¬($xA(x) Ù "xB (x)) ;

22)"x (A(x) É ¬ B (x)) É ¬("xA(x) Ù $xB (x)) ;

23)$x (P (x) É Q (x)) : ("xP (x) É $xQ (x)) ;

24)$x (P (x) Ù (B É R (x))) É ("x (P (x) É ¬R (x)) É ¬B).

52

18. Найти нормальную форму для следующих предикатов:

1)	$x"yA(x, y) Ù $x"yB(x, y) ;	3)	$x"yA(x, y) É $x"yB(x, y) ;
2)	$x"yA(x, y) Ú $x"yB(x, y) ;	4)	$x"yA(x, y) É "x$yB(x, y) ;

5)($x"yA(x, y) Ú $xB(x)) É $y"xC (x, y);

6)$x"y"z (A(x, y) Ù¬ B ( y, z) Ù¬ C ( y, z));

7)($x"yA(x, y) Ú ¬"x"yB(x, y)) É ¬"zC (z) .

19.Какие из приведенных имен являются противоречащими, а какие противоположными:

1)	высокий – низкий;	2)	молодой – старый;
3)	близкий – неблизкий;	4)	близкий – далекий;

5)совершеннолетний – несовершеннолетний;

6)равнодушный – неравнодушный;

7)молотый кофе – растворимый кофе?

20.Указать, какие из приведенных высказываний являются общеутвер- дительными, общеотрицательными, частноутвердительными, частноот- рицательными.

1)Всякий моряк умеет плавать.

2)У каждой лошади есть хвост.

3)Ни одна кошка не дружит с мышами.

4)Есть кошки, которые дружат с собаками.

5)Не все книги содержат полезную информацию.

6)Некоторые люди не умеют читать.

7)Ряд водоплавающих не дышит жабрами.

8)Несколько человек не пошли в музей.

9)Многие люди верят в злых духов.

10)Люди в подавляющем большинстве хотят добра.

21.Какие из следующих высказываний могут быть одновременно истинными, но не могут быть одновременно ложными?

1)	Все врачи окулисты.	2)	Некоторые из врачей окулисты.
3)	Среди врачей нет окулистов.	4)	Некоторые врачи не окулисты.

22. Какие из следующих высказываний не могут быть одновременно истинными, но могут быть одновременно ложными?

1)Все лыжники – мастера спорта.

2)Отдельные лыжники – мастера спорта.

3)Некоторые лыжники не являются мастерами спорта.

4)Ни один лыжник не является мастером спорта.

53

23.Какие из следующих высказываний противоречат друг другу?

1)Каждый кашалот является водоплавающим.

2)Ни один кашалот не является водоплавающим.

3)Отдельные кашалоты не являются водоплавающими.

4)Некоторые кашалоты – водоплавающие.

5)Не все кашалоты дышат жабрами.

6)Нет кашалота, который дышал бы жабрами.

7)Кашалот дышит жабрами.

8)Некоторые кашалоты дышат жабрами.

24.Выяснить, могут ли быть одновременно истинными следующие суждения.

1)«Если я куплю билеты, то мы пойдем в театр»,

«Я куплю билеты, и мы пойдем в театр».

2)«Если ты не виноват, то тебе нечего бояться», «Ты не виноват, но тебе есть чего бояться».

3)«Хотя бы одна из роз в этом прекрасном букете – алая», «Все розы в этом прекрасном букете – алые».

25.Рассмотрим два определения легкой контрольной. Будем считать контрольную легкой, если:

1)каждую задачу решил хотя бы один ученик;

2)хотя бы один ученик решил все задачи.

Может ли контрольная быть легкой в смысле первого определения и трудной (не легкой) в смысле второго? Может ли работа быть легкой

всмысле второго определения и трудной в смысле первого?

26.Ученики 10Б класса хвастались тем, что они выше ростом учеников 10А. На вопрос учителя математики: «Что, собственно, означает, что вы выше ростом?» – ученики дали следующие ответы.

1)Любой из нас выше любого из них.

2)Самый высокий из нас выше самого высокого из них.

3)Для каждого из нас найдется ученик 10А класса меньшего роста.

4)Каждый ученик 10А класса ниже хотя бы одного ученика нашего

класса.

5)Средний рост учеников нашего класса больше среднего роста учеников 10А класса.

Есть ли среди этих ответов равносильные? Если есть, то какие?

54

27. Восстановить суждение по данной схеме отношений между терми- нами:

			1)	S	– книга, P – учебник;
		P
	S		2)	S	– символ, P – знак;

3)S – паук, P – насекомое;

4)S – человек,

S		P		P – бессмертное существо;
			5)	S	– рациональное число,
				P – иррациональное число;
			6)	S	– жилой дом,
S	P			P – кирпичный дом;
			7)	S	– те, кто любят есть рыбу,

P– люди;

8)S – автор романа «Идиот»,

	S, P	P – автор романа «Игрок».
		9) S	– ЭВМ, P – компьютер.

28. Представить с помощью круговых схем отношения между объема- ми имен:

1) плоская замкнутая геометрическая фигура – треугольник – прямо- угольник – квадрат – прямоугольный треугольник;

2) число – четное число – нечетное число – простое число – число 2 – число, делящееся на 4, – число, делящееся на 8;

3) дедушка – отец – сын – внук; 4) водоплавающее животное – рыба – животное, дышащее жабрами, –

кит – акула – треска; 5) переводчик – человек, знающий иностранный язык, – человек,

знающий французский язык, – человек, имеющий высшее образование; 6) адмирал – английский адмирал – адмирал Нельсон – русский

адмирал – адмирал Ушаков.

55

29.Установить посылки и заключение в следующих умозаключениях.

1)Если судья – потерпевший, то он не может участвовать в рас- смотрении данного дела; а так как этот судья – потерпевший, то, значит, он не может участвовать в рассмотрении этого дела.

2)Так как все студенты юридических вузов изучают логику, то, следовательно, среди тех, кто изучает логику, есть студенты юридических вузов.

3)Все следователи – юристы. Это вытекает из того, что некоторые юристы – следователи.

4)Первым пришел, конечно же, Петров. Это следует из того, что Яковлев не был первым. Не мог быть первым и Ковалев. Но тройка призеров включала только перечисленных спортсменов.

5) Известно, что в правильном треугольнике медианы в точке их пересечения делятся в отношении 1:2. В треугольнике ABC медианы в точке их пересечения делятся в отношении 1:2. Значит, треугольник ABC – правильный.

30.Являются ли правильными следующие умозаключения?

1)Каждый любит сам себя. Значит, кого-то кто-нибудь любит.

2)Все любят Джейн. Значит, все любимы кем-то.

3)Этому никто не поверит. Значит, судья этому не поверит.

4)Ни одно животное не бессмертно. Кошки – животные. Значит, некоторые кошки не бессмертны.

5)Перья есть только у птиц. Ни одно млекопитающее не является птицей. Значит, все млекопитающие лишены перьев.

6)Имеются прилежные студенты. Ни один студент не лишен способно- стей. Значит, некоторые студенты, лишенные способностей, не прилежны.

7)Глупец был бы способен на это. Я на это не способен. Значит,

яне глупец.

8)Если бы кто-нибудь мог решить эту задачу, то и какой-нибудь математик мог бы. Кэбот – математик, а не может ее решить. Значит, задача неразрешима.

9)Всякий, кто может решить эту задачу, – математик. Кэбот не может её решить. Значит, Кэбот – не математик.

10)Тот, кто распускает этот слух, должен быть и ловким, и бесприн- ципным. Кэбот не ловок. Лоувелл не беспринципен. Значит, ни Кэбот, ни Лоувелл не распускают этот слух.

56

11)Все книги имеют страницы; следовательно, неверно, что некото- рые книги не имеют страниц.

12)Некоторые умозаключения не являются правильными; значит, неверно, что все умозаключения правильные.

13)Все планеты вращаются вокруг своей оси; значит, некоторые планеты вращаются вокруг своей оси.

14)Некоторые животные не говорят; следовательно, некоторые гово- рящие не являются животными.

15)Некоторые люди не являются поэтами; следовательно, некоторые поэты – не люди.

16)Все металлы не являются жидкостями; значит, все жидкости не являются металлами.

17)Некоторые металлы – жидкости; значит, некоторые жидкости – металлы.

31.Какие из следующих шести теорем являются по отношению друг

кдругу обратными, противоположными, противоположными обратным? Какие из этих теорем верны?

1)Если каждое из двух чисел кратно 7, то их сумма кратна 7.

2)Если ни одно из двух чисел не делится на 7, то их сумма делится на 7.

3)Если хотя бы одно из двух чисел кратно 7, то их сумма кратна 7.

4)Если сумма двух чисел кратна 7, то каждое слагаемое кратно 7.

5)Если сумма двух чисел не делится на 7, то ни одно из слагаемых не делится на 7.

6)Если сумма двух чисел не делится на 7, то хотя бы одно из слагае- мых не делится на 7.

32.Для каждой из следующих теорем сформулировать обратную, противоположную и противоположную обратной теоремы. Указать, какие из этих теорем верны.

1)Если квадратное уравнение имеет два различных действительных корня, то дискриминант этого квадратного уравнения положителен.

2)Если параллелограмм является прямоугольником, то вокруг него можно описать окружность.

3)Если последовательность сходится, то она ограничена.

4)Если функция дифференцируема в точке, то она непрерывна в ней.

57

33. Установить фигуру и модус силлогизмов. Определить, является ли заключение силлогизма логически правильным.

1)Все женщины любят красиво одеваться. Некоторые профессора – женщины.

Некоторые профессора любят красиво одеваться.

2)Всякое хищение – умышленное преступление. Кража – тайное хищение имущества.

Кража – умышленное преступление.

3)Некоторые телевизоры – цветные.

Некоторые телевизоры не являются транзисторными. Некоторые цветные телевизоры не являются транзисторными.

4) В зимние месяцы идет снег. В январе идет снег.

Январь – зимний месяц.

5)Некоторые писатели – женщины. Все женщины любят цветы.

Среди тех, кто любит цветы, есть писатели.

6)«Жмурки» – детская игра.

Некоторые детские игры небезопасны. «Жмурки» не являются безопасной игрой.

7)Каждый честный человек выполняет свои обещания. Этот человек не выполняет своих обещаний.

Этот человек – бесчестный.

8)Движение вечно.

Хождение в институт есть движение. Хождение в институт вечно.

9)Не всякий, кто умеет читать, может написать книгу. Этот ребенок не может написать книгу.

Этот ребенок не умеет читать.

10) Ни один эгоист не нравится окружающим.

Все обязательные люди окружающим нравятся.

Ни один обязательный человек не является эгоистом.

11)Все студенты – люди. Все люди – не рыбы.

Все рыбы – не студенты.

58

12) Все солдаты умеют маршировать.

Некоторые маленькие дети не умеют маршировать. Некоторые маленькие дети не являются солдатами.

13)Все кухни должны проветриваться. Это помещение не является кухней.

Это помещение не должно проветриваться.

14)Все актеры тщеславны.

Тщеславные люди стремятся к успеху. Некоторые из стремящихся к успеху – актеры.

15) Некоторые учебники имеют схемы и графики.

Ни одна книга, имеющая схемы и графики, мне не интересна. Некоторые учебники мне не интересны.

16) Взятка – уголовное преступление.

Всякое уголовное преступление – наказуемо. Взятка – наказуема.

34.Привести примеры силлогизмов, построенных по правильным модусам.

35.Установить, какое из суждений пары является достаточным основа- нием для второго.

1)Треугольник ABC равен треугольнику ABD. Треугольник ABC и треугольник ABD имеют равные площади.

2)Адрес на конверте указан точно. Письмо дойдет до адресата.

3)Данное число делится на 3. Данное число делится на 9.

4)Высказывание x É y является истинным. Высказывание ¬ y É ¬ x является истинным.

5)Известно, что из A следует B, а из B следует C. Если A, то C.

36.Установить, соблюдаются ли требования закона достаточного осно- вания в следующих примерах.

1)Петров стал хуже учиться после того, как стал заниматься в секции легкой атлетики. Значит, именно занятия легкой атлетикой стали причи- ной того, что Петров стал хуже учиться.

2)На одной из контрольных работ Иванов не справился с решением задачи. Преподаватель после этого сделал вывод, что Иванов совершенно не умеет решать задачи.

59

37.Указать ошибку в рассуждениях.

1)«Из всей силы я ударил себя кулаком по правому глазу. Из глаза, конечно, так и посыпались искры, и порох в то же мгновение вспыхнул. Советую вам всякий раз, когда вы вздумаете развести огонь, добывать из правого глаза такие же искры». Барон Мюнхгаузен.

2)Шестилетний Андрюша моется в ванной.

–Мама , можно я твоим шампунем вымою голову?

–Можно.

Взял флакон в руки и прочитал: «Для сухих волос».

– Нет, мне нельзя, у меня ведь уже мокрые волосы!

3 ) Человек со временем посетит Марс. Иванов – человек, значит, Иванов со временем посетит Марс.

38.Указать ошибку в рассуждениях.

1)В семье Н. пятеро детей – все девочки. Значит, шестой ребенок тоже будет девочкой.

2)Я успешно сдала и этот экзамен, конечно же, благодаря тому, что сдавала его в бирюзовом платье, – подумала Наташа. – Ведь экзамен по математике я сдавала в нем и сдала успешно. Экзамен по физике

ятоже сдавала в нем и тоже успешно. Да и историю я сдавала в нем, а по истории я получила «отлично». Теперь все экзамены буду сдавать только в бирюзовом.

3)Что мне не нравится в тебе, – говорит молодая жена мужу, – так

это твое непостоянство. В понедельник тебе понравилась картошка, во вторник тебе понравилась картошка, в среду тебе понравилась картош- ка, в четверг тебе понравилась картошка, в пятницу тебе понравилась картошка, а вот в воскресенье ты вдруг заявил, что она тебе не нравится.

4) Как показывает статистика, преобладающее большинство дорож- но-транспортных происшествий приходится на долю машин, едущих с умеренной скоростью, и лишь малое число – на долю машин, едущих со скоростью свыше 100 км/ч. Значит, водить машину на больших скоро- стях безопасней.

60