3 Переход между базисами
Дизъюнктивная нормальная форма (ДНФ) – это нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ.
Пример. .
Совершенная дизъюнктивная нормальная форма (СДНФ) – это такая ДНФ, которая удовлетворяет трём условиям:
в ней нет одинаковых элементарных конъюнкций;
в каждой конъюнкции нет одинаковых пропозициональных букв;
каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФ пропозициональных букв, причём в одинаковом порядке.
Для любой выполнимой функции алгебры логики существует своя СДНФ, причём единственная.
Конъюнктивная нормальная форма (КНФ) – это нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов. Конъюнктивная нормальная форма удобна для автоматического доказательства теорем. Любая булева формула может быть приведена к КНФ.
Пример.
Совершенная конъюнктивная нормальная форма (СКНФ) – это такая КНФ, которая удовлетворяет трём условиям:
в ней нет одинаковых элементарных дизъюнкций;
в каждой дизъюнкции нет одинаковых пропозициональных переменных;
каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв.
Для перехода между базисами используются законы де Моргана:
, (1)
. (2)
Выполнив инверсию выражений (1) и (2), получим:
, (3)
. (4)
Также для перехода потребуются формулы Пирса и Шеффера:
, (5)
. (6)
Выполнив инверсию выражений (5) и (6), получим:
, (7)
. (8)
Задача 5. Задано выражение в совершенной дизъюнктивной нормальной форме:
. (9)
Требуется перейти к базису Пирса.
Решение.
В базисе Пирса отсутствует операция логического умножения, поэтому с помощью выражения (2) заменим конъюнкцию на дизъюнкцию внутри скобок выражения (9). Получим:
. (10)
Внутри скобок выражения (10) применим выражение (5). Получим:
. (11)
Применив к выражению (11) операцию (7), получим ответ:
. (12)
Замечание. В полученном выражении (12) скобки раскрывать нельзя.
Рисунок 13 – Логическая схема для выражения
Задача 6. Задано выражение в совершенной дизъюнктивной нормальной форме:
. (13)
Требуется перейти к базису Шеффера.
Решение.
В базисе Шеффера отсутствует операция логического сложения, поэтому с помощью выражения (1) заменим дизъюнкцию на конъюнкцию между скобок выражения (13). Получим:
. (14)
Внутри скобок выражения (14) применим выражение (6). Получим:
. (15)
Применив к выражению (15) операцию (8), получим ответ:
. (16)
Замечание. В полученном выражении (16) скобки раскрывать нельзя.
Рисунок 14 – Логическая схема для выражения
Варианты заданий для задач № 5 и № 6:
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.
33.
34.
35.
36.
37.
38.
Задача 7. Задано выражение в совершенной конъюнктивной нормальной форме:
. (17)
Требуется перейти к базису Шеффера.
Решение.
В базисе Шеффера отсутствует операция логического сложения, поэтому с помощью выражения (1) заменим дизъюнкцию на конъюнкцию внутри скобок выражения (17). Получим:
. (17)
Внутри скобок выражения (17) применим выражение (6). Получим:
. (18)
Применив к выражению (18) операцию (8), получим ответ:
. (19)
Замечание. В полученном выражении (19) скобки раскрывать нельзя.
Рисунок
15 – Логическая схема для выражения
Задача 8. Задано выражение в совершенной конъюнктивной нормальной форме:
. (20)
Требуется перейти к базису Пирса.
Решение.
В базисе Пирса отсутствует операция логического умножения, поэтому с помощью выражения (2) заменим конъюнкцию на дизъюнкцию между скобками выражения (20). Получим:
. (21)
Внутри скобок выражения (21) применим выражение (5). Получим:
. (22)
Применив к выражению (22) операцию (5), получим ответ:
. (23)
Замечание. В полученном выражении (23) скобки раскрывать нельзя.
Рисунок 16 – Логическая схема для выражения
Варианты заданий для задач № 7 и № 8:
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.
33.
34.
35.
36.
37.
38.