Дискретка
30. Полнота системы булевых функций. Теорема Поста (без доказательства).
Множество функций алгебры логики называется полной системой, если замыкание этого множества совпадает с множеством всех функций. (В частности, для двузначной логики .) Другими словами, должна быть возможность любую функцию алгебры логики выразить формулой с использованием функций множества .
Теорема Поста
Система булевых функций F является полной тогда и только тогда, когда она не содержится ни в одном из классов , т.е. когда в ней имеется хотя бы одна функция, не сохраняющая 0, хотя бы одна функция, не сохраняющая 1, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.
Содержание
- 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. Полнота системы булевых функций. Теорема Поста (без доказательства).