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