4. Правила вывода.

   1. Правило вывода modus ponens (MP): если A и B произвольные формулы, то B непосредственно выводима из формул A и A ⊃ B по

правилу вывода modus ponens.

2. Правило обобщения (Gen): если A - произвольная формула, то из

A по правилу обобщения непосредственно выводима формула ∀x_iA.

Gen = {(A, ∀x_iA) | A - формула}.

Замечание 5.2.2 . В алфавит не входят символы ∨, ∧, ≡, ∃x. Тем

не менее, мы можем использовать эти символы, как краткую форму

записи в некоторых сложных выражениях:

A ∨ B = (¬A ⊃ B),

A ∧ B = (¬(A ⊃ ¬B)),

A ≡ B = ((A ⊃ B) ∧ (B ⊃ A)) = (¬((A ⊃ B) ⊃ ¬(B ⊃ A))),

∃x_iA = ¬∀x_i¬A.

3. Интерпретация

Понятие интерпретации позволяет поставить в соответствие формуле некоторый смысл. Для этого каждому символу алфавита, который

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

1. Для предметных переменных в интерпретации задается произвольное множество M - область интерпретации. Каждая предметная переменная может принимать произвольное значение из M .

2. В интерпретации каждой предметной константе сопоставляется единственный элемент из M .

3. i

   Каждому функциональному символу f ⁿ

в интерпретации сопоста-

вляется функция

_f n

_i : M × M × · · · × M

n

→ M.

Здесь n - число аргументов функции, а i - номер функции с данным числом аргументов.

Функциональные символы в частности и термы в общем позволяют косвенно ссылаться на элемент в M .

4. i

   Каждому предикатному символу Aⁿ

в интерпретации сопоставля-

ется функция

_An

_i : M × M × · · · × M

n

→ {0, 1}.

i

Другими словами, каждому предикатному символу Aⁿ сопоставляется n-

арное отношение на множестве M .

Предикатный символ представляет элементарное высказывание, утверждающее, что некоторые n объектов находятся в некотором отношении.

Пример 5.2.6 . Запишем уравнение y = x² + 2x + 1 на языке предикатов. Область интерпретации M = R. В уравненииесть

одно бинарное отношение "=" и действия умножения и сложения над элементами из области интерпретации.

Пусть A²(x₁, x₂) = 1 ⇔ x₁ = x₂. Пусть f ²(x₁, x₂) = x₁ + x₂ и

1

f

(

x

2

² ₁, x₂) = x₁

• x₂

. Пусть c₁

1

= 1.

(y, x) = A²(y, f ²(f ²(x, x), f ²(f ²(f ²(c₁, c₁), x), c₁))) = 1 тогда и

Тогда A

1 1 2

1 2 1

только тогда, когда y = x² + 2x + 1.

1

Можно было бы упростить запись использовав другую интерпретацию. Например, введя f ¹(x) = x² + 2x + 1, нашу формулу

можно будет записать как A(y, x) = A²(y, f ¹(x)).

1 1

5. Рассмотрим, как интерпретируются формулы, построенные из символов описанных выше с использованием логических операций и

квантора всеобщности. Будем обозначать A_I формулу, полученную

из A заменой символов исчисления предикатов на соответствующие

отношения, операции и константы интерпретации I.

Пусть A(x_i1 , x_i2 , ..., x_ik ) - формула, x_i1 , x_i2 , ..., x_ik - все ее свободные переменные. I - интерпретация формулы A с областью интерпретации

M .

Для каждого предикатного символа мы знаем, какая функция ему сопоставляется интерпретацией. Пусть формуле A в интерпретации I

соответствует функция

A_I : M × M × · · · × M

k

Тогда будем полагать, что

→ {0, 1}.

(¬A(x_i1 , x_i2 , ..., x_ik ))_I = 1 ⇐⇒ A_I (x_i1 , x_i2 , ..., x_ik ) = 0,

(∀x_it A(x_i1 , ..., x_it−1 , x_it , x_it+1 , ..., x_ik ))_I = 1 ⇐⇒

⇐⇒ A_I (x_i1 , ..., x_it−1 , x, x_it+1 , ..., x_ik ) = 1, ∀x ∈ M,

если квантор берется по свободной переменной формулы A, и

(∀x_sA(x_i1 , x_i2 , ..., x_ik ))_I = A_I (x_i1 , x_i2 , ..., x_ik ),

если у A нет свободной переменной x_s.

Пусть A(x_i1 , x_i2 , ..., x_ik ) и B(x_j1 , x_j2 , ..., x_jl ) - формулы, которым в

интерпретации I сопоставлены соответственно функции A_I и B_I . Тогда

(A(x_i1 , ..., x_ik ) ⊃ B(x_j1 , ..., x_jl ))_I = 1 ⇐⇒

⇐⇒ A_I (x_i1 , ..., x_ik ) = 1 влечет B_I (x_j1 , ..., x_jl ) = 1.

Если задана интерпретация, замкнутая формула принимает фиксированное значение - "истина" или "ложь".

Пример 5.2.7 . Рассмотрим интерпретацию для формулы

A(x₁) = ¬A²(x₁, a₁) ∧ ∀x₂(∃x₃A²(x₁, f ²(x₂, x₃)) ⊃

1 1 1

⊃ (A²(x₂, x₁) ∨ A²(x₂, a₁))).

1 1

1

Пусть область интерпретации M = N, A²

• отношение равенства,

_f 2

₁ - операция умножения, a₁ = 1. Тогда формулу можно переписать следующим образом:

A_I (x₁) = (x₁ /= 1) ∧ ∀x₂(∃x₃(x₁ = x₂ · x₃) ⊃ ((x₁ = x₂) ∨ (x₂ = 1))).

Таким образом, в данной интерпретации A_I - функция равная 1 тогда и только тогда, когда ее единственный аргумент x₁ - простое число.

Пример 5.2.8 . Пусть задан алфавит:

1. Предметные переменные: x₁, x₂, ...

2. Предикатные символы A³, A³.

1 2

3) ⊃, ¬, ∀x_i, (, ), ,.

Рассмотрим интерпретацию I: M = 2^D = {X | X ⊆ D}, где D -

некоторое множество.

_A3

₁(x₁, x₂, x₃) = 1 ⇔ x₃ = x₁ ∪ x₂.

_A3

₂(x₁, x₂, x₃) = 1 ⇔ x₃ = x₁ ∩ x₂.

Задача: простроить формулы для предикатов

A∅(x1) = 1	⇔	x1 = ∅.
A=(x1, x2) = 1	⇔	x1 = x2.
A⊆(x1, x2) = 1	⇔	x1 ⊆ x2.
A1(x1) = 1	⇔	|x1| = 1.

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

1

A_∅(x₁) = ∀x₂A³(x₁, x₂, x₂).

1

A₌(x₁, x₂) = A³(x₁, x₁, x₂).

3

A_⊆(x₁, x₂) = A₂(x₁, x₂, x₁).

A₁(x₁) = ¬A_∅(x₁) ∧ ∀x₂(A_⊆(x₁, x₂)∨

2

∨ ∃x₃(A³(x₁, x₂, x₃) ∧ A_∅(x₃))).

Определение 5.2.7 . Будем говорить, что формула A выполнима в

I, если ∃d₁ ∈ M , ∃d₂ ∈ M , ..., ∃d_k ∈ M : A_I (d₁, d₂, ..., d_k) = 1.

Определение 5.2.8 . Будем говорить, что формула A истинна в I, если ∀d₁ ∈ M , ∀d₂ ∈ M , ..., ∀d_k ∈ M : A_I (d₁, d₂, ..., d_k) = 1.

Пример 5.2.9 . Рассмотрим интерпретацию для формулы A =

(∀x₁(A¹(x₁) ⊃ A¹(x₁)) ∧ A¹(a₁)) ⊃ A¹(a₁). Пусть M - множество всех

1 2 1 2

_A1

когда-либо живших на земле;

₁(x) = 1 тогда и только тогда, когда x

• 2

  человек; A¹(x) = 1 тогда и только тогда, когда x - смертен; a₁ =

Сократ.

Тогда формула A может читаться следующим образом: "Любой

человек смертен и Сократ - человек. Следовательно, Сократ -

смертен."

Формула замкнута и в интерпретации принимает фиксированное значение 1. Таким образом, формула A - истинна в данной

интерпретации.

Определение 5.2.9 . Будем говорить, что формула A ложна в I, если

∀d₁ ∈ M , ∀d₂ ∈ M , ..., ∀d_k ∈ M : A_I (d₁, d₂, ..., d_k) = 0.

Определение 5.2.10 . Будем говорить, что I - модель для множе- ства формул Γ, если любая формула A ∈ Γ будет истинна в I.

Определение 5.2.11 . Будем говорить, что формула A выполнима, если существует интерпретация I, такая что A выполнима в I.

Определение 5.2.12 . A - логически общезначима, если A истинна в любой интерпретации.

Определение 5.2.13 . Будем говорить, что формула A противоречие, если ¬A - логически общезначима.

Определение 5.2.14 . Будем говорить, что A логически влечет B (B логическое следствие A), если (A ⊃ B) - логически общезначима.

Замечание 5.2.3 . Раньше мы уже приводили определение 5.2.12 под номером 5.2.1. Здесь повторяем его, пользуясь строго определенными понятиями.

Логически общезначимые формулы - аналог тавтологий в исчислении высказываний в том смысле, что они представляют собой логические законы математической логики, любая интерпретация которых будет давать нам логически истинное высказывание. В отличии от исчисления высказываний здесь нет алгоритма, позволяющего для произвольной формулы определить, является ли она логически общезначимой, хотя можно построить формальную теорию, в которой будут выводиться только логически общезначемые формулы.

Теорема 5.2.1 . Пусть A - формула исчисления предикатов. Тогда,

A - логически общезначима тогда и только тогда, когда f--_ИП A.

Замечание 5.2.4 . Поскольку не существует алгоритма, позволяюще- го определить, является ли заданная формула логически общезначимой, формальная теория исчисление предикатов не является разрешимой.