Равносильность формул

Две формулы логики предикатов называются равносильными (рав­ными), если они принимают одинаковые истинностные значения при всех значениях входящих в эти формулы свободных переменных (мно­жество D; предикаты и функции, определенные на D; предметы из D). Другими словами, две формулы из ЛП равносильны, если на всякой интерпретации эти формулы одновременно истинны или ложны. Приведем примеры равносильных формул.

1. ($х)А(х) = ($у)А(у).

2. ("x)A(x) = ("y)A(y), т.е. возможны переименования связанных предмет-ных переменных.

3. ($х)($у)А(х,у) = ($у)($х)А(х,у).

4. ("x)("y)A(x,y) = ("y)("x)A(x,y), т.е. соседние одноименные кванторы можно менять местами.

5. ù ("x)A(x) = ($х) ù А(х).

В самом деле, пусть D - произвольное множество, на котором определены все свободные переменные и константы формулы А, кроме х. Тогда на указанном наборе переменных высказывание ù(" х)А(х) истинно «не для всех х из D А(х) истинно «существует х = х₀ Î D, для которого А(х₀) ложно «существует х = х₀ Î D, для которо­го ù А(х₀) истинно «($x) ù A(x) истинно.

6. ù ($х)А(х) = ("х) ù А(х).

В самом деле, ("x) ù A(x) = ù ù ("х) ù А(х) = ù ($х) ù ù А(х) = ù ($х)А(х).

7. ("x)A(x) = ù ($х) ù А(х).

В самом деле, ("x)A(x) = ù ù ("x)A(x) = ù ($х) ù А(х).

8. ($х)А(х) = ù ("x) ù A(x).

В самом деле, ($х)А(х) = ù ù ($х)А(х) = ù ("x) ù A(x).

9. ($х)(А(х) & Н) = ($х)А(х) & Н, где формула Н не содержит переменную х свободно.

В самом деле, ($ х) (А(х) & Н) истинно «существует х = х₀ Î D, для которого A(х₀) и H истинны «($ х)А(х) & Н истинно.

10. ("x)(A(x) V Н) = ("x)A(x) V Н, где формула Н не содержит переменную х свободно.

В самом деле, ("x)(A(x) V Н) = ù ù ("х)(А(х) V Н) = ù ($х) ù (А(х) V Н) =
ù ($х)(ù А(х) & ù Н) = ù ($х) ù А(х) V ù ù Н = ("x) ù ù A(x) V Н = ("x)A(x) V H.

11. ($х)(А(х) V В(х)) = ($х)А(х) V ($х)В(х).

В самом деле, ($ х)(А(х) V В(х)) истинно «существует х = х₀, для которого А(х₀) или В(х₀) истинно «($ х)А(х₀) V В(х₀) истинно.

12. ("x)(A(x) & В(х)) = ("x)A(x) & ("x)B(x).

В самом деле, пусть С(х) = А(х) & В(х). Тогда ("x)C(x) = ù ù (Ах)С(х) =
ù ($х) ù (А(х) & В(х)) = ù ($х)(ù А(х) V ù В(х)) = ù (($х) ù А(х) V ($х) ù В(х)) =
ù ($х) ù А(х) & ù ($х) ù В(х) = ("x)A(x) & ("x)B(x).

Формулы 11 и 12 утверждают, что квантор существования можно распределять по дизъюнкции, а квантор общности по конъюнкции. Что касается распределения квантора существования по конъюнкции, а квантора общности по дизъюнкции, то здесь общезначимы формулы

($х)(А(х) & В(х)) ® ($х)А(х) & ($х)В(х);

("x)A(x) V ("x)B(x) ® ("x)(A(x) V В(х)).

Обратные следования неверны.

13. ($х)А(х) & ($х)В(х) = ($х)($_У)(А(х) & В(у)).

В самом деле, высказывание ($ х)А(х) & ($ х)В(х) истинно «существуют элементы х₀ и y₀, для которых

А(х₀) и В(у₀) истинны «($ х) ($ у)(А(х) & В(у)) истинно.

14. ("x)A(x) V ("x)B(x) = ("x)("y)(A(x) V В(у)).

В самом деле, ("x)A(x) V ("x)B(x) = ("x)A(x) V ("y)B(y) = ("x)(A(x) V ("y)B(y)) = ("x)("y)(A(x) V B(y)).

15. ("x)(C ® B(x)) = С ® ("x)B(x), где формула С не содержит переменной х свободно.

В самом деле, ("x)(C ® В(х)) = ("х)(ù С V В(х)) = ù С V ("x)B(x) =
С ® ("x)B(x).

16. ("x)(B(x) ® С) = ($х)В(х) ® С, где формула С не содержит переменную х свободно.

В самом деле, ("x)(B(x) ® С) = ("x)(ù B(x) V С) = ("х) ù В(х) V С =
ù ($х)В(х) V С = ($х)В(х) ® С.

17. ($х)(С ®В(х)) = С ® ($х)В(х),

где формула С не содержит переменной х свободно.

18. ($х)(В(х) ® С) = ("x)B(x) ® С,

где формула С не содержит переменной х свободно.

Замечание. Если в формулах с 1 по 18 заменить равенство на эквивалентность º, причем эквивалентность двух формул А º В по­нимать как (А ® В) & (В ® А), то формулы с 1 по 18 станут обще­значимыми.

3.3.1. Релятивизованные кванторы

Пусть А(х) и В(х) - формулы логики предикатов, имеющие свобо­дную переменную х и возможно другие свободные переменные. Пусть

($х)_A(x)В(х) означает ($х)(А(х) & В(х)),

("x)_A(x) В(х) означает ("x)(A(x) ® В(х)).

Кванторы ($х)_A(x) и ("x)_A(x) называются релятивизованными.

Справедливы следующие равносильности:

ù ($x)_A(x)B(x)=("х)_A(x) ù B(x);

ù ("х)_А(х) В(х) = ("x)_A(x) ù B(x).

В самом деле, ù ($х)_A(x) В(х) = ù ($х)(А(х) & В(х)) = ("x) ù (A(x) & B(x)) = ("x)(ù A(x) V ù В(х)) = ("x)(A(x) ®ù В(х)) = ("х)_А(x) ù В(х);

ù ("х)_A(х) В(х) = ù (" x)(A(x) ® В(х)) = ($ х) ù (ù А(х) V В(х)) =
($ х) (А(х) & ù В(х)) = ($ х)_А(х) ù B(x).