Исчисление предикатов

9.1. Общее понятие о логическом исчислении

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

всякое ли утверждение, сформулированное в терминах данной теории, можно доказать или опровергнуть (вопрос о полноте);

нельзя ли в этой теории доказать какое-либо утверждение и его отрицание (вопрос о непротиворечивости) и др.

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

Каждое логическое исчисление характеризуется:

набором используемых в нем символов, или алфавитом;

правилами построения из алфавита корректных утверждений, или формул;

некоторым фиксированным наборам формул, называемым системой аксиом;

наборами правил.

Алфавит, правила образования формул и само множество формул образуют язык исчисления, а правила преобразования формул образуют синтаксис исчисления.

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

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

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

9.2. Формулы алгебры предикатов

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

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

Если А = {а₁, а₂, …, а_n} — алфавит, то любая последовательность его букв называетсясловом в алфавите А. При этом число m называется длиной слова. Длина слова Р обозначается в виде ℓ(Р). Для удобства в рассуждениях вводится еще символ Λ для обозначения пустого слова, т.е. слова, не содержащего ни одной буквы. По определению ℓ(Λ) = 0.

Так как слово есть конечная последовательность букв, то можно все буквы в слове естественным образом занумеровать и говорить о 1-й, 2-й, и т.д. буквах слова. Обычно слова записывают в строки, а буквы в них нумеруют слева направо. Два слова называют равными, или графически равными, если они имеют одинаковую длину и соответствующие их буквы равны. Равенство будем обозначать знаком «=». Множество всех слов и всех слов длины m в алфавите А обозначим соответственно через W(A) и W_m(A).

На множестве W(A) можно ввести операцию умножения (или приписывания) слов, взяв в качестве произведения слов P, Q слово PQ, полученное приписыванием слова Q справа к слову P.

Говорят, что слово P является подсловом Q, если существуют такие слова L, R (возможно пустые), что Q = LPR.

В этом случае говорят также, что слово Р входит или имеет вхождение в слово Q. Может оказаться, что указанная выше пара слов L, R находится по словам P и Q неоднозначно. Выпишем все такие различные пары слов (L_i, R_i) и упорядочим их по возрастанию длины слова L_i. Получим:

Q = L₁PR₁ = L₂PR₂ = … L_sPR_s.

В этом случае говорят, что имеется s вхождений слова P в слово Q, и все эти вхождения упорядочивают по возрастанию длины слова L_i. В соответствии с этим говорят о 1-м, 2-м, и т.д. вхождениях слова P в слово Q. Например, слово «арарат» содержит два вхождения слова «ара».

Перейдем к определению формул алгебры предикатов на алгебраической системе М(σ). Сигнатуру σ представим в виде объединения σ = σ₁Uσ₂, где σ₁ — множество символов операций, а σ₂ — непустое множество символов предикатов на М. В частности, множество σ₁ может быть и пустым. Обозначим через σ₀ подмножество из σ₁ обозначений всех нуль-арных операций, т.е. выделенных элементов множества М. Оно может быть любым подмножеством из М. При определении формулы в качестве обозначений будут использоваться различные буквы (возможно, с индексами): a, d, c для элементов из σ₀; f, φ, ψ для элементов из σ₁; p, q для элементов из σ₂. Кроме того, будут использоваться: множество Х символов предметных переменных со значениями из М, обозначаемых буквами x, y, z, u, v (возможно, с индексами); множество О логических операций , v, , ┐, ,  и служебных символов — скобок и запятых. Таким образом, алфавитом при построении формул будет служить множество Ҩ = σ  X  O.

В конкретных примерах для операций и предикатов будут использоваться также общепринятые обозначения +, , *, =, ≤ и т.д.

Определим предварительно понятие терма на системе М(σ).

Определение 9.1.

1. Каждый символ переменного из Х или константы из σ₀ есть терм.

2. Если f — символ n-арной операции из σ и t₁, …, t_n — термы, то слово f(t₁, …, t_n) есть терм.

3. Других термов нет.

Таким образом, множество термов для М(σ) есть минимальное подмножество слов в алфавите Ҩ, содержащее множество σ  X и замкнутое относительно образования слов по правилу 2. Если вместо переменных из Х в терм t подставить элементы из М и произвести все указанные в t операции, то мы получим элемент из М, называемый значением терма t. Следовательно, терм t определяет функцию на M, зависящую от тех переменных, которые входят в t. Так, если M = N и σ = {0, 1, +}, то термами могут быть представлены все многочлены над N.

Теперь определим понятие формулы. В формулах нам необходимо будет различать свободные и связанные вхождения переменных. Эти понятия удобнее определить параллельно с определением формулы.

Определение 9.2.

1. Любой символ нуль-местного предиката σ есть формула.

2. Если р — символ n-местного предиката из σ, а t₁, …, t_n — термы, то слово p(t₁, …, t_n) есть формула.

3. Если А и В — формулы, то слова (A)  (B), (A) v (B), (A) -> (B), ┐(А)*¹ также являются формулами. В них каждое вхождение переменной является вхождением в формулу А или В и считается таким же (свободным или связанным), каким оно было соответственно в А или В.

4. Если А — формула, в которой есть свободное вхождение переменной x_i, то слова  x_i (A) и  x_i (A) являются формулами, в которых все вхождения переменных, отличных от x_i, называются так же, как и в А, а все вхождения переменной x_i называются связанными. При этом формула А называется областью действия записанного перед ней квантора  или  по переменной x_i.

5. Других формул нет.

Формулы, определенные в пунктах 1-2, называются элементарными. Все вхождения переменных в элементарные формулы называются свободными.

Замечание. В приведенном определении формулы на алгебраической системе М(σ) от М, по существу, использовалось лишь множество выделенных элементов σ₀. Поэтому формулу М(σ) можно рассматривать также и как формулу на любой другой алгебраической системе сигнатуры σ₀. В связи с этим формулы на алгебраической системе М(σ) называют просто формулами алгебры предикатов сигнатуры σ.

Число всех логических операций, участвующих в записи формулы А, назовем рангом формулы А и обозначим через r(A). В частности, r(A) = 0 в том и только том случае, когда А — элементарная формула.

Рассмотрим пример. Пусть р₁, р₂ — символы двухместных предикатов. Тогда выражение

x₁((x₁(p₁(x₂, x₁))) v (x₂(()))) (9.1)

есть формула, поскольку p₁(x₂, x₁), p₂(x₁, x₂) являются формулами по пункту 2, это элементарные формулы. Тогда есть формула по пункту 3, x₁(p₁(x₂, x₁)) и есть формулы по пункту 4 и, далее

(x₁(p₁(x₂, x₁))) v (x₂())

есть формула по пункту 3. В ней последнее вхождение х₁ свободно, а потому (9.1) есть формула по пункту 4.

Заметим, что в формуле (9.1) все вхождения переменной х₁ связанные, первое вхождение переменной х₂ свободно, остальные — связанные.

Число скобок при записи формул можно уменьшить, если условиться:

не заключать в скобки элементарные формулы;

не заключать в скобки формулу, над которой находится знак отрицания;

считать, что операция  сильнее , обе эти операции сильнее , а операции навешивания кванторов сильнее всех других операций;

не заключать в скобки большие латинские буквы, являющиеся обозначениями формул;

опускать скобки в формулах вида

(…((A₁  A₂)  A₃)…)  A_k, (…((A₁ v A₂) v A₃)…) v A_k;

записывать формулу δ₁x₁(δ₂x₂(…(δ_kx_kA)…)) с кванторами δ₁, …, δ_k в виде δ₁x₁δ₂x₂ … δ_kx_kA и в виде δ₁x₁, x₂, …, x_kA при совпадении кванторов δ₁, …, δ_k.

При указанных соглашениях формулу (9.1) можно записать в виде

x₁(x₁p₁(x₂, x₁) v x₂).

В дальнейшем для сокращения иногда будем опускать знак , т.е. вместо А  В писать АВ.

Если А — формула сигнатуры σ, то любое ее подслово, являющееся формулой, называют подформулой формулы А. Подробнее понятие подформулы можно определить индукцией по рангу формулы.

Определение 9.3.

1. Подформулой элементарной формулы А называется сама формула А.

2. Подформулами любой формулы вида AB, A v B, A  B называется сама эта формула и все подформулы формул А и В.

3. Подформулами любой формулы вида A, xA, xA называются сама эта формула и все подформулы формулы А.

Пользуясь определением 9.3, нетрудно выписать все подформулы любой заданной формулы. Так, подформулами формулы (9.1) будут она сама и формулы:

x₁p₁(x₂, x₁) v x₂,,

x₂,p₁(x₂, x₁), p₂(x₁, x₂), x₁p₁(x₂, x₁).

Из рассмотренных в 9.2 правил получения предикатов на множестве М из заданных предикатов видно, что любая формула А алгебры предикатов сигнатуры σ является предикатом на алгебраической системе М(σ), зависящим лишь от тех предметных переменных, которые имеют свободное вхождение в А. Если такими переменными являются x₁, …, x_n, то формулу А иногда записывают в виде A(x₁, …, x_n). Заменив свободные вхождения переменных в формуле А элементами из М (одинаковыми для всех вхождений одной переменной), мы получим высказывание, значение которого можно вычислить, исходя из значений элементарных высказываний и используя определение логических операций. Значения этих высказываний называются значениями формулы А на М(σ) при соответствующих значениях переменных.

Определение 9.4. Формула А алгебры предикатов сигнатуры σ называется выполнимой на алгебраической системе М(σ), если она принимает значение «и» хотя бы при одном наборе из М для переменных, имеющих свободное вхождение в А. В противном случае формула А называется ложной на М(σ). Формула А называется истинной на М(σ), если она принимает значение «и» при любых наборах значений из М для переменных, имеющих свободные вхождения в А.

Определение 9.5. Формула алгебры предикатов сигнатуры σ называется выполнимой, тождественно истинной или тождественно ложной, если она соответственно выполнима хотя бы на одной алгебраической системе, истинна на всех системах или ложна на всех системах сигнатуры σ.

Тождественную истинность (ложность) формулы А обозначают в виде А  и (А  л).

Примеры 9.6.

1. А  (В  А)  и для любых формул А, В.

2. A л для любых формул А, В.

3. Формула

x₂, x₃((x₁ = x₂x₃)  (x₁ = x₂) v (x₁ = x₃) (9.2)

выполнима, но не истинна на алгебраической системе N(. ; =). Легко видеть, что она зависит лишь от х₁ и принимает истинное значение в том и только в том случае, когда значением переменной х₁ является простое число.

Формула x₁, x₂ (x₁x₂ = x₂x₁) выполнима, так как она выполнима, например, на системе N(. ; =). Однако она не тождественно истинна, поскольку существуют некоммутативные системы с операцией умножения.

Пример 3 показывает, что формулами алгебры предикатов можно записывать те или иные свойства элементов алгебраических систем, или характеризовать те или иные подмножества ее основного множества или множества наборов ее элементов. Так формула (9.2) характеризует множество всех простых чисел. Формула x₂(x₁x₂ = x₃) характеризует множество пар натуральных чисел, из которых первое делит второе, т.е. отношение делимости на N.

Пример 4 показывает, что формулы алгебры предикатов сигнатуры σ могут быть использованы для характеризации алгебраических систем сигнатуры σ. Формула из этого примера выделяет класс алгебраических систем с коммутативной операцией умножения, если под равенством = понимать отношение (предикат) совпадения элементов множества.