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

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

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

Если А = { а ₁, а ₂, …, а_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.

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

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

Дата добавления: 2014-12-29