Классификационные определения для формул логики предикатов

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

Т.е. формула выполнима (опровержима) на M, если существует истинная (ложная) ее интерпретация.

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

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

Тавтология F обозначается .

Значение формулы логики предикатов

Логическое значение формулы логики предикатов определяется, когда задано множество M, на котором определены входящие в эту формулу предикаты.

Логическое значение зависит от трех видов переменных:

1) Значений входящих в формулу переменных высказываний (пропозициональных переменных) – нульместных предикатных переменных;

2) Значений предикатных переменных;

3) Значений свободных предметных переменных из множества M.

Пример

Рассмотрим формулу , в которой двухместный предикат P (x, y) определен на множестве M M, где . В эту формулу входит:

P (x, y) – переменный предикат;

x, y, z – предметные переменные;

y, z – связанные переменные;

x – свободная переменная.

Возьмем вместо P (x, y) фиксированный предикат , свободной переменной придадим значение .

Тогда при предикат принимает значение ложь.

Импликация при всех принимает значение истина, т.е. высказывание имеет значение истина.