Глава 2. Теория булевых функций.
25. Определение булевых функций и булевых векторов. Задание б.ф. с помощью таблиц истинности. Количество булевых функций от nпеременных. Фиктивные и существенные переменные. Таблица булевых функций двух переменных.
26. Задание б.ф. с помощью формул (определение формулы по индукции через элементарную формулу). Эквивалентные формулы. Подстановка и замена. Примеры эквивалентных формул.
27. Двойственность. Таблица истинности двойственной функции. Теорема о двойственной функции. Принцип двойственности. Примеры.
28. Понятие нормальной формы. Примеры. Требование на единственность и существование алгоритма построения. Теоремы о разложении. Следствия (разложение по одному элементу, по всем, двойственность).
29. Дизъюнкт и конъюнкт. ДНФ и КНФ. Основная теорема о нормальной форме. Совершенные нормальные формы и их связь с таблицей истинности.
30. Эквивалентные преобразования формул. Таблица эквивалентных формул*. Пример эквивалентного преобразования. Полином Жегалкина.
31. Импликанты. Сокращенные и минимальные дизъюнктивные формы. Минимизация методом Квайна. Пример.
32. Сокращенные и минимальные дизъюнктивные формы. Минимизация булевых функций методом Карно. Упрощение электрических схем. Примеры.
32. Функциональная декомпозиция. Простая дизъюнктивная декомпозиция. Пример. Сложные дизъюнктивные декомпозиции. Логические сети.
33. Полнота и замыкание классов функций. Лемма о представимости. Свойства замыкания (4 штуки). Замкнутый класс. Полный класс. Базис. Примеры полных классов.
34. Класс Т0 функций, сохраняющих 0 (замкнутость и мощность его). Класс Т1 функций, сохраняющих 1. Пример.
35. Класс Sсамодвойственных функций. Теорема о несамодвойственной функции. Пример.
36. Класс Mмонотонных функций. Теорема о немонотонной функции. Пример.
37. Класс Lлинейных функций. Теорема о нелинейной функции. Пример.
38. Теорема Поста (с доказательством). Следствие о четырех функциях в полной системе. Пример применения. Предполные классы. Теорема о предполных классах.
Глава 3. Элементы комбинаторики.
39. Комбинаторика. Основные правила комбинаторики - правила суммы и произведения. Комбинаторные конфигурации – выборки. Размещения с повторениями – все выборки. Формула, пример.
40. Размещения без повторений – инъективные выборки. Формула, пример. Перестановки и их групповые свойства. Сочетания – монотонные выборки (в т.ч. инъективные сочетания без повторений). Формулы, пример.
41. Три основных свойства сочетаний. Бином Ньютона. Суммы биномиальных коэффициентов. Треугольник Паскаля. Его связь с биномиальными коэффициентами.
42. Разбиения. Числа Стирлинга 2 рода. Теорема о рекуррентной формуле. Теорема о разложении по биномиальным коэффициентам.
43. Количество всех сюрьективных выборок. Числа Стирлинга 1 рода. Связь чисел Стирлинга. Числа Белла – количество всех разбиений. Теорема о числах Белла.
44. Принцип включений и исключений. Теорема обращения. Формулы обращения для биномиальных коэффициентов. Замкнутые формулы для чисел Стирлинга (все – без доказательства, только схемы доказательств). Пример.
45. Определение рекуррентного соотношения (рекуррентной формулы). Линейные и однородные соотношения, возвратная последовательность. Характеристический многочлен. Решение рекуррентного соотношения (определение и простой пример).
46. Примеры рекуррентных соотношений: арифметическая и геометрическая прогрессии, числа Фибоначчи (задача о кроликах и о последовательностях нулей и единиц). Процесс последовательных разбиений.
47. Теорема о решении однородного линейного рекуррентного соотношения (с доказательством). Пример.
48. Решение неоднородного рекуррентного соотношения. Нахождение частного решения. Пример.
49. Определение производящей функции. Известные примеры: сумма геометрической прогрессии, бином Ньютона. Простейшие формальные операции над рядами.
50. Использование рядов для доказательства тождеств. Деление многочленов и производящие функции. Таблица производящих функций.
51. Решение рекуррентных соотношений с помощью производящих функций. Общий принцип и примеры. Производящая функция чисел Фибоначчи. Неоднородный случай.