Интерпретация формул

Пусть формула А = A(Р₁,..., P_n, f₁,..., f_m, x₁,..., х_k, а₁,..., а_r). Набор (Р₁,..., P_n, f₁,..., f_m, x₁,..., х_k,а₁,...,а_r) называется сигнатурой формулы А. Зафиксируем некоторое множество D, зададим на D преди­каты P₁,...,P_n; функции f₁,..., f_m; предметы x₁,..., х_k, а₁,..., а_r. Набор I = (D, Р ₁,..., P _n, f ₁,..., f _m, x ₁,..., х _k, а ₁,..., а _r) называется интерпретацией формулы А. Множество D называется предметной областью интерпретации I. Формула А при таком выборе переменных (предикатных, функциональных, предметных) и констант превращается в высказывание А = А (Р ₁,..., P _n, f ₁,..., f _m, x ₁,..., х _k, а ₁,..., а _r ), истинное или ложное.

Пример. Пусть формула

A(P,Q,R,y,z,a) = ($ х)(ù Р(х,а) & ù P(x,z) & Q(x,y) & R(x,y));

D = {0,1,2,...} - множество натуральных чисел;

Р(х,у) есть х = у;

Q(x,y) есть х £ у;

R(x,y) есть Div(x,y) (x делит у);

у = 8, z = 4, а = 1.

Тогда высказывание A = A (P,Q,R,y,z,a) =

($ х)( ù Р(х,а) & ù P(x,z) & Q(x,y) & R(x,y)) =

($ х)(х ¹1& x ¹4 & x£ 8 & Div(x, 8 ))

истинно.

Определение (значение t [ x ₁ ,...,x_s ]терма t(x₁,...,x_s) на ин­терпретации I).

1. Если t = х_i, то t [ x _l ,...,x_s ]= x_i.

2.Если t = а_i, то t [ x ₁ ,...,x_s ] =a_i.

3.Если t = f(t₁,...,t_u), то t [ x₁,...,х_s ] = f (t ₁[ x _l,... ,x_s ] ,...,t_u [ x _l...., x_s ]).

Определение. Значение формулы А при некоторой интерпретации I обозначается через I(A) (либо A_I) и определяется индуктивно следующим образом:

1. Если А есть атом P(t₁,…,t _u), то I(A) = P (t₁[ x₁,…,x_k ],…,t _u [ x₁,…,x_k ]).

2. Если А есть В * С, где знак * Î {&, V, ®}, то I(A) «I(B) * I(C).

3. Если А есть ù В, то I(A) «ù (I(B)).

4. Если А есть ($x) B(x), то I(A) «$x Î D I(B(x)).

5. Если А есть ("x) B(x), то I(A) «"x Î D I(B(x)).

Определение. Формула А выполняется на интерпретации I (или интерпретация I выполняет формулу А), если I(А) = И (обозначение ╞ I(А)).

Определение. Формула А опровергается на интерпретации I (или интерпретация I опровергает формулу А), если I(A) = Л (обозначение ù╞ I(А)).

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

Пример. Пусть формула А = ("x)($y)P(x,y) ® ($y)("x)P(x,y).

1. Положим интерпретацию I = (D, Р(х,у)) = ({1,2}, х £ у). Высказывание ("x)($y) х £ у ® ( $ у)( " х) х £ y истинно из-за истин­ности заключения. Поэтому ╞ I(А), т.е. интерпретация I превращает формулу А в истинное высказывание.

2. I = ({1,2}, х = у). Высказывание ("x)($y) х = у ® ( $ у)( " х) х = у ложно, ибо его посылка истинна, а его заключение ложно. Поэтому ù ╞ I(А), т.е. I опровергает А.

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

Заметим, что формулы А(х₁,…,х_k) и ("x₁)…("x_k)A(x₁,…,x _k) общезначимы или не общезначимы одновременно. Поэтому при вычисле­нии общезначимости формул можно ограничиться замкнутыми формулами (т.е. формулами без свободных предметных переменных).

Теорема. Чтобы формула логики предикатов была общезначима, не­обходимо и достаточно, чтобы ее отрицание было невыполнимо.

Доказательство. Пусть формула А общезначима. Допустим, что формула
ù А выполнима. Тогда существует интерпретация I, для кото­рой ╞ I (ù А). Поэто-му ù ╞ I(А). Противоречие с общезначимостью А.

Пусть теперь формула ù А невыполнима. Допустим, что формула А общезначимой не является. Тогда существует интерпретация I, кото­рая опровергает А, т.е. ù ╞ I(А). Поэтому ╞ I(ù А). Противоречие с невыполнимостью формулы ù А.

Определение. Формула В есть логическое следствие формул А₁, A₂,...,A_k, если формула A₁& А₂&... & А_k® В общезначима.

Заметим, что если формула логики предикатов не содержит кван­торов, то ее можно рассматривать как формулу логики высказываний, построенной из элементарных формул логики предикатов.

Определение. Интерпретация I есть модель для формулы А (для множества формул S), если ╞ I(А) (I выполняет всякую формулу из S). Интерпретация I называется опровержением формулы А (множества формул S), если I опровергает А (I опровергает хотя бы одну формулу в S).