Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Топ:
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
Интересное:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Дисциплины:
2022-11-14 | 26 |
5.00
из
|
Заказать работу |
|
|
Дизъюнктивной нормальной формой или ДНФ называется дизъюнкция простых конъюнкций. Например — является ДНФ.
Совершенной дизъюнктивной нормальной фор
мой или СДНФ называется такая ДНФ, у которой в каждую конъюнкцию входят все переменные данного набора пременных, причём в одном и том же порядке. Например: .
Конъюнктивная нормальная форма. КНФ — это конъюнкция простых дизъюнкций.
Совершенной конъюнктивной нормальной формой (СКНФ), называется такая КНФ, у которой в каждую дизъюнкцию входят все переменные данного набора, причём в одном и том же порядке.
КНФ может быть преобразована к эквивалентной ей ДНФ путём раскрытия скобок по правилу:
1. Предмет комбинаторики. Логические правила комбинаторики.
2. Число r-перестановок (с повторениями и без повторений) из n элементов. Число всех
подмножеств n-элементного множества.
3. Число r-сочетаний из n элементов. Биномиальная теорема и следствия из нее. Основные
свойства биномиальных коэффициентов. Треугольник Паскаля.
4. Число-разбиений конечного множества. Другая комбинаторная интерпретация
этого числа. Полиномиальная теорема.
5. Число r-сочетаний с повторениями из n элементов.
6. Метод включения и исключения (формула для числа элементов, не обладающих ни
одним из заданных свойств).
7. Метод включения и исключения (формула для числа элементов, обладающих в точности
t (t ≥ 1) свойствами из числа заданных свойств).
8. Применение метода включения и исключения (задача о беспорядках, задача о числе
сюръективных отображений).
9. Понятие рекуррентного соотношения. Рекуррентное соотношение k-го порядка для
функции одной переменной, его общее решение.
10. Общее решение линейного однородного рекуррентного соотношения с постоянными
|
коэффициентами.
11. Числа Фибоначчи. Вывод формулы n-го числа Фибоначчи решением линейного
однородного рекуррентного соотношения 2-го порядка.
12. Общее решение линейного неоднородного рекуррентного соотношения с постоянными
коэффициентами.
13. Разбиение подстановки на циклы. Число подстановок n-элементного множества,
имеющих предписанных циклический тип.
14. Число Стирлинга 1-го рода. Рекуррентное соотношение для числа Стирлинга 1-го рода.
15. Упорядоченные и неупорядоченные разбиения множеств. Число Стирлинга 2-го рода.
Формула и рекуррентное соотношение для числа Стирлинга 2-го рода.
16. Число Белла. Рекуррентное соотношение для числа Белла.
17. Упорядоченные и неупорядоченные разбиения чисел. Рекуррентные соотношения для
количества неупорядоченных разбиений натурального числа на фиксированное число
слагаемых.
18. Система различных представителей. Теорема Холла (без доказательства).
19. Система общих представителей, критерий существования.
20. Теорема Рамсея.
21. Булевы функции. Способы их задания. Число булевых функций от n переменных.
22. Основные логические равносильности.
23. Разложение Шеннона и следствие из него.
24. Двойственное разложение Шеннона и следствие из него.
25. Дизъюнктивная нормальная форма (ДНФ) и конъюнктивная нормальная форма (КНФ).
Совершенные ДНФ и КНФ.
26. Задача минимизации булевых функций в классе ДНФ. Полная и приведенная системы
импликант булевой функции. Связь между минимальной и тупиковой ДНФ.
27. Алгоритм Квайна нахождения минимальной ДНФ булевой функции.
28. Полиномиальная нормальная форма. Полином Жегалкина. Теорема о единственности
представления булевой функции посредством полинома Жегалкина.
29. Замкнутые классы булевых функций.
30. Полнота системы булевых функций. Теорема Поста (без доказательства)
|
|
|
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!