Algebraic approach to logical inference implementation

Algebraic Approach to Logical Inference Implementation

1317

5 LOGICAL INFERENCE IN NTA

5.1 Computational Complexity of Algebraic Operations

in Logical Inference

The most popular systems of logical inference in mathematical logic are as follows:

1. Hilbert-style calculi proposed in [7];

2. natural deduction calculus developed by logician G.Gentzen [6];

3. logical inference based on Resolution Principle that became widely known after

the article [2] was published.

Logical inference systems often use two theorems introduced and proved in [1] (they

have numbers 2.1 and 2.2 there). They are reproduced below since they allow to

derive logical corollaries by algebraic methods as well as by inference rules.

Theorem 16. Let formulas F

1

, . . . , F

n

and G be given. Then G is a logical corollary

to F

1

, . . . , F

n

if and only if the formula ((F

1

∧ . . . ∧ F

n

) ⊃ G) is a valid one.

Theorem 17. Let formulas F

1

, . . . , F

n

and G be given. Then G is a logical corollary

to F

1

, . . . , F

n

if and only if the formula (F

1

∧ . . . ∧ F

n

∧ ¬G) is inconsistent.

Logical inference in NTA is based on the Theorems 16 and 17 which can be

expressed in NTA terms as follows, since NTA is isomorphic to algebra of sets.

Method 1. Let NTA objects F

1

, . . . , F

n

and G be given. Then G is a logical corol-

lary to F

1

, . . . , F

n

if and only if (F

1

∩

G

. . . ∩

G

F

n

) = Ø and (F

1

∩

G

. . . ∩

G

F

n

) ⊆

G

G.

Method 2. Let NTA objects F

1

, . . . , F

n

and G be given. Then G is a logical corol-

lary to F

1

, . . . , F

n

if and only if (F

1

∩

G

. . . ∩

G

F

n

) = Ø and F

1

∩

G

. . . ∩

G

F

n

∩

G

G = Ø.

NTA structures can be polynomially reduced to logical ones; hence computa-

tional complexity of algorithms on NTA structures fully corresponds to computa-

tional complexity of algorithms solving problems on logical structures. A significant

number of such problems arising during logical analysis by means of deduction proce-

dures, for instance, the satisfiability problem for a conjunctive normal form (CNF),

are NP-complete problems with regard to their computational complexity (i.e. they

require algorithms of exponential complexity). However, there are many special

cases that are solvable in polynomial time only. As far as the problem of CNF sa-

tisfiability is concerned, they are CNFs with at most two literals in every clause or

CNFs with Horn clauses only. Identifying cases where we can recognize satisfiability

in polynomial time is of great importance for applied research since it reduces the

time required for implementation of algorithms.

The special cases mentioned above can be expressed in NTA structures as well;

however, NTA has its own means for reducing laboriousness and sometimes com-

putational complexity of algorithms. These will be briefly introduced in the next

section.

---

1318

B. Kulik, A. Fridman, A. Zuenko

In NTA, deducibility checks are not based on inference rules; rather, they check

enclosure of certain NTA objects into each other or emptiness of intersection of

certain relations including NTA objects related to alternative classes. Consequently,

in order to implement logical inference in NTA, we need to solve two key problems,

namely enclosure check for two NTA objects and transformation of an NTA object

into one of alternative classes. In general case, complexity of these problems is

greater than polynomial, coinciding with complexity of similar problems expressed

in terms of mathematical logic.

Enclosure check for two NTA objects (A ⊆

G

B) corresponds to validity check

for implication A ⊃ B in logic. Transformation of an NTA object into object of

an alternative class is equivalent to transformation a CNF into a DNF or vice versa.

Table 2 contains different combinations of NTA objects; those marked with

a symbol “+” are the ones for which the algorithms for applicable operations are

polynomial, given that all attribute domains are sets rather than multiplace rela-

tions.

Operation

C-n-tuple

C-system

D-n-tuple

D-system

Member check for an elementary

n-tuple

+

+

+

+

Check of enclosure

of a C-n-tuple into

+

+

+

Check of enclosure

of a C-system into

+

+

+

Check of enclosure

of a D-n-tuple into

+

+

+

Check of enclosure

of a D-system into

Table 2. Complexity of NTA operations

Table 2 shows that computational complexity of operations depends on the

structure class of the NTA objects used in the operations. For instance, enclosure

check of a C-n-tuple into a C-system has exponential computational complexity

while enclosure check of a C-n-tuple or even a C-system into a D-system is polyno-

mial.

Transformation of an NTA object into one of an alternative class when the initial

object is a D-system or a C-system is computationally harder than an NP-complete

problem; it belongs to the class of #P-complete problems, i.e. enumeration ones.

Maximum complexity estimate for transformation of an NTA object into one of

an alternative class is easy to calculate. Suppose we have a D-system of dimension

M × N , where M is the number of rows and N is the number of columns of this

structure. Then every D-n-tuple can be transformed into a C-system with no more

than N rows, and solving this problem will take M − 1 sequential calculations

of intersections. If we consider the complexity of intersection for two C-n-tuples

a constant B, then the maximum computational complexity of this operation is

---