Равносильные формулы логики предикатов

1. Две формулы A и B логики предикатов называются равносильными на области M, если они принимают одинаковые логические значения для всех значений, входящих в них переменных, принадлежащих области M.

2. Две формулы A и B логики предикатов называются равносильными, если они равносильны на всякой области.

Как и в алгебре логики, для равносильности формул используют обозначение .

К сказанному нужно добавить, что все равносильности алгебры логики будут верны, если в них вместо высказываний подставить формулы логики предикатов. В логике предикатов, кроме равносильностей, аналогичных равносильностям алгебры логики, имеются еще собственные равносильности, не имеющие аналогов в алгебре логики. Эти дополнительные равносильности обусловлены кванторными операциями. Приведем основные из этих равносильностей. Пусть A(x) и B(x) - переменные предикаты, а C - переменное высказывание, тогда имеют место следующие равносильности:

1) ;

2) ;

3) ;

4) ;

5) – эта равносильность свиде-тельствует о том, что квантор всеобщности можно вносить и выносить за скобки в конъюнкции;

6) ;

7) ;

8) ;

9) .

Равносильности 6 - 8 говорят о том, что переменное высказывание можно вносить под знак квантора всеобщности и выносить из-под знака этого квантора в конъюнкции, дизъюнкции и импликации.

Несколько особой в этом смысле является равносильность 9. В ней переменное высказывание вносится под квантор (правая часть этой равносильности), а выносится квантор (левая часть этой равносильности). Покажем, что это правильно, и одновременно отметим, что в некоторых учебных пособиях ошибочно в этой равносильности переменное высказывание вносится и выносится из-под одного и того же квантора :

.

Последняя формула получена на основании равносильности 7. Далее:

10) , т.е. квантор существования можно вносить и выносить за скобки в дизъюнкции;

11) ;

12) ;

13) ;

14) .

Равносильности 11 - 13 говорят о том, что переменное высказывание можно вносить под знак квантора существования и выносить из-под этого квантора в конъюнкции, дизъюнкции и импликации.

Так же, как и равносильность 9, равносильность 14 является особой. В ней переменное высказывание вносится под квантор , а выносится из-под квантора . Покажем, что это действительно так:

. На основании равносильности 12 имеем

.

15) ;

16) .

Приведем обоснование некоторых из этих равносильностей. Однако сразу же нужно отметить, что если в алгебре логики для установления равносильности двух формул мы использовали либо алгебраическое преобразование формул, либо строили для них таблицы истинности, то в алгебре предикатов такой подход не приемлем. Это объясняется тем, что в алгебре логики можно было легко перебрать всевозможные наборы логических значений высказываний, так как каждое из них принимает всего два значения: 0 либо 1. В алгебре предикатов логическое значение предиката зависит уже от переменных, принимающих значения не из множества , а из множеств различной природы, в том числе из бесконечных дискретных и непрерывных множеств. Построить же такие таблицы истинности невозможно, так как такие таблицы должны иметь неограниченные размеры.

Поэтому в алгебре предикатов при установлении тех или иных их свойств в основном пользуются непосредственными рассуждениями, применяя аксиомы и законы алгебры логики.

Так, равносильность 1 означает тот простой факт, что если не для всех x истинно A(x), то существует x, при котором будет истинным противоположный предикат .

Аналогично равносильность 2 означает тот простой факт, что если не существует , при котором истинно A (x), то для всех будет истинным противоположный предикат .

Равносильности 3 и 4 получаются из равносильностей 1 и 2 соответственно, если над обеими их частями выполнить операцию отрицания, а затем воспользоваться законом двойного отрицания:

;

.

Приведем рассуждения, обосновывающие равносильность 5. Если оба предиката A(x) и B(x) тождественно истинные, то будет тождественно истинным и предикат , а поэтому будут истинными высказывания

; .

Эти два высказывания являются соответственно левой и правой частями равносильности 5, т.е. в этом случае обе части равносильности 5 принимают значение “истина”. Но может быть и другой случай, когда хотя бы один из предикатов A(x) или B(x) будет не тождественно истинным. Пусть, например, A(x) не тождественно истинный предикат. Тогда не тождественно истинным будет и предикат , а поэтому будут ложными и высказывания

, и ,

т.е. и в этом случае обе части равносильности 5 принимают одинаковые (ложные) значения. Рассмотренные два случая представляют всевозможные “комбинации” логических значений высказываний, входящих в левую и правую части равносильности 5, которые являются одновременно или истинными, или ложными. А это и означает их равносильность.

Еще более “длинно” доказывается равносильность формул, содержащих переменные высказывания и предикаты. Здесь надо проанализировать логические значения формул при двух логических значениях переменного высказывания и определенных предположениях о логических значениях предикатов и высказываний, полученных путем связывания переменных кванторами. Таковыми, например, являются равносильности 8, 9, 13 и 14.

Докажем равносильность 8. Пусть переменное высказывание принимает значение “ложь”. Тогда тождественно истинным будет предикат , так как в таком случае исключается из рассмотрения единственная импликация , когда она принимает ложное значение. Очевидно, что истинными будут и высказывания и (по тем же причинам). То есть в этом случае обе части равносильности 8 принимают одинаковые логические значения “истина”.

Пусть теперь переменное высказывание C принимает значение “истина”. Если при этом предикат B(x) является тождественно истинным, то будет тождественно истинным и предикат (так как ), а значит, истинными будут и высказывания , и . Таким образом, и в этом случае обе части равносильности 8 принимают одинаковые истинные значения.

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

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

Аналогично доказываются и остальные из перечисленных равносильностей.

Особый интерес представляют две последние равносильности –15 и 16. Казалось бы, что в дизъюнкции, образованной двумя высказываниями, каждое из которых получено путем применения квантора , последний можно вынести за скобку. Но оказывается, что , аналогично в конъюнкции , т.е. в таких формулах нельзя выносить за скобки и вносить в них кванторы и !

Однако левую часть каждой из этих неравносильностей можно видоизменить так, что вынесение кванторов за скобки станет возможным. Для этого нужно предварительно переименовать переменные. Это можно делать, так как обозначение переменной в предикате произвольно. Поэтому высказывания и - равносильны.

Далее, анализируя равносильности 5, 6 и 7, видим, что квантор выносится за скобку, когда он применяется к предикату с той переменной, на которую он же и указывает, или к переменному высказыванию, у которого переменной нет.

Таким образом, можно записать последовательность равносильных преобразований:

.

Этим, собственно говоря, и доказывается равносильность 15.

Точно так же доказывается равносильность 16. Только в этом случае следует обратить внимание на равносильности 10, 11 и 12, указывающие на то, в каких случаях можно выносить за скобки квантор существования .

Исходя из этого, можно записать последовательность равносильных преобразований:

.

Это и доказывает равносильность 16.

Упражнения

1. Какие из следующих выражений являются формулами логики предикатов (в каждой формуле выделите свободные и связанные переменные):

1) ; 2) ; 3) ;

4) ; 5) ; 6) ?

2. Найти отрицание следующих формул:

1) ; 2) ;

3) ; 4) ;

5) ; 6) ;

7) ;

8) .

3. Какие из следующих предложений истинны и какие ложны, если предикат определен на множестве и означает “x<y”:

1) ; 2) ; 3) ; 4) ;

5) ; 6) ; 7) ; 8) ?

4. Пусть предикат B(x,y) определен на множестве и представляет высказывательную форму “ x<y ”. Какие из приведенных предикатов тождественно истинные, а какие тождественно ложные, а может быть, и ни те, и ни другие:

1) ; 2) ; 3) ; 4) ?

5. Пусть A (x) и B (x) - любые предикаты. Какие из следующих формул равносильны формуле :

1) ; 2) ; 3) ; 4) ;

5) ; 6) ; 7) ?

6. Доказать, что для любой формулы логики предикатов можно построить равносильную ей формулу, не содержащую:

1) кванторов существования; 2) кванторов всеобщности.