Задача. Пусть формула А(x,y,z) задана своей таблицей истинности.
|
х |
у |
z |
А(x,y,z) |
|
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
0 |
|
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
|
0 |
1 |
0 |
0 |
|
0 |
0 |
1 |
0 |
|
0 |
0 |
0 |
0 |
Восстановим формулу по её таблице
истинности. При значениях переменных в первой, четвертой и пятой строках
формула принимает истинное значение. Используя таблицы истинности конъюнкции,
построим соответствующие элементарные конъюнкции. Ясно, что
при значениях переменных в первой строке
конъюнкция xyz истинна,
при значениях переменных в четвертой
строке конъюнкция Øxyz истинна,
при значениях переменных в пятой строке
конъюнкция xØyØz истинна.
А теперь из этих элементарных конъюнкций
построим совершенную дизъюнктивную нормальную форму:
хyz Ú Øxyz Ú xØyØz.
Т.к. построенные элементарные конъюнкции
при значениях переменных в других строках принимают ложное значение, то
нетрудно проверить, что эта формула соответствует таблице истинности формулы А(x,y,z):
А(x,y,z)= хyz Ú Øxyz Ú
xØyØz.
Т.о., для того, чтобы отличную от
тождественно ложной формулу привести к совершенной дизъюнктивной
нормальной форме, необходимо построить дизъюнкцию из элементарных
конъюнкций, соответствующих значениям переменных высказываний, при которых
формула принимает истинное значение, причем в элементарную конъюнкцию
высказывание должно входить само, если оно истинно, и с отрицанием, если оно
ложно.
Приведем алгоритм построения СКНФ.
Для того, чтобы отличную от тождественно
истинной формулу привести к совершенной конъюнктивной
нормальной форме, необходимо построить конъюнкцию из элементарных
дизъюнкций, соответствующих значениям переменных высказываний, при которых
формула принимает ложное значение, причем в элементарную дизъюнкцию
высказывание должно входить само, если оно ложно, и с отрицанием, если оно
истинно.
Например, СКНФ формулы из вышеприведенной
задачи имеет вид:
А(x,y,z)= (ØхÚØyÚz) (ØxÚyÚØz)(xÚØyÚz) (xÚyÚØz) (xÚyÚz).