Isomorphism of predicate formulas in artificil intelligence problems

T. M. Kosovskaya

Zapiski Nauchnykh Seminarov POMI, Investigations on applied mathematics and informatics. Part I, Tome 499 (2021), pp. 38-52

Résumé

The notion of isomorphism of elementary conjunctions of atomic predicate formulas was introduced by the author for solving some AI problems formulated in the predicate calculus language. Two elementary conjunctions are isomorphic if they coincide up to the names of their arguments and the order of literals. This notion specifies such an equivalence relation between formulas that they determine the same relation between the elements of the investigated object. This notion allows you to formulate and solve a number of problems, such as – “setting a metric in the space of elementary conjunctions of predicate formulas”, which is important, for example, when solving the problem of clustering; – construction of a “multilevel description of classes in a recognition problem”, which significantly reduces its computational complexity while its multiple solutions; – construction of “logical databases”, taking into account the relationship between elements of such bases; – construction of “logic ontologies”; – formation a “predicate network”, in which, in contrast to the classical artificial neural network, its configuration (the number of layers and the number of cells in a layer) can change after additional training; – formation of a “fuzzy predicate networ” that allows to recognize new, absent in the training set, objects and to calculate the“degree of confidenc” in the correctness of recognition in the process of its implementation. Brief descriptions of solutions to these problems (with links to complete solutions) are provided in this article.

Bibliographie

[1] N. Nilson, Iskusstvennyi intellekt. Metody poiska reshenii, Mir, M., 1973

[2] T. M. Kosovskaya, “Nekotorye zadachi iskusstvennogo intellekta, dopuskayuschie formalizatsiyu na yazyke ischisleniya predikatov, i otsenki chisla shagov ikh resheniya”, Trudy SPIIRAN, 14 (2010), 58–75

[3] S. Rassel, P. Norvig, Iskusstvennyi intellekt: sovremennyi podkhod, Per. s angl., 2-e izd., Izdatelskii dom “Vilyam”, M., 2006, 1408 pp.

[4] T. M. Kosovskaya, D. A. Petrov, “Vydelenie naibolshei obschei podformuly predikatnykh formul dlya resheniya ryada zadach iskusstvennogo intellekta”, Vestnik SPbGU. Prikladnaya matematika. Informatika. Protsessy upravleniya., 13:3 (2017), 250–263 | MR

[5] T. M. Kosovskaya, N. N. Kosovskii, “Polinomialnaya ekvivalentnost zadach izomorfizm predikatnykh formul i izomorfizm grafov”, Vestnik Sankt-Peterburgskogo universiteta. Matematika. Mekhanika. Astronomiya, 6(64):3 (2019), 430–439 | MR | Zbl

[6] T. M. Kosovskaya, “Chastichnaya vyvodimost predikatnykh formul kak sredstvo raspoznavaniya ob'ektov s nepolnoi informatsiei”, Vestn. S.-Peterburg.un-ta, Ser. 10, 2009, no. 1, 74–84

[7] T. Kosovskaya, “Distance between objects described by predicate formulas”, Mathematics of Distances and Applications, International Book Series. Information Science and Computing, 25, eds. M. Deza, M. Petitjean, K. Markov, ITHEA-Publisher, Sofia, Bulgaria, 2012, 153–159

[8] T. M. Kosovskaya, “Nekotorye zadachi iskusstvennogo intellekta, dopuskayuschie formalizatsiyu na yazyke ischisleniya predikatov, i otsenki chisla shagov ikh resheniya”, Trudy SPIIRAN, 2010, no. 14, 58–75

[9] T. M. Kosovskaya, “Mnogourovnevye opisaniya klassov dlya umensheniya chisla shagov resheniya zadach raspoznavaniya obrazov, opisyvaemykh formulami ischisleniya predikatov”, Vestn. S.-Peterburg.un-ta. Ser. 10, 2008, no. 1, 64–72 | MR

[10] M. Geri, D. Dzhonson, Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982

[11] T. M. Kosovskaya, “Postroenie mnogourovnevoi bazy dlya umensheniya vychislitelnoi slozhnosti resheniya zadachi kon'yunktivnyi bulevskii zapros”, Materialy konferentsii “INFORMATsIONNYE TEKhNOLOGII V UPRAVLENII” (ITU-2018), 11-ya Rossiiskaya Multikonferentsiya po Problemam Upravleniya (2–4 Oktyabrya 2018 g., Sankt-Peterburg, Gnts Rf Ao “KONTsERN «TsNII "ELEKTROPRIBOR”), 2018, 33–38

[12] T. M. Kosovskaya, “Vydelenie izomorfnykh podformul kak sredstvo dlya sozdaniya logicheskoi ontologii”, Materialy konferentsii “INFORMATsIONNYE TEKhNOLOGII V UPRAVLENII” (ITU-2020), 12-ya Rossiiskaya Multikonferentsiya po Problemam Upravleniya (7–8 Oktyabrya 2020 g., Sankt-Peterburg, Gnts Rf Ao “KONTsERN "TsNII "ELEKTROPRIBOR”), 2020

[13] T. M. Kosovskaya, “Samoobuchayuschayasya set s yacheikami, realizuyuschimi predikatnye formuly”, Trudy SPIIRAN, 2015, no. 6 (43), 94–113

[14] T. Kosovskaya, “Fuzzy Recognition by Logic-Predicate Network”, Advances in Science, Technology and Engineering Systems J., 5:4 (2020), 686–699 | DOI

[15] T. M. Kosovskaya, “Podkhod k resheniyu zadachi postroeniya mnogourovnevogo opisaniya klassov na yazyke ischisleniya predikatov”, Trudy SPIIRAN, 2014, no. 3 (34), 204–217