Computing and Informatics, Vol. 31, 2012, 1295–1328
ALGEBRAIC APPROACH TO LOGICAL INFERENCE
IMPLEMENTATION
Boris Kulik
Institute of Problems in Machine Science
Russian Academy of Sciences (RAS)
61 Bolshoi pr., 199178 St. Petersburg, Russia
e-mail: ba-kulik@yandex.ru
Alexander Fridman, Alexander Zuenko
Institute for Informatics and Mathematical Modelling
Kola Science Centre of RAS
24A Fersman str., 184209 Apatity, Russia
e-mail: {fridman, zuenko}@iimm.kolasc.net.ru
Communicated by Ivan Plander
Abstract. The paper examines the usage potential of n-tuple algebra (NTA) de-
veloped by the authors as a theoretical generalization of structures and methods
applied in intelligence systems. NTA supports formalization of a wide set of lo-
gical problems (abductive and modified conclusions, modelling of graphs, semantic
networks, expert rules, etc.). This article mostly describes implementation of logi-
cal inference by means of NTA. Logical inference procedures in NTA can include,
besides the known logical calculus methods, new algebraic methods for checking
correctness of a consequence or for finding corollaries to a given axiom system.
Inference methods consider (above feasibility of certain substitutions) inner struc-
ture of knowledge to be processed, thus providing faster solving of standard logical
analysis tasks. Matrix properties of NTA objects allow to decrease laboriousness of
intellectual procedures as well as to efficiently parallel logical inference algorithms.
In NTA, we discovered new structural and statistical classes of conjunctive normal
forms whose satisfiability can be detected for polynomial time. Consequently, many
algorithms whose complexity evaluation is theoretically high, e.g. exponential, can
in practice be solved in polynomial time, on the average. As for making databases
more intelligent, NTA can be considered an extension of relational algebra to know-
ledge processing. In the authors’ opinion, NTA can become a methodological basis
for creating knowledge processing languages.
1296
B. Kulik, A. Fridman, A. Zuenko
Keywords: Data processing, knowledge representation, intelligence system, multi-
place relation, general theory of relations, n-tuple algebra, flexible universe, logical
inference, knowledge processing language, parallel computing
1 INTRODUCTION
Developers of modern intelligence systems face certain challenges resulting from fun-
damentally different approaches used in constructing databases (DB) and knowledge
bases (KB). KB design is based on a mathematical system that is named by a number
of terms: formal approach, axiomatic method, symbolic logic, theory of formal sys-
tems (TFS). Development of TFS began in the works of B. Russell, L. Wittgenstein,
D. Hilbert, G. Peano and others at the beginning of 20
th
century when paradoxes
of set theory were discovered and the algebra of sets and Boolean algebra were no
longer the most important approaches to foundations of logic.
In TFS, inference rules are defined in the way that allows to interpret new symbol
constructions as corollaries to or new theorems from the symbol constructions or
statements that are axioms or theorems in the given formal system.
Additionally, in TFS we need to reduce many logical analysis tasks to satisfia-
bility checks for a certain logical formula, this check being able to return only two
possible answers (“yes” or “no”). Despite a substantial number of positive results
that have been obtained in this field, such a reduction is not sufficiently simple yet.
Moreover, the reduction is unrealizable in cases when we need not only to receive
a “yes/no” answer but also to estimate the value of some parameters in the formal
system or to assess the structure and/or number of objects that satisfy the given
conditions. That is why artificial intelligence languages based on declarative ap-
proach grew much more complicated due to the necessity of furnishing them with
different non-declarative procedures and functions.
Today, mathematical logic is based on strict rules of pure calculus. This calculus
has been proven to be isomorphic to some algebraic systems; for instance, propo-
sitional calculus is isomorphic to Boolean algebra. However, algebraic (procedural)
approach is fairly seldom used by itself in theoretical research on classical logic to-
day. On the other hand, algebraic methods are widely used in applied research,
particularly in software implementation of mentioned non-declarative functions in
intelligence systems.
Algebraic techniques, e.g. those of relational algebra are most commonly used in
constructing data processing systems. Note that the term “data processing lan-
guages” (DPL) is very popular in data management while intelligence systems
mostly deal with knowledge representation languages (KRL). This shows the de-
clarative origin of KRLs and the procedural basis of DPLs. In other words, DPLs
regulate the way actions are performed on data, whereas KRLs specify what is to
be done with the knowledge without determining how to do this. Thus, algebraic
approach seems to be a rational supplement to traditional formal methods in logic
Algebraic Approach to Logical Inference Implementation
1297
for improving logical analysis techniques and creating knowledge processing lan-
guages (KPL) that allow to flexibly program and compare algorithms for intelligent
procedures.
Methodical differences in constructing DBs and KBs make using them within
a single integrated software system complicated. This problem was first posed at the
IJCAI ’95 (The International Joint Conference on Artificial Intelligence in Montreal,
Canada on August 19 through 25, 1995) and now it becomes even more topical as
making database management systems (DBMS) more intelligent by developing DB
semantic interfaces, deductive DBs, etc., becomes more important. This is why
developing a unified methodology of data and knowledge processing is required.
In our opinion, this can be achieved through algebraic methods if the concept of
multiplace relation is used as a base concept. This idea allows to represent many
data and knowledge systems not only as an artificial language, but also as a totality
of relations with different diagrams that are subject to certain operations similar to
those of algebra of sets.
Below we briefly describe conventional mathematical sections dealing with rela-
tions, and propose a mathematical system named n-tuple algebra (NTA) [9, 11] and
developed for solving the set of problems described above [13, 21]. We believe that
NTA can be used as a base for creating knowledge processing languages.
2 RELATIONS IN MATHEMATICS
A general theory of relations has not been developed yet. The term “theory of rela-
tions” is usually used either for theory of binary relations or for theory of multiplace
relations based on relational algebra. In any case, these theories accept the classical
mathematical definition of a relation through Cartesian product. If D is a Cartesian
product of n different or equal sets, then an n-place relation R is a certain subset of
elementary n-tuples contained in D.
Such a definition of a multiplace relation allows treating relations as ordinary
sets if they are defined on the same Cartesian product D. If so, the complement of
a multiplace relation R is the set difference D \ R. For example, if
D = {1, 2, 3, 4, 5} × {1, 2, 3, 4, 5},
and R is a relation “less than” in the set of numbers {1, 2, 3, 4, 5}, then after elimi-
nating all elementary n-tuples belonging to R, from D we get a set of elementary
n-tuples corresponding to the relation “more than or equal to”.
However, this conformity between algebra of multiplace relations and algebra of
sets is no longer valid in totalities of relations defined on various Cartesian products
since it is impossible to determine operations of union and intersection for these.
Besides, algebra of multiplace relations includes operations of composition and join
that have no equivalent operations in algebra of sets.
According to the classical definition, a multiplace relation is a set of elemen-
tary n-tuples; however, this definition is not always practical since it results in
Dostları ilə paylaş: |