1310
B. Kulik, A. Fridman, A. Zuenko
4.2 Correspondence between N-tuple Algebra and Predicate Calculus
In trivial case (when individual attributes do not correspond to multiplace rela-
tions), an n-tuple corresponds to conjunction of one-place predicates with different
variables. For example, a C-n-tuple P [XY Z] = [P
1
P
2
P
3
] where P
1
⊆ X; P
2
⊆ Y ;
P
3
⊆ Z corresponds to a logical formula H = P
1
(x) ∧ P
2
(y) ∧ P
3
(z).
A D-n-tuple P =
P
1
P
2
P
3
corresponds to the negation of the formula H
(disjunction of one-place predicates) ¬H = ¬P
1
(x) ∨ ¬P
2
(y) ∨ ¬P
3
(z).
An elementary n-tuple that is a part of a non-empty NTA object corresponds
to a satisfying substitution in a logical formula.
An empty NTA object corresponds to an identically false formula.
An NTA object that equals any particular universe corresponds to a valid for-
mula, or a tautology.
A non-empty NTA object corresponds to a satisfiable formula.
In NTA, attribute domains can be any arbitrary sets that are not necessarily
equal to each other. This means that NTA structures correspond to formulas of
many-sorted predicate calculus.
Now let us consider quantifiers in NTA.
If a dummy attribute is added to a C-n-tuple or a C-system, the procedure
corresponds to the derivation rule of predicate calculus called generalization rule. For
example, if an NTA object G[XZ] =
{a, c}
∗
{a, c, d}
{b, c}
corresponds to a formula
F (x, z) of predicate calculus, by adding a dummy attribute Y into this NTA object
we get an NTA object G
1
[XY Z] = +Y (G[XZ]) =
{a, c}
∗
∗
{a, c, d}
∗
{b, c}
which
corresponds to the formula ∀yF (x, z) derived from the formula F (x, z) according
to generalization rule. This relation is obvious for C-n-tuples and C-systems, but
needs to be proved for D-n-tuples and D-systems.
Theorem 13. Adding a new dummy attribute to a D-n-tuple or a D-system cor-
responds to the formula ∀y(P ).
Proof. Let a D-n-tuple P [X
1
X
2
. . . X
n
] = ]P
1
P
2
. . . P
n
[ be given. If we add a dummy
attribute Y to it, we get Q[Y X
1
X
2
. . . X
n
] = ]ØP
1
P
2
. . . P
n
[. Transforming this NTA
objects into C-systems, we have
P =
P
1
∗
. . .
∗
∗
P
2
. . .
∗
. . .
. . .
. . .
. . .
∗
∗
. . .
P
n
;
Q =
∗
P
1
∗
. . .
∗
∗
∗
P
2
. . .
∗
. . .
. . .
. . .
. . .
. . .
∗
∗
∗
. . .
P
n
Hence, Q = +Y (P ) = ∀y(P ).
2
Suppose that a D-system R[X
1
X
2
. . . X
n
] is given. Let R
1
= +Y (R) = R
1
[Y X
1
X
2
. . . X
n
]. In the D-system R
1
, “Ø” are components of the attribute Y in all D-n-
tuples. After transforming this D-system into a C-system according to Theorem 9,
Algebraic Approach to Logical Inference Implementation
1311
the results in projection [X
1
X
2
. . . X
n
] are the same as in transformation of the D-
system R into a C-system, and dummy components “*” are now components of the
attribute Y in the C-system R
1
. Therefore, R
1
= +Y (R) = ∀y(R).
The two theorems that follow define the semantics of the operation -Attr.
Theorem 14. Let R[. . . X . . .] be a C-system that has no C-n-tuples with empty
components in the X attribute. Then for the predicate P (. . . , x, . . .) that corre-
sponds to this C-system, the formula −X(R) corresponds to the formula ∃x(P ).
Proof. Let R be a C-n-tuple. Then under the conditions of the theorem corre-
spondence −X(R) ⇔ ∃x(P ) is evident. Let R be a C-system that contains C-
n-tuples R
1
, R
2
, . . . , R
n
. This means that R = R
1
∪ R
2
∪ . . . ∪ R
n
. Formula
P = P
1
∨ P
2
∨ . . . ∨ P
n
, where P
i
are formulae that correspond to C-n-tuples R
i
corresponds to this formula in predicate calculus. Applying −X operation to R, we
get −X(R) = −X(R
1
) ∪ −X(R
2
) ∪ . . . − X(R
n
).
A formula of predicate calculus ∃x(P
1
) ∨ ∃x(P
2
) ∨ . . . ∨ ∃x(P
n
) corresponds to the
right part of the above equality. According to the rules of equivalent transformations
in mathematical logic, the formula equals to a formula ∃x(P
1
∨ P
2
∨ . . . ∨ P
n
), which
is ∃x(P ) after substitution.
2
Theorem 15. Let R[. . . X . . .] be a D-system that has no D-n-tuples with compo-
nents “*” in the X attribute. Then for a predicate P (. . . , x, . . .) corresponding to
this D-system, formula −X(R) corresponds to the formula ∀x(P ).
Proof. The formula ∀x(P ) is known to be equal to ¬(∃x(¬P )). A C-system R that
equals to the complement of the D-system R corresponds to the expression ¬P .
Q = −X(R) corresponds to the formula ∃x(¬P ) since satisfies the conditions of
Theorem 14. Then ¬(∃x(¬P )) is an NTA object that equals a D-system all of whose
components equal the complements of corresponding components of Q. Therefore,
Q = −X(R) as the attribute X has been eliminated from the C-system R.
2
Hence, if an attribute (e.g. X) is eliminated from a C-system, it means that
the quantifier ∃x is applied to this object, and if this attribute is eliminated from
a D-system, it means that the quantifier ∀x is applied to this object. For example,
let a C-system and its complement expressed as a D-system be given:
Q[XY Z] =
{a, b, d}
{f, h}
{b}
{b, c}
∗
{a, c}
and
Q[XY Z] =
{c}
{g}
{a, c}
{a, d}
Ø
{b}
.
Then
∃x(Q[XY Z]) =
{f, h}
{b}
∗
{a, c}