TY - JOUR

T1 - ISOMORPHISM OF PREDICATE FORMULAS IN ARTIFICIAL INTELLIGENCE PROBLEMS

AU - Kosovskaya, Tatiana

N1 - Conference code: 22

PY - 2019/6

Y1 - 2019/6

N2 - The paper discusses various aspects of application of the notion of isomorphism of elementary conjunc- tions of predicate formulas in Artificial Intelligence (AI) problems that can be formalized by means of predicate calculus. The notion of isomorphism of various objects is widespread in mathematics. Moreover, isomorphic objects have a large number of identical properties. The definition of isomorphic elementary conjunctions of predicate formulas is given in the paper. The main property of such formulas is that they define the same relation between their arguments. The main difference between the notion of isomorphism and the notion of equivalence is that the equivalent formulas must have the same arguments, and the arguments of isomorphic formulas may be significantly different. In the framework of the logic-objective approach to solving AI problems, the following problems, for solving which the notion of isomorphism is used, are considered: the problem of object classification; creating a level description of classes to decrease the computational complexity of the analysis problem of a complex object; creating a level descriptionof the database to decrease computational complexity while multiple solution of the problem Conjunctive Boolean Query; definition of a metric in the space of elementary conjunctions of predicate formulas.

AB - The paper discusses various aspects of application of the notion of isomorphism of elementary conjunc- tions of predicate formulas in Artificial Intelligence (AI) problems that can be formalized by means of predicate calculus. The notion of isomorphism of various objects is widespread in mathematics. Moreover, isomorphic objects have a large number of identical properties. The definition of isomorphic elementary conjunctions of predicate formulas is given in the paper. The main property of such formulas is that they define the same relation between their arguments. The main difference between the notion of isomorphism and the notion of equivalence is that the equivalent formulas must have the same arguments, and the arguments of isomorphic formulas may be significantly different. In the framework of the logic-objective approach to solving AI problems, the following problems, for solving which the notion of isomorphism is used, are considered: the problem of object classification; creating a level description of classes to decrease the computational complexity of the analysis problem of a complex object; creating a level descriptionof the database to decrease computational complexity while multiple solution of the problem Conjunctive Boolean Query; definition of a metric in the space of elementary conjunctions of predicate formulas.

KW - логико-предметное распознавание, изоморфизм формул, NP-полнота, GI-полнота

UR - http://www.foibg.com/ijita/vol26/ijita26-03.pdf

M3 - Article

VL - 26

SP - 221

EP - 230

JO - International Journal on Information Theory and Applications

JF - International Journal on Information Theory and Applications

SN - 1310-0513

IS - 3

Y2 - 1 July 2019 through 12 July 2019

ER -