Algebraic approach to logical inference implementation

1306

B. Kulik, A. Fridman, A. Zuenko

For example, a C-system P [XY Z] =

{a, b, d}

{f, h}

{b}

{b, c}

∗

{a, c}

transforms

into a C-system P [Y XZ] =

{f, h}

{a, b, d}

{b}

∗

{b, c}

{a, c}

due to transposition of

attributes.

Inversion of NTA objects. In case of binary relations, swapping columns with-

out swapping attributes allows to get the relation inverse to the initial one. For

example, swapping columns of relation G[XY ] =

{a}

{a, b}

{b, c}

{a, c}

turns it into

the inverse relation G

−1

[XY ] =

{a, b}

{a}

{a, c}

{b, c}

. In this case, inversion of an

NTA object turns all the elementary n-tuples (s, t) of the initial relation into

the inverse ones (t, s). If an elementary n-tuple contains identical elements (e.g.

(b, b)), it does not change during the inversion.

Addition of a dummy attribute (+Attr) is done when the added attribute is

missing in the relation diagram of an NTA object (NTA objects with duplicate

attributes are also possible, but are not considered here). This operation simul-

taneously adds the name of a new attribute into the relation diagram and adds

a new column with dummy components into the corresponding place; dummy

components “*” are added into C-n-tuples and C-systems, and dummy compo-

nents “Ø” are added into D-n-tuples and D-systems.

Elimination of an attribute (-Attr) is done in the following way: a column is

removed from an NTA object, and the corresponding attribute is removed from

the relation diagram.

Semantics of the +Attr and -Attr operations will be explained below in Sec-

tion 4. These operations are used, in particular, for calculating join or composition

of two different-type relations defined by NTA objects. In general case, join and

composition operations of relations can be performed for any pairs of NTA objects.

Let two structures R

1

[V ] and R

2

[W ] be given, where V and W are sets of at-

tributes and V = W . These sets can be separated into nonintersecting subsets

with the following transformations:

X = W \ V ;

Y = W ∩ V ;

Z = V \ W .

Then we get V = Y ∪ Z and W = X ∪ Y . Taking this into account, the given

relations can be expressed as follows: R

1

[Y Z ] and R

2

[X Y ].

Join operation R

1

[Y Z ] ⊕ R

2

[X Y ] for relations is usually done by pairwise

comparison of all elementary n-tuples from different relations. If comparing these

n-tuples shows that they coincide in the projection [Y ], an n-tuple with relation

diagram [X Y Z ] is formed from the two n-tuples, the new n-tuple becoming one of

the elements of the relational join. For example, there are two elementary n-tuples

---

Algebraic Approach to Logical Inference Implementation

1307

T

1

∈ R

1

and T

2

∈ R

2

, where

T

1

[Y Z ] = (c, d, e, f, g);

T

2

[X Y ] = (a, b, c, d, e),

and

T

2

[X ] = (a, b);

T

1

[Z ] = (f, g);

T

1

[Y ] = T

2

[Y ] = (c, d, e).

Then the result of join of these n-tuples is the elementary n-tuple T

3

[X Y Z ] =

(a, b, c, d, e, f, g).

In NTA relational join operation is substantially simplified and can be calculated

without pairwise comparison of all elementary n-tuples using the following formula:

R

1

[Y Z ] ⊕ R

2

[X Y ] = +X (R

1

) ∩ +Z (R

2

).

(1)

Operation of composition R

1

[Y Z ] ◦ R

2

[X Y ] of relations is performed after

calculating their join. For this, we need to eliminate the projection [Y ] from all

elementary n-tuples belonging to the join. For example, an elementary n-tuple

T

4

[X Z ] = (a, b, f, g) is the composition of the two n-tuples T

1

and T

2

considered

above.

In NTA, the composition of relations is calculated according to the formula:

R

1

[Y Z ] ◦ R

2

[X Y ] = −Y (+X (R

1

) ∩ +Z (R

2

)) = −Y (R

1

⊕ R

2

),

(2)

if (R

1

⊕ R

2

) is a C-n-tuple or a C-system.

Here is an example. Let the following NTA objects be given in space S :

R

1

[Y Z] =

{f }

{a, b}

{g, h}

{a, c}

;

R

2

[XY ] =

{a}

{g, h}

{b, c}

{f }

Let us calculate join of these relations by formula (1):

R

1

⊕ R

2

=

∗

{f }

{a, b}

∗

{g, h}

{a, c}

∩

{a}

{g, h}

∗

{b, c}

{f }

∗

=

{b, c}

{f }

{a, b}

{a}

{g, h}

{a, c}

Then we calculate their composition in the relation diagram [XZ] by formula (2):

R

1

◦ R

2

=

{b, c}

{a, b}

{a}

{a, c}

Let us call relations and operations of algebra of sets with preliminary addition

of missing attributes to NTA objects generalized operations and relations and denote

them as follows: ∩

G

, ∪

G

, \

G

, ⊆

G

, =

G

, etc. The first two operations completely corre-

spond to logical operations ∧ and ∨. NTA relation ⊆

G

corresponds to deducibility re-

lation in predicate calculus. Relation =

G

means that two structures are equal if they

have been transformed to the same relation diagram by adding certain attributes.

This technique offers a fundamentally new approach to constructing logical inference

and deducibility checks introduced below; but first let us describe some examples of

expressing conventional mathematical structures by means of NTA objects.

---