Algebraic approach to logical inference implementation

1300

B. Kulik, A. Fridman, A. Zuenko

In a space of properties S with attributes X

i

(i.e. S = X

1

× X

2

× . . . × X

n

),

the flexible universe will be comprised of different projections i.e. subspaces that use

a part of attributes from S . Every such subspace corresponds to a partial universe.

Definition 2. An elementary n-tuple is a sequence of elements each belonging to

the domain of the corresponding attribute in the relation diagram. An example of

an elementary n-tuple T [XY Z] is given above.

Definition 3. A C-n-tuple is an n-tuple of sets (components) defined in a certain

relation diagram; each of these sets is a subset of the domain of the corresponding

attribute.

A C-n-tuple is a set of elementary n-tuples; this set can be enumerated by

calculating the Cartesian product of the C-n-tuple’s components. C-n-tuples are

denoted with square brackets. For example, R[XY Z] = [ABC] means that A ⊆ X,

B ⊆ Y , C ⊆ Z and R[XY Z] = A × B × C.

Definition 4. A C-system is a set of homotypic C-n-tuples that are denoted as

a matrix in square brackets. The C-n-tuples that such a matrix contains are rows

of this matrix.

A C-system is a set of elementary n-tuples. This set equals to the union of sets

of elementary n-tuples that the corresponding C-n-tuples contain. For example,

a C-system Q[XY Z] =

A

1

B

1

C

1

A

2

B

2

C

2

can be represented as a set of elementary

n-tuples calculated by formula Q[XY Z] = (A

1

× B

1

× C

1

) ∪ (A

2

× B

2

× C

2

).

In order to combine relations defined on different projections within a single

algebraic system isomorphic to algebra of sets, NTA introduces dummy attributes

formed by using dummy components. There are two types of these components.

One of them called a complete component is used in C-n-tuples and is denoted

by “*”.

A dummy component “*” added in the i

th

place in a C-n-tuple or in

a C-system equals to the set corresponding to the whole range of values of the

attribute X

i

. In other words, the domain of this attribute is the value of the dummy

component. For example, if the domain of attribute X is given (here it equals to

the set {a, b, c, d}), the C-n-tuple Q[Y Z] = [{f, g} {a, c}] can be expressed in the

relation diagram [XY Z] as a C-n-tuple [∗{f, g} {a, c}]. Since the dummy component

of Q corresponds to an attribute with the domain X, the equality [∗{f, g} {a, c}] =

[{a, b, c, d} {f, g} {a, c}] is true. Another dummy component (Ø) called an empty

set is used in D-n-tuples.

A C-n-tuple that has at least one empty component is empty. In NTA, if we deal

with models of propositional or predicate calculuses, this statement is accepted as

an axiom which has an interpretation based on the properties of Cartesian products.

Below, we will show that usage of dummy components and attributes in NTA

allows to transform relations with different relation diagrams into ones of the same

type, and then to apply operations of theory of sets to these transformed relations.

---

Algebraic Approach to Logical Inference Implementation

1301

The proposed technique of defining dummy attributes differs from the known tech-

niques essentially due to the fact that new data are inputted into multiplace relations

as sets rather than elementwise, which significantly reduces both computational la-

boriousness and memory capacity for representation of the structures.

Operations (intersection, union, complement) and checks of relations of inclusion

or equality for these NTA objects are based on Theorems 1–6. Here they are given

without proof because their formulating in terms of NTA corresponds to the known

properties of Cartesian products. Let two homotypic C-n-tuples P = [P

1

P

2

. . . P

n

]

and Q = [Q

1

Q

2

. . . Q

n

] be given.

Theorem 1. P ∩ Q = [P

1

∩ Q

1

P

2

∩ Q

2

. . . P

n

∩ Q

n

].

Example 1. [{b, d} {f, h} {a, b}] ∩ [∗{f, g}{a, c}] = [{b, d} {f } {a}];

[{b, d} {f, h}{a, b}] ∩ [∗{g} {a, c}] = [{b, d} Ø {a}] = Ø.

Theorem 2. P ⊆ Q, if and only if P

i

⊆ Q

i

for all i = 1, 2, . . . , n.

Theorem 3. P ∪ Q ⊆ [P

1

∪ Q

1

P

2

∪ Q

2

. . . P

n

∪ Q

n

], equality being possible only in

two cases:

1. P ⊆ Q or Q ⊆ P ;

2. P

i

= Q

i

for all corresponding pairs of components except one pair.

Note that in NTA, according to Definition 4, equality P ∪Q =

P

1

P

2

. . .

P

n

Q

1

Q

2

. . .

Q

n

is true for all cases.

Theorem 4. Intersection of two homotypic C-systems equals to a C-system that

contains all non-empty intersections of each C-n-tuple of the first C-system with

each C-n-tuple of the second C-system.

Example 2. Let the following two C-systems be given in space S:

R

1

[XY Z] =

{a, b, d}

{f, h}

{b}

{b, c}

∗

{a, c}

,

R

2

[XY Z] =







{a, d}

∗

{b, c}

{b, d}

{f, h}

{a, c}

{b, c}

{g}

{b}







.

We need to calculate their intersection. First we calculate intersection of all the

pairs of C-n-tuples that the two different C-systems contain:

[{a, b, d} {f, h} {b}] ∩ [{a, d} ∗ {b, c}] = [{a, d} {f, h} {b}];

[{a, b, d} {f, h} {b}] ∩ [{b, d} {f, h} {a, c}] = Ø;

[{a, b, d} {f, h} {b}] ∩ [{b, c} {g} {b}] = Ø;

[{b, c} ∗ {a, c}] ∩ [{a, d} ∗ {b, c}] = Ø;

---