Algebraic approach to logical inference implementation



Yüklə 404,26 Kb.
Pdf görüntüsü
səhifə1/14
tarix11.12.2017
ölçüsü404,26 Kb.
#15052
  1   2   3   4   5   6   7   8   9   ...   14


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




Yüklə 404,26 Kb.

Dostları ilə paylaş:
  1   2   3   4   5   6   7   8   9   ...   14




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©www.genderi.org 2024
rəhbərliyinə müraciət

    Ana səhifə