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

3.1.Равносильные формулы алгебры предикатов. Пусть а и в – некоторые формулы, а – множество, допустимое для этих формул. Совместной интерпретацией формул а и в на множестве называется всякая пара ‹а’, в’› интерпретации для а и в, при которых переменные предикаты, входящие в а и в одновременно, одинаково интерпретируются на и потому имеет смысл говорить об общих логических возможностях для а’и в’ на .

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

Из определения непосредственно следует, что если множество является допустимым для одной из формул а и в и не является допустимым для другой, то а и в на множестве неравносильны.

Определение2. Две формулы а и в называются равносильными, если они равносильны на любом множестве.

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

1. ,2. , 3. , 4. ,

5. , 6. , 7. , 8. , 9. ,

10. , 11. ,

12. , 13. ,

14. , 15. ,

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

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

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

20.Доказательство общезначимости доказуемых формул исчисления высказываний. Предложение 2.7. Во всяком исчислений предикатов первого порядка всякая теорема является логически общезначимой.

Доказательство. В силу свойства (VII) понятия истинной формулы, аксиомы, задаваемые схемами (1)-(3), логически общезначимы. В силу свойств (Х) (следствие) и (ХI), логически верны аксиомы, порождаемые схемами (4)-(5). В силу (III) и (VI), правила вывода МР и Gen сохраняют свойство логической общезначимости. Таким образом, всякая теорема любого исчисления предикатов логически общезначима.

(VII) Всякий частный случай всякой тавтологии истинен во всякой интерпретации. (Частным случаем данной пропозициональной формы мы называем всякую формулу, получаемую подстановкой формул в эту пропозициональную форму вместо пропозициональных букв с тем условием, чтобы вместо всех вхождений одной и той же пропозициональной буквы подставлялась одна и та же формула.

(Х) Лемма. Пусть t и v – термы, s – последовательность из ∑, t’ получается из t подстановкой v вместо всех вхождений х_i и s’ получается из s заменой в ней ее i-й компоненты на s*(v); тогда s*(t’)= (s’) *(t).

(ХI) Если формула А не содержит х_i в качестве свободной переменной, то формула

истинна во всякой интерпретации.