Algebraic approach to logical inference implementation

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.

---