Сборник задач по дискретной математике (стр. 1 )

СБОРНИК ЗАДАЧ

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

НОВОСИБИРСК 2003г.

УДК 519.1

Бернштейн Т. В. Сборник задач по дискретной математике.

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

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

Рецензенты: д. ф.-м. н., проф. , к. ф.-м. н., доц. .

Направление подготовки дипломированных специалистов 654400 «Телекоммуникации» (квалификация – инженер, для специальностей 201800) и направление 550400 «Телекоммуникации» степень (квалификация) – магистр техники и технологии, бакалавр техники и технологии.

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

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

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

ОГЛАВЛЕНИЕ

ГЛАВА I Множества и операции над ними……………………………………...4

ГЛАВА II Отношения и функции ………………………………………………..7

ГЛАВА III Логика высказываний. Функции алгебры логики…………………11

ГЛАВА IV Язык логики предикатов…………………………………………….18

ГЛАВА V Машина Тьюринга……………………………………………………20

ГЛАВА VI Элементы теории графов …………………………………………..23

ГЛАВА VII Элементы теории автоматов……………………………………….29

ОТВЕТЫ И УКАЗАНИЯ………………………………………………………...34

КОНТРОЛЬНЫЕ ЗАДАНИЯ…………………………………………….40

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

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

Под множеством будем понимать любую определенную совокупность объектов. Запись означает, что элемент x принадлежит множеству М, а запись означает, что элемент x не принадлежит множеству М. Два множества А и В равны (А=В), если они состоят из одних и тех же элементов. Множество А содержится во множестве В , если все элементы множества А являются элементами множества В. При этом А называется подмножеством В. Семейство всех подмножеств данного множества М обозначается через Р(М). Множество, не содержащее элементов, называется пустым и обозначается через . Множество всех элементов, рассматриваемых в данном случае, называется универсальным множеством и обозначается через U.

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

или .

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

и .

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

и .

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

.

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

.

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

AB AB A\B AB

U U U U

A B A B A B A B

Рассмотрим произвольное множество и элемент . Число называется индикатором принадлежности элемента x множеству А, если

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

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

1.  Доказать, что если А есть множество корней уравнения и В={2,3}, то А=В.

2.  Доказать, что .

3.  Дано 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}.

Задать перечислением элементов множества:

а) ; б) ; в) ; г) С\А; д) А\С;

е) ; ж) ; з) ; и) .

4.  Дано ,

А={a | , а – четное}, В={b | , }, С={с | , c>3}.

Задать множества:

а) ; б) ; в) ; г) ; д) ; е) С\А;

ж) ; з) ; и) ; к) ; л) .

5.  Построить диаграммы Эйлера – Венна для множеств:

а) ; б) ; в) ;

г) ; д) ; е) .

6.  Задать табличным способом множества:

а) ; б) ; в) .

7.  Доказать тождества:

а) ; б) ;

в) ; г) ;

д) ; е) ;

ж) .

8.  Доказать тождества:

а) ; б) ;

в) ; г) ;

д) ;

е) .

9.  Доказать, что:

а) ; б) , если ;

в) , если ; г) , если и .

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

а) ; б) ; в) ; г) .

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

Прямым (декартовым) произведением множеств ,…, называется множество . Если , то множество называется прямой степенью множества A и обозначается .

Бинарным отношением между элементами множеств А и В называется любое подмножество R множества . Если А=В, то отношение R называется бинарным отношением на А.

Областью определения бинарного отношения R называется множество

Dom(R)={x | и существует y такой, что }.

Областью значений бинарного отношения R называется множество

Im(R)={y | и существует x такой, что }.

Для бинарных отношений определены обычным образом операции объединения, пересечения, разности.

Дополнением бинарного отношения называется множество

.

Обратным отношением для бинарного отношения называется множество .

Бинарное отношение R на множестве А называется

рефлексивным, если для всех ;

антирефлексивным, если для всех ;

симметричным, если , для всех ;

антисимметричным, если

и , для всех ;

транзитивным, если

и , для всех .

Рефлексивное, симметричное и транзитивное отношение R на множестве А называется отношением эквивалентности и разбивает множество А на классы эквивалентности по отношению R.

Рефлексивное, антисимметричное и транзитивное отношение R на множестве А называется отношением нестрогого порядка. Антирефлексивное, антисимметричное и транзитивное отношение R на множестве А называется отношением строгого порядка.

Отношение f из А в В называется функциональным (или просто функцией), если для любого и любых

и .

При этом говорят, что функция имеет тип f из А в В и пишут .

Функция f называется всюду определенной, если Dom(f)=A;

сюръективной, если Im(f)=B; инъективной, если для любых и любого если и .

Функция f называется взаимно – однозначной или биективной, если она всюду определена, сюръективна и инъективна.

1.  Даны множества X={x,y}, Y={x,y, z}. Задать следующие множества:

а); б) ; в) ; г) .

2.  Найти геометрическую интерпретацию множеств:

а) ; б) ; в) .

3.  Задать перечислением пар следующие бинарные отношения. Построить матрицы данных отношений:

а) R={(x,y) | x,y{1,2,3,4}, x<y};

б) R={(x,y) | x{1,2,3,4,5}, y{12,16}, x делит y};

в) R={(x,y) | x,y{1,2,3,4,5}, (x+y) четно};

г) R={(x,y) | x,y A, x предшествует y}, где А={понедельник, вторник, среда, четверг, пятница, суббота, воскресение}.

4.  Найти Dom(R), Im(R), , для следующих бинарных отношений:

а) R={(x,y) | x,y{1,2,3,4}, x y};

б);

в) ;

г) , где M={x,y}.

5.  Определить, выполняются ли для следующих отношений свойства рефлексивности, антирефлексивности, симметричности, антисимметричности, транзитивности:

а) отношения “быть знакомым”, “жить в одном городе”,

“быть моложе” на множестве людей;

б) отношение на множестве ;

в) отношение строгого включения на множестве Р(А), где Р(А)={1,2,…,n};

г) R={(m,n) | m и n взаимно просты} на множестве ;

д) R={(m,n) | m-n=2} на множестве ;

е) R={(x,y) | (x+2y) делится на 3} на множестве ;

ж) R={((x,y),(u,v)) | x+v=y+u} на множестве .

6.  Определить, выполняются ли для отношений задач 3а), 3в), 3г) свойства рефлексивности, антирефлексивности, симметричности, антисимметричности. Какими соответствующими свойствами обладают матрицы данных отношений?

7.  Построить бинарное отношение:

а) рефлексивное, симметричное, не транзитивное;

б) рефлексивное, антисимметричное, не транзитивное;

в) рефлексивное, не симметричное, транзитивное;

г) не рефлексивное, антисимметричное, транзитивное;

8.  Доказать, что следующие отношения являются отношениями эквивалентности:

а) ;

б) ;

в) .

9.  Проиллюстрировать с помощью диаграмм Венна разбиение множества U на следующие классы эквивалентности:

а) ,; б) , , .

10.  Выяснить, какие из следующих подмножеств множества являются функциями из в :

а) ; б) ;

в) ; г) .

11.  Выяснить, какие из следующих функций являются взаимно – однозначными из в :

а) ; б) ;

в) ; г) .

Глава III. Логика высказываний.

Функции алгебры логики

Высказыванием называется повествовательное утверждение, которое либо истинно, либо ложно (но не то и другое одновременно). Высказывание называется простым (элементарным), если оно рассматривается как одно неделимое целое. Простые высказывания обозначаются переменными, принимающими истинностные значения И и Л. Сложное высказывание - высказывание, составленное из простых с помощью логических связок. Логические связки (операции) будем интерпретировать как функции, заданные на множестве {И, Л} («истина», «ложь»} со значением в этом же множестве.

Функцией алгебры логики (или логической функцией) f от n переменных называется функция типа , где В={0,1}.

Любую логическую функцию можно задать таблицей истинности:

Значения переменных	Значение функции

Следующая таблица задает логические функции двух переменных:

		обозначение	наименование
			константа 0
			конъюнкция
			переменная
			переменная
			неравнозначность
			дизъюнкция
			стрелка Пирса
			эквивалентность
			отрицание
			импликация
			отрицание
			импликация
			штрих Шеффера
		1	константа 1

Логическая функция существенно зависит от переменной , если существует такой набор значений , что