42. Дизъюнктивные и конъюнктивные нормальные формы. Алгоритм приведения формулы к днф и кнф.
Если х – логическая переменная, , то выражение: называется литерой. Литеры x и называются контрарными.
Элементарной конъюнкцией или конъюнктом называется конъюнкция литер. Элементарной дизъюнкцией или дизъюнктом называется дизъюнкция литер.
ДНФ – дизъюнкция конъюнктов. КНФ – конъюнкция дизъюнктов. Любая формула эквивалентна некоторой ДНФ и КНФ.
Алгоритм приведения формулы к ДНФ:
Выразить все логические операции, участвующие в построении формулы через дизъюнкции, конъюнкции и отрицания: , .
Используя законы де Моргана, переносим все отрицания к переменным и сокращаем двойные отрицания.
Используя закон дистрибутивности , преобразуем формулу так, чтобы все конъюнкции выполнялись раньше дизъюнкций.
Алгоритм приведения формулы к КНФ:
Выразить все логические операции, участвующие в построении формулы через дизъюнкции, конъюнкции и отрицания: , .
Используя законы де Моргана, переносим все отрицания к переменным и сокращаем двойные отрицания.
Используя закон дистрибутивности , преобразуем формулу так, чтобы все дизъюнкции выполнялись раньше конъюнкций.
Yandex.RTB R-A-252273-3
- Множества. Основные операции над множествами и их свойства. Диаграммы Венна. Декартово произведение множеств.
- Отношения и бинарные отношения, область определения, область значения, обратные отношения. Произведение отношений.
- Функции. Инъекции, сюръекции, биекции. Понятие последовательности.
- Множество натуральных чисел. Два подхода к определению множества натуральных чисел. Аксиомы Дедекинда-Пеано. Принцип математической индукции.
- Понятие мощности множества. Сравнение мощностей. Теорема Кантора-Берштейна. Операции над кардинальными числами.
- Конечные, счетные, континуальные множества. Мощность булеана.
- Матрицы бинарных отношений и их свойства. Специальные бинарные отношения.
- Отношения эквивалентности и разбиения. Фактор-множества. Матрица отношения эквивалентности.
- Отношения порядка. Максимальные и минимальные, наибольший и наименьший элементы частично упорядоченного множества. Диаграммы Хассе. Линейно и вполне упорядоченные множества.
- Алгебраические системы: определение и примеры. Понятие полугруппы, моноида, группы; задание с помощью таблицы Кэли.
- Морфизмы алгебраических систем.
- Подсистемы. Термы сигнатуры ∑. Подсистема, порожденная множеством, ее структура.
- Конгруэнции, фактор-алгебры, теорема о гомоморфизме.
- 17.Многообразия. Теорема Биркгофа.
- Решетки. Дистрибутивные решетки. Критерий дистрибутивности.
- Булевы алгебры. Теорема Стоуна. Принцип двойственности для булевых алгебр.
- Булево кольцо.
- 18. Алгебры отношений. Реляционные алгебры.
- 27. Виды и способы задания графов.
- 28. Подграфы и части графа. Операции над графами. N-Мерные кубы.
- Объединение: .
- 29. Маршруты, циклы, цепи. Достижимость и связность (матрицы достижимости, контрдостижимости, связности).
- 30. Расстояние в графах. Центральные и периферийные вершины.
- 31. Взвешенное расстояние. Алгоритм Форда-Беллмана.
- 32. Степени вершин. Эйлеровы графы, циклы, цепи. Алгоритм построения эйлерова цикла.
- 33. Гамильтоновы графы. Постановка задачи коммивояжера.
- 34. Деревья, леса. Остовы графов. Цикломатическое число, коранг. Алгоритм построения остова минимального веса. Обходы графов по глубине и ширине.
- 35. Упорядоченные и бинарные деревья. Соответствия между ними.
- 36. Фундаментальные циклы, разрезы. Матрицы фундаментальных циклов, разрезов.
- 37. Раскраска графов. Планарные графы.
- 38. Формулы алгебры логики, их таблицы истинности.
- 39. Булевы функции, способы их задания. Представления булевых функций формулами.
- 40. Эквивалентность формул.
- 41. Двухэлементная булева алгебра. Алгебра булевых функций. Фактор-алгебра алгебры формул.
- 42. Дизъюнктивные и конъюнктивные нормальные формы. Алгоритм приведения формулы к днф и кнф.
- 43. Теорема Шеннона. Теорема о функциональной полноте. Способы построения сднф и скнф.
- 44. Импликанты, простые импликанты. Сокращенные, тупиковые, минимальные нормальные формы. Алгоритм Квайна построения мднф.
- 45. Карты Карно. Построение мднф с помощью карт Карно.
- 46. Принцип двойственности. Самодвойственные функции.
- 47. Теорема Жегалкина. Способы построения полиномов Жегалкина. Линейные функции.
- 48. Классы Поста. Полные системы булевых функций. Теорема Поста. Базисы.
- 49. Логические сети. Реализация булевых функций контактными схемами и схемами из функциональных элементов.