GED / Шевелев / Diskret_mat1

Ю. П. Шевелёв

ДИСКРЕТНАЯ

МАТЕМАТИКА

Часть 1

Теория множеств Булева алгебра

I

С

А В

R = А U В I С

f = RS + RS + PQS

Томск 2003

Министерство образования Российской Федерации

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ

Ю.П. Шевелёв

ДИСКРЕТНАЯ

МАТЕМАТИКА

Часть 1

Теория множеств Булева алгебра

(Автоматизированная технология обучения «Символ»)

Допущено Министерством образования Российской Федерации в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению и специальности «Прикладная математика и информатика»

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

Томск 2003

2

УДК 512.563.3 (075) ББК 22.1я73

Ш 37

Рецензенты:

Профессор кафедры защиты информации и криптографии Томского государственного университета, д-р техн. наук А. М. Оранов

Отдел информатизации образования Томского политехнического университета, зав. отделом канд. техн. наук Ю.В. Карякин

Шевелев Ю. П.

Ш 37 Дискретная математика. Ч. 1: Теория множеств. Булева алгебра (Автоматизированная технология обучения «Символ»): Учебное пособие. — Томск. гос. ун-т систем управления и радиоэлектроники, 2003. — 118 с.

Изложены основные сведения из теории множеств: алгебра множеств, бинарные отношения, бесконечные множества, теория нечётких множеств. Из булевой алгебры представлены разделы: минимизация булевых функций в дизъюнктивных и конъюнктивных нормальных формах с учётом неопределенных состояний, булевы уравнения, первые сведения о булевом дифференциальном исчислении. Во второй части освещены темы: теория конечных автоматов — синтез логических (комбинационных) и многотактных схем, теорема Поста о функциональной полноте; комбинаторика — размещения, сочетания и перестановки с повторениями и без повторений, разбиение множеств и др.; теория графов — графы и ориентированные графы, сети, деревья и др., а также приведены контрольные работы по всему курсу дискретной математики. В первой части более 1500 упражнений, во второй — более 2000. Все упражнения закодированы, что обеспечивает возможность работы с пособием в режиме автоматизированного самоконтроля с применением устройств СИМВОЛ или их компьютерных аналогов (разработки Томского государственного университета систем управления и радиоэлектроники).

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

УДК 512.563.3 (075)

ББК 22.1я 73

Набор С.Э. Астапенко Верстка Ю.П. Шевелев

©Томский гос. ун-т систем управления и радиоэлектроники, 2003

©Шевелев Ю.П., 2003

3

СОДЕРЖАНИЕ ПЕРВОЙ ЧАСТИ

ПРЕДИСЛОВИЕ ................................................................	7 3.7. Об эквивалентности множеств точек геометричес-
	ких объектов .......................................................................	37

	ТЕОРИЯ МНОЖЕСТВ		3.8. Трансфинитные числа					38
	ВВЕДЕНИЕ .........................................................................	9	3.9.	Парадоксы теории множеств				38
	1. АЛГЕБРА МНОЖЕСТВ...........................................	10	3.10. Упражнения		на тему	«Парадоксы	теории
	1.1. Множества	10
			множеств» ...........................................................................					39
	1.2. Подмножества .............................................................	12	4. ЭЛЕМЕНТЫ ТЕОРИИ НЕЧЕТКИХ МНОЖЕСТВ43
	1.3. Диаграммы Венна. Универсальное множество	13	4.1.	Вводные замечания.....................................................				43
	1.4. Объединение множеств	14	4.2. Нечеткие множества ...................................................					44
	1.5. Пересечение множеств	15	4.3. Объединение нечетких множеств ..............................					44
	1.6. Дополнение множеств	16	4.4. Пересечение нечетких множеств ...............................					45
	1.7. Законы де Моргана	17	4.5. Дополнение нечеткого множества.............................					46
			4.6. Разность и
	1.8. Разность множеств	18			симметрическая разность нечетких
			множеств					47
	1.9. Симметрическая разность множеств.........................	18	4.7.	Основные свойства операций над нечеткими
	1.10. Закон поглощения	19	множествами.......................................................................					47
	1.11. Закон склеивания.......................................................	20		БУЛЕВА АЛГЕБРА
	1.12. Теоретико-множественные преобразования.......	21						48
	2. БИНАРНЫЕ ОТНОШЕНИЯ		ВВЕДЕНИЕ .......................................................................
		22	1. ВВОДНЫЕ ПОНЯТИЯ					48
	2.1. Декартово произведение множеств	22
			1.1. Двоичные числа					48
	2.2. Степень множества .....................................................	23	1.2. Понятие высказывания					49
	2.3. Понятие бинарного отношения..................................	23	1.3. Аксиомы булевой алгебры					50
	2.4. Симметрия отношений ...............................................	25	1.4. Свойства дизъюнкции и конъюнкции					51
	2.5. Транзитивность отношений........................................	25	1.5. Теоремы одной переменной					51
	2.6. Рефлексивность отношений .......................................	26	1.6. Дизъюнктивные и конъюнктивные формы					52
	2.7. Отношения эквивалентности......................................	26	1.7. Теоремы поглощения, склеивания и де Моргана					53
	2.8. Отношения строгого порядка.....................................	27	1.8. Инвертирование сложных выражений					54
	2.9. Отношения нестрогого порядка.................................	27	2. ДИЗЪЮНКТИВНЫЕ			ФОРМЫ	БУЛЕВЫХ
	2.10. Упорядоченные множества	28
			ФУНКЦИЙ .................................................................					54
	2.11. Отношения соответствия	28	2.1.	Понятие булевой функции..........................................				54
	2.12. Функциональные отношения. Отображения	29	2.2.	Как задать булеву функцию........................................				55
	2.13. Реляционная алгебра	29	2.3.	Минтермы....................................................................				56
	3. БЕСКОНЕЧНЫЕ МНОЖЕСТВА	31	2.4.	Совершенная дизъюнктивная нормальная форма....				57
	3.1. Вводные замечания	31	2.5.	Теорема разложения для ДНФ...................................				58
	3.2. Сравнение бесконечных множеств	31	2.6.	Карта Вейча .................................................................				59
	3.3. Счетные множества	33	2.7.	Нанесение функций на карту Вейча ..........................				60
	3.4. Несчетные множества	35	2.8.	Нахождение СДНФ при помощи карт Вейча ...........				60
	3.5. Гипотеза континуума	36	2.9.	Алгебраическое упрощение булевых функций.........				62
	3.6. Трансцендентные числа	36	2.10. Понятие импликанты ................................................					63
			2.11. Метод Квайна ............................................................					63

4

	2.12. Нахождение простых импликант по карте Вейча...				64	7.5. Числовое представление систем булевых функций			..88
	2.13. Метод Петрика...........................................................				65	7.6. Зависимость и независимость булевых функций......89
	2.14. Минимизация булевых		функций	при помощи	67	7.7. Виды зависимости между двумя функциями ............90
	карт Вейча ..........................................................................					7.8. Нахождение явного вида логической зависимости			91
	3. КОНЪЮНКТИВНЫЕ		ФОРМЫ	БУЛЕВЫХ	68	8. БУЛЕВЫ УРАВНЕНИЯ			92
	ФУНКЦИЙ ........................................................................
	3.1. Основной способ нахождения КНФ...........................68					8.1. Уравнения с одной неизвестной переменной............			92
	3.2. Макстермы ...................................................................68					8.2. Уравнения	с несколькими неизвестными		94
	3.3. Совершенная конъюнктивная нормальная форма				69	переменными.......................................................................
						8.3. Уравнения конъюнктивного типа			94
	3.4. Теорема разложения для КНФ				70
						8.4. Уравнения дизъюнктивного типа			95
	3.5. Нахождение сокращенных КНФ				70
						8.5. Другие типы булевых уравнений			96
	3.6. Нахождение тупиковых и минимальных КНФ				71
						8.6. Булевы уравнения с несколькими неизвестными
	3.7. Перевод функций из КНФ в ДНФ				71
						функциями			97
	4. НЕПОЛНОСТЬЮ ОПРЕДЕЛЕННЫЕ БУЛЕВЫ				72	8.7. Ещё раз о формах высших порядков .........................			98
	ФУНКЦИИ ........................................................................					8.8. Неразрешимые уравнения			99
	4.1. Понятие неполностью		определенной булевой
	функции ...............................................................................				72	9. ПОРОГОВЫЕ ФУНКЦИИ			99
	4.2. СДНФ неполностью определенных функций ...........				72	9.1. Основные понятия .......................................................			99
	4.3. СКНФ неполностью определенных функций............				73	9.2. Функции, определяемые порогом при неизмен-
	4.4. Минимизация ДНФ неполностью определенных					ных весах ..........................................................................			100
	функций ...............................................................................				73	9.3. Теоремы о пороговых функциях ..............................			101
	4.5. Минимизация	КНФ неполностью		определенных	75	9.4. Нахождение пороговых функций.............................102
	функций ...............................................................................					9.5. Мажоритарные функции			103
	5. ФОРМЫ ВЫСШИХ ПОРЯДКОВ.............................				76	9.6. Симметрические мажоритарные функции			104
	5.1. Понятие порядка булевой функции				76
	5.2. Граф-схема булевой функции.....................................				77	10. БУЛЕВО	ДИФФЕРЕНЦИАЛЬНОЕ		105
	5.3. Абсолютно минимальные формы				78	ИСЧИСЛЕНИЕ...............................................................
						10.1. Аксиомы алгебры Жегалкина			105
	5.4. Повышение порядка булевых функций				78
						10.2. Перевод булевых выражений в алгебру Жегал-
	5.5. Классификация форм булевых функций				79
						кина и наоборот ..............................................................			105
	5.6. О классификации форм высших порядков ................				79	10.3. Применение карт Вейча в алгебре Жегалкина......			106
	6. СИММЕТРИЧЕСКИЕ БУЛЕВЫ ФУНКЦИИ .....				81	10.4. Понятие производной от булевой функции.......			108
	6.1. Понятие симметрической функции............................				81	10.5. Производная первого		порядка	109
	6.2. Способы представления симметрических функций....				81	10.6. Дифференцирование		булевых функций
	6.3. Операции над симметрическими функциями............82					с применением	карт Вейча.........................................		110
	6.4. Разложение симметрических функций для ДНФ......83					10.7. Смешанные производные .......................................			111
	6.5. Разложение симметрических функций для КНФ......				84	10.8. Теоремы о разложении булевых функций.............			111
	6.6. Общий случай симметрии функций...........................				84	10.9. Разложение булевых функций в ряд Тейлора .......			112
	7. ЧИСЛОВОЕ	ПРЕДСТАВЛЕНИЕ		БУЛЕВЫХ	85	10.10. Нахождение отдельных конъюнкций ряда			114
	ФУНКЦИЙ .......................................................................					Тейлора.............................................................................
	7.1. Понятие изображающего числа булевой функции ...				85	ЛИТЕРАТУРА			116
	7.2. Операции над изображающими числами				86		................................................................
									117
	7.3. Изображающие числа функций высших порядков				87	УКАЗАТЕЛЬ ТЕРМИНОВ .........................................
	7.4. Восстановление булевой функции по изображаю-
	щему числу.........................................................................				87

5

СОДЕРЖАНИЕ ВТОРОЙ ЧАСТИ

ТЕОРИЯ КОНЕЧНЫХ АВТОМАТОВ

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

1.ДИОДНО-РЕЗИСТОРНЫЕ СХЕМЫ………………5

1.1.Вводные понятия ……………………………………. 5

1.2.Простейшие диодно-резисторные схемы…………... 6

1.3.Выпрямительный мост………………………………. 7

2.КОНТАКТНЫЕ СТРУКТУРЫ……………………. 8

2.1.Контактные элементы……………………………….. 8

2.2.Контактная реализация логических операций И,

ИЛИ, НЕ………………………………………………….. 9

2.3.Построение контактной структуры по булевой функции…………………………………………………….9

2.4.Логический синтез контактных структур.…….……. 11

2.5.Мостиковые структуры……………………………… 12

2.6.Симметрические структуры………………….……… 13

2.7.Полная симметрическая структура Шеннона ……... 14

2.8.Структура «чет-нечет»………………………………. 14

2.9.Пример практического применения структуры

«чет-нечет»……………………………………………….. 14

2.10.Структуры с перестраиваемой схемой соеди-

нений………………………………………….…………….15

2.11.Примеры контактных структур……………………16

2.12. Контактные структуры с элементами памяти .... 18

3. КОМБИНАЦИОННЫЕ СХЕМЫ…………………. 20

3.1.Логические элементы……………………………….. 20

3.2.Элемент И…………………………………………….. 20

3.3.Элемент ИЛИ………………………………………… 20

3.4.Инвертор и схема И-НЕ……………………………... 21

3.5.Понятие суперпозиции………………………………. 22

3.6.О нагрузочной способности логических эле-

ментов……………………………………………………... 22

3.7.Комбинационные схемы и булевы функции ДНФ

и КНФ……………………………………………………... 23

3.8.Комбинационные схемы и булевы функции выс-

ших порядков…………………………………………….. 24

3.9.Логический синтез комбинационных схем……. ….. 25

3.10. Синтез преобразователя двоичного числа в код «2 из 5»……………………………………………… 26

3.11.Полный дешифратор……………………………….. 27

3.12.Синтез неполного дешифратора…………………… 28

3.13.Мультиплексор……………………………………… 28

3.14.Однородные среды…………………………….…… 29

3.15.Схемы сравнения двух двоичных чисел………….. 30

3.16.Схема «чет-нечет»………………………………….. 31

3.17.Синтез двоичного сумматора…………………….... 31

3.18.Вычисление бесповторных булевых функций.…… 32

3.19.Обнаружение одиночных искажений в двоич-

ных кодах…………………………………………………. 33

3.20.Коды Хэмминга…………………………………….. 35

3.21.Комбинационный формирователь кодов Хэм-

минга………………………………………………………. 36

3.22.Рефлексные коды. Коды Грея…………………… 36

3.23.Преобразователь кода Грея в весовой двоич-

ный код…………………………………………………… 37

3.24.Преобразование произвольного рефлексного ко-

да в двоичный весовой код……………………………. 37

4. ФУНКЦИОНАЛЬНАЯ ПОЛНОТА СИСТЕМЫ ЛОГИЧЕСКИХ ЭЛЕМЕНТОВ………………………... 39

4.1.Понятие функциональной полноты……………….. 39

4.2.Самодвойственные функции…………………………39

4.3.Линейные функции………………………………… 40

4.4.Монотонные функции………………………………40

4.5.Функции, сохраняющие единицу…………………. 41

4.6.Функции, сохраняющие нуль………………………42

4.7.Теорема Поста о функциональной полноте….……43

4.8.Функции двух аргументов………………………… 44

4.9.Минимальные полные системы элементарных функций………………………………………………….. 46

4.10.О реальных системах логических элементов.…... 47

5. МНОГОТАКТНЫЕ АВТОМАТЫ………………. 49

5.1.Однотактные и многотактные автоматы…………. 49

5.2.Триггер типа RS…………………………………….. 49

5.3.Триггер типа Т ……………………………………... 50

5.4.Асинхронные автоматы на Т-триггерах…………... 51

5.5.Синтез синхронных автоматов на триггерах типа Т……………………………………………………. 52

5.6.Триггер типа JK…………………………………... 53

5.7.Синтез многотактных автоматов на JK-триг-

герах………………………………………………………54

5.8.Сдвиговый регистр……………………………….. 55

5.9.Синтез многофункциональных автоматов……….56

5.10.Основная модель конечного автомата …………56

5.11.Автомат Мили ……………………………………57

5.12.Автомат Мура …………………………………… 58

КОМБИНАТОРИКА

ВВЕДЕНИЕ…………………………………………….. 59

1. ОСНОВНЫЕ ФОРМУЛЫ КОМБИНАТОРИКИ.59

1.1.Понятие факториала……………………………. 59

1.2.Правило произведения в комбинаторике…….. 60

1.3.Правило суммы в комбинаторике…………….. 61

1.4. Правило суммы и диаграммы Венна ………… 62

1.5.Перестановки без повторений…………………… 62

1.6.Перестановки с повторениями……………………. 62

1.7.Размещения без повторений …………………….. 63

1.8.Размещения с повторениями …………………….. 64

1.9.Сочетания без повторений ………………………. 65

1.10.Свойства сочетаний без повторений…………... 67

1.11.Сочетания с повторениями………………………68

1.12.Упражнения на применение основных фор-

мул комбинаторики…………………………………….. 69

2. КОМБИНАТОРНЫЕ ЗАДАЧИ…………………...70

2.1.Разбиение множества на два подмножества…70

2.2.Разбиение множества на несколько подмно-

жеств …………………………………………………….. 72

2.3.Задача о переключателях …………………………..73

2.4.Задача о расписании занятий……………………… 74

2.5.Задача о подборе экипажа космического ко-

рабля …………………………………………………….. 75

2.6.Задача о беспорядках ……………………………… 75

2.7.Двоично-кодированные системы …………….……76

2.8.Код Морзе ………………………………………….. 77

2.9.Простые числа ……………………………………... 78

2.10.Задача о числе делителей …………………………79

2.11.Задача о вписанных треугольниках……………… 80

2.12.Задача о разбиении числа на слагаемые………… 81

2.13.Задача о «счастливых» троллейбусных би-

летах …………………………………………………….. 82

2.14.Упражнения по всему курсу комбинаторики…… 83

		6
	ТЕОРИЯ ГРАФОВ	форм ……………………………………………………...117
	ВВЕДЕНИЕ…………………………………………….. 87	2.4. Нахождение совершенных дизъюнктивных нор-
	1. ВВОДНЫЕ ПОНЯТИЯ……………………………. 87	мальных форм …………………………………………. 117
	1.1. Граф ………………………………………………… 87	2.5. Теорема склеивания ……………………………… 118
	1.2. Псевдограф. Мультиграф ……………………….. 87	2.6. Нахождение сокращенных дизъюнктивных нор-
	1.3.Подграф. Надграф. Частичный граф ……………. 88	мальных форм …………………………………………. 118
	1.4. Смежность. Инцидентность. Степень вершины… 89	2.7. Нахождение минимальных дизъюнктивных нор-
	1.5. Однородный граф. Полный граф. Дополнение	мальных форм …………………………………………. 118
	графа ………………………………………………….…. 90	2.8. Нахождение минимальных ДНФ инверсий буле-
	1.6. Объединение и пересечение графов ……………. 90	вых функций …………………………………………… 118
	1.7. Изоморфизм ………………………………………... 91	2.9. Нахождение минимальных конъюнктивных нор-
	1.8. Матрицы смежности и инцидентности ………….. 92	мальных форм …………………………………………. 118
	2. СВЯЗНЫЕ ГРАФЫ……………………………….. 93	2.10. Минимизация ДНФ с учетом неопределенных
	2.1. Маршруты, цепи, циклы …………………………... 93	состояний ……………………………………………….. 119
	2.2. Связность графа ……………………………………94
		2.11. Нахождение минимальных КНФ с учетом не-
	2.3. Нахождение простых цепей ……………………... 95
		определенных состояний ……………………………… 119
	2.4. Применение метода нахождения всех простых
		2.12. Симметрические функции…. …………………… 119
	цепей …………………………………………………….. 95
		2.13. Числовое представление систем булевых
	2.5. Эйлеровы цепи и циклы. Уникурсальная линия... 96
		функций …………………………………………………. 119
	2.6. Гамильтоновы графы …………………………….. 98
		2.14. Булевы уравнения ………………………………. 119
	2.7. Задача о коммивояжере ………………………… 99
		2.15. Пороговые функции …………………………….. 120
	2.8. Двудольные графы ………………………………... 99
		2.16. Нахождение производных от булевых функций ..120
	2.9. Метрика графа …………………………………….. 100
		3. ТЕОРИЯ КОНЕЧНЫХ АВТОМАТОВ ………... 120
	3. ПЛАНАРНЫЕ И ПЛОСКИЕ ГРАФЫ………… 101
		3.1. Синтез контактных структур ………………………120
	3.1. Вводные понятия …………………………………. 101
		3.2. Построение комбинационной схемы на основе
	3.2. Теорема Эйлера о плоских графах …………….. 101
		ДНФ булевой функции ……………………………….. 120
	3.3. Гомеоморфизм …………………………………….. 101
	3.4. Критерий Понтрягина-Куратовского ……………. 102	3.3. Построение комбинационной схемы на основе
	3.5. Двойственные графы ………………………………103	КНФ булевой функции ……………………………….. 121

3.6.Инверсные структуры и двойственные графы… 104 3.4. Синтез комбинационной схемы …………………. 121

3.7.Деревья и лес ………………………………….….. 104 3.5. Синтез преобразователя кодов ……………….….. 121

3.8. Фундаментальная система циклов …………….. 105 3.6. Синхронный автомат на JK-триггерах …………. 121

3.9.Кодирование деревьев …………………………… 105 3.7. Синтез автомата на JK-триггерах ……………..….. 122

3.10.Построение дерева по его коду ………………. 106 4. КОМБИНАТОРИКА………………………………. 122

	3.11. Разрезы ……………………………………….…… 107	4.1. Число сочетаний без повторений и число раз-
	3.12. Хроматическое число графа. Гипотеза четы-	мещений с повторениями …………………………….. 122
	рех красок ……………………………………………….108	4.2. Задачи на применение основных формул ком-
	4. ОРИЕНТИРОВАННЫЕ ГРАФЫ……………….. 108	бинаторики ……………………………………………… 122
	4.1. Понятие орграфа. Матрица смежности. Изомор-
		5. ТЕОРИЯ ГРАФОВ…………………………………. 123
	физм ……………………………………………………... 108
		5.1. Двойственные графы ………………………….….. 123
	4.2. Степень вершины орграфа ………………………. 109
		5.2. Нахождение простых цепей ……………………... 123
	4.3. Маршруты, цепи, циклы в орграфах …………... 110
		5.3. Декодирование деревьев …………………………. 123
	4.4. Связность орграфа. Эйлеровы цепи и циклы
		КРАТКО О СИСТЕМЕ «СИМВОЛ»
	в орграфе ……………………………………………….. 110
	4.5. Полный орграф …………………………………… 111	1. ОБЩИЕ СВЕДЕНИЯ О СИСТЕМЕ «СИМВОЛ» 124
	4.6. О теории трансверсалей …………………………..112	1.1. Компьютерное обучение …………………………. 124
	4.7. Метод нахождения всех трансверсалей ………... 112
		1.2. Недостатки систем автоматизированного кон-
	4.8. Нахождение максимальной пропускной способ-
		троля …………………………………………………….. 124
	ности транспортной сети ……………………………... 113
		1.3.Четыре уровня ИДС «Символ» ……………….…. 124
	4.9. Орграфы и бинарные отношения. Диаграммы
		1.4. Анализ ответов в ИДС «Символ» ……………… 125
	Хассе …………………………………………………….. 114
		1.5. Внешний контроль в ИДС «Символ» …………. 125
	4.10. Сколько существует графов? …………………... 115
		1.6. Специализированное устройство «Символ» …… 125
	КОНТРОЛЬНЫЕ РАБОТЫ
		2. ПРИМЕНЕНИЕ ИДС «СИМВОЛ»……………... 125
	ВВЕДЕНИЕ ……………………………………………. 116	2.1. Область применения ……………………………… 125
	1. ТЕОРИЯ МНОЖЕСТВ …………………………… 116	2.2. ИДС «Символ» в начальной школе ……….…… 126
	1.1. Операции над множествами ………………….…. 116	2.3. Таблицы сложения и умножения …………….….126
	1.2. Теоретико-множественные преобразования ……. 116	2.4. ИДС «Символ» в средней школе. Дидактичес-
	1.3. Упрощение формул с учетом отношения вклю-	кий фонд ………………………………………………... 126
	чения …………………………………………………….. 116	2.5. Дидактический фонд ИДС «Символ» для вузов.. 127
	2. БУЛЕВА АЛГЕБРА ………………………………. 117	2.6. Перспективы развития ИДС «Символ» …………127
	2.1. Теорема поглощения ……………………………… 117	ЛИТЕРАТУРА………………………………………128
	2.2. Инвертирование дизъюнктивных нормальных	ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ ………………129
	форм ……………………………………………………...117
	2.3. Инвертирование конъюнктивных нормальных

7

ПРЕДИСЛОВИЕ

Что такое дискретная математика? Какими призна-	эстетической точки зрения ей нет равных:	это самая
ками характеризуются входящие в нее разделы? Хотя в	«красивая» из всех наук современности.
целом границы, определяющие дискретную математику,	В пособии булева алгебра представлена 10 главами.
в значительной степени являются условными, все же	Некоторые из них по содержанию освещены достаточно
можно указать признак, позволяющий достаточно четко	полно, другие же являются лишь вводно-ознакомитель-
разделить всю современную математику на две состав-	ными (подобно разделу «Теория множеств»), носящими
ляющие. Суть этого признака заключена в самом назва-	пропедевтический характер (пропедевтика — введение в
нии «дискретная математика», где дискретность высту-	какую-либо науку, подготовительный курс. От греч.
пает как противоположность непрерывности, обознача-	propaideuō — предварительно обучаю). К ним относятся
ющая отсутствие понятия предельного перехода. С этой	такие темы, как «Булево дифференциальное исчисле-
точки зрения в дискретную математику могут быть	ние», «Булевы уравнения», «Пороговые функции» и др.
включены такие разделы, как теория множеств, теория	Предполагается, что на основе полученных сведений по
дискретных автоматов, математическая логика, теория	той или иной теме студент в дальнейшем при необхо-
графов и сетей, комбинаторика, векторная и матричная	димости сможет самостоятельно глубже изучить соот-
алгебры, теория чисел, теория конечных групп, колец и	ветствующие вопросы, обратившись к специальной
полей, теория алгебраических систем и многие другие.	литературе. В очной системе образования на освоение
С позиций «чистой» математики среди этих разделов нет	всего раздела булевой алгебры следует планировать 14
второстепенных. С прикладной же точки зрения не все	часов лекций и 20 часов практических занятий. На само-
разделы одинаково важны. Это обстоятельство наклады-	стоятельное изучение потребуется не менее 45 часов.
вает определенные ограничения на подбор материала для	Необходимо отметить, что в литературе наряду с
учебного пособия, чтобы не слишком обременять сту-	термином «булева алгебра логики» используются и
дентов избыточной информацией, особенно на началь-	синонимы, такие, как алгебра Буля [14; 16; 24], алгебра
ном этапе знакомства с элементами дискретной мате-	логики [4; 24; 50], алгебра событий [11], алгебра кнопок
матики.	[24], алгебра исчисления высказываний [1], пропозицио-
Данное пособие предназначено не для математиков,	нальная логика [24], булева алгебра [12, с. 8;	20, с. 21;
оно ориентировано на студентов, обучающихся в техни-	44; 50, с. 75; 51, с. 542, 575], логика предложений [9],
ческих вузах и техникумах, в учебных программах кото-	математическая логика [13], бинарная булева алгебра
рых предусмотрены предметы, связанные с электрони-	[21], алгебра релейных цепей [23] и др. Не все эти
кой, информатикой и вычислительной техникой. В связи	термины являются полными синонимами (полные сино-
с этим в пособие включены разделы дискретной матема-	нимы — вообще большая редкость). Однако с приклад-
тики, имеющие прямое отношение к электронике, вы-	ной точки зрения различия между ними несущественны,
числительной технике и информатике: теория множеств,	поэтому практически любой из них можно взять за
булева алгебра логики, теория конечных автоматов, ком-	основу. При подготовке данного пособия начальным
бинаторика и теория графов. Эти разделы отличаются	ориентиром послужили книги [12; 14; 20; 44], в которых
наиболее яркой прикладной ориентацией. Их вполне	используется термин «булева алгебра», в связи с чем этот
можно рассматривать как общеобразовательные дисцип-	термин принят и в данном пособии. Другие же авторы
лины, составляющие минимум, обязательный для каждо-	часто употребляют словосочетание «алгебра логики». Это
го, кто впервые приступает к изучению основ дискрет-	можно объяснить тем, что с точки зрения «чистой»
ной математики с целью применения полученных сведе-	математики булевых алгебр, в наиболее общем случае
ний в своей практической деятельности.	определяемых как частично упорядоченные множества
Пособие состоит из двух частей. Первая часть в ос-	специального типа [24, с. 74], существует много и их
новном является теоретической. В нее входит теория	интерпретация в виде алгебраической системы высказы-
множеств и булева алгебра (алгебра логики). Теория	ваний является лишь частным случаем. Однако термин
множеств представлена как вводно-ознакомительный	«булева алгебра» также имеет право на существование, и
курс. Он рассчитан на 8 лекционных часов и 6–8 часов	его следует использовать хотя бы для того, чтобы во имя
практических занятий. При самостоятельном изучении	исторической справедливости не забывать, с чьим
потребуется до 20 часов, если считать обязательным	именем связан важнейший раздел математики, который
выполнение 25 % всех упражнений.	по возможностям его практического применения не
Наибольшее внимание в пособии уделено булевой	имеет себе равных среди других булевых алгебр.
алгебре — важнейшему разделу современной математи-	Во второй части пособия значительное внимание
ки. Во-первых, булева алгебра является фундаментом	уделено прикладным вопросам дискретной математики.
всех без исключения информационных технологий. Во-	Особенно это относится к разделу «Теория конечных
вторых, с ее помощью решаются самые разнообразные	автоматов», где на многих примерах показано приме-
логические задачи (о беспорядках, о расписании, о на-	нение булевой алгебры. На весь этот раздел достаточно
хождении всех трансверсалей и др.). В третьих, она	16 лекционных часов и 30 часов практических занятий.
находит широчайшее применение в технических облас-	При самостоятельном его изучении потребуется около 60
тях (логический синтез контактных структур, комби-	часов, если выполнять 25 % всех упражнений.
национных и многотактных электронных схем, их	Темы «Комбинаторика» и «Теория графов» представ-
минимизация, анализ работы и др.). Даже с чисто	лены в пособии в небольшом объеме. Они могут быть
	освоены студентами за 8 лекционных часов и 16 часов

8

практических занятий. На самостоятельное их изучение

ческих вузов, для которых математика — инструмент для

необходимо не менее 30 часов.

практической деятельности.

Таким образом, материал обеих частей данного посо-

Кроме учебных пособий, существуют научно-попу-

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

лярные издания, например [6; 36; 52]. В большинстве

Из них 46 часов — лекции и 74 часа — практические

случаев они не содержат сведений, необходимых инже-

занятия, но при условии, что выполняется хотя бы 25 %

неру в его практической работе. По ним невозможно

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

изучить какой-либо раздел математики. Но это не зна-

сократить до 10 %, то на практические занятия вместо 74

чит, что читать их бесполезно. Даже сложные понятия

достаточно 45 часов. При самостоятельном изучении

(типа простой импликанты в булевой алгебре или функ-

пособия необходимо не менее 160 часов.

ционально полной системы в теории комбинационных

В пособии более 3500 упражнений. Большинство из

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

них просты, и для их выполнения достаточно ознако-

воспринимаются при чтении, после чего без особого тру-

миться с соответствующим теоретическим материалом.

да узнаются при изучении специальных изданий.

Ни к одному из упражнений ответы в открытом виде

При подготовке данного пособия автор стремился

в

не приведены. Вместо них указаны специальные коды,

основном к доступному изложению материала (за

счет

внешне не несущие никакой информации об ответах. При

определенного снижения строгости), чтобы его с малыми

использовании пособия в традиционной (беском-

затратами труда и времени могли освоить как студенты

пьютерной) системе обучения на коды можно не обра-

технических вузов, так и школьники старших классов

щать внимания. Иное дело, если воспользоваться уст-

общеобразовательных школ, и вообще каждый, кто

ройством «Символ» либо его компьютерным аналогом

изъявит желание ознакомиться с вводными поняти-ями

(устройство «Символ» и компьютер входят в состав тех-

представленных в данном пособии разделов диск-ретной

нических средств информационно-дидактической систе-

математики.

мы (ИДС) «Символ», разработанной лабораторией ИДС

Пособие написано в соответствии с программой

кафедры высшей математики ТУСУРа). В этом случае

подготовки и выпуска учебных пособий, разработанной

студент может работать над упражнениями в режиме

кафедрой высшей математики ТУСУРа. Программа

самоконтроля, совершенно не нуждаясь в услугах препо-

охватывает все традиционные разделы курса высшей

давателя. Исключение составляют только девять упраж-

математики для технических вузов, а также наиболее

нений подраздела

3.10 теории множеств, где предла-

важные в прикладном отношении темы дискретной

гается разобраться в парадоксах, т. е. рассуждениях, при-

математики.

водящих к утверждениям, противоречащим доказанным

Автор выражает глубокую благодарность заведующе-

теоремам и здравому смыслу. Эти упражнения не со-

му кафедрой высшей математики ТУСУРа профессору

держат ни кодов,

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

Леониду

Иосифовичу Магазинникову за

активное

со-

рассуждения студентов могут быть оценены только на

действие в работе над пособием на всех ее этапах — от

уровне неформального внешнего контроля.

замысла

до

опубликования;

заведующему СКБ

«Им-

Благодаря большому числу кодированных упражне-

пульс»,

канд.

техн. наук, доценту каф. промышленной

ний, содержащихся в пособии, создаются благоприятные

электроники

ТУСУРа Михаилу

Юрьевичу Шевелеву,

условия для организации самостоятельной работы сту-

проверившему

решения и коды

большей

части

задач

дентов в системе дистанционного образования. При этом

пособия и разработавшему систему автоматического ко-

кодированные упражнения могут быть использованы не

дирования заданий, применение которой позволило мно-

только на этапе самоподготовки, но и для проведения

гократно сократить трудозатраты на кодирование упраж-

контрольных работ, а также на зачетах и экзаменах. При

нений (по сравнению с устройством «Символ»); рецен-

формировании контрольных заданий преподаватель мо-

зенту

доктору

технических наук,

профессору кафедры

жет либо выбирать упражнения из данного пособия, либо

защиты

информации и криптографии Томского

госу-

разрабатывать свои и самостоятельно их кодиро-вать.

дарственного

университета

Александру

Михайловичу

Операции кодирования в

системе

«Символ» авто-

Оранову, внимательно прочитавшему рукопись и выска-

матизированы. При отсутствии компьютера кодировать

завшему ряд существенных замечаний, что во многом

можно и вручную с применением специализированных

способствовало улучшению содержания пособия,

и ре-

устройств. (Краткие сведения о системе «Символ» приве-

цензенту заведующему отделом информатизации образо-

дены в конце второй части данного пособия.)

вания

Томского политехнического университета

канд.

По всем разделам дискретной математики существует

техн.

наук

Юрию Васильевичу Карякину, рассмотрев-

обширная литература. В основном это монографии, жур-

шему пособие с позиций автоматизации самоконтроля и

нальные статьи и

учебные

пособия.

И монографии, и

внесшему ряд

рекомендаций

по

его представлению в

журнальные статьи не могут быть рекомендованы сту-

виде компьютерного учебника. Кроме того, автор благо-

дентам технических вузов, особенно при первом знаком-

дарит редактора издательства ТУСУРа Любовь Ивановну

стве с основами тех или иных направлений дискретной

Кирпиченко, благодаря усилиям которой пособие офор-

математики, поскольку они предназначены в основном

млено в соответствии с современными требованиями к

для математиков-профессионалов. Существующие учеб-

изданию учебной литературы.

ные пособия (например, [14; 27; 33; 46; 47]), написаны не

так академично, как журнальные статьи и монографии, то

ТУСУР, лаб. ИДС кафедры высшей математики.

есть в гораздо более доступном изложении, но все же

634050,

г. Томск, просп. Ленина, 40.

надо отметить, что их авторы больше ориентируются на

Телефон

(382-2) 53-32-60.

студентов университетов, изучающих математику как

Автор

свою будущую специальность, чем на студентов техни-

9

ТЕОРИЯ МНОЖЕСТВ

ВВЕДЕНИЕ

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

При самоконтроле с применением устройства «Сим- вол» (или компьютера) необходимо пользоваться сле- дующей инструкцией:

1)включить устройство, нажать кнопку СБРОС;

2)посимвольно набрать код задания. Он указан в круглых скобках перед условием упражнения;

3)посимвольно набрать ответ;

4)нажать кнопку КОНТРОЛЬ. Если загорится инди- катор ПРАВИЛЬНО, ответ признаётся верным. Если же загорится индикатор НЕПРАВИЛЬНО, ответ является неверным.

Кроме того, необходимо учитывать следующие тре- бования:

1) если ответ состоит из последовательности несколь- ких чисел (или букв), то при их вводе в устройство никакие знаки, отделяющие одно число от другого, не используются (ни пробелы, ни запятые, ни точки, ни точки с запятой). Например:

(ЕК2). Укажите элементы множества

A = {x / 7 ≤ x < 15, x — простое число}.

Ответом является последовательность чисел 7, 11, 13. В устройство вводим: ЕК271113, где ЕК2 — код зада- ния, 71113 — ответ. Числа, образующие ответ, вводятся всегда в порядке возрастания, без использования запятых (а в случае букв — в алфавитном порядке);

2)в конце условий некоторых упражнений стоит по- метка (лат.). Она напоминает о том, что ответ необхо- димо вводить в латинском алфавите;

3)ответ может быть представлен в виде какой-либо формулы:

Упростить выражения (лат.): (АНО). AI B IC U AI B IC = K

(УМП). B IC U AIC U B IC = K

В первом упражнении ответ имеет вид AIC , во втором — A UC. (Здесь и в дальнейшем упрощение осуществляется до предела.) В обоих случаях ответы набираются посимвольно за исключением того, что знак пересечения не вводится. При самоконтроле по первому

упражнению набираем: АНО А–С, где АНО — код задания, А–С — ответ, набираемый в латинском алфавите. Черточка перед буквой С обозначает знак дополнения. Он набирается перед буквой. При проверке второго ответа в устройство вводим: УМП A UC, где

УМП — код задания, A UC — ответ, набираемый также в латинском алфавите. Буквы, входящие в формулы, вво- дятся в алфавитном порядке. Между буквами необходи- мо вставить знак объединения;

4) в некоторых упражнениях после кода задания стоит знак «!» (восклицательный). Он напоминает о том, что

под кодом задания представлено более одного вопроса	и
что при самоконтроле сначала вводится код задания,	а

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

Кнопку КОНТРОЛЬ можно нажимать только после ввода всех ответов на вопросы задания. Если загорится инди- катор НЕПРАВИЛЬНО, то это значит, что среди ответов есть, по меньшей мере, одна ошибка. Где находится эта ошибка, устройство не сообщает. Ее надо найти само- стоятельно. Рассмотрим пример:

(ЯКИ)! Найдите:

а) число элементов булеана множества

А = {a, b, c, d, e, f};

б) число несобственных подмножеств множества А; в) число двухэлементных подмножеств множества А.

Здесь под одним кодом представлено три упражне- ния, ответы к которым имеют вид: 64 — на первый во- прос, 2 — на второй и 15 — на третий. При самоконтроле в устройство вводим ЯКИ64215, где ЯКИ — код задания, 64215 — ответы на все три вопроса;

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

(ПАФ). Укажите степени принадлежности каждого

~

элемента нечеткого множества A , если

~ =

A {(0,45 / 2), (0,9 / 3)}

и если базовое множество имеет вид

М = {1, 2, 3}.

Ответом являются числа: 1; 0,55; 0,1. В устройство вводим: ПАФ10,550,1, где ПАФ — код задания, все остальное — ответ.

Перечисленные требования, которые необходимо соблюдать при вводе ответов в устройство «Символ», являются основными. Существуют и другие требования, но все они достаточно просты, понятны из условий задач, поэтому рассматривать их нет необходимости.