Правильно построенные формулы (ППФ)
. Как видно из определения, ППФ – это предикат первого порядка.
Примеры простых предикатов:
SX.S# = SPJX.S#;
SX.S# = ‘S1’;
SX.S# = SPJX.S# AND SPJX.P# = ‘P1’;
NOT (SX.Ci = ‘Яя’);
IF SX.Ci = ‘Яя’ THEN SPJX.S# = ‘S1’;
Последний предикат – пример намеренно бессмысленного, но синтаксически правильного высказывания.
Правильно построенная формула может содержать кванторы EXISTS (существует) и FORALL (для всякого).
Выражение EXISTS SX (SX.Ci = ‘Яя’) может быть прочитано так: «Существует в области определения переменной SX кортеж со значением атрибута Ci равным ‘Яя’». Предикат принимает значение .T., если в текущем значении отношения S есть хотя бы один кортеж со значением Ci = ‘Яя’.
Вообще говоря, если R
– некоторое отношение, t – переменная, определенная на R, t1, t2, …, tn
– значения t (кортежи R), a f(t)
– ППФ, то формула EXISTS t (f(t)) равносильна бескванторной формуле .F. OR f(t1) OR f(t2) OR … OR f(tn).
Выражение FORALL SX (SX. Ci = ‘Яя’) может быть прочитано так: «В каждом кортеже отношения S значение атрибута Ci равно ‘Яя’».
В предыдущих обозначениях формула FORALL t (f(t)) равносильна бескванторной формуле .Т. AND f(t1) AND f(t2) AND … AND f(tn). Очевидно, FORALL t (f(t)) равносильно NOT EXISTS t (NOT (f(t)).
Переменная t, входящая в ППФ, называется связанной
или свободной в зависимости от того, действует ли на формулу квантор по t.
Примеры:
f(t) – переменная t свободная;
f(t, q) – переменные t и q свободные;
EXISTS t (f(t, q)) – переменная t связанная, q – свободная;
FORALL
t (f(t)) AND g(t) - первое вхождение t – связанное, второе – свободное.
В последней формуле одним и тем же символом t обозначены разные переменные, возможно, определенные на одной и той же области. В первой подформуле можно изменить имя переменной, не меняя смысла высказывания и значения предиката. Переменная служит здесь лишь для связи внутренних параметров предиката f( ) с внешним квантором. Второе вхождение переменной t
имеет совершенно иной смысл. Здесь g(t)
принимает то или иное значение в зависимости от значения переменной t. Заменить t на x, например, здесь нельзя, поскольку х и t могут принимать различные значения.
Связанная переменная подобна локальной переменной в языках программирования.
Формула, в которой все переменные связаны, называется закрытой. Например, FORALL x (EXISTS y (f(x, y)))
– закрытая формула. Формула, содержащая по крайней мере одну свободную переменную, называется открытой.
