Глава 2. Логика предикатов первого порядка

Глава 2. Логика предикатов первого порядка

Логика высказываний обладает довольно слабыми выразительными возможностями. В ней нельзя выразить даже очень простые с математической точки зрения рассуждения. Рассмотрим, например, следующее умозаключение. “Всякое целое число является рациональным. Число 2 – целое. Следовательно, 2 – рациональное число”. Все эти утверждения с точки зрения логики высказываний являются атомарными. Средствами логики высказываний нельзя вскрыть внутреннюю структуру и поэтому нельзя доказать логичность этого рассуждения в рамках логики высказываний. Мы рассмотрим расширение логики высказываний, которое называется логикой предикатов первого порядка (или логикой первого порядка, или логикой предикатов).

Интерпретация в логике первого порядка

Необходимо соотнести формулы логики предикатов первого порядка и предикаты. Как и в логике высказываний, подобное соотнесение осуществляет функция, называемая интерпретацией.

Определение. Интерпретацией на непустом множестве M называется функция, заданная на сигнатуре F ∪ R, которая

1) константе ставит в соответствие элемент из M;

2) символу n -местной функции ставит в соответствие некоторую n -местную функцию, определенную на множестве M;

3) символу n -местного предиката ставит в соответствие n -местный предикат, заданный на M.

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

Пример 1. Пусть сигнатура состоит из символов одноместного предиката P и двухместного предиката D, M = {2,

3, 6, 9, 12, 15} и 

F = P (x) & (∀ y)(P (y) → D (x, y)).

Поставим в соответствие символу P предикат “ x – простое число”, символу D – предикат “ x меньше или равно y ”. Тогда формула F получит в соответствие предикат “ x = 2”. На этом же множестве можно рассмотреть и другую интерпретацию: P ставится в соответствие “ x – нечетное число”, D – предикат “ x делит y ”. В таком случае, формула F получает в соответствие предикат “ x = 3”. Если ϕ – интерпретация, то предикат, соответствующий формуле F, будем обозначать через ϕ F.  

Одним из основных типов задач этой главы являются задачи, связанные с использованием выразительных возможностей языка логики предикатов. В качестве примера рассмотрим задачу перевода на язык логики предикатов следующего рассуждения. “Каждый первокурсник знаком с кем-либо из спортсменов. Никакой первокурсник не знаком ни с одном любителем подледного лова. Следовательно, никто из спортсменов не является любителем подледного лова”. Для удобства ссылок это рассуждение условимся называть рассуждением о первокурсниках. Выберем следующую сигнатуру (сигнатурные элементы приведены с предполагаемой интерпретацией).

П (x): “ x – первокурсник”, 

С (x): “ x – спортсмен”, 

Л (x): “ x – любитель подледного лова”, З (x, y): “ x знаком с y ”.

Тогда рассуждение запишется в виде следующей последовательности формул:

H ₁ = (∀ x)[ П (х) → (∃ y)(C (y) & З (x, y))], 

H ₂ = (∀ x)(∀ y)[ П (x)& Л (y) → З (x, y)], 

H ₃ = (∀ x)(C (x) → Л (x)).

Мы установили, что выразительных средств логики предикатов достаточно, чтобы записать рассуждение о первокурсниках. Естественно далее поставить вопрос, логично ли оно? Будет ли третье предложение следствием первых двух? На этот вопрос мы ответим в §5. 

Логическое следствие

Определение. Формула G (x ₁, …, x_n) называется логическим следствием формул F ₁(x ₁, …, x_n), …, F_k (x ₁, …, x_n), если для любой интерпретации ϕ с областью М и любых a ₁, …, a_n ∈ M из истинности высказываний (ϕ F ₁)(a ₁, …, a_n), …, (ϕ F_k)(a ₁, …, a_n) следует истинность высказывания (ϕ G)(a ₁, …, a_n).

Пример 1. Пусть F ₁ = (∀ x)(P (x)→ Q (x)& R (x)), F ₂ = P (c), G = Q (c). Покажем, что формула G является логическим следствием формул F ₁ и F ₂. Возьмем интерпретацию ϕ с областью M такую, что высказывания ϕ F ₁ и ϕ F ₂ истинны. Элемент ϕ(c) обозначим буквой b. Истинность ϕ F ₂ означает, что высказывание (ϕ P)(b) истинно. А истинность высказывания ϕ F ₁ означает, что для любого элемента x ∈ M истинно высказывание (ϕ P)(x) → (ϕ Q)(x)&(ϕ R)(x). Поскольку это высказывание истинно для любого х, оно, в частности, истинно для x = b. Мы видим, что истинна импликация (ϕ P)(b) → (ϕ Q)(b)&(ϕ R)(b) и ее посылка (ϕ P)(b). Из таблицы истинности импликации следует истинность заключения (ϕ Q)(b)&(ϕ R)(b). Следовательно, истинно высказывание (ϕ Q)(b). А это и есть ϕ G. Мы доказали, что если истинны высказывания ϕ F ₁ и ϕ F ₂, то истинно высказывание ϕ G, т.е. что G –логическое следствие F ₁ и F ₂. 

Пример 2. В качестве второго примера докажем нелогичность рассуждения о первокурсниках, приведенное в §3. Мы записали это рассуждение в виде последовательности формул H ₁, H ₂, и H ₃. Для доказательства нелогичности рассуждения надо найти интерпретацию ϕ, при которой формулы H ₁ и H ₂ истинны, а формула H ₃ ложна. Пусть множество М состоит из трех элементов 2, 3, 4. Символы С, Л и П проинтерпретируем следующим образом:

(ϕ С)(x) = “ х – простое число”, 

(ϕ Л)(х) = “ х – четное число”, 

(ϕ П)(х) = “ х >4”, 

т.е. П интерпретируется как тождественно ложный пре-

дикат. Символу З поставим в соответствие произвольный двухместный предикат. Тогда формулы H ₁ и H ₂ истинны, поскольку посылки импликаций этих формул ложны при любом x. А формула H ₃ ложна. Чтобы убедиться в этом достаточно взять x = 2. Следовательно, рассуждение о первокурсниках нелогично. 

Определение. Множество формул

K = { F ₁(x ₁, …, x_l), …, F_m (x ₁, …, x_l)}

называется выполнимым, если существует интерпретация ϕ с областью M и элементы a ₁, …, a_l ∈ M такие, что все высказывания (ϕ F ₁)(a ₁, …, a_l), …, (ϕ F_m)(a ₁, …, a_l) истинны.

Пример 3. Множество формул K = { F ₁ = (∀ x)(∃ y)(P (y)

& Q (x, y)), F ₂ = (∀ y) Q (c, y), F ₃ = P (c)} выполнимо. Возьмем в качестве области интерпретации множество натуральных чисел N. Символы P, Q и с проинтерпретируем следующим образом:

(ϕ P)(u) = “ u – простое число”, (ϕ Q)(u, v) = “ u меньше или равно v ”, ϕ(с) = 1.

Тогда высказывание ϕ F ₁ означает, что для любого натурального числа х найдется простое число y, которое не меньше х, высказывание ϕ F ₂ означает, что 1 –наименьшее натуральное число, а высказывание ϕ F ₃ означает, что 1 – непростое число. Ясно, что все эти высказывания истинны, и поэтому множество формул K выполнимо. 

Понятия логического следствия и выполнимости в логике первого порядка связаны точно так же, как и в логике высказываний.

Теорема 2.2. Формула G (x ₁, …, x_n) является логическим следствием формул F ₁(x ₁, …, x_n), …, F_k (x ₁, …, x_n) тогда и только тогда, когда множество формул { F ₁(x ₁, …, x_n), …,

F_k (x ₁, …, x_n), G (x ₁, …, x_n)} невыполнимо.

Доказательство теоремы 2.2 аналогично доказательству теоремы 1.2 и поэтому не приводится.

Нормальные формы

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

Определение. Формула G имеет предваренную нормальную форму (сокращенно: ПНФ), если 

G = (Q ₁ x ₁)…(Q_nx_n) H,

где Q ₁, …, Q_n кванторы, а формула H не содержит кванторов.

Например, формула (∀ x)(∃ y)(P (x, y) & Q (y)) имеет предваренную нормальную форму, а формула (∀ x)(T (x) & S (x, y)) не имеет.

Теорема 2.3. Для всякой формулы F существует формула G, равносильная F и имеющая предваренную нормальную форму.

Доказательство теоремы легко следует из анализа алгоритма приведения к ПНФ.

...

E_n (x, y) = 

(∃ z ₁)…(∃ z_n)[ P (x, z ₁) & P (z ₁, z ₂) &…& P (z_n, y)],

...

Используя определение транзитивного замыкания и предположение о том, что формула F (x, y) определяет транзитивное замыкание, получаем, что формула F (x, y) есть логическое следствие множества формул K. По теореме компактности F (x, y) есть логическое следствие некоторого конечного подмножества K ^/ множества K. Можно считать, что 

K ′ = { E ₀(x, y), E ₁(x, y), …, E_d (x, y)}

для некоторого d.

Пусть M = {0, 1, …, d +1, d +2}. На множестве M определим двухместный предикат S следующим образом:

S (u, v) ⇔ u +1 равно v

Например, высказывания S (0, 1), S (1, 2) истинны, а высказывание S (0, 2) ложно. Отметим, что высказывание S ⁺(0, d +2) истинно. Рассмотрим интерпретацию ϕ, для которой (ϕ P)(u, v) = S (u, v). Все высказывания (ϕ E ₀)(0, d +2), (ϕ E ₁)(0, d +2), …,(ϕ E_d)(0, d +2) истинны. Так как формула F (x, y) есть логическое следствие множества формул K ^/, истинно высказывание (ϕ F)(0, d +2). С другой стороны, поскольку F (x, y) определяет транзитивное замыкание и истинно высказывание S ⁺(0, d +2) (другими словами, высказывание (ϕ P)⁺(0, d +2)), то истинно высказывание (ϕ F)(0, d +2). Мы доказали, что истинно и последнее высказывание, и его отрицание. Полученное противоречие показывает, что не существует формулы логики первого порядка, определяющей транзитивное замыкание предиката. 

Глава 2. Логика предикатов первого порядка

Логика высказываний обладает довольно слабыми выразительными возможностями. В ней нельзя выразить даже очень простые с математической точки зрения рассуждения. Рассмотрим, например, следующее умозаключение. “Всякое целое число является рациональным. Число 2 – целое. Следовательно, 2 – рациональное число”. Все эти утверждения с точки зрения логики высказываний являются атомарными. Средствами логики высказываний нельзя вскрыть внутреннюю структуру и поэтому нельзя доказать логичность этого рассуждения в рамках логики высказываний. Мы рассмотрим расширение логики высказываний, которое называется логикой предикатов первого порядка (или логикой первого порядка, или логикой предикатов).