Совершенной дизъюнктивной формой формулы алгебры высказываний (СДНФ) называется ДНФ, в которой:
2. различны все члены каждой конъюнкции;
3. ни одна конъюнкция не содержит одновременно переменную и отрицание этой переменной;
4. каждая конъюнкция содержит все переменные, входящие в формулу, т.е. имеет вид
,
где дизъюнкция берется по всем наборам с=(с1, с2, …, сn) из 0 и 1, для которых F(c)=1.
Теорема (о СДНФ). Для всякой не равной тождественному нулю формулы логики высказываний F(x1, x2, …, xn) существует такая формула F1, зависящая от того же списка переменных и находящаяся в СДНФ относительно этого списка, что F1 выражает собой формулу F. Формула F1 определена однозначно с точностью до перестановки дизъюнктивных членов.
Совершенной конъюнктивной формулой формулы алгебры высказываний (СКНФ) называется КНФ, в которой:
1. различны все члены конъюнкции;
2. различны все члены каждой дизъюнкции;
3. ни одна дизъюнкция не содержит переменную вместе с отрицанием этой переменной;
4. каждая дизъюнкция содержит все переменные, входящие в исходную формулу, т. е. имеет вид
,
где конъюнкция берется по всем наборам с=(с1, с2, …, сn) из 0 и 1, для которых F(c)=0.
Теорема (о СКНФ). Для всякой не равной тождественной единице формулы логики высказываний F(x1, x2, …, xn) существует такая формула F1, зависящая от того же списка переменных и находящаяся в СКНФ относительно этого списка, что F1 выражает собой формулу F. Формула F1 определена однозначно с точностью до перестановки конъюнктивных членов.
Опишем два способа приведения к совершенным нормальным формам.
1-й способ – аналитический.
Приведение к СДНФ. Алгоритм приведения.
1. привести формулу с помощью равносильных преобразований к ДНФ.
2. удалить члены дизъюнкции, содержащие переменную вместе с ее отрицанием (если такие окажутся);
3. из одинаковых членов дизъюнкции (если такие окажутся) удалить все, кроме одного;
4. из одинаковых членов каждой конъюнкции (если такие окажутся) удалить все, кроме одного;
5. если в какой-нибудь конъюнкции не содержится переменной xi из числа переменных, входящих в исходную формулу, добавить к этой конъюнкции член и применить закон дистрибутивности конъюнкции относительно дизъюнкции;
6. если в полученной дизъюнкции окажутся одинаковые члены, воспользоваться предписанием из п. 3.
Полученная формула и является СДНФ данной формулы.
Привести следующие формулы к СДНФ с помощью равносильных преобразований:
1. ;
2. ;
3. .
Решение.
1. .
2.
3.
Приведение к СКНФ. Алгоритм приведения.
1. привести формулу с помощью равносильных преобразований к КНФ.
2. удалить члены конъюнкции, содержащие переменную вместе с ее отрицанием (если такие окажутся);
3. из одинаковых членов конъюнкции (если такие окажутся) удалить все, кроме одного;
4. из одинаковых членов каждой дизъюнкции (если такие окажутся) удалить все, кроме одного;
5. если в какой-нибудь дизъюнкции не содержится переменной xi из числа переменных, входящих в исходную формулу, добавить к этой дизъюнкции член и применить закон дистрибутивности дизъюнкции относительно конъюнкции;
6. если в полученной конъюнкции окажутся одинаковые члены, воспользоваться предписанием из п. 3.
Полученная формула и является СКНФ данной формулы.
Привести следующие формулы к СКНФ с помощью равносильных преобразований:
1. ;
2. .
Решение.
1.
2.
2-й способ – табличный.
Составляем таблицу истинности для данной функции.
Приведение к СДНФ. Алгоритм приведения.
Строим таблицу значений формулы. Рассматриваем только те строки, в которых значение формулы равно единице. Каждой такой строке соответствует конъюнкция всех аргументов (без повторений). Причем, аргумент, принимающий значение 0, входит в нее с отрицанием, значение 1 – без отрицания. Наконец, образуем дизъюнкцию всех полученных конъюнкций.
Построить СДНФ для данных формул логики высказываний.
1. .
2.
Решение.
1. .
Строим таблицу истинности для формулы F:
№
x
y
z
Рассматриваем только 4, 5 и 7 наборы, так как только на этих наборах формула принимает значение равное единице.
СДНФ имеет вид:
2. 2.
Строим таблицу истинности для формулы F:
№
x
y
x® y
F=(x® y)ÙxÙy
СДНФ (1): № 3:
F = x y.
Приведение к СКНФ. Алгоритм приведения.
Рассматриваем только те строки таблицы, где формула принимает значение 0. Каждой такой строке соответствует дизъюнкция всех переменных (без повторений). Причем аргумент, принимающий значение 0, берется без отрицания, значение 1 – с отрицанием. Наконец, образуют конъюнкцию полученных дизъюнкций.
Построить СКНФ для данных формул логики высказываний.
1. .
2.
Решение.
1. Строим таблицу значений, используя предыдущий пример.
№
x
y
z
Рассматриваем только наборы, на которых формула принимает значение ноль.
СКНФ (0): № 0, 1, 2, 3, 6:
2. Строим таблицу значений, используя предыдущий пример.
№
x
y
F=(x® y)ÙxÙy
СКНФ (0): № 0, 1, 2:
Любую булеву функцию можно выразить в виде формулы через элементарные функции: отрицание, конъюнкцию, дизъюнкцию, двоичное сложение и константу 0 или 1.
Эти функции можно рассматривать как систему элементарных функций, через которые выражается любая булева функция.
Система булевых функций {f1, f2, …, fm} называется полной, если любая булева функция может быть выражена через функции этой системы с помощью составления из них сложных функций..
Составление сложных функций из элементарных функций системы называется суперпозицией.
Достаточное условие полноты системы.
Пусть система функций {f1, f2, …, fm} (I) полная и любая из функций этой системы может быть выражена через функции g1, g2, …, gl , тогда система { g1, g2, …, gl}(II) тоже полная.
Полноту системы можно доказать , опираясь на то, что любая булева функция представима в виде полинома, или доказав с помощью достаточного условия.
,
,
и применить закон дистрибутивности конъюнкции относительно дизъюнкции;
;
;
.
.
и применить закон дистрибутивности дизъюнкции относительно конъюнкции;
.
.
.