§ 5. Совершенные дизъюнктивная и конъюнктивная нормальные формы
|
x1 |
… |
xn |
A(x1 , … , xn ) |
|
… |
… |
… |
… |
|
1 |
… |
n |
A(1 , … , n ) |
|
… |
… |
… |
… |
|
x1 |
x2 |
x3 |
? |
|
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
|
1 |
0 |
1 |
0 |
|
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
0 |
Если формула A(x1 , x2 , x3 ) – искомая, то
A(x1 , x2 , x3 ) = 1
(x1 = 0 x2 = 0 x3 = 1) (x1 = 0 x2 = 1 x3 = 1)
(x1 = 1 x2 = 0 x3 = 1)
(
x3
=
1)
(
x2
x3
= 1)
(x1
=
1)
(
x3
)
(
x2
x3
)
(x1
)
= 1.
Таким образом, в качестве искомой формулы можно взять
A(x1
, x2
, x3
) = (
x3
)
(
x2
x3
)
(x1
).
Полученное в
примере выражение для формулы A(x1
, x2
, x3
)
устроено
регулярно: оно является дизъюнкцией
выражений вида y1
y2
y3
, где каждое
yi
является
или переменной xi
или её
отрицанием
.
Аналогичные построения можно применить
и в общем случае, используя соответствующие
общие обозначения, к описанию которых
теперь и переходим.
Для пропозициональной
переменной
x
и фиксированного
значения
{0, 1} введём
следующее обозначение x
=
. Выражение
x
можно считать
булевой функцией переменного x,
вычисляя её значение при x
=
{0, 1} естественным
образом:
=
.
Найденная в предыдущем примере формула в этих обозначениях может быть записана так: A(x1 , x2 , x3 ) = (x10 x20 x31) (x10 x21 x31 ) (x11 x20 x30 ). Следует заметить, что наборы степеней при переменных x1 , x2 , x3 , т.е. наборы (0; 0; 1), (0; 1; 1), (1; 0; 0), – это в точности те интерпретации из исходной таблицы, при которых в последнем её столбце стоит значение 1:
A(x1
, x2
, x3
) =
.
Лемма (о значениях выражения x ) . (1) x = 1 x = .
(2)
.
(3)
=
1
(x1
= 1)
…
(xn
= n)
.
(4)
.
Доказательство.
Следующая
таблица показывает, что x
= 1 тогда и
только тогда, когда
x
=
, а также, что
:
|
|
формула x |
x |
значение x |
|
формула
|
x |
значение
|
значение
|
|
0 |
|
0 |
1 |
1 |
x |
0 |
0 |
0 |
|
1 |
0 |
1 |
1 |
1 | ||||
|
1 |
x |
0 |
0 |
0 |
|
0 |
1 |
1 |
|
1 |
1 |
1 |
0 |
0 |
Остальные утверждения отсюда следуют:
(
= 1)
(
=
1)
…
(
=
1)
(x1
= 1
…
xn
= n),
.
Лемма доказана.
Элементарной
конъюнкцией (соответственно
дизъюнкцией) от n
пропозициональных переменных x1
, … , xn
назовём
формулу вида
(соответственно
),
где k
n,
1
i1
< … < ik
n,
{0, 1}. Менее
формально, элементарная конъюнкция
(дизъюнкция) – это выражение y1
…
yk
(соответственно
y1
…
yk
), где каждое
ys
является
либо пропозициональной переменной,
либо её отрицанием, причём переменные,
участвующие в этом выражении упорядочены
по возрастанию своих номеров. Если в
элементарной конъюнкции (соответственно
дизъюнкции) участвуют все переменные,
т.е. k
= n,
то такая элементарная конъюнкция
(соответственно дизъюнкция) называется
совершенной
элементарной конъюнкцией
(соответственно
дизъюнкцией)
. Любая
дизъюнкция различных элементарных
конъюнкций (соответственно конъюнкция
различных элементарных дизъюнкций)
называется дизъюнктивной
нормальной формой (соответственно
конъюнктивной
нормальной формой)
. Любая
дизъюнкция различных совершенных
элементарных конъюнкций (соответственно
конъюнкция различных совершенных
элементарных дизъюнкций) называется
совершенной
дизъюнктивной нормальной формой,
или кратко СДНФ
(соответственно
совершенной
конъюнктивной нормальной формой,
или кратко
СКНФ).
Таким образом, СДНФ
(соответственно СКНФ)
может быть записана так:
(соответственно
).
Примеры: 1.
конъюнкция x
не является
элементарной конъюнкцией, т.к. одна
переменная в ней участвует дважды –
вначале без отрицания, а потом с
отрицанием.
2.
x
–совершенная
элементарная конъюнкция от двух
переменных
x
и y,
но она не является совершенной
элементарной конъюнкцией от трёх
переменных
x,
y,
z
(т.к. переменная
z
не участвует
в этом выражении). Эта формула будет
совершенной дизъюнктивной нормальной
формой от переменных x,
y,
но она не будет совершенной, если
рассматривать её от трёх переменных.
3.
(x1
x2
x3)
(
)
–совершенная
конъюнктивная нормальная форма от
переменных x1
, x2
, x3
.
4. (x1
x2
x3)
(x1
x2
x3)
(
)
–не является
совершенной конъюнктивной нормальной
формой от переменных x1
, x2
, x3
, т.к. содержит
две одинаковые элементарные дизъюнкции.
5.
Любая дизъюнктивная нормальная форма
принимает значение 1
хотя бы на
одном наборе пропозициональных
переменных. Докажем это для совершенной
дизъюнктивной нормальной формы – в
общем случае рассуждения аналогичны.
Действительно, формула
истинна
тогда и только тогда, когда истинна хотя
бы одна её элементарная конъюнкция
.
Ввиду леммы она истинна при x1
= 1
, … , xn
= n
, что и
требовалось доказать.
6.
Как следует из предыдущего примера,
для противоречий не существует СДНФ.
Однако легко записать формулу от n
переменных,
равносильную противоречию: например,
x1
.
7. Любая конъюнктивная нормальная форма принимает значение 0 хотя бы на одном наборе пропозициональных переменных. Доказательство аналогично предыдущему.
8.
Как следует из предыдущего примера, для
законов логики не существует СКНФ.
Однако, легко записать формулу от n
переменных,
равносильную закону логики: например,
x1
.
Возвращаемся к общей задаче построения формулы с заданной таблицей истинности.
Теорема (о СДНФ и СКНФ). (1) Для любой таблицы, последний столбец которой состоит не из одних нулей, существует СДНФ с этой таблицей истинности.
(2) Эта СДНФ единственна с точностью до порядка совершенных элементарных конъюнкций.
(3) В частности, для любой формулы A(x1 , … , xn ), не являющейся противоречием, существует единственная (с точностью до перестановки элементарных конъюнкций) равносильная ей СДНФ.
(1) Для любой таблицы, последний столбец которой состоит не из одних единиц, существует СКНФ с этой таблицей истинности.
(2) Эта СКНФ единственна с точностью до порядка совершенных элементарных дизъюнкций.
(3) В частности, для любой формулы A(x1 , … , xn ), не являющейся законом логики, существует единственная (с точностью до перестановки элементарных дизъюнкций) равносильная ей СКНФ.
|
x1 |
… |
xn |
A(x1 , … , xn ) |
|
… |
… |
… |
… |
|
1 |
… |
n |
A(1 , … , n ) |
|
… |
… |
… |
… |
0. Для
этого по данной таблице
образуем следующее
выражение Д(x1
, … , xn
) =
.
Это – СДНФ,
причём(Д(1 , … , n ) = 1) (найдётся такая интерпретация (1 ; … ; n ), что
A(1
, … , n)
= 1, и
=
1)
(найдётся такая интерпретация
(1 ; … ; n ), что A(1 , … , n) = 1, и (1 = 1) … (n = n ))
(A(1 , … , n) = 1), что и требовалось.
(2) Докажем теперь единственность (с точностью до перестановки элементарных конъюнкций) СДНФ с заданной таблицей истинности. Пусть нашлись две такие СДНФ Д1(x1 , … , xn ) и Д2(x1 , … , xn ), что Д1(x1 , … , xn ) Д2(x1 , … , xn ). Будет показано, что любая элементарная конъюнкция формулы Д1(x1 , … , xn ) участвует и в Д2(x1 , … , xn ), и наоборот, любая элементарная конъюнкция формулы Д2(x1 , … , xn ) участвует в Д1(x1 , … , xn ). Таким образом, будет показано, что эти СДНФ состоят из одного и того же набора элементарных конъюнкций.
Пусть элементарная
конъюнкция
участвует в Д1(x1
, … , xn
).
Тогда эта конъюнкция принимает
значение 1
при x1
= 1
, … , xn
= n
, а значит,
Д1(1
, … , n
) = 1.
Ввиду Д1(x1
, … , xn
)
Д2(x1
, … , xn
)
имеем Д2(1
, … , n
) = 1.
Значит, найдётся такая элементарная
конъюнкция
в Д2(x1
, … , xn
),
что
=
1. Однако,
(
=
1)
(1
= 1
…
n
= n
),
т.е. элементарная конъюнкция
участвует и в формуле Д2(x1
, … , xn
).
Аналогично доказывается, что любая элементарная конъюнкция формулы Д2(x1 , … , xn ) участвует и в формуле Д1(x1 , … , xn ), а значит, эти СДНФ состоят из одних и тех же совершенных элементарных конъюнкций (с точностью до их перестановки).
(3) следует
из (1) и
(2):
достаточно по заданной формуле A(x1
, … , xn
)
0
построить
таблицу
истинности, и найти единственную СДНФ
Д(x1
, … , xn
) с
этой таблицей истинности. Тогда
A(x1
, … , xn
)
Д(x1
, … , xn
).
(1)
выведем это из (1).
По условию, искомая формула A(x1
, … , xn
) не
тождественно истинна,
так что
(x1
, … , xn
)
0.
По доказанному в (1),
найдётся СДНФ
Д(x1
, … , xn
) =
(x1
, … , xn).
Значит,
A(x1
, … , xn
)
(x1
, … , xn
)
{де Морган}
– искомая СКНФ.
(2)
Если найдены
две равносильные СКНФ
К1(x1
, … , xn
)
К2(x1
, … , xn
),
то у формулы
(x1
, … , xn
)
существовали
бы две СДНФ
(x1
, … , xn
) и
(x1
, … , xn
).
По доказанному в (1),
(x1
, … , xn
) и
(x1
, … , xn
)
отличаются только порядком элементарных
конъюнкций, а значит, К1(x1
, … , xn
) и
К2(x1
, … , xn
)
отличаются только порядком элементарных
дизъюнкций, что и требовалось.
(3) выводится из (1) и (2) аналогично тому, как (3) выведено из (1) и (2).
Теорема доказана.
На практике СКНФ
можно
получать, как следует из приведённых
при доказательстве теоремы вычислений,
без привлечения отрицания формулы. По
заданной таблице истинности формулы
для каждого набора значений (1
; … ; n
) со
свойством A(1
, … , n)
= 0 построим
элементарную дизъюнкцию
и конъюнкцию всех таких дизъюнкций:
,
которая и будет СКНФ
для исходной
не тождественно истинной формулы A(x1
, … , xn
).
Примеры: 1.
Построить СКНФ
для формулы
(x
y)
z
(y
x)
.
|
x |
y |
z |
x y |
((x y) z |
y x |
|
((y
x)
|
A |
|
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
|
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
|
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
Вначале строим таблицу истинности формулы. Далее, выбираем нулевые значения формулы с интерпретациями (0; 1; 0) и (1; 0; 1) соответственно и строим по этим наборам элементарные дизъюнкции
.
Таким образом,
СКНФ такова:
К(x,
y,
z)
=
.
2. Предыдущую задачу можно решить и без построения таблицы истинности, воспользовавшись основными равносильностями:
((x
y)
z)
((y
x)
)
((
y)
z)
((
x)
)
{дистрибутивность}
((
y)
((
x)
)))
(z
((
x)
)))
((
y)
(
x))
((
y)
)
(z
(
x))
(z
)
{
y
x
1,
z
1}
(
y
)
(x
z)
– СКНФ.
3. Построим СДНФ для формулы примера 1.
Выбираем все
единичные значения формулы, которым
отвечают интерпретации (0;
0; 0), (1; 0; 0), (1; 1; 0), (0; 0; 1), (0; 1; 1)
и (1; 1; 1)
соответственно.
Строим по этим наборам элементарные
конъюнкции x0
y0
z0
=
,x1
y0
z0
=
,x1
y1
z0
=
,x0
y0
z1
=
,x0
y1
z1
=
и x1
y1
z1
= x
y
z
. Таким
образом, СДНФ
такова:
.
4. Предыдущую задачу можно решить и без построения таблицы истинности, воспользовавшись основными равносильностями:
((x
y)
z)
((y
x)
)
((
y)
z)
((
x)
)
{дистрибутивность}
(
z)
(y
z)
(
)
(x
)
{склейка}
(
y
z)
(
z)
(x
y
z)
(
y
z)
(x
)
(
)
(x
y
)
(x
)
{идемпотентность}
(
y
z)
(
z)
(x
y
z)
(
)
(x
y
)
(x
).
Упражнение. Постройте СДНФ и СКНФ для следующих формул:
а)
a
b
,б)
a
,в)
,г)
a ®
b Ù
c «
c Ù
,д)
Ú
a Ù
bÚ
,е)
(a «
b)
c
c
.
Зададимся следующим вопросом: сколько можно выписать подряд попарно неравносильных формул исчисления высказываний от n пропозициональных переменных ? С одной стороны, каждая формула имеет таблицу истинности. С другой стороны, в этом параграфе было доказано, что для каждой таблицы значений существует реализующая её формула исчисления высказываний. Поэтому максимальное количество попарно неравносильных формул равно количеству различных таблиц истинности (при фиксированном порядке перечисления наборов значений переменных в первых n столбцах этих таблиц).
Сколько же существует
таблиц истинности ? Если зафиксировать
один и тот же порядок перечисления
наборов значений переменных в первых
n
столбцах
этих таблиц, то каждая таблица полностью
определяется своим последним столбцом,
который является набором из нулей и
единиц длины 2n.
Всего существует
таких наборов,
т.е. всего существует
таблиц
истинности, а значит, и
попарно
неравносильных формул от n
переменных.
Поскольку каждая
не тождественно ложная формула имеет
однозначно определённую
СДНФ, общее
количество СДНФ
(с точностью
до перестановки их совершенных
элементарных конъюнкций)
равно
– 1. Столько
же существует и различных СКНФ
(с точностью
до перестановки их совершенных
элементарных дизъюнкций). Значит
доказана
Теорема (о
количестве неравносильных формул от
n
переменных).
(1)
Максимальное количество попарно
неравносильных формул исчисления
высказываний от n
пропозициональных переменных равно
.
(2) Существует
ровно
– 1 неравносильных между собой СДНФ
и столько же неравносильных между собой
СКНФ.