Нахождение посылок для данного следствия.

Задача нахождения всех формул, из которых данная формула логически следует, является обратной по отношению к той, которая была рассмотрена в предыдущем пункте. Ее решение основывается на следующей теореме.

Теорема 6.20. Чтобы найти все формулы, логическим следствием каждой из которых будет данная формула G(XX,..., Хп), нужно действовать по следующему алгоритму. Найти СКН-форму для формулы G(XU ... ,Хп); выявить все совершенные дизъюнктивные одночлены, которые в ней отсутствуют', составить всевозможные конъюнкции формулы G(Xx,...,Xn) с недостающими дизъюнктивными одночленами. Получившаяся совокупность формул (вместе с формулой G) будет искомой (с точностью до равносильности формул).

Доказательство. Ясно, что из каждой формулы этой совокупности будет логически следовать формула G, так как G л Н *= G (конъюнкция сильнее каждого из сомножителей). Обратно, покажем, что каждая формула F, из которой логически следует данная формула G, имеет указанный вид, т.е. представляет собой конъюнкцию формулы G и некоторых совершенных дизъюнктивных одночленов, отсутствующих в СКН-форме для G. В самом деле, пусть F *= Си G = Dx л D2 л ... л Dk — СКН-форма для формулы G(XX, ..., Хп) и F= А! л А2 л ... лА,- СКН-форма для формулы F(XU ..., Xn). По определению логического следования, F *= G означает, что если формула F(XU ..., Хп) на некотором наборе Аи ..., Ап значений пропозициональных переменных приняла значение 1, то и формула G(XU ..., Хп) на этом наборе примет значение 1. Другими словами, если формула G{XX,..., Хп) на некотором наборе А\, ..., Ап значений пропозициональных переменных принимает значение 0, то и формула F(XU ..., Хп) на этом наборе принимает значение 0. Но все наборы значений переменных, на которых G принимает значение 0, находятся во взаимно-однозначном соответствии с совершенными дизъюнктивными одночленами D\, D2, ..., Dk, образующими СКН-форму для формулы G, т.е. если G(AU ..., Ап) = 0, то Dt{Ab ..., Ап) = 0 для некоторого 1 <i< к. Следовательно, F(AU ..., Ап) = 0 и значит на этом же наборе принимает значение 0 некоторый совершенный дизъюнктивный одночлен А/, входящий в ее СКН-форму. Но тогда этот одночлен совпадает с одночленом Д. Таким образом, каждый совершенный дизъюнктивный одночлен D, из СКН-формы для G входит в СКН-форму для формулы F, т.е. СКН-форма для У7имеет вид: F= D\ л D2 л ... л Dk л A^+1 л ... л А5, где A^+1, ..., А^ — совершенные дизъюнктивные одночлены от переменных Хи ..., Хп, не входящие в СКН-форму для формулы G. П

Заключение Список использованной литературы

18