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

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

а) XY;

б) XY;

в) XY;

г) (XY);

д) (XY)(XY).

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

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

XY(XY)(YX)(XY)(XY).

Недостающими в этой форме дизъюнктивными одночленами вида X*Y* являются XY и XY. Поэтому искомыми посылками для данной формулы являются формулы (XY)(XY), (XY)(XY) и (XY)(XY)(XY). Преобразуем их равносильным образом к более простым формулам:

(XY)(XY)(XY)(XY)(XY)(XY)XXY;

(XY)(XY)(XY)(XY)(XY)(XY)YXY;

(XY)(XY)(XY)(XY)(XY)(XY)(XY)(XY)(XY)XXX0

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

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

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

а) XYZ, YV, F(Z,V) |=XV;

б) XZ, YV, F(Z,V) |=XY;

в) XZ, Y(XZ), F(X,Y) |= YZ;

г) XZ, YZ, Z(YV), F(X,Y) |= XV;

д) YZ, (XZ)(VY). F(X,Y) |= XV;

е) XY, F(X,Y,Z) |= Z.

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

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

Z	V	F(Z,V)
0	0	1
0	1	1
1	0	1
1	1	0

Находим СКН-форму для искомой формулы. Получаем: F(Z,V)ZVZV.

39. В следующем рассуждении найдите недостающую посылку, связывающую высказывания «Прямые a и b лежат в одной плоскости» и «Прямые a и b скрещиваются» так, чтобы рассуждение было правильным:

1. Прямые a и b либо параллельны, либо пересекаются, либо скрещиваются.

2. Прямые a и b лежат в одной плоскости и не пересекаются.

3. ???

Следовательно, прямые a и b лежат в одной плоскости и параллельны.

Решение: Введем обозначения для простейших высказываний, входящих в это рассуждение:

X: «Прямые a и b параллельны»;

Y: «Прямые a и b пересекаются»;

Z: «Прямые a и b скрещиваются»;

V: «Прямые a и b лежат в одной плоскости».

Тогда задача сводится к отысканию такой формулы F(Z,V), зависящей от переменных Z и V, что справедлива следующая выводимость:

XYZ, YV, F(Z,V) |= XV.

В задаче 5.38, а такая формула нами найдена: ZV. Остается придать этой формуле содержательный смысл: «Если Прямые a и b скрещиваются, то они не лежат в одной плоскости».

40. В следующем рассуждении найдите недостающую посылку так, чтобы рассуждение было правильным и посылка выражала связь между высказываниями «Целое число оканчивается нулем»; «Целое число делится на 5»; «Целое число оканчивается цифрой 5».

1. Целое число делится на 5 и не оканчивается нулем.

2. ???

Следовательно, целое число оканчивается цифрой 5.

Указание: см. задачу 5.38,е.