Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Топ:
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Интересное:
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Дисциплины:
2022-11-14 | 33 |
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. Полнота системы булевых функций. Теорема Поста (без доказательства)
|
|
|
История развития хранилищ для нефти: Первые склады нефти появились в XVII веке. Они представляли собой землянные ямы-амбара глубиной 4…5 м...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!