Algebraic approach to logical inference implementation

1312

B. Kulik, A. Fridman, A. Zuenko

and

∀x(Q[XY Z]) =

{g}

{a, c}

Ø

{b}

.

The next section is concerned with logical inference techniques in NTA. These

techniques are applicable to the knowledge and data structures introduced earlier,

as well as to certain different ones (e.g. relational tables in deductive DBs).

4.3 Systems with Measurable Attributes

Many attributes, e.g. duration, length, etc., can be given as systems of open, closed

and semi-open intervals. Modern measure theory is based on this type of data being

described by semi-ring algebra [8], while in NTA algebra of components corresponds

to the laws of algebra of sets. As we found, this incompliance can be eliminated

with the following method that we called interval quantization method (IQM).

Let a closed interval Ω on a numeric axis be the definitional domain of a certain

attribute, and a finite set E = {E

i

} of closed intervals be given for which E

i

⊆ Ω. On

the numeric axis, the margins of the intervals are represented by sets of coordinates

of their initial and end points. By arranging these coordinates in ascending order,

we can split the system of intervals into quanta, i.e. into points and open intervals.

It is clear that in this case the interval Ω is split into a certain composite set that

contains m open intervals and m + 1 isolated points, two of which are endpoints of

the interval Ω. Methodological difficulties caused by the fact that the set consists

of heterogeneous objects (points and intervals) can be solved if we define a point as

a degenerate interval of zero measure.

An example of quantization process for four intervals E

1

, E

2

, E

3

, E

4

is shown in

Figure 4. Intervals E

i

are moved above the numeric axis for visualization purposes.

 

 

 

 

 

E

1

 ⇒ 

E

2

 ⇒ 

E

3

 ⇒ 

E

4

 ⇒ 

Ω  ⇒ 

            P   a    b           c      d      e      f          g     h                Q 

 

Fig. 4. Quantization of an interval system

Here, the interval Ω whose endpoints are P and Q, contains inner points a, b,

. . . , h. Accordingly, each interval E

i

can be represented as a set of quanta; for

example, the closed interval E

3

is a set that contains points and open intervals:

E

3

= {c, d, e, f, (c, d), (d, e), (e, f )}. If we are concerned only with the metric prop-

erties of the objects that we are describing, we can represent the interval E

3

as

a set {(c, d), (d, e), (e, f )} of open non-intersecting intervals. By similar quantiza-

tion for each measurable attribute, we can represent the metric space as an NTA

---

Algebraic Approach to Logical Inference Implementation

1313

object whose components are ordinary sets, the introduced notations for points and

intervals being their elements. Methods of immersion NTA structures into a metric

space are now used for logic-probabilistic analysis of systems [14].

When an interval system (Ω, E) for a certain attribute is transformed into an ele-

mentary interval system (Ω, F ), where E = {E

i

} is a set of the initial intervals, and

F = {F

r

} is a set of quanta, the following relation is true for any E

i

:

E

i

=

k

F

k

,

where F

k

are certain quanta of F . In this case, the measure µ for the initial inter-

val E

i

is calculated by the formula below:

µ(E

i

) =

k

µ(F

k

).

We have proved that in NTA, if each component of a C-n-tuple has a finite measure,

the measure of this C-n-tuple is the product of its components’ measures. For

example, for a C-n-tuple C

1

= [{(a, c), (e, g)} {(i, k), (n, p)}],

µ(C

1

) = (µ((a, c)) + µ((e, g))) × (µ((i, k)) + µ((n, p))).

When calculating the measure of a C-system it is important to remember that the

intersection of its C-n-tuples can be nonempty, and to make applicable corrections

using the relation µ(A ∪ B) = µ(A) + µ(B) − µ(A ∩ B) for arbitrary C-n-tuples A

and B.

Now let us consider an example of IQM implementation. Let the following

logical formula whose satisfiability needs to be checked, be given:

(x > 3) ∧ (x < 4) ∧ (y > 2) ∧ (y < 7) ∧ (z > 5) ∧ (z < 6) ∧ (x > y) ∧ (y > z). (3)

Considering the applicable generalized operations (see Section 3.2) the NTA expres-

sion below corresponds to the analyzed formula:

P [XY Z] ∩

G

MORE [Y Z] ∩

G

MORE [XY ],

where the C-n-tuple P [XY Z] = [{(3, 4)}, {(2, 7)}, {(5, 6)}] corresponds to the ex-

pression (x > 3) ∧ (x < 4) ∧ (y > 2) ∧ (y < 7) ∧ (z > 5) ∧ (z < 6).

Re-

lations MORE [Y Z] and MORE [XY ] correspond to the predicates (x > y) and

(y > z), their generalized intersection corresponding to the relational join operation.

Thus, the satisfiability problem comes down to finding the measure of a C-system

P [XY Z] ∩

G

(MORE [Y Z] ⊕ MORE [XY ]). If this measure is not equal to zero, the

formula (3) is satisfiable, a domain of nonzero volume corresponding to this formula

in property space X × Y × Z. If the opposite is true, the formula is not satisfiable.

Since only the metric aspects are of interest to us, let us express the components

of the C-n-tuple P [XY Z] trough quanta (2, 3), (3, 4), (4, 5), (5, 6), (6, 7):

P [XY Z] = [{(3, 4)}, {(2, 3)}, {(3, 4)}, {(4, 5)}, {(5, 6)}, {(6, 7)}, {(5, 6)}] .

---