Algebraic approach to logical inference implementation

Algebraic Approach to Logical Inference Implementation

1321

=

t

11

Ø

Ø

Ø

t

21

Ø

Ø

Ø

∪

t

11

Ø

Ø

Ø

Ø

t

22

t

23

t

24

∪

Ø

t

12

t

13

t

14

t

21

Ø

Ø

Ø

∪

Ø

t

12

t

13

t

14

Ø

t

22

t

23

t

24

.

If at least one of the final D-systems is nonempty, then the initial D-system is

nonempty as well.

While being inapplicable to solving practical problems, this theorem provides

the grounds for some corollaries of practical importance. Let us introduce some new

terms that we use for considering these corollaries below.

A conflicting pair of a D-system is a nonintersecting pair of nonempty compo-

nents in the same attribute.

A conflict attribute of a D-system is an attribute in which the intersection of

all nonempty components is empty; if this intersection is nonempty, this attribute

is a non-conflict attribute.

A non-conflict block (BlN C) of a D-system is its vertical block that contains

only non-conflict attributes. Respectively, a vertical block that contains conflict

attributes is a conflict block (BlC). From the definitions, it is clear that a non-

conflict block can contain empty components, while the intersection of all nonempty

components in each attribute of this block is nonempty.

A monotonous attribute of a D-system is a non-conflict attribute that contains

no empty components.

A monotonous block (BlM ) of a D-system is a non-conflict block that contains

no D-n-tuples all of whose components are empty.

For a D-system Q[X] containing a monotonous block BlM (Q), let us construct

a C-n-tuple C

int

[X], each of whose components that corresponds to an attribute from

the relation diagram of the monotonous block equals the intersection of all nonempty

components of the block belonging to this attribute, the rest of the components of

this C-n-tuple being dummy ones, i.e. equal to “*”.

Theorem 19. If a D-system Q contains a monotonous block, it is nonempty, and

C

int

⊆ Q.

Proof. It is clear that under the hypothesis of the theorem C

int

= Ø, and that

for each D-n-tuple Q

i

in the system Q C

int

⊆ Q

i

is true, since each monotonous

block always has a nonempty component which includes the corresponding C

int

component. This implies that C

int

⊆ Q.

2

Let us consider the following D-system as an example:

T =







{A, B}

{f, g}

{a, c, d}

Ø

{e}

{b, c}

{A}

{g, h}

Ø







It is easy to see that the first and the third attribute in the T are non-conflict

and that they make up a monotonous block. Respectively, C

int

= [{A} ∗ {c}].

---

1322

B. Kulik, A. Fridman, A. Zuenko

According to Theorem 19, T is nonempty and C

int

⊆ T , which is also verified

through Theorems 11 and 12.

Let us now consider D-systems with non-conflict blocks that contain D-n-tuples

all of whose components are empty. Let a D-system Q contain a non-conflict block

T

1

= BlN C(Q). Then after the applicable swaps of rows and columns, the D-

system Q can be represented as a block matrix T =

T

11

T

12

T

21

T

22

, where T

11

is

a submatrix of the matrix Q whose D-n-tuples have no empty components and T

12

is a submatrix of the matrix Q whose D-n-tuples contain only empty components.

Theorem 20. If a D-system Q has a non-conflict block, then Q is nonempty, if

and only if after dividing Q into a block matrix T the D-system represented by the

block T

22

is non-empty.

Proof. Necessity. From Theorem 18, it is clear that one of the D-systems that

is the result of intersection of the blocks on the main diagonal can be represented

as a block matrix

T

11

Ø

Ø

T

22

. Since the D-system T

11

is monotonous, there is

a nonempty C-n-tuple C

11

, where C

11

⊆ T

11

. If T

22

is nonempty, in the projection

corresponding to T

22

there exists such a C-n-tuple C

22

that C

22

⊆ T

22

. Intersection

of C

11

and C

22

forms a non-empty C-n-tuple C

0

, since all non-dummy components of

the n-tuple C

11

correspond to the dummy components of the C-n-tuple C

22

and vice

versa. From Theorems 11 and 12, C

0

⊆ T . Sufficiency. Suppose that T

22

is empty,

and Q is nonempty. Then T

22

is equivalent to a D-system of the same dimension,

all of whose components are empty sets. If we substitute this D-system for T

22

, the

lower part of the block matrix will contain D-n-tuples all of whose components are

empty; therefore, the corresponding D-system is also empty.

2

Let us analyze the following D-system as an example:

Q =











{A, B}

{e, f }

{a, b}

Ø

Ø

{g, h}

Ø

{e}

{A}

{e}

{b}

{f, g}

Ø

{e, h}

Ø

{g, h}











.

Its first and third columns are non-conflict. Therefore, after the applicable swap

of rows and columns, it can be converted to an equivalent block matrix

Q

1

=











{A, B}

{a, b}

{e, f }

Ø

{A}

{b}

{e}

{f, g}

Ø

Ø

{g, h}

{e}

Ø

Ø

{e, h}

{g, h}











.

To check nonemptiness of this D-system it is sufficient to check nonemptiness

of the D-system T

22

=

{g, h}

{e}

{e, h}

{g, h}

. The first column of this D-system is

---