Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
е) Если формула имеет вид (VF^p) SI или (3/^) Si, или (VP(p) Si, или (3Р(р) Si, то значение ^ определяется так же, как и в случае д). Разница состоит лишь в том, что в качестве значений переменных F(f и P^f теперь надо брать операции и предикаты на множестве 4, 150
ЯЗЫКИ ПЕРВОЙ II ВТОРОЙ СТУПЕНИ
[Гл. III
Формула % называется истинной на заданном множестве А при заданных значениях всех ее свободных переменных, если значение gf равно И. Формула % называется ложной, если значение ее равно JI. Рассмотрим, например, формулу
(3X1) Ff(XuX2) = х9. (5)
Чтобы найти ее значение, надо сначала указать основное множество А и задать значения предметных переменных и функционального переменного Пусть А — совокупность натуральных чисел, F^ = Тогда
истинность формулы (5) равносильна истинности соотношения
^O \ %<2. "^r -??
и, например, формула (5) истинна для X2= 2, X3 = 5 и ложна для х2~ 5, X3 = 2.
На том же множестве А ={0,1, . . .} рассмотрим формулу
(Vx1) (Зх2) Ff (х2, Ff (X1, х3)) = х3. (6)
Пусть значение Ff' есть операция сложения чисел, значение F^ есть операция умножения. Тогда истинность формулы (6) будет равносильна истинности утверждения о том, что для каждого натурального х уравнение
у + ха = а (7)
имеет хотя бы одно натуральное решение у. Это, очевидно, верно, если а = 0, и ложно, если а Ф 0.
При тех же значениях переменных истинность формулы
(Ix2) (Vxi) Ff (х2, Ff (хи х3)) = х3
равносильна истинности утверждения о том, что существует такое натуральное число у, для которого для всех натуральных значений х выполнено равенство (7).
При записи формул языка 2-й ступени обычно пользуются разного рода сокращениями. Наиболее употребительные из них следующие. Прежде всего, не выписывают внешних скобок. Например, словом
X1 = X2 & H X1 — X3 СИНТАКСИС И СЕМАНТИКА
151
обозначают формулу
(Xi ~ Xz & н X1 = X3).
Вместо формулы П ? = t) пишут %Ф t). При последовательности кванторов V промежуточные кванторы опускают и вместо (Vxi) (Vxj) ... (Vxh) ?! пишут (VXiX) ... хи) St- Аналогично вместо (Эжг) (ЭXj) . . . (Злъ) SI пишут (3XiXj ... Xk) Si. В формулах вида
(...((SiVSts)VSWV---VSTft)
опускают скобки и пишут
. WiVSf2V^V-.-VSIa-
Чтобы еще б0лее сократить количество скобок в формулах, пользуются известным правилом силы операции, полагая, что связка V сильнее связки & и связка & сильнее связки -V. Это значит, что при отсутствии некоторых скобок их надо восстанавливать в следующем порядке: сначала выделяем скобками такой минимальный отрезок, содержащий первый знак V і который вместе с этим знаком и восстанавливаемыми скобками образует формулу. Восстановив этим способом скобки для знаков \J , переходим к восстановлению скобок, связанных со знаками &, и затем к восстановлению скобок, связанных со знаками -v. Например, слово
-Ixl = X2St-IPfMPf^x1=X3 (8)
после восстановления скобок переходит в формулу ((-IX1 = X2Sc (н Pf V Pf)) -+X1 = X5),
для которой слово (8) и служит сокращенной записью.
Изложенные способы сокращенной записи позволяют избегать лишних нагромождений скобок. Наряду с этим применяется важный способ сокращения записи путем введения новых обозначений. Пусть формула SI содержит подформулу 55, имеющую свободные в Я предметные переменные Xi, Xj. Для подформулы 35 можно ввести обозначение U (xt, Xj), где U — символ, не входящий в алфавит рассматриваемого языка. Подставляя в формулу SI вместо 05 слово U (Xi, Xj), получим новое слово, которое 152
ЯЗЫКИ ПЕРВОЙ II ВТОРОЙ СТУПЕНИ [Гл. III
и называется сокращенной записью формулы 21. Такие сокращенные обозначения можно вводить не только для подформул, но и для отдельных переменных. Например, мы будем говорить: возьмем какую-нибудь бинарную операцию L, унарные предикаты Q, R, предметные переменные х, у и рассмотрим формулу
L (х, y)=L(y,x)&iQ (х) &R(y). (9)
Это значит, что мы рассматриваем формулу, которая юлучается из слова (9) подстановкой вместо х, у каких-то различных предметных переменных Xi, Xj, вместо L какого-то функционального переменного Ff^ и вместо Q, R каких-то различных унарных предикатных переменных Р?\ Рї\
Как уже говорилось в п. 3.1, термы вида FW (хщ, . .., хт.) иногда обозначают через хт ... xm.Ff\
а формулы Р(р (Xml, . .., хт.) — через Xmi .. . xm.Pf\ Для бинарных операций и предикатов вместо F (х, у), P (х, у) иногда пишут xFy, хРу. В результате довольно длинные формулы, имеющие, например, вид
P(F(x, у), z)&F(x, z) =F (z, х), оказывается возможным записать короче в виде (xFy) Pz & xFz = zFx.
Для того чтобы говорить о значении формулы или терма, надо сначала фиксировать основное множество А и на нем задать значения свободных переменных, входящих в формулу. Иногда бывает интересно фиксировать значения лишь некоторых свободных переменных на А и затем следить за законом изменения значения формулы или терма при изменении значений остальных свободных переменных. В этом случае часто в заданную формулу вместо свободных переменных, имеющих фиксированные значения, подставляют обозначения этих значений и рассматривают формулу смешанного вида, составленную частично из символов языка 2-й ступени и частично из обозначений конкретных элементов, операций и предикатов, являющихся значениями соответствующих переменных заданной формулы. СИНТАКСИС И СЕМАНТИКА
