1302
B. Kulik, A. Fridman, A. Zuenko
[{b, c} ∗ {a, c}] ∩ [{b, d} {f, h} {a, c}] = [{b} {f, h} {a, c}];
[{b, c} ∗ {a, c}] ∩ [{b, c} {g} {b}] = Ø.
Then we form a C-system from non-empty C-n-tuples:
R
1
∩ R
2
=
{a, d}
{f, h}
{b}
{b}
{f, h}
{a, c}
.
Theorem 5. Union of two homotypic C-systems equals to a C-system that contains
all C-n-tuples of the operands.
After calculating the union of the C-systems, the total number of n-tuples in
the derived C-system can be reduced in some cases by using conditions 1. or 2. of
Theorem 3.
In order to introduce the algorithms for calculating complements of NTA objects,
we need one more definition.
Definition 5. A complement (P
j
) of any component P
j
of an NTA object is defined
as a complement to the domain of the attribute corresponding to this component.
For example, if a C-n-tuple R[XY Z] = [ABC] is given, then A = X \ A,
B = Y \ B and C = Z \ C.
Theorem 6. For an arbitrary C-n-tuple P = [P
1
P
2
. . . P
n
]
P =
P
1
∗
. . .
∗
∗
P
2
. . .
∗
. . .
. . .
. . .
. . .
∗
∗
. . .
P
N
In the above C-system P whose dimension is n × n, all the components except
the diagonal ones are dummy components. We shall call such C-systems diagonal
C-systems.
Here is an example. Let a C-n-tuple T = [{b, d} {f, h} {a, b}] be given in the
space S = X × Y × Z where X = {a, b, c, d}, Y = {f, g, h}, Z = {a, b, c}. Then
T =
X \ {b, d}
∗
∗
∗
Y \ {f, h}
∗
∗
∗
Z \ {a, b}
=
{a, c}
∗
∗
∗
{g}
∗
∗
∗
{c}
We can denote diagonal C-systems as one n-tuple of sets, using reversed square
brackets for expressing this. Then we get the following equality: T = ]{a, c} {g} {c}[.
Such a “reduced” expression for a diagonal C-system makes up a new NTA
structure called a D-n-tuple.
Algebraic Approach to Logical Inference Implementation
1303
Definition 6. A D-n-tuple is an n-tuple of components enclosed in reversed square
brackets which equals a diagonal C-system whose diagonal components equal the
corresponding components of the D-n-tuple.
The complement of a C-n-tuple can be directly recorded as a D-n-tuple. For
example, if T
1
= [{b, d} ∗ {a, b}], then T
1
= ]{a, c} Ø {c}[. In D-n-tuples the constant
“Ø” is a dummy component.
This structure not only allows to compactly denote diagonal C-systems, but can
be also used in some operations and retrieval queries. The terms C-n-tuple and
D-n-tuple were chosen due to the following reason: if we represent the components
of these n-tuples as predicates, C-n-tuple corresponds to conjunction of these predi-
cates, and D-n-tuple corresponds to disjunction of these predicates. D-n-tuples are
used to form one more NTA structure, namely a D-system.
Definition 7. A D-system is a structure that consists of a set of homotypic
D-n-tuples and equals the intersection of sets of elementary n-tuples that these
D-n-tuples contain.
Expression for a D-system is analogous to that of a C-system except that in this
case reversed square brackets are used instead of the regular ones.
Theorem 7. The complement of a C-system is a D-system of the same dimension,
in which each component is equal to the complement of the corresponding component
in the initial C-system.
Proof. Let a C-system P that contains a set {P
1
, P
2
, . . . , P
n
} of C-n-tuples be given.
This means that P = P
1
∪ P
2
∪ . . . ∪ P
n
. Calculating its complement according to de
Morgan’s law, we get the following result: P = P
1
∩ P
2
∩ . . . ∩ P
n
. Then the validity
of this theorem follows from the Theorem 6 and Definitions 6 and 7.
2
For example, the complement of a C-system
F [XY Z] =
{a, b, d}
{f, h}
{b}
{b, c}
∗
{a, c}
given in a space S can be calculated as a D-system
F =
X \ {a, b, d}
Y \ {f, h}
Z \ {b}
X \ {b, c}
Y \ ∗
Z \ {a, c}
=
{c}
{g}
{a, c}
{a, d}
Ø
{b}
.
It is easy to see that relations between C-objects (C-n-tuples and C-systems)
and D-objects (D-n-tuples and D-systems) are in accordance with de Morgan’s laws
of duality. Due to this fact, they are called alternative classes. Calculation of the
complement for an NTA object always has polynomial computational complexity.
Operations of union and intersection have polynomial complexity for NTA objects
belonging to the same class, but a transformation into an alternative class is also
necessary for objects of different classes.