Определение. Набор {X,A,F,P} называется сигнату-рой формулы В.
Формулу можно представить в виде некоторой слож-ной зависимости В{X,A,F,P}.
Определение. Зафиксируем некоторое множество М и зададим на нем набор конкретных переменных Х ', констант A', функций F', предикатов P'. Набор I={М, Х ', A', F', P'} называется интерпретацией формулы В. М называется предметной областью интерпретации I.
Если формула замкнута, то она либо истинна либо ложна, т.е. превращается в логическую константу. Если же формула имеет свободные переменные, то при задании ин-терпретации она превращается в логическую функцию, при-нимающую значения истинности в зависимости от значений переменных на предметном множестве М.
Пример 1. Допустим, дана замкнутая формула ЛП:
B = " х$ у Р(х,у).
В формуле B: Х=(x ,y), A = (Æ ), F = (Æ );P = (P(x,y)).
1. Рассмотрим первую интерпретацию формулы В. В ней принимаем: М = {N} - множество натуральных чисел, Р(х,у) = S(x,y) =“ у больше х”. В интерпретации I1 = (N,(x,y),Æ ,Æ , S(x,y)) формула B приобретает следующий смысл: ”Для лю-бого натурального числа х существует натуральное число у, большее его“. Очевидно, в интерпретации I1 формула В = И.
2. Рассмотрим вторую интерпретацию формулы В. М = {N},
Р(х,у) = Q(x,y )=“ у меньше х”. В интерпретации I2= (N, (x, y),Æ,Æ,Q(x,y)) формула имеет смысл: ”Для любого нату-рального числа х существует натуральное число у , меньшее его“. Поскольку для х = 1 меньшего числа не существует, то в интерпретации I2 формула В = Л.
Пример 2. Рассмотрим формулу В(х) =Ø $ у Р(х,у) & Р(у,a) & S(x,y).
В ней одна свободная переменная - x , множества X,A,F,P следующие: Х=(x ,y), A = (а ), F = (Æ );P = (P(x,y), S(x,y)).
Дадим следующую интерпретацию формулы В . М = {N} - множество натуральных чисел, а=1, Р(х,у) = NE(х,у)= “ у не равно х”, S(x,y) = Div(x,y) =” у делит х без остатка”. В интерпретации I = (N,(x,y),(1),Æ,(NE(x,y),Div(x,y))) форму-ла B истинна при данном значении х, тогда и только тогда, когда не существует натурального у, не равного 1 и х, которое делит х без остатка.Таким образом, в приведенной интерпретации формула В принимает значения истинности тогда и только тогда, когда число х является простым. Подставляя различные значения х, будем получать сле-дующие значения истинности: В(2) = И, В(4) = Л, В(7) = И, В(10) =Л, В(17) = И и т.д.
Определение. Интерпретация I = {М, Х', A', F', P'}вы-полняет формулу В{X,A,F,P}, если высказывание В { Х ', A', F', P'} - истинно. Обозначаем I|=В.
Определение. Интерпретация I = {М, Х ', A', F', P'}опровергает формулу В{X,A,F,P}, если высказывание В { Х ',
A', F', P'} - ложно. Обозначаем I Ø|=В.
Определение. Формула Вобщезначима (опровержи-ма) на множестве М, если любая интерпретация I с предмет-ной областью М выполняет (опровергает) формулу В.
Определение. Формула Ввыполнима ( невыполнима) намножестве М, если существует интерпретация I с пред-метной областью М, которая выполняет формулу В (любая
интерпретация I с предметной областью М опровергает формулу В).
Пример 3. Рассмотрим формулу В { (х, у), Æ, Æ, (Р,Q)} = Ø Р(х,у)® Q(х,у). В качестве предметной области М примем множество {0,1}. В качестве интерпретации I1 на М зададим Р(х,у)=(х®у)¯z, Q(х,у)=z. Формула В=(х®у)¯z ®z является тавтологией в ИВ. Это можно выяснить при помощи таблицы истинности. Поэтому интерпретация I1 выполняет ее на множестве М .
Определение. Интерпретация I есть модель для фор-мулы В (множества формул S), если I|=В (I выполняет лю-бую формулу из S ). Интерпретация I называется опровер-жением формулы В (множества формул S), если IØ|=В (I опровергает хотя бы одну формулу в S ).
Определение. Формула Вистинна ( ложна) в данной интерпретации, если ВºИ(ВºЛ) при любом значении сво-бодных переменных, входящих в нее.
При доказательстве истинности формул обычно при-меняют метод доказательства от противного - допускают существование интерпретации, в которой формула будет ложна и приводят утверждение к противоречию.
Пример 4. Доказать тождественную истинность фор-мулы Ø $ х Р(х) ® Ø " х Р(х).
Решение. Допустим, на некотором ненулевом множестве М и сигнатуре s формула ложна. Из ложности импликации следует, одновременное выполнение двух условий:
Ø $ х Р(х) =И и Ø " х Р(х)= Л.
Снимая отрицания, получим: $ х Р(х) =Л и " хР(х)= И. Из первого утверждения следует, что существуют лож-ные значения предиката Р на множестве М , из второго следует, что все значения Р на М должны быть истинны. Полученное противоречие доказывает тождественную ис-тинность формулы.
