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