Алексеев В.Б. Лекции по дискретной математике. ВМК, 2004. Электронный ресурс (1083731)
Текст из файла
Московский Государственный Университет
имени М. В. Ломоносова
Факультет вычислительной математики и кибернетики
В. Б. Алексеев
Лекции по
дискретной математике
Москва 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, т.е.
.
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
