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

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

ИНСТИТУТ ТЕХНОЛОГИИ И БИЗНЕСА

ДИСКРЕТНАЯ МАТЕМАТИКА

Находка

Пак Г.К. Дискретная математика. Учеб. пособие. – Находка: Институт технологии и бизнеса, 2001. - 109 с.

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

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

Рецензенты: зав. кафедрой теории функций и функционального анализа ДВГУ, д-р физ.-мат. наук, профессор Фролов Н.Н.,

декан факультета математики и математического моделирования ДВГУ, профессор Осипов В.Б.

ISBN –

г Пак Г.К., 2001

г Институт технологии и бизнеса, 2001

ОГЛАВЛЕНИЕ

Предисловие…………………………………………………………………………..

Глава 1. Множества …………………………………………………………………

1.1. Способы описания множеств…………………………………………….

1.2. Операции над множествами………………………………………………

1.3. Декартово произведение………………………………………………….

1.4. Бинарные отношения……………………………………………………...

1.5. Функции……………………………………………………………………

1.6. Эквивалентность…………………………………………………………..

1.7. Частичный порядок……………………………………………………….

1.8. Мощность множества…………………………………………………….

1.9. Счетные множества……………………………………………………….

1.10. Метод полной математической индукции……………………………….

Глава 2. Комбинаторика ……………………………………………………………

2.1. Размещения………………………………………………………………..

2.2. Сочетания………………………………………………………………….

2.3. Бином Ньютона……………………………………………………………

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

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

2.6. Принцип включения и исключения………………………………………

Глава 3. Булевы функции ………………………………………………………….

3.1. Алгебра высказываний……………………………………………………

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

3.3. Формулы алгебры логики…………………………………………………

3.4. Алгебра Буля………………………………………………………………

3.5. Эквивалентные формулы………………………………………………….

3.6. Элементарная конъюнкция. Элементарная дизъюнкция……………….

3.7. Совершенная дизъюнктивная нормальная форма……………………..

3.8. Совершенная конъюнктивная нормальная форма……………………..

3.9. Принцип двойственности…………………………………………………

3.10. Полином Жегалкина………………………………………………………

Глава 4. Замкнутые классы и полнота ……………………………………………

4.1. Замыкание множества булевых функций……………………………….

4.2. Классы функций, сохраняющих константы…………………………….

4.3. Класс самодвойственных булевых функций……………………………

4.4. Класс монотонных булевых функций……………………………………

4.5. Класс линейных булевых функций………………………………………

4.6. Три леммы…………………………………………………………………

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

4.8. Предполные классы……………………………………………………….

4.9. Замкнутые классы…………………………………………………………

Глава 5. Графы и сети ………………………………………………………………

5.1. Степень вершины графа…………………………………………………..

5.2. Способы задания графа…………………………………………………..

5.3. Изоморфизм графов………………………………………………………

5.4. Подграф, маршрут, цепь, цикл……………………………………………

5.5. Связность………………………………………………………………….

5.6. Геометрическая реализация графа……………………………………….

5.7. Эйлерова характеристика…………………………………………………

5.8.

Терема Понтрягина – Куратовского…………………………………….

5.9. Эйлеровы графы…………………………………………………………..

5.10. Оценка числа графов………………………………………………………

5.11. Деревья…………………………………………………………………….

5.12. Корневое дерево…………………………………………………………..

5.13. Сильносвязные сети………………………………………………………

5.14. Суперпозиция сетей………………………………………………………

5.15. π-сети………………………………………………………………………

Глава 6. Теория кодирования ……………………………………………………..

6.1. Алфавитное кодирование………………………………………………..

6.2. Алгоритм Маркова Ал. А. распознавания однозначности

декодирования……………………………………………………………..

6.3. Неравенство Макмиллана………………………………………………..

6.4. Коды с минимальной избыточностью…………………………………..

6.5. Код Хэмминга……………………………………………………………..

6.6. Самокорректирующиеся коды……………………………………………

Глава 7. Теория алгоритмов ……………………………………………………….

7.1. Машина Тьюринга………………………………………………………..

7.2. Язык конфигураций……………………………………………………….

7.3. Действия над машинами Тьюринга………………………………………

7.4. Вычислимые функции……………………………………………………

7.5. Программа удвоения……………………………………………………..

7.6. Программа перестановки…………………………………………………

7.7. Программа сжатия………………………………………………………..

7.8. Программа для вычисления ху, ………………………………

7.9. Канторовские нумерации…………………………………………………

7.10. Нумерация машин Тьюринга…………………………………………….

7.11. Универсальная машина Тьюринга………………………………………

7.12. Алгоритмическая неразрешимость проблемы самоприменимости……

7.13. Рекурсивные функции…………………………………………………….

Глава 8. Минимизация булевых функций ……………………………………….

8.1. Интервалы………………………………………………………………….

8.2. Сокращенная ДНФ………………………………………………………..

8.3. Тупиковая ДНФ……………………………………………………………

8.4. Метод Блейка сокращения ДНФ…………………………………………

8.5. Алгоритм перехода от сокращенной ДНФ к тупиковой……………….

Глава 9. Синтез схем из функциональных элементов …………………………

9.1. Функция Шеннона………………………………………………………..

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

Глава 10. Автоматные функции ………………………………………………….

10.1. Детерминированные функции……………………………………………

10.2. Задание детерминированных функций деревьями……………………..

10.3. Вес дерева…………………………………………………………………

10.4. Усеченное дерево…………………………………………………………

10.5. Ограниченно-детерминированные функции……………………………

10.6. Канонические уравнения…………………………………………………

10.7. Операции над ограниченно-детерминированными функциями……….

10.8. Полные системы…………………………………………………………..

Список литературы…………………………………………………………………..

ПРЕДИСЛОВИЕ

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

– множество натуральных чисел, т.е.

– множество целых неотрицательных чисел, расширенное множество натуральных чисел, т.е. = {0, 1, 2, 3, …};

– множество целых чисел, т.е. = {0, ±1, ±2, …};

– множество рациональных чисел, ={ / : , Î ; ¹ 0};

– множество вещественных чисел;

– множество комплексных чисел;

означает " x – элемент множества ;

Í означает " N есть подмножество множества ;

Û ;

– число сочетаний из по ;

– число размещений из по (r -перестановки из );

– число сочетаний с повторениями из по ;

– число размещений с повторениями из по ;

■ – конец доказательства, этот же знак ставится после формулировки теоремы, если её доказательство не приводится;

Þ – из предложения следует ;

Û – предложения и равносильны;

– для любого элемента из имеет место предложение ;

– существует элемент из , для которого верно утверждение