Часть 1. Язык предикатов

1.1. Предварительные сведения

Пусть U  некоторое множество объектов, представляющих предмет нашего рассмотрения, будем называть его в дальнейшем универсумом рассуждения.

Если f  символ, обозначающий некоторую k-местную функцию, отображающую U ^k в U, и a₁, a₂, ...,  a_k  обозначения некоторых объектов из U, то выражение f (a₁, a₂, ...,  a_k) используется обычно как имя элемента из U, который соответствует набору элементов a₁, a₂, ...,  a_k при отображении f.

Имея имена объектов и функций, мы можем строить из них более сложные имена. Например, если g  имя одноместной, а h  двухместной функции и a, b  имена объектов из U, то, используя традиционным образом скобки, мы можем построить сложное имя h(g(a), h(b, g(a))). Чтобы определить значение этого имени, сначала следует определить значение имени g(a), затем h(b, g(a)) и, наконец, h(g(a), h(b, g(a))).

Наряду с именами объектов будем использовать также специальные символы, называемые переменными. Если, например, x  переменная, то выражение h(g(x), h(b, g(a))) рассматривают как именную форму (схему) для образования имени. Подставляя в такие формы вместо переменных имена объектов, будем получать новые имена.

Выражения, построенные из функциональных символов, символов объектов и переменных, называются термами. Ниже мы дадим точное определение терма.

Пусть теперь Q  имя некоторого k-местного отношения, t₁, t₂, ..., t_k  имена объектов (простые или сложные), тогда выражение Q(t₁, t₂, ..., t_k) рассматривается как элементарное (атомарное) высказывание: «Элементы с именами t₁, t₂, ..., t_k находятся в отношении с именем Q».

Истинностным значением этого высказывания является истина или ложь, в зависимости от того, находятся или не находятся элементы с именами t₁, t₂, ..., t_k в отношении с именем Q.

Если в выражения t₁, t₂, ..., t_k входят переменные, то выражение Q(t₁, t₂, ..., t_k) рассматривают как элементарную высказывательную форму, которая может быть превращена в элементарное высказывание подстановкой имен объектов вместо переменных.

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

Например, термы с двухместной функцией сложения записываются в виде t₁+ t₂, а не в виде + (t₁, t₂); аналогично, выражения элементарных высказываний t₁ = t₂, t₁ < t₂ и т.д. используются вместо выражений = (t₁, t₂), < (t₁, t₂) и т.д. При этом часто используются различные правила опускания скобок.

Из элементарных высказывательных форм и высказываний с помощью логических связок  (если..., то...),  (…и…),  (…или…),  (не…) и кванторов  (для любого) и  (существует) с использованием скобок могут быть образованы сложные высказывания и высказывательные формы.

Чтобы предварительно продемонстрировать способы построения сложных высказываний, рассмотрим пример.

Выберем в качестве универсума множество N, состоящее из натуральных чисел, включая 0, и рассмотрим известные арифметические функции +, ; предикаты =, <; имена натуральных чисел 0, 1, 2,... и переменные x, y, z.

Выражения x + 2, x + y, (x + 2)3, 1 + 2 будут термами в инфиксной записи, те же термы в префиксной записи выглядят следующим образом: + (x, 2), + (x, y),  (+ (x, 2), 3), +(1, 2).

Высказывательные формы x < 2, x + 2 < (x + 2)y, 2 < 2 + 1 в префиксной записи будут такими: < (x, 2), < (+ (x, 2), (+ (x, 2), y)), < (2, + (2, 1)).

Выражение ((x + 2) < 6)&(2 < (x + 1)) будет сложной высказывательной формой, которая при подстановке вместо x константы 2 превращается в истинное высказывание: «2 + 2 < 6 и 2 < 2 + 1». При подстановке константы 4 она превращается в ложное высказывание.

Выражение x [(x + 2 < 6)&(2 < x + 1)] можно перевести на русский язык следующим образом. «Существует такое значение переменной x, при котором x + 2 < 6 и 2 < x + 1». Очевидно, это высказывание истинно, в качестве x можно взять константу 2 или 3.

Выражение x [(x + 2 < 6)&(2 < x + 1)] переводится на русский язык следующим образом. «Для любого значения переменной x из множества N имеют место неравенства x + 2 < 6 и 2 < x + 1». Очевидно, это утверждение ложно.

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