Нормальные формы булевых функций

Слайд 2

 

 

 

 

 

 

Слайд 3

Конъюнктивной нормальной формой (КНФ) называется произвольная конъюнкция дизъюнктивных одночленов.

 

Дизъюнктивной нормальной формой (ДНФ)

Конъюнктивной нормальной формой (КНФ) называется произвольная конъюнкция дизъюнктивных одночленов. Дизъюнктивной нормальной формой
называется произвольная дизъюнкция конъюнктивных одночленов.

 

Слайд 4

Всякую формулу равносильными преобразованиями можно привести к ДНФ и КНФ.
Алгоритм:
Избавиться от операций

Всякую формулу равносильными преобразованиями можно привести к ДНФ и КНФ. Алгоритм: Избавиться
импликации, эквивалентности, штрих Шеффера, стрелка Пирса, сложение по модулю два;
Довести знаки отрицания до независимых переменных, используя законы де Моргана;
Применяя закон дистрибутивности, преобразовать формулу к дизъюнкции конъюнктивных одночленов (конъюнкции дизъюнктивных одночленов);
Постоянно избавляться от двойных отрицаний.

Слайд 5

Замечание: Для того чтобы проверить правильно ли привели формулу к КНФ и

Замечание: Для того чтобы проверить правильно ли привели формулу к КНФ и
ДНФ, можно построить таблицы истинности первоначальной и получившихся формул. Последние столбцы таблиц этих формул должны принимать одинаковые значения истинности.

Слайд 6

Одночлен от некоторых переменных называется совершенным, если каждая из этих переменных входит

Одночлен от некоторых переменных называется совершенным, если каждая из этих переменных входит
в него ровно один раз, со знаком отрицания или без него.

Нормальная форма от некоторых переменных называется совершенной, если каждый входящий в нее одночлен является совершенным одночленом от тех же самых переменных. (СДНФ и СКНФ)

 

Слайд 7

Теорема 1: Если формула не тождественно истинная, то для нее существует и

Теорема 1: Если формула не тождественно истинная, то для нее существует и
при том единственная СКНФ. Теорема 2: Если формула не тождественно ложная, то для нее существует и при том единственная СДНФ.

Слайд 8

Алгоритм нахождения СДНФ:
Строим таблицу истинности;
Выбираем те строки таблицы, на которых формула принимает

Алгоритм нахождения СДНФ: Строим таблицу истинности; Выбираем те строки таблицы, на которых
значение истина;
Для каждой выбранной строки строим конъюнктивный одночлен из переменных, от которых зависит формула следующим образом: если переменная в строке принимает значение истина, то она непосредственно входит в элементарную конъюнкцию, если ложь, то она входит с отрицанием;
Из конъюнктивных одночленов составляем СДНФ.
Имя файла: Нормальные-формы-булевых-функций.pptx
Количество просмотров: 30
Количество скачиваний: 0