DOI: 10.17587/prin.7.252-257

Extended Model of LP-inference on Boolean Lattice

I. Yu. Ivanov, hour1scorp@gmail.com, Voronezh State University, 394006, Voronezh, Russian Federation

Corresponding author: Ivanov Ilya Yu., Postgraduate Student, Voronezh State University, 394006, Voronezh, Russian Federation, e-mail: hour1scorp@gmail.com

Production systems are widespread in informatics. They are based on productions, or rules, of the from "A produces B", where A and B are the elements of some hierarchy. Software, the state of which is defined by a set of variables values and rules of transition from one state to another (productions) determined by executing code, is an example of aforementioned system. Another example is expert production systems, the rules of which have implicative semantics: "if A holds, then B is true". In this case A is called premise and B is called conclusion of a rule. There are two types of problems to be solved within expert production systems: forward inference and backward inference. Each of these problems has at least two special features. Firstly, the high computational complexity which is caused by exponential complexity of propositional logic algorithms, which are applied to process premises and conclusions of rules. Secondly, the need to obtain truth of facts on particular stages of inference for external sources of data querying (e.g., knowledge bases, experts etc.). Obviously, speed of external queries processing is extremely lower than speed of computational device (e.g., CPU). Therefore, a problem of "slow" queries quantity minimizing arises. Previously S. D. Makhortov introduced the concept of production-logical equations on atom-derived lattice. These equations can be applied to perform LP-inference — algebraic method of backward inference that minimizes a number of "slow" queries in a system that uses only one logical connection, conjunction, in its rules. Later, a new class of production logical equations on boolean lattice has been introduced by the author of the paper. With these equations, it is possible to implement LP-inference that performs similar optimization in systems that use a full set of zero-order propositional languages operations in its rules: conjunctions, disjunctions and negations. In addition, the solvability of these equations was investigated and the method of particular solutions finding was proposed. In this paper, the questions related to general solution of production-logical equation on LP-structure of zero order are examined. Obtained results complete building of extended model of LP-inference on boolean lattice.

Keywords: productions, production-logical systems, mathematical lattices, propositional logic, backward inference, LP-structures, LP-inference, production-logical equations, particular solutions, general solution

pp. 252–257

For citation:
Ivanov I. Yu. Extended Model of LP-inference on Boolean Lattice, Programmnaya Ingeneria, 2016, vol. 7, no. 6, pp. 252—257.

This work was supported by the Russian Foundation for Basic Research, project nos. 15-07-05341