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

1.38. Найдите все неравносильные между собой и не тождественно ложные формулы алгебры высказываний, для которых следующая формула является логическим следствием
(за исключением самой данной формулы):

а)	г)
б)	д)
в)

Решение. а) Чтобы определить, логическим следствием каких посылок является данная формула F (Х₁, Х₂,......, Х_n), ее необходимо привести к совершенной конъюнктивной нормальной форме и затем составить конъюнкции формулы F с недостающими в ее СКН-форме совершенными дизъюнктивными одночленами вида (где есть либо X_i, либо ØХ_i), взятыми по одному, по два и т. д.

Приведем данную формулу к СКН-форме:

Недостающими в этой форме дизъюнктивными одночленами вида являются и . Поэтому искомыми посылками для данной формулы являются формулы и Преобразуем их равносильным образом к более простым формулам:

(т. е. эта последняя посылка представляет собой тождественно ложную формулу, из которой логически следует всякая формула алгебры высказываний, в том числе и данная ).

Итак, всякая формула, для которой формула является логическим следствием, равносильна либо формуле X&Y, либо формуле ØХ&ØY, либо тождественно ложна. Поскольку из тождественно ложной формулы логически следует любая формула, то мы впредь не будем упоминать тождественно ложную формулу в числе возможных посылок для данной формулы (за исключением случая, когда тождественно ложная формула является единственной посылкой для данной формулы).

1.39. Найдите недостающую посылку (формулу) F, зависящую лишь от указанных пропозициональных переменных так, чтобы была верна следующая выводимость:

а) ├ X & Y;

б) ├ ;

в) ├ ;

г) ├ X & ØV;

д) ├ ;

е) ├ Z;

Решение. а) Составим таблицы истинности для формул, являющихся посылками и заключением:

X	Y	Z	V

Далее, в правом столбце отметим цифрами те строки, в которых обе данные посылки принимают значение 1, а следствие принимает значение 0. Этому требованию отвечает лишь четвертая строка, в которой l(Z)=1 и l(V)=1. Ясно, что при этих значениях Z и V искомая посылка F(Z, V) должна принять значение 0, так как в противном случае формула X&V не будет логическим следствием формул , и F (Z, V) (потому что на значениях l(X)=0, l(Y)=0, l(Z)=1, l(V)=1 все посылки примут значение 1, а формула X&V примет значение 0). Будем считать, что на других наборах значений переменных Z и V формула F(Z, V) принимает значение 1. Итак, для искомой посылки F(Z, V) получаем следующую таблицу истинности:

Находим СКН-форму для искомой формулы. Получаем: F(Z, V)=ØZÚØV=ZÞØV.