Т. А. Сливина математическая логика и теория алгоритмов

Теорема 2. Для того, чтобы формула А была выполнимой, необходимо и достаточно, чтобы формула была не общезначима.
Доказательство. Необходимость. Пусть формула А выполнима. Это означает, что существует область М и набор значений переменных, входящих в формулу А, при которых формула А принимает истинное значение. Очевидно, что на этом наборе значений переменных формула принимает ложное значение, и, следовательно, формула необщезначима.
Достаточность. Пусть формула не общезначима. Тогда существует область М и набор значений переменных, входящих в формулу, при которых формула принимает ложное значение. На этом наборе значений переменных формула А принимает значение «истина», и поэтому формула А выполнима.
Отметим, что общезначимую формулу называют логическим законом.
Проблема разрешимости в логике предикатов также как и в алгебре логики состоит в том, чтобы определить к какому классу относится формула – т. е. является ли она общезначимой, выполнимой или тождественно ложной. Если бы такой алгоритм существовал, то как и в алгебре высказываний, он сводился бы к критерию тождественной истинности любой формулы логики предикатов.
Замечание. В отличие от алгебры логики в логике предикатов не применим метод перебора всех вариантов значений переменных, входящих в формулу, так как таких вариантов может быть бесконечно много.
В 1936 году американский математик А. Черч доказал, что проблема разрешимости логики предикатов в общем виде алгоритмически не разрешима, то есть не существует алгоритма, который бы позволил установить, к какому классу формул относится любая формула логики предикатов.
Проблема разрешимости в логике предикатов достаточно сложная задача и решается лишь в отдельных частных случаях.


§ 5. Применение языка логики предикатов для записи математических предложений, определений, построения отрицания предложений

Язык логики предикатов используется в математике для записи математических предложений и определений. Например:

1. Определение предела числовой последовательности:
> 0 < ).
Здесь использован трехместный предикат
Q : < ).
2. Определение предела функции в точке:
> 0 > 0 (0 < < < ).
Здесь использован трехместный предикат
P : (0 < < < ).
3. Определение непрерывности функции в точке: Функция f (x), определенная на множестве Е, непрерывная в точке х₀ Е, если
> 0 > 0 ( < < ).
Здесь использован трехместный предикат
P :( < < ).
4. Определение возрастающей функции: Функция f(x), определенная на множестве Е, возрастает на этом множестве, если
(х₁ < х₂ f(x₁) < f(x₂)).
Здесь использован двухместный предикат Q(x₁, x₂): (x₁ < x₂ f (x₁) < f(x₂)).