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

9)Если 2 – простое число, то оно наименьшее из простых чисел. Если 2 – наименьшее простое число, то 1 не есть простое число. Число 1 не есть простое число. Следовательно, 2 – простое число.

10)Иванов не сделает эту работу, если ее сделает Петров. Петров и Сидоров сделают эту работу в том и только том случае, если ее сделает Иванов. Сидоров эту работу сделает, а Иванов нет. Следовательно, Петров не сделает эту работу.

11)Петров, Иванов и Семенов собираются встречать Новый Год. Если Петров поедет в Москву, то Иванов поедет в Киев. Петров поедет

вМоскву или в Кострому. Если Петров поедет в Москву, то Семенов останется в Москве. Но Семенов не останется в Москве. Значит, Иванов поедет в Киев.

12)Если будет сильный ветер, мы не пойдем на каток, а отправимся

вмузей. Если мы пойдем на каток, то встретим много знакомых. Если мы отправимся в музей, то увидим много интересного. Мы не встретим мно- гих знакомых и не увидим много интересного. Значит, завтра не будет сильного ветра.

21.На столе три одинаковых ящика. В одном из них два белых шара,

вдругом – белый и черный, а в третьем – два черных. На крышках ящиков сделаны надписи «2 белых», «2 черных» и «белый и черный», но ни одна из них не соответствует действительности. Как, вынув только один шар, определить, в каком ящике какие лежат шары?

22.Перед судом стоят три человека, из которых только один может быть преступником.

Известно, что преступник, отвечая на вопросы, всегда лжет, а тот, кто не принимал участия в преступлении, всегда говорит правду.

Получив ответ одного из них на вопрос: «Виновны ли Вы?», судья задал двум оставшимся один и тот же вопрос: «Прав ли первый?» На этот вопрос он получил следующие ответы:

Второй: Первый прав. Третий: Первый солгал. Кто же преступник?

41

23. Четыре подруги Маша, Полина, Ольга и Наташа участвовали в соревнованиях по бегу и заняли первые четыре места. Установить, кто какое место из них занял, если известно, что в каждом из приведенных ниже ответов, которые дали лукавые девушки опоздавшему к финишу корреспонденту, верной является лишь его половина.

Наташа: Ольга была второй, а Полина – третьей.

Маша: Нет, Наташа. Ольга была первой, а второй была ты.

Ольга: Да что вы, девочки! Второй была Маша, а Полина прибежала четвертой.

24.Студент Лентяев, встретив в конце зачетной недели своих товари- щей по группе, спросил их о том, какие экзамены и в какой очередности им придется сдавать. Ребята решили подшутить над Лентяевым и дали ему такие ответы:

Сергей: Математический анализ сдаем вторым, а физику – третьим. Николай: Нет, третьим сдаем историю, а последним – психологию. Петр: Психология будет первым экзаменом, а сразу за ней – история.

Федор : Все-таки вторым мы сдаем математический анализ, а четвер- тым геометрию.

Леонид : Первым экзаменом у нас – физика, а геометрия, действи- тельно, четвертая.

Всвоих ответах каждый из ребят лишь наполовину сказал правду,

вчем они честно признались Лентяеву. После этого Лентяев, поразмыслив, установил точное расписание экзаменов. Попытайтесь сделать это и вы.

25.Пытаясь вспомнить победителей прошлогоднего турнира, пять бывших зрителей турнира заявили:

1)Антон был вторым, а Борис – пятым;

2)Виктор был вторым, а Денис – третьим;

3)Григорий был первым, а Борис – третьим;

4)Антон был третьим, а Евгений – шестым;

5)Виктор был третьим, а Евгений – четвертым.

Впоследствии выяснилось, что каждый зритель ошибся в одном из двух своих высказываний. Каково было истинное распределение мест в турнире?

42

26.Три девушки Аня, Варя и Клара ходили в кино. Одна из них была

вкрасном платье, другая – в белом, третья – в синем. На вопрос, какое на каждой из девушек было платье, они дали ответ:

Аня была в красном, Варя – не в красном, Клава – не в синем.

В этом ответе из трех частей одна верна, две неверны. В каком платье была каждая из девушек?

27. Инспектор Борисов точно знал, что преступник скрывается в одном из трех мест: на даче в Переделкино, у своего знакомого в Марьиной роще или же на квартире у перекупщика краденого на Таганке. В одном из этих же мест могла быть и жена преступника, которая была нужна инспектору для уточнения некоторых деталей следствия. Близкие преступника на вопрос о месте его пребывания дали различные ответы. Его мать сказала, что он наверняка в Переделкино, откуда он уже целую неделю не выезжает. Сестра преступника указала на Марьину рощу. Брат же утверждал, что на Таганке находится жена преступника, которая, может быть, знает, где его искать.

Зная, что все родственники при ответе на вопрос солгали, инспектор Борисов без труда выяснил, где скрывается преступник.

28. Инспектору Борисову стало известно, что совершена кража в ювелирном магазине. «Кто же «взял» магазин?» – задумался инспек- тор. Он знал, что это мог сделать либо вышедший недавно на свободу матерый уголовник по кличке «Лось», либо появившийся в городе Аполлон Рубашкин, которого знали в уголовном мире как «Артиста», либо «начинающий», но уже поднаторевший в преступном промысле Павел Смышляев.

Вскоре инспектору Борисову поступила информация:

1)ювелирный магазин ограбил не Аполлон;

2)магазин «взял» Смышляев.

Спустя некоторое время выяснилось, что только одно из этих сообщений соответствует действительности. Этого оказалось достаточ- ным для того, чтобы инспектор Борисов установил, кто совершил кражу. Как он это сделал?

43

29. Брауну, Джонсу и Смиту предъявлено обвинение в соучастии в ограблении банка. Похитители скрылись на ожидавшем их автомобиле. На следствии они дали следующие показания:

Браун: Преступники были на синем «Бьюике». Джонс: Преступники были на черном «Крайслере».

Смит: Это был Форд Мустанг и ни в коем случае не синий. Каждый из них указал правильно либо марку машины, либо ее цвет.

Какого цвета был автомобиль и какой марки?

30. По подозрению в совершенном преступлении задержали Брауна, Джона и Смита. Один из них был уважаемым в городе стариком, другой был малоизвестным чиновником, третий – известным мошенником. В процессе следствия старик говорил правду, мошенник лгал, а третий задержнный в одном случае говорил правду, а в другом – ложь. Вот что они утверждали:

Браун: Я совершил это. Джон невиновен.

Джонс: Браун невиновен. Преступление совершил Смит. Смит: Я невиновен, виновен Браун.

Определить имя старика, мошенника и чиновника и кто из них вино- вен, если известно, что преступник один.

31. Браун, Джонс и Смит обвиняются в подделке сведений о подлежащих налоговому обложению доходах. Они дают под присягой такие показания:

Браун: Джонс виновен, а Смит невиновен. Джонс: Если Браун виновен, то виновен и Смит.

Смит: Я невиновен, но хотя бы один из них двоих виновен. Обозначим буквами Б, Д и С высказывания: «Браун виновен»,

«Джонс виновен», «Смит виновен». Выразить показания каждого из обвиняемых формулой. Построить для этих формул таблицы истинно- сти. Затем ответить на следующие вопросы:

1)Совместимы ли показания всех троих заподозренных (т.е. могут ли они быть верны одновременно)?

2)Показания одного из обвиняемых следуют из показаний другого;

очьих показаниях идет речь?

3)Если все трое невиновны, то кто совершил лжесвидетельство?

4) Предполагая, что показания всех обвиняемых верны, указать, кто невиновен, а кто виновен.

5) Если невиновные говорят истину, а виновные лгут, то кто невино- вен, а кто виновен?

44

32. Гриша, Миша и Игорь – сыновья военнослужащих. У одного из них отец – офицер флота, у второго – ракетчик, а у третьего – десантник.

Юноши приняли решение тоже стать военными. Один из них попал на флот, другой стал ракетчиком, а третий – десантником.

Михаил по состоянию здоровья не попал в десантники, а Игорь не попал на флот. Не попал на флот и сын моряка.

Если сын десантника не стал десантником, то им стал сын ракетчика, а если Игорь – десантник, то сын моряка – не ракетчик.

Вопрос: где же служат ребята и их отцы?

33. Пятеро выпускников школы обсуждали, кто кем станет.

Андрей считал, что банкиром может стать любой из них, но только не Дмитрий. Виктор утверждал, что ему нравится профессия метрдотеля. А Дмитрий полагал, что самый подходящий кандидат в метрдотели – это Григорий. Борис говорил, что он никогда не будет врачом, утверждая при этом, что Андрей может стать учителем. Григорий же утверждал, что Борис может быть блистательным актером.

Жизнь у ребят сложилась по-разному. Оказалось, что те, кто стали учи- телем и метрдотелем, ошибались в своих суждениях. А актер и банкир ока- зались целиком правы. Установить, кто из них какую профессию выбрал.

34. Петя, Вася и Маша остались дома одни. Кто-то из них ел варенье. На вопрос мамы, кто это сделал, они сказали:

Петя: Я не ел. Маша тоже не ела.

Вася: Маша действительно не ела. Это сделал Петя. Маша: Вася врет. Это он съел.

Выяснить, кто ел варенье, если известно, что двое из них оба раза сказали правду, а третий один раз соврал, а один раз сказал правду.

35. Четыре семьи, дружившие между собой, держали по 10 различных животных. Их питомцами были белки, кролики, хомяки и ежи. Каждая семья держала разное число разных животных – от одного до четырех,

и ни в одной семье не было одинакового количества одних и тех же зверушек. Определить, сколько и каких животных было в каждой семье, если известно, что:

1 ) у Ивановых, Сидоровых и Петровых ежей было не два;

2)у Ивановых и Петровых кроликов, а у Кузнецовых кроликов и хомяков было не по одному;

3)у Сидоровых, Петровых и Кузнецовых жили не по три белки;

4)у Ивановых и Петровых хомяков было не по два и не по четыре.

5.ИСЧИСЛЕНИЕ ПРЕДИКАТОВ

1.Будут ли следующие выражения формулами, и если это формулы, то какие переменные в них являются свободными, а какие связанными:

1) "x$y "q P(x, y, z,q);		2) "x P(x, y) É $y P(x, y) ;
3)	$x$y (P(x, y) ÙQ (x, y)); 4) Q ( y)Ù"x P(x, z)É$xR(x, y);
5)	$xP(x, y) É $zQ ( y, z);	6) "x (P(x, y) ÙQ (z) Ú $xR(x, y))?
2. Пусть A = {a,b,c} , а предикат Q(x, y) задан таб-
			x	y		Q(x, y)
лицей. Определить истинность следующих формул в
			a	a		0
модели M = A; Q(2) :			a	b		1
1) xQ (x,a), xQ (x,a), xQ (a, x), xQ (a, x);			a с			1
2) xQ (x,b), xQ (x,b), xQ (b, x), xQ (b, x);			b	a		0
			b	b		1
3) "x"yQ (x, y), "y"xQ (x, y),
			b с			1
	x yQ (x, y), y xQ (x, y);		с a			0
4) x yQ (x, y), y xQ (x, y),			с	b		1
			с	с		1
	$x"yQ (x, y), $y "xQ (x, y).

3. Пусть S (x, y, z) " x + y = z", P(x, y, z) " xy = z" . Дать словес-

ную формулировку и определить истинность предиката Q (x), высказы- ваний xQ (x), xQ (x) в модели M = ¢+ ; S(3), P(3) :

1) Q (x) = $y S ( y, y, x);	3) Q (x) = "y S ( y, y, x);
2) Q (x) = y P( y, y, x);	4) Q (x) = y P( y, y, x).

4. Пусть S (x, y, z) " x + y = z", P(x, y, z) " xy = z" . Дать словес-

ную формулировку и определить истинность следующих высказываний

в моделях M1 = ¢+ ; S(3), P(3)	и M2 = ¡+ ; S(3), P(3) :
1) y x S ( y, y, x);	3) x y S ( y, y, x);
2) $y "x P( y, y, x);	4) "x$y P( y, y, x).

46

5. Рассмотреть в модели M = A; Q(2) все варианты квантификации

переменных предиката Q (x, y). Определить истинность получаемых выражений, если:

1)	Q(x, y) " x кратно y":
	а) A = {0,1,2,3,4,5,6,7,8,9},		б)	A = ¥;
2)	A = {0,1,2,3,4,5,6,7,8,9}:
	а) Q(x, y)	" x имеет общий делитель с y",
	б) Q(x, y)	"x, y делятся на 3",
	в) Q(x, y)	" x, y − четные числа";
3) Q(x, y) "x ≤ y":
	а) A = {0,1,2,3,4,5,6,7,8,9},		б)	A = ¥, в) A = Z ;

4)Q(x, y) " x знаком с y", A – множество студентов вашей группы;

5)A – множество людей:

	а) Q(x, y)	" x любит y", б) Q(x, y)			" x − родитель y" ,
	в) Q(x, y) " x живет в одном городе с y";
6) A =P (B), B – непустое множество:
	а) Q(x, y)	"x y",		б) Q(x, y) "x пересекается с y".
6. Пусть M =		¢+ ; S(3), P(3) , где
	S (x, y, z) " x + y = z", P(x, y, z) " xy = z" .
Записать формулы, выражающие следующие утверждения:
1)	x = 0 ;	4)	x – четное число;		7)	x = y ;
2)	x = 1;	5)	x – нечетное число;		8)	x ≤ y ;
3)	x = 2 ;	6)	x – простое число;		9)	x < y ;

10)x – делит y ;

11)z – наименьшее общее кратное x и y ;

12)z – наибольший общий делитель x и y ;

13)сложение коммутативно;

14)умножение коммутативно;

15)сложение ассоциативно;

15) умножение ассоциативно;

17)умножение дистрибутивно относительно сложения;

18)множество простых чисел бесконечно.

47

7. Пусть A – множество точек, прямых и плоскостей трехмерного евклидова пространства. Рассмотрим модель M = A; f , где f – соответ-

ствие, которое для предикатных символов P1 (x), P2 (x), P3 (x), Q(x, y), E (x, y) определяет следующие предикаты:

P1 (x) "x − точка", P2 (x) "x − прямая", P3 (x) "x − плоскость", Q(x, y) " x лежит на y", E (x, y) " x совпадает с y".

I.Записать в этой модели следующие утверждения.

1)Через каждые две точки можно провести прямую и притом един- ственную, если эти две точки различны.

2)Через каждые три точки, не лежащие на одной прямой, можно провести единственную плоскость.

3)Через точку, не лежащую на данной прямой, можно провести прямую, параллельную данной прямой, причем только одну.

II. Записать в этой модели определения:

1) параллельных прямых;		2) параллельных плоскостей.
8. Пусть P A2 – бинарное		отношение. Подобрать необходимую
модель и записать следующие утверждения и их отрицания:
1)	P – рефлексивно;	4)	P – антисимметрично;
2)	P – иррефлексивно;	5)	P – транзитивно;
3)	P – симметрично;	6)	P – эквивалентность.

9. Пусть L – множество людей, f – соответствие, которое для предикат-

ных символов M (x), W (x), P(x, y), Ch(x, y), S (x, y), D(x, y), F (x, y),

Dc(x, y), H (x, y), Wf (x), C (x, y), E (x, y), определяет предикаты:

M (x) " x − мужчина",		W (x) " x − женщина",
P(x, y)	" x − родитель y",	Ch(x, y)	" x − ребенок y",
S (x, y)	" x − сын y",	D(x, y) " x − дочь y",
F (x, y)	" x − предок y",	Dc(x, y)	" x − потомок y",
H (x, y)	" x − муж y" ,	Wf (x, y)	" x − жена y",
	C (x, y) " x и y	− супруги",

E (x, y) " x и y − один и тот же человек".

48

Записать в модели M = L; f утверждения:

1)некоторые супруги бездетны;

2)некоторые супруги имеют детей;

3)некоторые супруги имеют детей только женского пола;

4)некоторые супруги имеют детей только мужского пола;

5)x – внебрачный сын y ;

6)x – внебрачная дочь y ;

7)x – тесть (отец жены);

8)x – теща (мать жены);

9)x – свекор (отец мужа);

10)x – свекровь (мать мужа);

11)x – зять (муж дочери);

12)x – невестка (жена сына);

13)у каждого есть бабушка;

14)у каждого есть дедушка;

15)у каждого есть отец и мать;

16)x – незаконнорожденный;

M1 = L; E(2), P(2),C(2),M (1),W (1) ,

M2 = L; E(2), P(2), H (2),M (1),W (1) ,

M3 = L; E(2), P(2),Wf (2),M (1),W (1) ,

M4 = L; E(2),Ch(2),C(2),M (1),W (1) ,

M5 = L; E(2),Ch(2), H (2),M (1),W (1) ,

M6 = L; E(2),Ch(2),Wf (2),M (1),W (1) ,

M7 = L; E(2),S(2), D(2),C(2) ,

M8 = L; E(2),S(2), D(2), H (2) ,

M9 = L; E(2),S(2), D(2),Wf (2) .

формулы, выражающие следующие

17)x – деверь (брат мужа);

18)x – шурин (брат жены);

19)x – золовка (сестра мужа);

20)x – свояченица (сестра жены);

21)x – дядя (брат отца или матери);

22)x – тетя (сестра отца или матери);

23)x – сноха (жена брата мужа);

24)x – свояк (муж сестры жены);

25)x – племянник

(сын сестры или брата); 26) x – племянница

(дочь сестры или брата);

27)x – кузен (двоюродный брат);

28)x – кузина (двоюродная сестра);

29)x – двоюродный дядя;

30)x – двоюродная тетя;

31)x – двоюродный племянник;

32)x – двоюродная племянница;

M10 = L; E(2), F(2),C(2),M (1),W (1) ,

M11 = L; E(2), F(2), H (2),M (1),W (1) ,

M12 = L; E(2), F(2),Wf (2),M (1),W (1) ,

M13 = L; E(2), Dc(2),C(2),M (1),W (1) ,

M14 = L; E(2), Dc(2), H (2),M (1),W (1) ,

M15 = L; E(2), Dc(2),Wf (2),M (1),W (1) ,

49

10. Пусть f (x) – всюду определенная фиксированная функция. Рассмотрим модель M = ¡;g , где g – соответствие, которое для преди-

катных символов S (x), P(x, y, z), A(x, y, z), B(x, y, z), F (x, y, z) и S (x)

определяет предикаты:

S (x) " x > 0", P(x,a,b) " x [a,b]",

A(x, y, z) " x − y < z" , B(x, y, z) " f (x) − y < z" ,

F (x, y, z) " f (x) − f ( y) < z".

Сформулировать следующие утверждения:

1)число A есть предел функции f (x) при x → x0 ;

2)неверно, что число A есть предел функции f (x) при x → x0 ;

3)не существует предела функции f (x) при x → x0 ;

4)	f (x)	непрерывна в точке x0 ;	5)	f (x)	разрывна в точке x0 ;
6)	f (x)	непрерывна на [a,b];	7)	f (x)	разрывна на [a,b];

8)f (x) равномерно-непрерывна на [a,b];

9)f (x) не является равномерно-непрерывной на [a,b];

10)функция f (x) непрерывна на [a,b], но равномерно-непрерывной на этом отрезке не является.

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

1)f (x) – возрастающая функция;

2)f (x) – неубывающая функция;

3)f (x) – монотонная функция;

4)f (x) – ограниченная функция;

5)f (x) – бесконечно малая функция:

а) при x → x0 ,	б) при x → x0	+ 0 ,	в) при x → x0	− 0 ,
г) при x → +∞ ,	д) при x → −∞ ,		е) при x → ∞;
6) f (x) – бесконечно большая функция:
а) при x → x0 ,	б) при x → x0	+ 0 ,	в) при x → x0	− 0 ,
г) при x → +∞ ,	д) при x → −∞ ,		е) при x → ∞.

50