1304
B. Kulik, A. Fridman, A. Zuenko
For implementing intelligence systems, it is often necessary to transform NTA
objects into an alternative class. Complexity of this transformation will be discussed
below in Section 5. Let us now introduce theorems regulating this transformation.
Theorem 8. Every C-n-tuple (D-n-tuple) P can be transformed into an equiva-
lent D-system (C-system) in which every non-dummy component p
i
corresponding
to an attribute X
i
of the initial n-tuple is expressed by a D-n-tuple (C-n-tuple)
having the component p
i
in the attribute X
i
and dummy components in all the rest
attributes.
Proof. The statement regarding transformation a D-n-tuple into a C-system im-
mediately follows from the definition of a D-n-tuple as a compact expression for
the corresponding C-system. The algorithm of transformation of a C-n-tuple into
an equivalent D-system results from the duality property of alternative classes.
2
For example, a D-n-tuple ]A Ø BC[ where A, B, C are not dummy can be
recorded as a C-system
A
∗
∗
∗
∗
∗
B
∗
∗
∗
∗
C
, and a C-n-tuple [AB ∗ C] – as a D-
system
A
Ø
Ø
Ø
Ø
B
Ø
Ø
Ø
Ø
Ø
C
.
Evidently, algorithms for transformation of C-n-tuples and D-n-tuples into
structures of an alternative class are not exponentially complex. Laboriousness of
the algorithms increases significantly for C-systems and D-systems. Two following
assertions are given here without any proof due to their obviousness.
Theorem 9. A D-system P containing m D-n-tuples is equivalent to a C-system
equal to the intersection of m C-systems obtained by transformation every D-n-tuple
belonging to P into a C-system.
Theorem 10. A C-system P containing m C-n-tuples is equivalent to a D-system
equal to the union of m D-systems obtained by transforming every C-n-tuple be-
longing to P into a D-system.
Transformations of NTA objects into objects of alternative classes allow to realize
all operations of theory of sets on NTA objects, as well as all checks of relations
among such objects without having to represent the objects as sets of elementary n-
tuples. In some cases, inclusion checks can be done directly for structures belonging
to different alternative classes. The following theorems describe these cases.
Theorem 11. P ⊆ Q is true for a C-n-tuple P = [p
1
p
2
. . . p
n
] and a D-n-tuple
Q = ]q
1
q
2
. . . q
n
[ if and only if p
i
⊆ q
i
is true for at least one value of i.
Proof. A D-n-tuple is equivalent to a C-system containing n C-n-tuples all of
whose components are complete dummy components except q
i
. So, the necessity
of the theorem statement follows from the fact that a C-system is a union of the
Algebraic Approach to Logical Inference Implementation
1305
C-n-tuples. Indeed, if one of the C-n-tuples Q
i
belonging to the C-system obtained
after transforming the initial D-n-tuple Q equals to [∗ ∗ . . . q
i
. . . ∗] and p
i
⊆ q
i
, then
P ⊆ Q
i
and hence P ⊆ Q. Let us prove the sufficiency. Suppose p
i
⊆ q
i
is false
for every i. We need to prove that P ⊆ Q is impossible then. This supposition lets
us conclude that for every i, there is a r
i
= p
i
\ q
i
= Ø. Consequently, r
i
⊆ p
i
and
r
i
⊆ q
i
for every i. Then, a non-empty C-n-tuple R = [r
1
r
2
. . . r
n
] exists for which
R ⊆ P and R ⊆ Q that proves impossibility of P ⊆ Q is.
2
Theorem 12. P ⊆ Q is true for a C-n-tuple P and a D-system Q if and only if
P ⊆ Q
j
is true for every D-n-tuple Q
j
belonging to Q.
Proof. A D-system is an intersection of sets comprising all elementary n-tuples from
D-n-tuples contained in the D-system, then, if P is included in every D-n-tuple, it
is included in their intersection i.e. in the D-system.
2
We have already mentioned that NTA allows performing operations of algebra
of sets on homotypic (having the same relation diagram) NTA objects only. In order
to perform these on multiplace relations defined on different diagrams, we need to
transform them into ones of the same diagram. For this, NTA has 5 more operations
on attributes, namely:
1. renaming of attributes;
2. transposition of attributes and corresponding columns in NTA objects;
3. inversion of NTA objects (for binary relations);
4. addition of a dummy attribute (+Attr);
5. elimination of an attribute (-Attr).
Below we introduce these operations and some derivative ones used in logical infer-
ence.
3.2 Operations with Attributes, Join and Composition Operations,
Generalized Operations
Renaming of attributes is only possible for attributes of the same sort. This
operation is used when it is necessary to substitute variables, particularly, in
algorithms for calculating transitive closure of a graph.
Transposition of attributes is an operation that swaps columns in an NTA ob-
ject’s matrix and respectively changes the order of attributes in the relation
diagram.
This operation does not change the content of the relation. The operation is
used for transforming NTA objects whose attributes are the same, but come in
different order to a form that allows performing algebra of sets’ operations on
them.