Формулы логики предикатов, их равносильность, выполнимость и общезначимость

Классификация формул логики предикатов. Сформулируем классификационные определения для формул логики предикатов. Рассмотрим некоторую интерпретацию с множеством М.

Определение. Формула А выполнима в интерпретации, если существует набор <a₁, …, a_n>, a_iÎ M, значений свободных переменных x_i1, …, x_inформулы А такой, что А|<a₁, …, a_n>=И.

Определение. Формула А истинна в данной интерпретации, если она принимает значение И на любом наборе <a₁, …, a_n>, a_iÎ M, значений своих свободных переменных x_i1, …, x_in.

Определение. Формула А выполнима (в логике предикатов), если существует интерпретация, в которой А выполнима.

Определение. Формула А, истинная при любой интерпретации, называется общезначимой или тождественно-истинной (в логике предикатов).

Теорема Черча. Не существует алгоритма, который для любой формулы логики предикатов устанавливает, общезначима она или нет.

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

Определение. Формулы А и В равносильны на множестве М, если они равносильны во всех интерпретациях, заданных на множестве М..

Определение. Формулы А и В равносильны в логике предикатов, если они равносильны на всех множествах (АºВ).

Укажем несколько правил перехода от одних формул к другим, им равносильным.

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

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