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

Определение 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.

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

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

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

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

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 ₂ ).

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

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

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