Algebraic approach to logical inference implementation
Yüklə 404,26 Kb. Pdf görüntüsü
|
Algebraic Approach to Logical Inference Implementation 1323
monotonous, therefore, it is nonempty and contains the C-n-tuple C 22 = [{h}∗]. The monotonous block T 11 contains a C-n-tuple [{A}{b}]. After reducing these C-n-tuples to the same relation diagram, their intersection equals the C-n-tuple C 0 = [{A}{b}{h}∗]. After swapping the attributes in accordance with the relation diagram of the initial D-system Q, this C-n-tuple is transformed into the C-n-tuple [{A}{h}{b}∗], which is the substitution for the D-system Q. With Theorems 11 and 12, we can verify that this substitution is correct. This example shows that, in the same D-system, relations stated in Theorems 19 and 20 can be used more than once, and that in some cases solving a problem in polynomial time is possible. Obviously, for an arbitrary D-system, the algorithm for finding non-conflict and monotonous blocks is polynomially dependent on the dimensions of this system. Furthermore, if a D-system has any monotonous blocks, its nonemptiness is checked through an algorithm that is polynomially dependent on the matrix dimensions of this D-system; and if a D-system has any non-conflict blocks, another D-system of smaller dimensions can be used to check nonemptiness of the initial D-system. In algorithms for solving CNF satisfiability problems and enclosure checks for NTA objects, such as for C-n-tuples in C-systems, matrix properties of NTA objects are widely used. At present, satisfiability recognition algorithms are developed to the greatest extent in propositional calculus. It has been proven [10] that, if a CNF is represented as a D-system that contains only three equally distributed (with the probability of 1/3) symbols: 1, 0 and Ø, this CNF is solvable, on the average, in polynomial time, this time being less than or equal to a third degree polynomial to the number of conjuncts. 5.3 New Features of Logical Inference In NTA Previous sections were concerned with using NTA structures for implementing known methods of logical inference. New implementations of logical procedures based on the suggested algebraic approach are presented below. Suppose that we have a system of axioms A 1 , . . . , A n represented as NTA objects. Let us describe methods for solving the following two problems through NTA. 1. Problem of correctness check for a consequence. If we have an alleged conse- quence B, the proof procedure is a correctness check for the following generalized inclusion: (A 1
G . . . ∩
G A n ) ⊆ G B. (4) This relation allows correctness checks not only for the inference rules of classical logic, but also for rules specific to a certain knowledge system. 2. Problem of derivation of arbitrary consequences. In order to solve this problem, we first calculate an NTA object A = A 1 ∩ G . . . ∩
G A n , after which we choose the B
i for which A ⊆ G B
is true. The authors have developed algorithms that allow to calculate possible corollaries for a known A using the relation (4). 1324 B. Kulik, A. Fridman, A. Zuenko Below we will consider A as a C-system. If it is not true for a given A, it can be transformed into a system using algorithms for transforming D-n-tuples or D-systems into C-systems. The following premises are commonly used for searching for possible conse- quences: 1. consequence Bi should preferably use only a small number of variables from the axioms A 1 , . . . , A n ; 2. the variables used are often determined based on semantic analysis of the given reasoning system. Let us consider formal methods (i.e. without taking semantic restrictions into account) for solving Problem 2. Decreasing the number of variables in B i is possible through eliminating some attributes from A. Obviously, after this the transformation relation A ⊆ G B i is true. Eliminating attributes from a C-system yields a projection whose properties determine the subsequent operations for consequence derivation. Such projection can be complete, i.e. can contain all elementary n-tuples for their relation diagram, or incomplete, if the opposite is true. If a projection is complete, it means that the consequence is a tautology and thus holds no interest for us; this is why we will consider incomplete projections only. Let us form a group of incomplete projections for the A. In this case, all the variety of ways to form possible consequences B i can be expressed by the following three rules: 1. keep one of the incomplete projections as a B i ;
i , provided that it includes at least one incomplete projection; 3. for the NTA object chosen according to the rules above, construct, by adding elementary n-tuples or C-n-tuples, an incomplete NTA object that covers it. As an example, let us prove correctness of one of the inference rules in natural calculus called the dilemma rule: A → C, B → C, A ∨ B C .
above it. The upper formulas can be considered axioms, and the lower ones can be considered corollaries to these axioms. By transforming the conjunction of the formulas above the solidus into a D-system within the [ABC] relation diagram, we get U p[ABC] =
{0} Ø {1} Ø {0}
{1} {1}
{1} Ø . The lower part of the rule can be expressed as a C-n-tuple Dn[C] = [{1}]. In order to prove by NTA methods that the given Algebraic Approach to Logical Inference Implementation 1325
rule is true, we need to verify the relation U p[ABC] ⊆ G Dn[C]. In this case, when the Up is a D-system and the inclusion check does not come down to algorithms of polynomial difficulty (see Table 2), it is rational to calculate U p[ABC] ∩ G Dn[C]
and to check if the derived system is empty by using methods from the Section 5.2 and from [9]. Transforming U p[ABC] into a C-system (this operation is often more laborious; then emptiness check for a D-system) yields U p[ABC] = {1} {0}
{1} ∗ {1} {1} . In
this case, the inclusion check U p[ABC] ⊆ G Dn[C] is feasible by an algorithm of polynomial hardness. This problem is a good example for implementing search for arbitrary conse- quences. Let us find incomplete projections in the C-system U p[ABC]. These projections are [C], [AB], [AC] and [BC]. For the first projection, we get U p[C] = {1} {1}
= [{1}], which corresponds to the logical formula of the C. The projections [AC] and [BC] ultimately yield the same result. The projection [AB] corresponds to the formula A ∨ B. The suggested approach allows to use algebraic methods for solving problems of logical inference. Moreover, it allows to see the essence of logical inference in classical logic in a new light. We know that if A ⊆ B is true, it means that B is a necessary condition or a property of A. The relation (4) shows that a logical consequence is correct not only because it has been obtained using inference rules whose meaning may not always be clear, but also because it is a necessary condition for existence of the antecedent. Above, we have already considered some examples of using algebraic approach for processing basic structures of data and knowledge. Let us now analyze in detail some ways of using NTA in certain existing program systems. 6 CONCLUSION This article suggests using algebraic approach based on general theory of multiplace relations for solving logical analysis problems, the mathematical base for this ap- proach being NTA, which is considered a Boolean structure in abstract algebra. The suggested generalized operations and relations significantly broadens the analytical scope and application field of NTA objects as compared to those of mathematical structures currently used for modeling and analyzing relations, e.g. in theory of binary relations or in relational algebra. The research data given above shows that NTA allows to unify processing various data and knowledge structures in artificial intelligence systems. Todays knowledge representation languages are declarative, which makes it difficult to find efficient algorithms for information systems that use heterogeneous structures, as well as for assessing operation speed of an algorithm. Conversely, in n-tuple algebra, many declarative commands can be represented as relatively simple procedures. As for im-
1326 B. Kulik, A. Fridman, A. Zuenko plementing logical inference procedures in n-tuple algebra, these can include, beside the known logical calculus methods, new algebraic methods for checking correctness of a consequence or for finding corollaries to a given axiom system. In some cases, NTA provides a faster solution to standard logical analysis tasks as it considers not only feasibility of certain substitutions, but also the inner struc- ture of knowledge to be processed. NTA allows to efficiently parallelize logical inference algorithms, i.e. to process knowledge in a way similar to that of tabular data processing in relational DBMS. Matrix properties of NTA objects allow to fur- ther decrease laboriousness of intellectual procedures. We found new structural and statistical classes of CNF with polynomially identifiable satisfiability properties in NTA. Consequently, many algorithms whose complexity evaluation is theoretically high, e.g. exponential, can in practice be solved in polynomial time, on the aver- age. This substantiates that using algebraic approach is practical not only for data management, but also for knowledge processing. We are planning to conduct future research in the following directions: • context-oriented database (knowledge base) management systems [3, 20]; • research on additional means of immersing NTA structures into measure spa- ces [14]; • modelling intelligent dynamic systems [12, 18] within situational approach [4, 5]. Acknowledgment The authors would like to thank the Russian Foundation for Basic Research (grants 12-07-00302, 11-08-00641, 12-07-00550, 12-07-00689), the Department for Nanotech- nologies and Information Technologies of RAS (project 2.11 of the current Pro- gramme of Basic Scientific Researches), and the Chair of RAS (project 4.3 of the Program #16) for their help in partial funding of this research. REFERENCES [1] Chang, C.-L.—Lee, R. C.-T.: Symbolic Logic and Mechanical Theorem Proving, Academic Press 1973. [2] Davis, M.—Putnam, H.: A Computing Procedure for Quantification Theory. J. Assoc. Comput. Mach., Vol. 3, 1960, pp. 201–215. [3] Ezhkova, I.: Is Universal Expert System Possible? Software & Systems. Vol. 1, 1991, No. 2, pp. 19–29. [4] Fridman, A. Ya.: Situative Approach to Modelling and Structure Control of Nature- Technical Complexes. In: Proceedings 4 th International Conference “System Identi- fication and Control Problems” (SICPRO ’05), Moscow, Russia (Institute of Control Science, Moscow Russia), 2005, pp. 1075–1108 (in Russian). [5] Fridman, A. Ya.—Fridman, O. V.: Situative Approach to Modelling of Perfor- mance and Safety in Nature-Technical Complexes. In: Juha Lindfors (Ed.): Applied Algebraic Approach to Logical Inference Implementation 1327
Information Technology Research – Articles by Cooperative Science Network, Uni- versity of Lapland, Finland, 2007, pp. 44–59. [6] Gentzen, G.: Untersuchungen ber das Logische Schließen. Math. Z., Vol. 39, 1934, pp. 176–210, pp. 405–431. [7] Hilbert, D.—Ackermann, W.: Grundz¨ uge der Theoretischen Logik. Berlin 1928. [8] Kolmogorov, A. N.—Fovin, S. V.: Elements of the Theory of Functions and Functional Analysis, 1: Metric and Normed Spaces. Graylock, Rochester, N. Y. 1957. [9] Kulik, B. A.: A Logic Programming System Based on Cortege Algebra. Journal of Computer and Systems Sciences International, Vol. 33, 1995, No. 2, pp. 159–170. [10] Kulik, B. A.: New Classes of Conjunctive Normal Forms with a Polynomially Re- cognizable Property of Satisfiability. Automation and Remote Control, Vol. 56, 1995, No. 2, pp. 245–255. [11] Kulik, B. A.: Representation of Logical Systems in a Probabilistic Space in Terms of Cortege Algebra, 1 – Elements of Cortege algebra. Automation and Remote Control, Vol. 58, 1997, No. 1, pp. 102–114. [12] Kulik, B. A.: Reliability Analysis of the Systems with Many States on the Basis of the Algebra of Tuples. Automation and Remote Control, Vol. 64, 2003, No. 7, pp. 1029–1034. [13] Kulik, B. A.: A Generalized Approach to Modelling and Analysis of Intelligent Sys- tems on the Cortege Algebra Basis. In: Proceedings Sixth International Conference on System Identification and Control Problems (SICPRO ’07), Moscow, Russia 2007, pp. 679–715 (in Russian). [14] Kulik, B. A.: N -Tuple Algebra-Based Probabilistic Logic. Systems Analysis and Operations Research, Vol. 46, 2007, No. 1, pp. 111–120. [15] Kulik, B. A.—Fridman, A.—Zuenko,A.: Logical Analysis of Intelligence Sys- tems by Algebraic Method. In: Cybernetics and Systems 2010: Proceedings of Twen- tieth European Meeting on Cybernetics and Systems Research (EMCSR 2010), 2010, Vienna, Austria, pp. 198–203 (ISBN 3-85206-178-8). [16] Mendelson, E.:. Introduction to Mathematical Logic. 4 th ed., Chapman & Hall 1997. [17] Russel, S.—Norvig, P.: Artificial Intelligence: A Modern Approach. Second Edi- tion, Prentice Hall 2003. [18] Sokolov, B. V.—Fridman, A. Ya.: Integrated Situational Modelling of Industry- Business Processes for Every Stage of Their Life Cycle. In: Proceedings 4 th Interna-
tional IEEE Conference “Intelligent Systems” (IS 2008), Varna, Bulgaria 2008, Vol. 1, pp. 8-35–8-40. [19] Zuenko, A. A.—Fridman, A. Ya.: Logical Inference in Semantic Analysis of Ad- hoc Path Queries. In: Proceedings 11 th National Conference in Artificial Intelligence with Foreign Collaboration (CAI-2008), Dubna, Russia 2008, Vol. 1, pp. 298–304 (in Russian). [20] Zuenko, A. A.—Fridman, A. Ya.: Context Approach in Support Systems for Open Subject Domains. Artificial Intelligence and Decision Making 3, 2008, pp. 41–51 (in Russian).
1328 B. Kulik, A. Fridman, A. Zuenko [21] Zuenko, A. A.—Fridman, A. Ya.: Development of N -Tuple Algebra for Logical Analysis of Databases with the Use of Two-Place Predicates. Journal of Computer and Systems Sciences International, Vol. 48, 2009, No. 2, pp. 254–261. Boris
Kulik graduated from Leningrad Mining Institute and worked for the USSR Ministry of Geology from 1971 to 1989 in automation of drilling control. Then he took up research on logic, mathematics and artificial intelligence and received his Ph. D. in 1996. Since 1997 he has worked in St. Petersburg Insti- tute of Problems in Machine Science of the Russian Academy of Sciences. He received his Doctor of Science (Physics and Mathe- matics) degree in 2008. At present, he teaches mathematics at the St. Petersburg University of Culture and Art. He has pub- lished 70 scientific papers including 4 monographs. Alexander Fridman graduated from Leningrad Electro-Tech- nical Institute in 1975 and worked in Baku (Azerbaijan) for Rus- sian Shipbuilding Ministry until 1989, when he moved to Apa- tity (Murmansk region, Russia) and began working for Russian Academy of Sciences (RAS). He received his Ph. D. in 1976, Doc- tor of Science degree in 2001 and Professor degree in 2008. At present he is the head of Laboratory on Information Technologies for Control of Industry-Natural Complexes in the Institute for Informatics and Mathematical Modelling of Technological Pro- cesses of RAS and Professor of Applied Mathematics Chair in Kola Branch of Petrozavodsk State University. He has 185 scientific publications including 1 monograph, 21 tutorials and 16 certificates for inventions. Alexander Zuenko a researcher of the Institute for Informatics and Mathematical Modelling of Technological Processes (RAS), graduated from the Petrozavodsk State University in 2005 and received his Ph. D. in 2009. His scientific activities relate to de- veloping software for modelling open subject domains, as well as to knowledge representation and processing. He has 25 scientific publications. Yüklə 404,26 Kb. Dostları ilə paylaş:
|