Algebraic approach to logical inference implementation
Yüklə 404,26 Kb. Pdf görüntüsü
|
1298 B. Kulik, A. Fridman, A. Zuenko redundancy due to multiple copying the same data to memory. Let us consider as an example a relation which reflects the fact that a professor Smith teaches subjects Mathematics, Logic, and Physics: {(Smith, Mathematics), (Smith, Logic), (Smith, Physics)}. This relation can be compacted as a Cartesian product {Smith} × {Mathematics, Logic, Physics}. Obviously, not every relation can be represented as a single Cartesian product composed of non-elementary sets. For example, the following relation cannot be expressed this way: P =
Smith Mathematics Smith Logic
Smith Physics
Burns Logic
Burns Philosophy
Nevertheless every relation can be represented as a union of certain Cartesian products that are, in a general case, composed of subsets of corresponding attributes. In our example, this union is P = {Smith} × {Mathematics, Logic, Physics} ∪ {Burns} × {Logic, Philosophy}. Transition from elementary n-tuples to ones com- posed of sets rather than elements provides a significant reduction in computational resources used for processing relations (calculating unions, intersections, comple- ments, etc.) and data storing. Theoretical basics of mathematical logic are set forth in formal language of pred- icate calculus [16]; but interpretation of logic uses a system that can be represented as a totality of relations with elements being sequences of symbols. The formulas of mathematical logic can be expressed as sets of satisfiable substitutions, i.e. relations as well. There exist different descriptive languages in artificial intelligence; but, as a rule, we can transform examples introduced in publications for illustrating different me- thods and approaches to structures like N (E 1 , E
2 , . . .) where N is a name of a re- lation or a predicate and E 1 , E 2 , . . . are names of objects belonging to certain totalities of values of properties (attributes) [17]. Operations on such structures completely correspond to those of theory of relations. Apart from this, an initial relation defined on a Cartesian product D = X 1 × X 2 × . . . × X n can be often split into blocks corresponding to relations on some projections of D, which greatly reduces laboriousness of operations on this relation by using its matrix properties. This allows to process every block separately using known features of Cartesian products, for instance, by paralleling the necessary operations. Since blocks reflect relations defined on different diagrams, it is necessary to provide specific algebraic operations to recover the initial relation from the blocks. This article introduces n-tuple algebra that uses Cartesian product of sets rather than sequences of elements (elementary n-tuples) as a basic structure, and imple- ments the general theory of multiplace relations. NTA supports formalization of a wide set of logical problems (abductive and modified conclusions, modelling of Algebraic Approach to Logical Inference Implementation 1299
graphs, semantic networks, expert rules, etc. [13, 19]). Below we will focus on per- forming logical inference by means of NTA. “Compacted” representation of relations allows to apply algebraic approach not only in database management systems, but in knowledge systems as well, as it re- duces computational laboriousness of logical inference in many cases. As for making DBs more intelligent, NTA can be considered an extension of relational algebra to knowledge processing. 3 BASICS OF N-TUPLE ALGEBRA 3.1 Basic Concepts and Structures N -tuple algebra was developed for modeling and analysis of multiplace relations. Unlike relational algebra used for formalization of databases NTA can use all mathe- matical logic’s means for logic modeling and analysis of systems, namely logical inference, corollary trueness’ check, analysis of hypotheses, abductive inference, etc. N -tuple algebra is based on the known properties of Cartesian products of sets which correspond to the fundamental laws of mathematical logic. In NTA, transitional results can be obtained without representation of structures as sets of elementary n-tuples since every NTA operation uses sets of components of attributes or n-tuples of components. Definition 1. N -tuple algebra is an algebraic system whose support is an arbi- trary set of multiplace relations expressed by specific structures, namely elementary n-tuple, C-n-tuple, C-system, D-n-tuple, and D-system, called n-tuple algebra ob- jects. So, apart from the elementary n-tuple, NTA contains four more structures providing a compact expression for sets of elementary n-tuples. Names of NTA objects consist of a name proper, sometimes appended with a string of names of attributes in square brackets; these attributes determine the relation diagram in which the n-tuple is defined. For instance, if an elementary n-tuple T [XY Z] = (a, b, c) is given, then T is the name of the elementary n-tuple (a, b, c), X, Y , Z are names of attributes, and [XY Z] is the relation diagram (i.e. space of attributes), a ∈ X, b ∈ Y and c ∈ Z. A domain is a set of all values of an attribute. Domains of attributes correspond to definitional domains of variables in mathematical logic, and to scales of properties in information systems. Hereafter attributes are denoted by capital Latin letters which may sometimes have indices, and the values of these attributes are denoted by the same lower-case Latin letters. A set of attributes representing the same domain is called a sort. Structures defined on the same relation diagram are called homotypic ones. Any totality of homotypic NTA objects is an algebra of sets. N -tuple algebra is based on the concept of a flexible universe. A flexible universe consists of a certain totality of partial universes that are Cartesian products of domains for a given sequence of attributes. A relation diagram determines a certain partial universe. Yüklə 404,26 Kb. Dostları ilə paylaş:
|