Интерпретация. Выполнимость и истинность.

Интерпретация S формулы А логики первого порядка состоит из непустой предметной области D и оценки (значения) всех констант, функциональных и предикатных символов формулы А.

1. Каждой предметной константе ставим в соответствие некоторый элемент из D.

2. Каждому n-местному функциональному символу ставим в соответствие отображение Dⁿ D.

3. Каждому n-местному предикатному символу ставим в соответствие отображение Dⁿ{И, Л}.

Таким образом, получаем два вида отображений – для функциональных и предикатных символов.

Отношения для интерпретации предикатных символов часто представляют следующим образом:

(P(c₁,…,c_n) = И)  < c₁,…,c_n>R_P.

Значения истинности для формул получаются следующим образом:

1. Значения истинности элементарных формул получается из соответствующих отображений.

2. Если формула имеет вид , (АВ), (АВ), (АВ), (АВ), то значение истинности получается из значений истинности формул А и В по таблицам истинности.

3. Формула у А получает значение истинности И, если А имеет значение истинности И при всех значениях входящих в неё переменных.

4. Формула у А получает значение истинности И, если А она имеет значение И при некотором (хотя бы одном) значении из области D.

В заданной интерпретации замкнутая формула имеет значение И или Л.

Для конечной области D={d₁,d₂,…,d_n}.

"x А(x)

$x А(x)

1. Формула А со свободными переменными выполнима в S, если существует подстановка констант вместо свободных индивидных переменных формулы А, такая, что формула А истинна в S.

2. Формула А истинна в S, если она истинна при любой подстановке констант вместо свободных индивидных переменных. Тогда S называется моделью формулы А.

3. Формула А выполнима, если существует модель А.

4. Формула общезначима, если она истинна в каждой интерпретации.

5. Формула А ложна в S, если она ложна при любой подстановке констант из D вместо свободных переменных формулы А.

6. Формула А не выполнима (противоречива), если она ложна в любой интерпретации S.

Свойства интерпретации.

1. А ложна в S тогда и только тогда, когда истинно в S. А истинна в S, если ложна в S.

2. Никакая формула не может быть истинной и ложной в одной и той же интерпретации S.

3. А истинна в S тогда и только тогда, когда x_i А истинна в S.

Замыканием формулы А называется формула, полученная из А приписыванием кванторов общности x_i для всех свободных переменных x_i формулы А (значение истинности формулы сохраняется).

4. Всякий частный случай всякой тавтологии – общезначимая формула.

5. А общезначима тогда и только тогда, когда невыполнима. А является противоречием тогда и только тогда, когда общезначима. Общезначимую формулу называют логическим законом.

6. Говорят, что А логически влечёт В, если для любой интерпретации S и любой подстановки термов вместо свободных переменных в формулу А&В, если истинно А, то истинно и В.

А логически влечёт В тогда и только тогда, когда АВ логически общезначима.

7. Формулы А и В эквивалентны, если каждая из них влечёт другую.

Логическая теория противоречива, если в ней выводимы одновременно А и для некоторой формулы А.

Теорема. Всякая непротиворечивая теория первого порядка имеет счётную модель.

Независимость системы аксиом

Теорема Чёрча. Исчисление предикатов неразрешимо.

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

Теорема Гёделя о полноте. В исчислении предикатов теоремами являются те и только те формулы, которые логически общезначимы.

Области разрешимости исчисления предикатов.

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

Более того, исчисление предикатов полуразрешимо, т.е. если формула общезначима, то доказательство её будет найдено (когда-нибудь), но невозможно определить, доказательство не найдено ещё, или же его не существует. Нельзя установить так же необщезначимость необщезначимой формулы.