1 Совершенная дизъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма Логические основы ЭВМ 10 класс Белоусова Елена Ивановна, учитель. - презентация

1 1 Совершенная дизъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма Логические основы ЭВМ 10 класс Белоусова Елена Ивановна, учитель информатики МОУ «СОШ 75», г. Чусовой, Пермский край

2 2 Простой конъюнкцией (элементарной) называется конъюнкция одной или нескольких переменных, при этом каждая переменная встречается не более одного раза (либо сама, либо ее отрицание). Не соответствует правилу

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

4 4 Простой дизъюнкцией (элементарной) называется дизъюнкция одной или нескольких переменных, при этом каждая переменная входит не более одного раза (либо сама, либо ее отрицание). Не соответствует правилу

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

6 6 Задача Пусть дана таблица истинности для некоторой логической функции F(X,Y). Перейти от таблицы истинности к формуле, а на ее основе построить функциональную схему. XYF

7 7 Логическая функция ФОРМУЛА ТАБЛИЦА ИСТИННОСТИ ПРОБЛЕМА Как от таблицы истинности перейти к формуле, чтобы построить функциональную схему? СХЕМА

8 8 Совершенной дизъюнктивной нормальной формой (СДНФ) называется такая дизъюнктивная нормальная форма, у которой в каждую конъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одном и том же порядке. Не соответствует правилу

9 9 Совершенной конъюнктивной нормальной формой (СКНФ) называется такая конъюнктивная форма, у которой в каждую дизъюнкцию входят все переменные данного списка (либо сами, либо их отрицания), причем в одном и том же порядке. Не соответствует правилу

10 10 Любую функцию можно представить в виде СДНФ, так и СКНФ, кроме константы 0 и константы 1 Теорема алгебры логики

11 11 Алгоритм получения СДНФ по таблице истинности 1.Отметить те строки таблицы истинности, в последнем столбце которых стоят 1: F(X,Y)YX 1* *1* Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение в данной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно 0, то ее отрицание : для 1-й строки, для 3-строки, для 4-строки 3. Все полученные конъюнкции связать в дизъюнкцию:

12 12 Алгоритм получения СКНФ по таблице истинности 1.Отметить те строки таблицы истинности, в последнем столбце которых стоят 0: F(X,Y)YX * Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение в данной строке равно 0, то в дизъюнкцию включать саму эту переменную, если равно 1, то ее отрицание : - для 2-й строки. 3. Все полученные дизъюнкции связать в конъюнкцию:

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

14 14 Проверка Покажем, что полученные по двум алгоритмам СДНФ и СКНФ эквивалентны. СДНФ и СКНФ Можем проверить, построив таблицу истинности по найденной формуле. XY

15 15 Логическая схема v F X Y

16 16 Задача уровня В Представить функцию в виде СДНФ, построить логическую схему этой функции abc =