METHODS FOR DECOMPOSITION OF CONJUNCTIVE FORMULAS IN FINITE PREDICATE ALGEBRA

Abstract

In this paper the subject matter is the methods of decomposing conjunctive formulas in the algebra of finite predicates and the possibility of using dependency structures of relational data to build compact logical networks. The work examines the interrelation between operations of relational algebra and predicate algebra, which makes it possible to form a mathematical framework for the rational representation of complex predicate models. The relevance of the study is determined by the need to create high-performance solutions for linguistic information processing and to optimize parallel computational structures. The goal of the work is to develop an effective method of binary predicate decomposition that reduces the number of auxiliary variable values and ensures the transformation of multidimensional predicate formulas into a compact system of binary relations suitable for hardware implementation in the form of logical networks. This approach improves model performance and reduces hardware complexity. To achieve this goal, the following tasks were carried out: analysis of functional, multivalued, and connection dependencies; determination of the conditions for the existence of quantifier-conjunctive decomposition; and investigation of cases in which a predicate can be represented as a system of binary formulas. The limitations of Cartesian decomposition were identified, and it was shown how dependency structures eliminate these drawbacks, forming more compact and structurally justified models. The research methods include the apparatus of finite predicate algebra, the theory of relational dependencies, techniques for constructing auxiliary predicates, variable elimination using existential quantifiers, and modeling processes in the form of logical networks. Special attention is paid to analyzing the structural properties of formulas that influence decomposition efficiency. The results of the research show that the proposed method allows obtaining more compact binary models in comparison to the Cartesian approach. Predicate decomposition applied to a morphological inflection model has confirmed a significant increase in efficiency during hardware implementation of the logical network and improved performance indicators. In the conclusions, it is emphasized that the use of dependency structures is an effective tool for optimizing formal models and opens opportunities for further automation of predicate-structure construction in tasks of logical analysis and knowledge processing.