Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс
Описание файла
Документ из архива "Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 2 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Онлайн просмотр документа "Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс"
Текст из документа "Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс"
Московский Государственный Университет
имени М. В. Ломоносова
Факультет вычислительной математики и кибернетики
В. Б. Алексеев
Лекции по
дискретной математике
Москва 2004
УДК 510.5, 519.71
ББК 22.12:22.18
А47
Алексеев В. Б. Лекции по дискретной математике (учебное пособие для студентов) — М.: Издательский отдел факультета ВМиК МГУ (лицензия ИД № 05899 от 24.09.2001), 2004 г. — ?? с.
Рецензенты: проф. Ложкин С. А., д. ф.-м. н.
??
Печатается по решению Редакционно-издательского совета факультета вычислительной математики и кибернетики МГУ им. М. В. Ломоносова
??
ISBN 5-89407-147-X © Издательский отдел факультета
Вычислительной математики и
Кибернетики МГУ им. М. В. Ломоносова,
2004 г.
Оглавление
| Введение | 5 |
| Глава I. Функции алгебры логики | 6 |
| §1. Функции алгебры логики. Равенство функций. Тождества для элементарных функций | 6 |
| §2. Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме | 9 |
| §3. Полные системы. Примеры полных систем | 11 |
| §4. Теорема Жегалкина о представимости функции алгебры логики полиномом | 12 |
| §5. Понятие замкнутого класса. Замкнутость классов T0, T1 и L | 14 |
| §6. Двойственность. Класс самодвойственных функций, его | 16 |
| §7. Класс монотонных функций, его замкнутость | 18 |
| §8. Лемма о несамодвойственной функции | 19 |
| §9. Лемма о немонотонной функции | 19 |
| §10. Лемма о нелинейной функции | 20 |
| §11. Теорема Поста о полноте системы функций алгебры логики | 21 |
| §12. Теорема о максимальном числе функций в базисе алгебры | 22 |
| §13. Теорема о предполных классах | 23 |
| §14. k-значные функции. Теорема о существовании конечной полной системы в множестве k-значных функций | 24 |
| Глава II. Основы теории графов | 26 |
| §15. Основные понятия теории графов. Изоморфизм графов. | 26 |
| §16. Деревья. Свойства деревьев | 29 |
| §17. Корневые деревья. Верхняя оценка их числа | 31 |
| §18. Геометрическая реализация графов. Теорема о реализации | 33 |
| §19. Планарные (плоские) графы. Формула Эйлера | 33 |
| §20. Доказательство непланарности графов K5 и K3,3. Теорема | 35 |
| §21. Теорема о раскраске планарных графов в пять цветов | 37 |
| Глава III. Основы теории управляющих систем | 40 |
| §22. Схемы из функциональных элементов. Реализация функций | 40 |
| §23. Сумматор. Верхняя оценка сложности сумматора. Вычитатель | 43 |
| §24. Метод Карацубы построения схемы для умножения, верхняя оценка её сложности | 45 |
| §25. Дешифратор. Асимптотика сложности дешифратора. Верхняя оценка сложности реализации произвольной функции алгебры логики | 48 |
| §26. Мультиплексор. Верхняя оценка сложности мультиплексора. Метод Шеннона | 50 |
| §27. Шифратор. Верхняя оценка сложности шифратора | 53 |
| Глава IV. Основы теории кодирования | 54 |
| §28. Алфавитное кодирование. Теорема Маркова о взаимной | 54 |
| §29. Неравенство Макмиллана | 56 |
| §30. Существование префиксного кода с заданными длинами | 57 |
| §31. Оптимальные коды, их свойства | 58 |
| §32. Теорема редукции | 60 |
| §33. Коды с исправлением r ошибок. Оценка функции Mr (n) | 61 |
| §34. Коды Хэмминга. Оценка функции M1 (n) | 63 |
| Глава V. Основы теории конечных автоматов | 66 |
| §35. Понятие ограниченно детерминированных (автоматных) функций, их представление диаграммой Мура. Единичная задержка | 66 |
| §36. Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений | 68 |
| §37. Моделирование автоматной функции схемой из | 69 |
| §38. Теорема Мура. Теорема об отличимости состояний двух | 71 |
Введение
Глава I. Функции алгебры логики
§1. Функции алгебры логики. Равенство функций. Тождества для элементарных функций
1°. Функции алгебры логики.
Определение 1. Пусть E2 = {0, 1} — основное множество (исходный алфавит значений переменных), тогда 
= {(α1, …, αn) | i αiE2}. Всюду определённой булевой функцией назовём отображение f (x1, …, xn): E2. Такую функцию можно задать таблично. Например, для n = 1:
| x | 0 | 1 | x |
|
| 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
При этом функция 0 называется константой нулём, функция 1 — константой единицей, функция x — тождественной, а функция 
— отрицанием x. При этом для последней функции используется также иное обозначение:
.
Для n = 2:
| x | y | f1 | f2 | f3 | f4 | f5 | f6 | f7 |
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
При заполнении таблицы столбцы переменных заполняются в лексикографическом порядке (по возрастанию двоичных чисел).
f1 — дизъюнкция, функция «или», логическое сложение: f1 = x y.
f2 — конъюнкция: f2 = x · y = x & y = xy.
f3 — сложение по модулю 2 (исключающее «или»): f3 = x y = x + y.
f4 — импликация: f4 = x y.
f5 — эквивалентность: f5 = x ~ y =
.
f6 — штрих Шеффера: f6 = x | y =
.
f7 — стрелка Пирса: f7 = x y =
.
Лемма (о числе слов). В алфавите A = {a1, …, ar} из r букв можно построить ровно rm различных слов длины m.
Доказательство. Проведём индукцию по m. Для m = 1 утверждение очевидно. Пусть утверждение леммы верно для m – 1, то есть существует ровно rm – 1 различных слов длины m – 1. Для каждого такого слова длины m – 1 существует ровно r возможностей добавить одну букву в конец. Так как всего слов длины m – 1 — rm – 1, то различных слов длины m получится r · rm – 1 = rm. Лемма доказана.
Рассмотрим таблицу некоторой функции алгебры логики от n переменных.
Для её задания необходимо и достаточно определить её значения на 2n наборах. Таким образом, получаем, что всего различных функций от n переменных столько, сколько существует различных наборов из нулей и единиц длины 2n, т.е.
.
