1.9. Восстановление формулы по её таблице истинности

 

Задача. Пусть формула А(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).