2. Модель. Формула алгебры предикатов сигнатуры .

Ряд важнейших понятий алгебры предикатов основывается на понятии модели.

Моделью  называется любое множество M с заданными на нем предикатами :

 = < M ; >.

Множество M называется основным множеством модели , предикаты – основными предикатами модели, и их набор  = <> называется сигнатурой модели. Натуральные числа k₁,  , k_n обозначают арности соответствующих предикатов, а их набор  = < k₁,  , k_n > называется типом модели.

Пример.

– множество натуральных чисел, E, S, P – определенные на множестве  предикаты равенства, сложения и умножения, т.е.

.

Модель  = <  ; E, S, P > является арифметикой натуральных чисел. Ее синатура  = < E, S, P > и тип  = < 2, 3, 3 >.

Любое множество моделей с одной и той же сигнатурой  называется классом K_ моделей сигнатуры .

Определим формулу алгебры предикатов сигнатуры . Так же как и в алгебре высказываний, такое определение является индуктивным.

1. Если и– предметные переменные, то выражениеесть формула. Такая формула называетсяатомарной, в ней все вхождения предметных переменных называются свободными.

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

3. Если U есть формула, то  U – также формула, и все свободные и связанные вхождения предметных переменных в формулу U являются соответственно свободными и связанными вхождениями в формуле  U.

4. Если U и V есть формулы, то выражения (U)  (V), (U)  (V), (U)  (V), (U) ~ (V) также являются формулами, причем все вхождения предметных переменных в этих формулах такие же, как и в формулах U и V.

5. Формулы могут быть образованы только с помощью правил 1 – 4.

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

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

вместо записи , где– некоторые кванторы, допускать запись;

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

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

не указывать явно с помощью верхнего индекса местность предиката.

Если формула U не содержит свободных вхождений предметных переменных, то, используя определения операций, можно вычислить ее логическое значение. Если в формуле U есть свободные вхождения предметных переменных, то она является предикатом, называемым формульным, зависящим от значений этих переменных. Но при каждой замене в этой формуле всех свободных вхождений предметных переменных элементами множества M она становится высказыванием, значение которого вычисляется так же, как и в первом случае. Например, формула на модели арифметики натуральных чисел является формульным предикатом от переменныхx и y, т.е.

(1)

и определяет отношение . Легко проверить, что,,.

Формула называетсявыполнимой на модели , если для некоторой системы элементов модели сигнатуры  значение формулы сигнатуры, т.е. высказывание , является истинным.

Формула U сигнатуры  называется выполнимой, если существует модель сигнатуры , на которой выполнима формула U.

Если высказывание является истинным для любой системы значений, то формула U называется истинной на модели .

Если формула не выполнима на модели , то она называется ложной на модели .

Так формула (1) является выполнимой на модели , но она не будет ни истинной, ни ложной на ней. Формула

выражает однозначность операции сложения и является истинной на этой модели, а формула – ложной.

Если формула U истинна на любой модели класса K_ , то она называется истинной на классе K_ .