- •1. Предмет комбинаторики. Логические правила комбинаторики.
- •2. Число r-перестановок (с повторениями и без повторений) из n элементов. Число всех подмножеств n-элементного множества.
- •3. Число r-сочетаний из n элементов. Биномиальная теорема и следствия из нее. Основныe свойства биномиальных коэффициентов. Треугольник Паскаля.
- •4. Число ( r1, ...,rk ) -разбиений конечного множества. Другая комбинаторная интерпретация этого числа. Полиномиальная теорема.
- •5. Число r-сочетаний с повторениями из n элементов.
- •6. Метод включения и исключения (формула для числа элементов, не обладающих ни одним из заданных свойств).
- •9. Понятие рекуррентного соотношения. Рекуррентное соотношение k-го порядка для функции одной переменной, его общее решение.
- •10. Общее решение линейного однородного рекуррентного соотношения с постоянными коэффициентами.
- •11. Числа Фибоначчи. Вывод формулы n-го числа Фибоначчи решением линейного
- •12. Общее решение линейного неоднородного рекуррентного соотношения с постоянными коэффициентами.
- •13. Разбиение подстановки на циклы. Число подстановок n-элементного множества, имеющих предписанных циклический тип.
- •14. Число Стирлинга 1-го рода. Рекуррентное соотношение для числа Стирлинга 1-го рода.
- •15. Упорядоченные и неупорядоченные разбиения множеств. Число Стирлинга 2-го рода. Формула и рекуррентное соотношение для числа Стирлинга 2-го рода.
- •16. Число Белла. Рекуррентное соотношение для числа Белла.
- •17. Упорядоченные и неупорядоченные разбиения чисел. Рекуррентные соотношения для количества неупорядоченных разбиений натурального числа на фиксированное число слагаемых.
- •18. Система различных представителей. Теорема Холла (без доказательства).
- •19. Система общих представителей, критерий существования.
- •20. Теорема Рамсея.
- •26.Задача минимизации булевых функций в классе днф. Полная и приведенная системы импликант булевой функции. Связь между минимальной и тупиковой днф.
- •27. Алгоритм Квайна нахождения минимальной днф булевой функции.
- •28. Полиномиальная нормальная форма. Полином Жегалкина. Теорема о единственности представления булевой функции посредством полинома Жегалкина.
- •29. Замкнутые классы булевых функций.
- •30. Полнота системы булевых функций. Теорема Поста (без доказательства).
26.Задача минимизации булевых функций в классе днф. Полная и приведенная системы импликант булевой функции. Связь между минимальной и тупиковой днф.
Задача минимизации булевой функции в классе ДНФ формулируется следующим образом: требуется для булевой функции nпеременных F построить ДНФ с минимально возможным числом слагаемых (КрДНФ) или с минимально возможным числом вхождений литералов (МДНФ).
множество импликант булевой функции образует полную
систему импликант ,если любая существенная вершина булевой функции
покрывается хотя бы одной импликантой этого множества.
Система простых импликант называется приведенной ,если
она является полной ,а никакая ее собственная часть уже не образует полную
систему импликант.
Связь:
Всякая минимальная ДНФ некоторой функции является ее тупиковой ДНФ.
Для получения МДНФ функции f необходимо построить все ТДНФ функции f и выбрать те из них, которые содержат минимальное число букв.
27. Алгоритм Квайна нахождения минимальной днф булевой функции.
(теорема Квайна). Если в СДНФ в начале произвести все операции неполного склеивания, а затем все операции поглощения, то в результате получится сокращенная ДНФ.
Покажем, что, применяя операцию неполного склеивания, получим все простые импликанты функции. Введем операцию развертывания, которая обратна операции склеивания: это есть умножение каждого произведения на выражение вида .
Пусть – простая импликанта некоторой трех переменных. Тогда:
получатся после многократного применения этой операции дизъюнкции конституент единицы исходной функции, т.е. ее СДНФ.
28. Полиномиальная нормальная форма. Полином Жегалкина. Теорема о единственности представления булевой функции посредством полинома Жегалкина.
Под полиномом булевой функции понимаем сложение по модулю два конечного множества элементарных конъюнкций. Степенью полинома является наибольший ранг элементарной конъюнкции, входящей в этот полином.
Полином, содержащий все переменные без знака отрицания, называется полиномом Жегалкина.
Для каждой булевой функции существует единственный полином Жегалкина, реализующий эту функцию.
29. Замкнутые классы булевых функций.
Замкнутый класс в теории булевых функций — такое множество функций алгебры логики, замыкание которого относительно операции суперпозиции совпадает с ним самим: . Другими словами, любая функция, которую можно выразить формулой с использованием функций множества , снова входит в это же множество.
30. Полнота системы булевых функций. Теорема Поста (без доказательства).
Множество функций алгебры логики называется полной системой, если замыкание этого множества совпадает с множеством всех функций. (В частности, для двузначной логики .) Другими словами, должна быть возможность любую функцию алгебры логики выразить формулой с использованием функций множества .
Теорема Поста
Система булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном из классов , т.е. когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.