Algebraic approach to logical inference implementation

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.

---