![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Пусть формула А = A(Р1,..., Pn, f1,..., fm, x1,..., хk, а1,..., аr). Набор (Р1,..., Pn, f1,..., fm, x1,..., хk,а1,...,аr) называется сигнатурой формулы А. Зафиксируем некоторое множество D, зададим на D предикаты P1,...,Pn; функции f1,..., fm; предметы x1,..., хk, а1,..., аr. Набор I = (D, Р 1,..., P n, f 1,..., f m, x 1,..., х k, а 1,..., а r) называется интерпретацией формулы А. Множество D называется предметной областью интерпретации I. Формула А при таком выборе переменных (предикатных, функциональных, предметных) и констант превращается в высказывание А = А (Р 1,..., P n, f 1,..., f m, x 1,..., х k, а 1,..., а 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 1 ,...,xs ]терма t(x1,...,xs) на интерпретации I).
1. Если t = хi, то t [ x l ,...,xs ]= xi.
2.Если t = аi, то t [ x 1 ,...,xs ] =ai.
3.Если t = f(t1,...,tu), то t [ x1,...,хs ] = f (t 1[ x l,... ,xs ] ,...,tu [ x l...., xs ]).
Определение. Значение формулы А при некоторой интерпретации I обозначается через I(A) (либо AI) и определяется индуктивно следующим образом:
1. Если А есть атом P(t1,…,t u), то I(A) = P (t1[ x1,…,xk ],…,t u [ x1,…,xk ]).
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, которая опровергает А.
Заметим, что формулы А(х1,…,хk) и ("x1)…("xk)A(x1,…,x k) общезначимы или не общезначимы одновременно. Поэтому при вычислении общезначимости формул можно ограничиться замкнутыми формулами (т.е. формулами без свободных предметных переменных).
Теорема. Чтобы формула логики предикатов была общезначима, необходимо и достаточно, чтобы ее отрицание было невыполнимо.
Доказательство. Пусть формула А общезначима. Допустим, что формула
ù А выполнима. Тогда существует интерпретация I, для которой ╞ I (ù А). Поэто-му ù ╞ I(А). Противоречие с общезначимостью А.
Пусть теперь формула ù А невыполнима. Допустим, что формула А общезначимой не является. Тогда существует интерпретация I, которая опровергает А, т.е. ù ╞ I(А). Поэтому ╞ I(ù А). Противоречие с невыполнимостью формулы ù А.
Определение. Формула В есть логическое следствие формул А1, A2,...,Ak, если формула A1& А2&... & Аk® В общезначима.
Заметим, что если формула логики предикатов не содержит кванторов, то ее можно рассматривать как формулу логики высказываний, построенной из элементарных формул логики предикатов.
Определение. Интерпретация I есть модель для формулы А (для множества формул S), если ╞ I(А) (I выполняет всякую формулу из S). Интерпретация I называется опровержением формулы А (множества формул S), если I опровергает А (I опровергает хотя бы одну формулу в S).
Дата публикования: 2015-01-23; Прочитано: 952 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!