ДНФ и КНФ
ЛЕКЦИЯ 8
В.И.ХАХАНОВ
Факультет компьютерной инженерии и управления, кафедра АПВТ,
ХНУРЭДИСКРЕТНАЯ МАТЕМАТИКА
Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
БУЛЕВА АЛГЕБРА ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ (ДНФ и КНФ)
Содержание
- 1. БУЛЕВА АЛГЕБРА ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ (ДНФ и КНФ)
- 2. Цель лекции – изучить способы представления булевых
- 3. Горбатов В.А. Основы дискретной математики. М.: Высш.
- 4. Базовые понятия: логические операциилогические переменные логические функцииТерминыКлючевые
- 5. ДНФ и КНФ
- 6. Def: Совершенной ДНФ (СДНФ) называется ДНФ, в
- 7. Пример получения СДНФ и СКНФ
- 8. Теорема ШеннонаЛюбая булева функция f0 представима в
- 9. Time-Out
- 10. Эквивалентность форм ДНФ и КНФПривести функцию к ДНФ и КНФ:Получение ДНФ:Получение КНФ
- 11. Сложность формы булевой функцииОценка сложности функции по
- 12. Пример оценки сложности функцииУменьшить функцию и оценить ее сложностьОценка сложности по Квайну: Q=L(f)+k=12+4=16Сложность по Квайну: Q=L(f)+k=7+3=10
- 13. Пример дизъюнктивного разложения по ШеннонуПолучить дизъюнктивное разложение
- 14. ВыводыВсякая ФАЛ может быть реализована формулой, оперирующей
- 15. Тест-заданиеОпределить сложность функции по Квайну
- 16. Скачать презентанцию
Цель лекции – изучить способы представления булевых функций в виде дизъюнктивных и конъюнктивных нормальных форм, а также их совершенных форм, определить связь и различие между ними, выявить их назначение Содержание: ДНФ
Слайды и текст этой презентации
Слайд 1БУЛЕВА АЛГЕБРА ДИЗЪЮНКТИВНЫЕ И КОНЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ (ДНФ и КНФ). СОВЕРШЕННЫЕ
ДНФ и КНФ
ХНУРЭ
Слайд 2Цель лекции – изучить способы представления булевых функций в виде
дизъюнктивных и конъюнктивных нормальных форм, а также их совершенных форм,
определить связь и различие между ними, выявить их назначениеСодержание:
ДНФ и КНФ
СДНФ и СКНФ
Теорема Шеннона
Тема: ДНФ и КНФ. СДНФ и СКНФ.
Слайд 3Горбатов В.А. Основы дискретной математики. М.: Высш. шк., 1986. 32-61с.
Савельев
А.Я. Прикладная теория цифровых автоматов. М.: Высш. шк., 1987. 272
с.Беннеттс Р.Д. Проектирование тестопригодных логических схем: Пер. с англ. М.: Радио и связь. 1990. 176 с.
Бондаренко М.Ф., Кривуля Г.Ф., Рябцев В.Г., Фрадков С.А., Хаханов В.И. Проектирование и диагностика компьютерных систем и сетей. К.: НМЦ ВО. 2000. 306 с.
Богомолов А.М., Сперанский Д.В. Аналитические методы в задачах контроля и анализа дискретных устройств. Саратов: Изд-во Саратовкого ун-та, 1986. 240с.
Хаханов В.И. Техническая диагностика элементов и узлов персональных компьюторов. К.: ИСМО, 1997. 308 с.
Хаханов В.І., Хаханова І.В., Кулак Е.М., Чумаченко С.В. Методичні вказівки до практичних занять з курсу “Дискретна математика”. Харків, ХНУРЕ. 2001. 87с.
Новиков Ф.А. Дискретная математика для программистов. С.-П., 2001.
С. 263-268.
Литература
Слайд 4Базовые понятия:
логические операции
логические переменные
логические функции
Термины
Ключевые слова:
первичный терм
конъюнктивный терм
дизъюнктивный терм
дизъюнктивная нормальная форма (ДНФ)
конъюнктивная нормальная форма (КНФ)совершенная ДНФ
совершенная КНФ
Слайд 6Def: Совершенной ДНФ (СДНФ) называется ДНФ, в которой нет равных
элементарных конъюнкций и все элементарные конъюнкции содержат одни и те
же переменные, от которых зависит функция, причем каждую – только один раз (включая вхождения под знаком отрицания).Def: Совершенная КНФ (СКНФ) определяется как такая КНФ, в которой нет одинаковых сомножителей; все сомножители содержат одни и те же переменные, от которых зависит функция, причем каждую переменную – только один раз.
Совершенные ДНФ и КНФ (СДНФ и СКНФ). 1
Слайд 8Теорема Шеннона
Любая булева функция f0 представима в виде разложения Шеннона:
Следствие
Предельное
разложение Шеннона (k=n) булевой функции f0 имеет вид
Слайд 11Сложность формы булевой функции
Оценка сложности функции
по Квайну есть
Q=L(f)+k,
где
L(f) – число букв, k – число конъюнктивных термов
функции.
Уменьшить
функцию или ее сложность можно с помощьюзаконов булевой алгебры.
Слайд 12Пример оценки сложности функции
Уменьшить функцию и оценить ее сложность
Оценка сложности
по Квайну: Q=L(f)+k=12+4=16
Сложность по Квайну: Q=L(f)+k=7+3=10
Слайд 13Пример дизъюнктивного разложения по Шеннону
Получить дизъюнктивное разложение функции по переменным
x, z:
Разложение по указанным переменным имеет вид:
Вычисление составляющих дает:
Искомое разложение:
Слайд 14Выводы
Всякая ФАЛ может быть реализована формулой, оперирующей символами , ,
¬, скобками и знаком равенства
Любая булева функция может быть представлена
в виде ДНФ, КНФ, СДНФ, СКНФДНФ и КНФ есть сокращенная форма записи СДНФ и СКНФ (таблицы истинности)
ДНФ есть наиболее распространенная форма описания цифровых систем, максимально приближенная к аппаратурной реализации
