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

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

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

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

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

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

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

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

Q = L1PR1 = L2PR2 = … LSPRS.

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

Перейдем к определению формул алгебры предикатов на алгебраической системе М(σ). Сигнатуру σ представим в виде объединения σ = σ1Uσ2, где σ1 — множество символов операций, а σ2 — непустое множество символов предикатов на М. В частности, множество σ1 может быть и пустым. Обозначим через σ0 подмножество из σ1 обозначений всех нуль-арных операций, т. е. выделенных элементов множества М. Оно может быть любым подмножеством из М. При определении формулы в качестве обозначений будут использоваться различные буквы (возможно, с индексами): A, D, C для элементов из σ0; F, φ, ψ для элементов из σ1; P, Q для элементов из σ2. Кроме того, будут использоваться: множество Х символов предметных переменных со значениями из М, обозначаемых буквами X, Y, Z, U, v (возможно, с индексами); множество О логических операций &, v, ®, ┐, ", $ и служебных символов — скобок и запятых. Таким образом, алфавитом при построении формул будет служить множество Ҩ = σ È X È O.

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

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

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

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

2. Если F — символ N-арной операции из σ и T1, …, TN — термы, то слово F(T1, …, TN) есть терм.

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

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

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

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

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

2. Если Р — символ N-местного предиката из σ, а T1, …, TN — термы, то слово P(T1, …, TN) есть формула.

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

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

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

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

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

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

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

"X1(($X1(P1(X2, X1))) v ("X2(()))) (9.1)

Есть формула, поскольку P1(X2, X1), P2(X1, X2) являются формулами по пункту 2, это элементарные формулы. Тогда есть формула по пункту 3, $X1(P1(X2, X1)) и есть формулы по пункту 4 и, далее

($X1(P1(X2, X1))) v ("X2())

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

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

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

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

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

Считать, что операция & сильнее Ú, обе эти операции сильнее ®, а операции навешивания кванторов сильнее всех других операций;

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

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

(…((A1 & A2) & A3)…) & AK, (…((A1 v A2) v A3)…) v AK;

Записывать формулу δ1X1(δ2X2(…(δKXKA)…)) с кванторами δ1, …, δK в виде δ1X1δ2X2 … δKXKA и в виде δ1X1, X2, …, XKA при совпадении кванторов δ1, …, δK.

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

"X1($X1P1(X2, X1) v "X2).

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

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

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

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

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

3. Подформулами любой формулы вида `A, "XA, $XA называются сама эта формула и все подформулы формулы А.

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

$X1P1(X2, X1) v "X2, ,

"X2, P1(X2, X1), P2(X1, X2), $X1P1(X2, X1).

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

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

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

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

Примеры 9.6.

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

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

3. Формула

"X2, X3((X1 = X2X3) ® (X1 = X2) v (X1 = X3) (9.2)

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

Формула "X1, X2 (X1X2 = X2X1) выполнима, так как она выполнима, например, на системе N(. ; =). Однако она не тождественно истинна, поскольку существуют некоммутативные системы с операцией умножения.

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

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

< Предыдущая		Следующая >