ДМ Практикум

Федеральное агентство связи Федеральное государственное образовательное бюджетное учреждение

высшего профессионального образования «Сибирский государственный уни-

верситет телекоммуникаций и информатики» (ФГОБУ ВПО «СибГУТИ»)

Т.В. Бернштейн, Т.В. Храмова

П Р А К Т И К У М

ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ

Рекомендовано Сибирским региональным учебно-методическим центром высшего профессионального образования в качестве учебного пособия для студентов, обучающихся по направлениям 210300 – « Радиотехника»,

210400 – « Телекоммуникации», 230100 – « Информатика и вычислительная техника»

Новосибирск

2011г

УДК 519.1

ББК 22.1

Б516

Практикум по дискретной математике / Бернштейн Т.В. Храмова Т.В. -

Новосибирск: СибГУТИ, 2011. – 131 с.

Учебное пособие сдержит краткие теоретические сведения, примеры и задания по основным разделам дискретной математики: теории множеств, ма- тематической логике, теории алгоритмов, теории графов, конечным автоматам и комбинаторике. В заключение дается 2 варианта тестовых заданий и 30 вари- антов контрольных заданий, охватывающих большую часть курса. Учебное по- собие предназначено для проведения практических занятий по дискретной ма- тематике при подготовке инженеров, а так же бакалавров и магистров (направ- ление «Телекоммуникации»)

Кафедра высшей математики

Для подготовки дипломированных специалистов по направлениям на- правлениям 210300 – « Радиотехника», 210400 – « Телекоммуникации», 230100 – «Информатика и вычислительная техника»

Утверждено редакционно-издательским советом СибГУТИ в качестве практикума

© Бернштейн Т.В. Храмова Т.В.

© Сибирский государственный университет

телекоммуникаций информатики, 2011г.

2

ОГЛАВЛЕНИЕ

ПРЕДИСЛОВИЕ….…………………………………………………….……..…..4

ВВЕДЕНИЕ…………………………………………………………………………5

Глава I. Множества и операции над ними……………………………………....6

Глава II. Отношения и функции …………………………………….…...……..13

Глава III. Формулы алгебры логики……………………..………….…….……21

Глава IV. Функции алгебры логики……...………………………….……….…29

Глава V. Предикаты……….………………………………………….……….…42

Глава VI. Машины Тьюринга ………………………………….………….…50

Глава VII. Графы……………………….…………………………….…………..55

Глава VIII. Некоторые задачи на графах………………………….……………68

Глава IX. Конечные детерминированные автоматы…………….……………..83

Глава X. Элементы комбинаторики…………………….……….………...…….92

ВАРИАНТЫ ТЕСТОВЫХ ЗАДАНИЙ…………………………………………98

КОНТРОЛЬНЫЕ ЗАДАНИЯ………………………………………..…110 ОТВЕТЫ И УКАЗАНИЯ……………………...…………………………….…119

СПИСОК ЛИТЕРАТУРЫ……………………………………………....130

ПРЕДИСЛОВИЕ

Авторы данного учебного пособия Т.В. Бернштейн и Т.В. Храмова имеют большой опыт чтения лекций и проведения практических занятий по дискретной математике на различных факультетах СибГУТИ, являются авто- рами и соавторами ряда учебных и методических пособий по различным разде- лам данного курса. Накопленный авторами опыт преподавания позволил им создать интересное и нужное учебное пособие. Учебное пособие предназначено для студентов, обучающихся по направлениям «Информатика и вычислитель- ная техника» и «Телекоммуникации». Также оно может быть полезно препода- вателям при подготовке к практическим занятиям и всем, кто хочет познако- миться с данным разделом математики.

Курс дискретной математики входит в программу подготовки специали- стов самых различных направлений. При всем многообразии существующей литературы преподаватели, ведущие практические занятия сталкиваются с оп- ределенными трудностями. Трудности связаны с тем, что задачи разбросаны по разным книгам, отличающимся стилями и глубиной изложения, а также ис- пользуемыми в них обозначениями. Материал предлагаемого пособия состав- лен в соответствии с рабочими программами курсов дискретной математики, читаемых в СибГУТИ. В нем изложены основы теории множеств, математиче- ской логики, теории графов и теории конечных детерминированных автоматов в форме задач. Пособие содержит десять глав. В начале каждой главы имеется краткое введение, содержащее определения всех основных понятий, исполь- зуемых в данной главе, и приводятся примеры решения задач. В каждой главе также содержатся тестовые задания, которые могут быть использованы как при изучении учебного материала, так и при проверке и самопроверке полученных знаний.

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

Профессор кафедры высшей математики НГУ

д. ф.-м. н. И. А. Мальцев.

4

ВВЕДЕНИЕ

Дискретная (или конечная) математика представляет собой раздел мате- матики, изучающий свойства конечных систем или систем, процессы в которых развиваются скачкообразно. Бурное развитие дискретной математики обуслов- лено развитием информационных и коммуникационных технологий. Дискрет- ная математика является основой для создания средств обработки и передачи информации, а также для моделирования различных систем. Целью преподава- ния дисциплины «Дискретная математика» является изучение студентами ос- нов математического аппарата, применяемого для решения задач управления и алгоритмизации процессов обработки информации.

Данное учебное пособие предназначено для студентов младших курсов технических вузов, изучающих дискретную математику, и преподавателей, ве- дущих практические занятия по данному предмету. Материал составлен в соот- ветствии с рабочими программами курсов дискретной математики, читаемых на технических факультетах СибГУТИ.

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

Книга написана на основе учебного пособия Бернштейн Т.В., Храмова Т.В. Сборник задач по дискретной математике. – Новосибирск: Изд-во СибГУ- ТИ, 2004 г. Кроме того, в учебное пособие вошли некоторые примеры и задачи из учебного пособия Носов В.И., Бернштейн Т.В., Носкова Н.В., Храмова Т.В.

Элементы теории графов. Учебное пособие. – Новосибирск: Изд-во СибГУТИ, 2008 г.

В книге используются следующие обозначения: начало решения задачи отмечается знаком , конец решения отмечается знаком .

Авторы выражают искреннюю благодарность заведующему кафедрой высшей математики СибГУТИ профессору В. К. Трофимову за помощь и под- держку на всех этапах подготовки данного учебного пособия.

Авторы благодарны А. Бернштейну за помощь в техническом оформле- нии рукописи.

5

Глава I. Множества и операции над ними

Под множеством будем понимать любую определенную совокупность объектов (элементов множества). Запись x M означает, что элемент x принад- лежит множеству М, а запись x M означает, что элемент x не принадлежит множеству М. Два множества А и В равны (А=В), если они состоят из одних и тех же элементов. Множество А содержится во множестве В ( A B) , если все элементы множества А являются элементами множества В. При этом А на-

зывается подмножеством В. Семейство всех подмножеств данного множества

М обозначается через Р(М). Множество, не содержащее элементов, называется пустым и обозначается через . Множество всех элементов, рассматриваемых в данном случае, называется универсальным множеством и обозначается через U. Мощностью конечного множества M (обозначается | M | ) называется число

элементов множества M . Для конечного множества M | P(M ) |= 2|M | .

Объединением множеств А и В называется множество

A B ={x | x A или x B}.

Пересечением множеств А и В называется множество

A ∩ B ={x | x A и x B}.

Разностью множеств А и В называется множество

A \ B = {x | x A и x B}.

Симметрической разностью множеств А и В называется множество

A B = ( A \ B) (B \ A) .

Дополнением множества А называется множество

A = U \ A .

Геометрическим представлением множеств являются диаграммы Эйлера- Венна. Основные операции над множествами представляются следующими диаграммами:

A B	A ∩B		A\B		A	B
U		U		U		U
A B	A	B	A	B	A	B
		Рисунок 1.1
Рассмотрим произвольное множество			A U	и элемент	x U . Функция

I A (x) называется индикатором принадлежности элемента x множеству А, если

6

1, x Î A,

I A (x) = Ï0, x A.

Индикаторы принадлежности элемента множествам, полученным из дан- ных множеств А и В с помощью основных операций, приведены в следующей таблице:

Таблица 1.1

I A (x)	IB (x)	I AÇB (x)	I AÈB (x)	I		(x)	I ADB (x)	I A\ B (x)
					A
0	0	0	0	1			0	0
0	1	0	1	1			1	0
1	0	0	1	0			1	1
1	1	1	1	0			0	0

Равенство двух множеств равносильно равенству их индикаторных функ- ций, определенных на одном и том же универсальном множестве. Включение A B равносильно неравенству

x U I A (x) ≤ IB (x) .

Пример 1.1. Доказать один из законов де Моргана для произвольных множеств A и B

A Ç B = A È B .

Для доказательства построим таблицы индикаторных функций левой (таблица 1.2) и правой (таблица 1.3) частей равенства:

Таблица 1.2

I A (x)	IB (x)	I AÇB (x)	I		(x)
				AÇB
0	0	0	1
0	1	0	1
1	0	0	1
1	1	1	0

Таблица 1.3

I A (x)	IB (x)	I		(x)	I		(x)	I		È		(x)
			A			B			A		B
0	0	1			1			1
0	1	1			0			1
1	0	0			1			1
1	1	0			0			0

Так как значения индикаторов совпадают при любом возможном значе- нии аргумента x , то равенство верно.

7

А) Контрольные вопросы

1.1Задайте различными способами множество первых десяти натуральных чисел.

1.2 Дайте определение операций пересечения A ∩ B , объединения A B , разности A \ B , симметрической разности A B множеств А и В, допол- нения A множества А.

1.3Перечислите основные свойства операций над множествами.

1.4Докажите, что если А есть множество корней уравнения x2 − 5x + 6 = 0 и

B = {2,3}, то А=В.

1.5Докажите, что Æ ¹ {Æ}.

1.6 Выразите индикаторы принадлежности I A (x) , I AÇB (x) , I AÈB (x) , I A\ B (x) ,

I ADB (x) через индикаторы принадлежности элемента исходным множест-

вам I A (x) и IB (x) .

1.7Докажите для конечного множества M равенство | P(M ) |= 2|M | , где

Р(М) – множество всех подмножеств множества M .

Б) Задачи и упражнения

1.8 Для множеств U = {a,b,c, d ,e, f },									A = {a,b,c} , B = {b,c, d , f }, C = {a,c,e} и
D = {c, d ,e, f } задайте перечислением элементов множества:
а) A ∩ B ;									б) A C ;
в)			;						г) C \ A;
	D
д) A \ C ;									е) B D ;
ж) ( A C						) \ B ;			з) (B \ C) ∩	D	;
и) (				∩ B) (				C) .
		A					D

1.9Дано N10 = {1,2,3,4,5,6,7,8,9,10},

А={a | a N10 , а –			четное}, В={b | b N10 , b £ 5 }, С={с | c N10 , c>3}.
Задайте множества:
а)		;	б)		;	в) A C ;
	A			B
г) C ∩ B ;			д) B \ A ;			е) C \ A;
ж) B C ;			з) A C ;			и)		B ;
							A
						8

к) ( A B) ;			л)	B	\ ( A ∩C) .

1.10Даны А, В и С – подмножества множества действительных чисел .

A = [0;5] , B = (−2;3) , C = [2;7) . Задайте множества:

а)

A

;

б)

B

;

в) A ∩C ;

г) C B ;

д) B \ A ;

е) C \ A;

ж) B C ;

з)

B ;

A

и) ( A C) \

B

.

1.11 Постройте диаграммы Эйлера –

Венна для множеств:

а)

∩ B ;

б) A ∩(B C) ;

A

в) ( A B) \ C ;

г) ( A \ B) \ ( A \ C) ;

д) ( A C) ( A B) ;

е) ( A

B

) \ (C

A) .

1.12Постройте таблицы индикаторов принадлежности для множеств:

а) A ∩ B ;

б) ( A \ C) B ;

в) ( A C) (B ∩C) (D A) ;

г) A B ;

д) ( A \ C) \ B ;

е) ( A C) B .

1.13Докажите тождества:

а) ( A ∩ B) = A B ;

б) ( A B) = A ∩ B ;

в) A \ ( A \ B) = A ∩ B ;

г) ( A B) ∩ A = ( A ∩ B) A = A ;

д) A ∩(B \ A) = ;

9

е) A ( A B) = B ;

ж) ( A B) ( A ∩ B) = A B .

1.14Докажите тождества:

а) A (B ∩C) = ( A B) ∩( A C) ;

б) A ∩(B \ C) = ( A ∩ B) \ ( A ∩C) ;

в) A \ (B \ C) = ( A \ B) ( A ∩C) ;

г) A (B C) = ( A B) C ;

д) A ∩(B C) = ( A ∩ B) ( A ∩C) ;

е) ( A ∩ B) (C ∩ D) = ( A C) ∩(B C) ∩( A D) ∩(B D) .

1.15Докажите, что:

а) ( A \ B) \ C ( A C) \ B ;

б) A B = A \ B , если B A ;

в) A ∩ B C , если A (B C) ;

г) A = B , если A ∩ B = и A B =U .

1.16Найдите все подмножества множеств:

	а) ;					б) { };
	в) {x};					г) {x, y} .
В)	Тестовые задания (укажите единственный верный ответ)
1.17	Дано множество N10					= {1, 2, 3, 4, 5, 6, 7,8, 9,10} и два его подмножества
	А={a | a N10 , а – нечетное}, В={b | b N10 , b ≤ 5 }.
	Множество		\		равно…
		B		A
	а) {2, 4} ;
	б) {7,9};
	в) {6,8,10};
	г) {1,3}.
1.18	Дано множество N10					= {1,2,3,4,5,6,7,8,9,10} и три его подмножества

10