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

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

а) нахождение посылок для данных следствий - student2.ru г) нахождение посылок для данных следствий - student2.ru
б) нахождение посылок для данных следствий - student2.ru д) нахождение посылок для данных следствий - student2.ru
в) нахождение посылок для данных следствий - student2.ru  

Решение. а) Чтобы определить, логическим следствием каких посылок является данная формула F (Х1, Х2, ......, Хn), ее необходимо привести к совершенной конъюнктивной нормальной форме и затем составить конъюнкции формулы F с недостающими в ее СКН-форме совершенными дизъюнктивными одночленами вида нахождение посылок для данных следствий - student2.ru (где нахождение посылок для данных следствий - student2.ru есть либо Xi , либо ØХi), взятыми по одному, по два и т. д.

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

нахождение посылок для данных следствий - student2.ru

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

нахождение посылок для данных следствий - student2.ru

нахождение посылок для данных следствий - student2.ru

нахождение посылок для данных следствий - student2.ru

нахождение посылок для данных следствий - student2.ru

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

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

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

а) нахождение посылок для данных следствий - student2.ru ├ X & Y;

б) нахождение посылок для данных следствий - student2.ruнахождение посылок для данных следствий - student2.ru ;

в) нахождение посылок для данных следствий - student2.ruнахождение посылок для данных следствий - student2.ru ;

г) нахождение посылок для данных следствий - student2.ru ├ X & ØV;

д) нахождение посылок для данных следствий - student2.ruнахождение посылок для данных следствий - student2.ru ;

е) нахождение посылок для данных следствий - student2.ru ├ Z;

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

X Y Z V нахождение посылок для данных следствий - student2.ru нахождение посылок для данных следствий - student2.ru нахождение посылок для данных следствий - student2.ru  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Далее, в правом столбце отметим цифрами те строки, в которых обе данные посылки принимают значение 1, а следствие принимает значение 0. Этому требованию отвечает лишь четвертая строка, в которой l(Z)=1 и l(V)=1. Ясно, что при этих значениях Z и V искомая посылка F(Z, V) должна принять значение 0, так как в противном случае формула X&V не будет логическим следствием формул нахождение посылок для данных следствий - student2.ru , нахождение посылок для данных следствий - student2.ru и 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) получаем следующую таблицу истинности:

Z V F(Z, V)

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

Наши рекомендации