Дизъюнктивно-нормальная и конъюнктивно- нормальная формы

Элементарной конъюнкцией называется конъюнкция,

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

Правило 1. Если ДНФ является трехчленом, зависящим от трех переменных, и если симметрия нарушена только по одной из переменных, то устраняется тот член дизъюнкции, который эту переменную не содержит.

Пусть необходимо привести к минимальной ДНФ следующее выражение .

Приводим сначала это выражение к ДНФ, пользуясь формулами перевода импликации и эквиваленции в элементарные логические операции и таблицей эквивалентностей (табл.1).. = =

=

.

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

Правило 2. Если ДНФ является трехчленом, зависящим от трех переменных и если симметрия нарушена по двум из

этих переменных, то данная ДНФ равносильна дизъюнкции, одним из членов которой является переменная, по которой

симметрия не нарушена, а вторым членом служит тот член первоначальной ДНФ, который эту переменную не содержит.

Совершенная ДНФ (СДНФ) должна удовлетворять следующим условиям:

1. Все элементарные конъюнкции различны.

2. Нет нулевых конъюнкций.

3. Ни одна из элементарных конъюнкций не содержит одинаковых членов.

4. Каждая элементарная конъюнкция содержит все переменные.

Для получения СДНФ необходимо сначала найти минимальную ДНФ, а затем путем ввода дополнительных множителей добиться выполнения условия 4, например,

Элементарной дизъюнкцией называется дизъюнкция, состоящая только из переменных или их отрицаний.

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

Для получения минимальной КНФ, также как и для получения ДНФ, в некоторых частных случаях можно использовать следующие правила:

Правило 1. Если КНФ зависит от трех переменных и представляет конъюнкцию трех элементарных дизъюнкций и если симметрия нарушена по одной из переменных, то поглощается та элементарная дизъюнкция, которая эту переменную не содержит.

Правило 2. Если КНФ зависит от трех переменных и

представляет собой конъюнкцию трех элементарных дизъюнкций и если симметрия нарушена по двум из этих

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

Для получения минимальной КНФ сначала получают КНФ. Пусть необходимо привести к минимальной КНФ следующее выражение .

Сначала получаем ДНФ:

=

.

Полученную ДНФ минимизируем, используя правило 2 для ДНФ, и получаем .

Для получения КНФ преобразуем ДНФ в КНФ, используя последнюю формулу из таблицы эквивалентностей:

Контрольные вопросы и упражнения

Упростить следующие выражения:

1. ;

2. ;

3. .

Используя основные эквивалентности исчисления высказываний, проверить следующие равносильности:

1. ;

2. ;

3.

4. ;

5. ;

6.

7 ;

8

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19.

20.

21. ;

22. ;

23. ;

24.

25. ;

26.

27.

28. ;

29. ;

30. ;

31. ;

32. .

Привести следующие формулы к минимальной ДНФ.

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. .

Привести следующие формулы к минимальной КНФ.

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. .

Привести следующие формулы к виду СДНФ.

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. .

Дата добавления: 2015-06-27