Логика предикатов. Равносильные формулы логики предикатов. Общезначимость и выполнимость формул

Определение 1. Две формулы логики предикатов А и В называются равносильными на области М, если они принимают одинаковые значения при всех значениях входящих в них переменных, отнесенных к области М.

Определение 2. Две формулы логики предикатов А и В называются равносильными, если они равносильны на всякой области (обозначение:).

Ясно, что все равносильности алгебры высказываний будут верны, если в них вместо переменных высказываний подставить формулы логики предикатов. Но, кроме того, имеют место равносильности самой логики предикатов.

Рассмотрим основные из этих равносильностей. Пусть А (х) и В (х) – переменные предикаты, а С – переменное высказывание. Тогда

1. ,

2. ,

3. ,

4. ,

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

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

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

Эти равносильности широко используются в логике предикатов при равносильных преобразованиях, если приходится иметь дело с выражениями, содержащими операцию отрицания.