3

ПРЕДИСЛОВИЕ

Как хорошо известно – теория значительно лучше усваивается при решении конкретных задач. В настоящем пособии подобраны задачи, по всем основным разделам курса «Дискретная математика»: множества, комбинаторика, математическая логика, основы теории кодирования информации, основы теории графов.

Предполагается наличие доброй воли для самостоятельного решения задач. А это, в свою очередь, предполагает, что студент предварительно проработает теоретический материал и имеет под руками пособие, в которое можно заглянуть при необходимости.

Как правило, задачи, относящиеся к одной теме, расположены в порядке возрастания их сложности. Иногда под одним номером Расположено несколько задач, не всегда одинаковых. В этом случае следует предварительно ознакомиться со всеми заданиями задачи, а потом приступать к их решению

Все задачи (за исключением некоторых задач на доказательство) снабжены ответами, некоторые указаниями, для более характерных задач приводятся подробные решения. Ответы, указания, решения приведены в конце каждого раздела. К ним следует обращаться не сразу. Следует попытаться решить, или хотя бы поразмышлять над решением, а уж потом искать ответы и подсказки.

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

Решение некоторых задач требует размышлений т времени. Но всегда следует помнить, что дорогу осилит идущий!

1.МНОЖЕСТВА

№1.1. Задать с помощью характеристического свойства: а) множество всех положительных чисел; б) множество всех неотрицательных чисел;

в) множество натуральных числа, меньших 7, кратных 7, кратных 23, делители 180.

Пример.

Множество натуральных чисел, кратных 23, можно задать в виде: {x N | x mod 23 = 0}.

№1.2. Для уравнения (х2-1)(2х-1)(х2 -2)(х2 +1) = 0 задать перечислением всех элементов множества корней: вещественных, целых, натуральных, рациональных, комплексных.

1.1.Отношения между множествами

№1.3. Определите отношения между множествами ( , , =)

а) прямоугольных и равнобедренных треугольников, б) ромбов и квадратов,

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

Изобразить эти отношения на диаграммах Э1лера – Венна. № 1.4. Какие из множеств будут равными между собой?

А = {a,b,с, {b,с},{b,а}, b}; А1 = {а,b {с,b},{b,а}, с};

А2 = {а,b,с}; А3 = {а,{b,с}}; А4 = { 2401 , 625 , 81 , 1 },

А5={12, 72, 32, 52}.

№ 1.5. Докажите, что, если А В, В С, С А, то А = В = С.

4

№ 1. 6. Найдите и изобразите на числовой прямой

АВ, А В, А \ В, если

1)A = {x R/, x2 - 7x –18 0}; B = {x R/,(2х-5)/(3х + 7) >= 3}.

2)A = {x R/, x2 –10x -24 0}; B = {x R/, | x/3 + 2| < 3}.

3)A = {x R/, (2x – 5) / (x + 4)}; B = {x R/, 1/3 – x/2 > x/6 + 1 }.

4)A = {x R/, 2x (x + 4) 3 (x + 4)}; B = {x R/, 2 x – 4 x + 5}..

5)A = {x R/, (x2 –3x +2) / (x + 4) 0}; B = {x R/, 2x–3< x / 4 + 5}.

6)A = {x R/, ln (x-5) > 2}; B = {x R/, x2 – 5x + 6 0}.

7)A = {x R/, lg ( x - 5) < 3}; B = {x R/, x2 + 5 x + 6 > 0}.

8)A = {x R/, ( 2x + 5)/( x + 4) 0}; B={x R/, 1/3 – x/2 > x/6 + 7 };

9)A = {x R/, lg (x - 5) > 3}; B = {x R/, (x - 5) / (x + 2) < 3}.

10)А = {x R/, x2 – 10x + 21 0}; B = {x R/, 4 – 5x 2x - 31}.

Пример. A = {x R/, lg (x + 15) < 2}; B={x R/, (x - 2) / (x - 7) < 5}.

Решение. Найдем решения соответствующих неравенств. а) неравенство lg( x + 15) < 2 равносильно системе

х 15 100 , что приводит нас к решению х (-15, 85) (рис.1)

x 15 0

						º ׀ ׀ ׀ ׀ ׀ ׀ ׀ ׀ ׀ ׀º
						-15			85
									Рис. 1. Множество А
б) рассмотрим неравенство (x-2) / (x-7) < 5.
Преобразуем его			x 2		5 0 , или				x 2 5x 35	0 , или
	x 8,25		x 7						x 7
		0 Решаем методом интервалов.
	x 7				-		8,25		+
+ 7
Получим х (- ∞, 7) (8,25 ; + ∞) (рис. 2)
		׀ ׀ ׀ ׀ ׀ ׀ ׀ ׀ ׀ º							º ׀ ׀ ׀ ׀ ׀ ׀ ׀ ׀ ׀
					7				8,25

Рис. 2. Множество В

Тогда

А В = (-15 ; 7) (8,25; 85) (рис. 3)

º׀ ׀ ׀ ׀ ׀ ׀ ׀ ׀ ׀ º		º׀ ׀ ׀ ׀ ׀ ׀ ׀ ׀ ○
-15	7	8 ,25	85

Рис. 3. Пересечение множества А и множества В

А В = (- ∞, + ∞) (рис. 4)
׀ ׀ ׀ ׀ ○׀ ׀ ׀ ׀ ׀ º												º ׀ ׀ ׀ ׀ ׀ ׀ ׀ ׀ ׀
-15	7											8,25
А \ В = (7; 8,25) (рис. 5)	Рис. 4.			Объединение множества А и множества В
º׀ ׀ ׀ ׀ ׀ ׀ ׀ ׀ ׀׀ ׀ ׀ ׀ ׀ º
7		8,25

Рис. 5. Разность множества А и множества В

№ 1.7. Доказать или опровергнуть справедливость равенств для произвольных множеств А, В, С. Проиллюстрируйте диаграммами Эйлера – Венна.

1) А (В \ С) = (А В) \ (А С) = (А В) \С, 2) (А \ В) \С =(А \ С) \ (В \ С),

3) А В = А (В \ А),

5

_ _

4) (А В) (А В ) = (А В) (А В ),

_

5) ( А В) А = А В, 6) (А В) \ С =(А \ С) (В \ С),

7) А \ В \ С = (А \ В) (А \ С).

Пример.

Проверим равенство 7).

Обозначим М1 = А \ В \ С, М2 = (А \ В) (А \ С).

1. Пусть х М1.Возможны два варианта. По определению разности имеем а) х А и х В \ С, значит, возможны два варианта: х В или х В и х С .

а1) т.к. х А и х В, то по определению разности х А \ В, а по определению объединения х М2.

а2) т.к. х А и х В и х С, то х А \ В и х А \ С, т..е. х М2. (рис. 6 -7). Т.о. в этом случае равенство 7) несправедливо. В принципе, на этом можно заканчивать решение задачи.

А В

С

Рис. 6. Множество М1

Рис. 7. Множество М2

б) х А\ В и х С. А это сразу же означает, что х М2 Мы показали, что М1 М2.

2. Пусть теперь для случая б) х М2.

Тогда х А \ В или х А \ С. Если х А\В, то х А и х В.

Про принадлежность х к С мы ничего сказать не можем, значит, х может принадлежать, а может и не принадлежать множеству М1. А это означает, что равенство 7) несправедливо. (рис. 8-9)

Рис. 8. Множество М2

Рис. 9. Возможная принадлежность элемента х

_ _

№ 1.8. Для множеств А и В известно, что А В. В каком отношении находятся А и В ? № 1.9. Пусть универсум - это множество студентов 1 курса Назовите дополнения

6

а) множества отличников, б) множества спортсменов,

в) множества отличников и спортсменов, г) множества отличников или спортсменов,

д) множества студентов не являющихся ни отличниками, ни спортсменами:

1.2. Разбиения множеств

Напоминаем, что некоторое свойство(ва) разбивает множество А на классы (подмножества), если каждый класс не пуст, попарное пересечение классов пусто, объединение классов образует множество А.

№ 1.10. Доказать, что множества А В С и А B С не пересекаются.

№ 1.11 Пусть М – универсальное множество. А и В – его подмножества. Докажите, что объединение мно-

		_ _	_	_
жеств А В,	А	В , А В, А		В образуют множество М.

№1.12. Из 100 студентов 1 курса 6 отличников, 20 спортсменов, 25 участников художественной самодеятельности, 3 являются отличниками и спортсменами, 6 – спортсменами и участниками художественной самодеятельности, 2 - отличниками и участниками художественной самодеятельности, 1 – отличник, спортсмен и участник художественной самодеятельности.

Сколько студентов не является ни отличниками, ни спортсменами, ни участниками художественной самодеятельности?

Сколько студентов является только отличниками?

Сколько студентов является отличниками или спортсменами?

Сколько студентов является спортсменами или участниками художественной самодеятельности?

Совет. Нарисуйте диаграмму Эйлера - Венна.

№1.13. Из 100 студентов изучают только немецкий язык -18, немецкий, но не английский - 23, немецкий и французский – 8, немецкий - 26, французский - 48, французский и английский - 8, никакого языка – 24.

Сколько студентов изучают только английский язык?

Сколько студентов изучают немецкий и английский, но не французский языки?

Совет. Нарисуйте диаграмму Эйлера – Венна.

№1.14. . В группе 25 человек. Иэ них 8 лыжников, 13 пловцов и 17 бегунов. Каждый спортсмен занимается только двумя видами спорта и учится на 3 или 4. В группе 6 отличников.

Сколько в группе спортсменов? Сколько в группе неуспевающих7

№1.15. 80 человек знают хотя бы один из трех языков. 10 знают только английский, 14 – только немецкий

20 только французский, а число знающих все три языка на 2 меньше числа знающих только английский и французский, на 4 меньше числа знающих только немецкий и французский и на 6 меньше числа знающих английский и немецкий. Сколько человек знают:

а) все три языка? б) французский и немецкий? в) французский или немецкий (хотя бы один)? г) или французский или немецкий (один)?

Решение Обозначим множества студентов: изучающих английский язык - А, изучающих французский язык - Ф, изучающих немецкий язык – Н. (рис. 10)

У 80

Рис. 10. Разбиение множества У на классы

Получили У= А Н Ф АН АФ НФ АНФ. Обозначим мощность множества буквой м. Тогда мУ=80. Т.к. классы не пересекаются, то мУ = мА + мН + мФ + мАН +мАФ + мНФ + мАНФ, т.е.

80 = 10 + 14 + 20 + мАН +мАФ + мНФ + мАНФ. Отсюда получим