Predicate Calculus as a Tool for AI Problems Solution: Algorithms and Their Complexity

1. Introduction

The choice of initial attributes for description of an object in an artificial intelligence (AI) problem is the first stage of any simulation of an informational process (representation of information for its further use).

At the 60–70th of the twentieth century, many authors (see, for example, [1]) offered to use predicate calculus for AI problem solving. The resolution method seemed to be a very easy and clear tool to solve problems dealing with compound objects, which can be described by properties of its elements and relations between these elements.

Until the notion of NP-complete problem (in particular, described in [2, 3]) was not widely adopted, such an approach seemed to be very convenient, but many such-a-way formalized problems occurred to be NP-complete or even algorithmic unsolvable.

While developing the effective algorithms deciding discrete problems, determination of estimations for number of steps of their run becomes one of the important problems. The absence of the proved estimations for number of an algorithm run steps is considered as an insufficient research of this algorithm. It is especially relevant for problems with big input. It concerns, in particular, to the algorithms deciding various AI problems. At practical use of an algorithm, it is important that it has polynomial upper bound of number of its run steps. The NP-completeness or NP-hardness of a problem means now that the polynomial algorithm of its decision is not known.

In 2007, the author proved NP-completeness of a series of AI problems formalized with the help of predicate calculus formulas [4], proved upper bounds for number of steps of algorithms solving these problems [5], and offered a level description of goal formulas for decreasing the number of proof steps [6]. Such a level description is based on the extraction of a common up to the names of its arguments sub-formula of the set of elementary conjunctions of atomic predicate formulas. These sub-formulas define generalized characteristics of an object.

Extraction of such sub-formulas allows to construct logic-predicate networks [7], which may change its configuration (the number of layers and the number of cells in the layer) during the process of training.

Extraction of these sub-formulas may serve as an instrument for constructing a multi-agent description of an object, when every agent can describe only a part of the object (these parts are intersected), but every agent gives its own names to the elements of the whole object [8].

Here, some AI problems formalized in such a way are under consideration. For these problems, the solving algorithms and upper bounds of their run are obtained. These upper bounds permit to point out the parameters of the problem, which mostly influence on the complexity of the algorithm, and to offer approaches permitting to decrease the complexity.

A model example illustrating the described approach and algorithms is given.

2. Logic-predicate approach to some AI problems and number of steps of these problems solution

Let an investigated object be presented as a set of its elements ω = {ω₁,…, ωt}. The set of predicates p₁,…, pn (every of which is defined on the elements of ω) characterizes properties of these elements or relations between them. Logical description S(ω) of an object ω is a collection of all true formulas in the form piτ¯or ¬piτ¯(where τ¯is an ordered subset of ω) describing the properties of ω elements or relations between them.

Let the set Ω of all investigated objects be a union of classes Ωk, (k = 1,…, K), i.e., Ω = ⋃k=1KΩk. Logical description of the class Ωk is such a formula Akx¯that if the formula Akω¯is true then ω ∈ Ωk. The class description may be represented as a disjunction of elementary conjunctions of atomic formulas.

Here and below, the notation x¯is used for an ordered list of the set x. To denote that there exists such a list x¯that all values for variables from the list x¯are distinct the notation ∃x¯≠Akx¯is used.

The introduced descriptions allow to solve many artificial intelligence problems [9]. Main of these problems may be formulated as follows.

Identification problem: to pick out all parts of the object ω that belongs to the class Ωk.

Classification problem: to find all such class numbers k that ω ∈ Ωk.

Analysis problem: to find and classify all parts τ of the object ω.

The solution of these problems may be reduced to the proof of logic sequents

respectively, and determination of the values for x¯and k. The number of Akx¯variables in the sequent (2) must be equal to the number of constants in ω.

Note that the proof of any of the sequent (1), (2), or (3) answers only the question “whether it is true?” Strictly speaking, in the sequents (1)–(3), instead of the symbols ∃x¯and ⋁k=1Kthere must be words “what are the distinct values of x¯” denoted as ?x¯and “what are the values of k?” denoted as ?k=1K, respectively. In such a case, the sequents (1)–(3) would take the form

If one uses an exhaustive or a logical algorithm (derivation in a sequent calculus or proof by resolution method), the algorithm gives the values for x¯and k.

The proof of sequents (1) and (3) is based on the proof of the sequent

where Ax¯is an elementary conjunction. It follows from the fact that Akx¯is a disjunction of the form C₁∨…∨Cr of elementary conjunctions of atomic formulas C₁,…,C_r, and ∃x¯≠(C₁∨…∨Cr) ⇔ (∃x¯≠C₁∨…∨ ∃x¯≠Cr). That is why we can consecutively check the sequents of the form Sω⇒∃x¯≠Cj. Here, the maximal value for j is r for the sequent (1), and the sum of the number of elementary conjunctions in all class descriptions for the sequent (3).

An exhaustive algorithm is widespread to prove (4). The total estimate for the number of steps (i.e., the number of comparisons) for the exhaustive algorithm solving (4) is

or, more roughly,

While using a logical algorithm (derivation in a predicate sequent calculus or proof by resolution method for predicate calculus), one must find unifier of the formula Ax¯and some subset of S(ω).

The number of steps (i.e., the number of comparisons) required for the solution of the system and, hence, for the logical algorithm solving (4) is

ai and si be the numbers of literals with the predicate pi in Ax¯and in S(ω), respectively. More roughly

where s′ = max{s₁,…, sn}.

The above-received estimations are exponential over the length of Ax¯. The ones for an exhaustive algorithm are exponential over the number of variables, and for a logical algorithm they are exponential over the maximal number of literals with the same predicate. It allows to choose the algorithm depending on characteristics of the concrete problem under consideration. Note that the reverse Maslov’s method [10, 11] has the same estimations for the solution of the sequent (4), but makes essentially smaller number of steps on the average.

The received estimations cannot be essentially decreased up to polynomial ones if P ≠ NP (classes P and NP are the classes of predicates checked in polynomial time by a deterministic or nondeterministic Turing machine respectively). More precisely, the problem (4) is NP-complete and, hence, the problems (1) and (3) are NP-complete, and the problems (4) and (5) are NP-hard [4, 5].

Problem (2) is strictly connected with the so-called “open” problem ISOMORPHISM OF GRAPHS [3], for which it is not proved neither its polynomiality nor its NP-completeness.

3. Level description of classes

Below, the designation Akx¯kwill be used for elementary conjunctions, which are disjunctive terms of a class description.

The notion of level description of classes was introduced in [6]. Such a description essentially allows to decrease the number of steps for an algorithm solving every of the above-formulated problems. This notion is based on the extraction of “frequently” appeared “sub-formulas” Pi1y¯i1(i = 1,…, n₁) of A1x¯1,…, AKx¯Kwith “small complexity” and changing them in these formulas by atomic formulas pi1yi1defined by an equivalence of the form pi1yi1⇔ Pi1y¯i1. New predicates pi1having new first-level arguments yi1for lists y¯i1of initial variables are called first-level predicates. The formula Ak1x¯k1is received from Akx¯kby means of a substitution of pi1yi1instead of Pi1y¯i1

Repeat the above-described procedure with all formulas Ak1x¯k1. After L repetitions, an L-level description in the following form is received:

The solution of the problem of the form (4) with the use of the level description of classes is decomposed on the sequential (l = 1, …, L) implementation of the actions 1–4:

1. For every i (i = 1,…, nl) check S^l−1(ω) ⇒ ∃y¯i1≠Pi1y¯i1and find all lists τ¯i1of previous levels constants for the values of the variable list yi1such that S^l−1(ω) ⇒Pi1τ¯i1.

2. Introduce new l-level atomic formulas pi1yi1defined by the equalities pi1yi1⇔ Pi1y¯i1with new l-level variables.

3. Substitute pi1yi1instead of Pi1y¯i1into Akl−1y¯kl−1and obtain Akly¯kl.

4. Add all constant atomic l-level formulas in the form pi1τil(τi1were received at the first step) to S^l−1(ω) and obtain Sl(ω) . Here τilτil are new l-level constants for the lists of (l − 1)-level constants

5. At last check SL(ω) ⇒ ∃y¯kL≠AkLy¯kL.

The decreasing of the number of steps for an algorithm solving every of the above formulated problems (1)–(3) with the use of a level description follows from the fact that in items 1, 2, and 5, we solve the same problem as it was formulated in Section 1 and has the number (4). The estimations of number of steps exponentially depend on the parameters of the formula, i.e., on the right part of implication. That is why the term “small complexity” for Pily¯ilmust be interpreted as “small number of variables in Pily¯il” for an exhaustive algorithm, and “small number of literals in Pily¯il” for a logical algorithm

Why did we use quotation marks for the term “sub-formulas?” Such formulas (elementary conjunctions) Pjly¯jlare not obliged to be precisely sub-formulas of A1x¯1, …, AKx¯Kbut may differ from these sub-formulas in names of variables and order of conjunctive terms

Definition 1. Elementary conjunctions P and Q are called isomorphic if there is an elementary conjunction R and substitutions λ_R,P and λ_R,Q of the arguments of P and Q, respectively, instead of the variables in R such that the results of these substitutions coincide up to the order of literals

The substitutions λ_R,P and λ_R,Q are called unifiers of R with P and Q, respectively.

Definition 2. Elementary conjunction C is called a common up to the names of arguments sub-formula of two elementary conjunctions A and B if it is isomorphic to some sub-formulas A′ and B′ of A and B, respectively

For example, let A(x,y,z) = p₁(x) & p₁(y) & p₁(z) & p₂(x, y) & p₃(x, z), B(x,y,z) = p₁(x) & p₁(y) & p₁(z) & p₂(x, z) & p₃(x, z)

Is the formula P(u,v) = p₁(u) & p₁(v) & p₂(u, v) their common sub-formula?

The formula P(u,v) is their common up to the names of variables sub-formula with the unifiers λ_P,A—substitution of x and y instead of u and v, respectively, and λ_P,B—substitution of x and z instead of u and v, respectively. It is so because P(x,y) = p₁(x) & p₁(y) & p₂(x,y) is a sub-formula of A(x,y,z) and P(x,z) = p₁(x) & p₁(z) & p₂(x,z) is a sub-formula of B(x,y,z).

An algorithm of extraction of a maximal (having a maximal number of literals) common up to the names of arguments sub-formula C of two elementary conjunctions A and B and determining the unifiers λ_c,A′ and λ_c,B′ is described in [12]. The number of steps of this algorithm is O(aa bb), where a and b are the numbers of literals in A and B, respectively. The minimal number of steps of this algorithm is O((ab)²), the middle estimate is O((ab)^{1/2 log(ab)}).

This algorithm allows to construct a level description for a set of goal elementary conjunctions. Essential difference between maximal common up to the names of arguments sub-formulas and sub-formulas in the level description consists in the fact that in the level description it is needed to extract sub-formulas with “small complexity” but not a maximal one. An algorithm of level description construction is in [6]. It consists in sequential pairwise extraction of common up to the names of variables sub-formulas of Aix¯iand Ajx¯jwith finding their unifiers and then the analogous procedure with the obtained sub-formulas.

Let N be the maximal number of literals Akx¯kin (k = 1,…, K). The upper bound of this algorithm number of steps is O(K²N^2N).

3.1. Example of sub-formula extraction and a level description construction

Return to the example in the previous section. There, we have seen a description of a class of “boxes” represented in Figure 1. According to these descriptions, we have received that given a “box” inside a complex contour image containing t nodes it would be recognized in O(t¹⁰) steps by an exhaustive algorithm and in O(s³⁷) steps by a logical algorithm (here, s is the maximal number of occurrences of the same predicate in the object description S(ω)).

Pairwise extraction of common up to the names of variables of elementary conjunctions, corresponding to these images, allows to extract common up to the names of variables sub-formulas corresponding to the images represented in Figure 2

These sub-formulas contain, respectively, 8, 8, 7, 7, 7, 8 variables and 18, 15, 11, 11, 15, 16 atomic formulas.

The following extraction by means of pairwise partial deduction between common sub-formulas corresponding to images ab, ac, ad, bc, bd, cd gives a sub-formula corresponding to the image represented in Figure 3.

Elementary conjunction P¹(x₁,x₂,x₃,x₄,x₅,x_9,x₁₀) = V(x₁,x₃,x₂) & V(x₂,x₁,x₅) & V(x₃,x₄,x₁) & V(x₃,x₅,x₁) & V(x₃,x₉,x₄) & V(x₃,x₉,x₅) & V(x₃,x₉,x₁) & V(x₅,x₂,x₄) & V(x₅,x₂,x₃) & V(x₉,x₁₀,x₃) & T(x₄,x₃,x₅), corresponding to this image, defines a first-level predicate p¹(x¹). The first-level variable x¹ is a variable for a list of seven initial variables x¹ = (x₁,x₂,x₃,x₄,x₅,x₉,x₁₀). The unifier of P¹(x₁,x₂,x₃,x₄,x₅,x_9,x₁₀) with the description of ab, ac, ad, ac, and bd is an identical substitution, but its unifier with the description of cd is a substitution of x₆ instead of x₅.

Elementary conjunctions P₁²(x¹,x₁,x₂,x₃,x₄,x₅,x₈,x₉,x₁₀), P₂²(x¹,x₄,x₅,x₆,x₉,x₁₀), P₃²(x¹,x₃,x₄,x₅,x₁₀), P₄²(x¹,x₂,x₅,x₆,x₁₀), corresponding to the images ab, ac, bd, cd and written with the use of the predicate p¹(x¹), define second-level predicates p₁²(x₁²), p₂²(x₂²), p₃²(x₃²), p₄²(x₄²) with the second-level variables x₁² = (x¹,x₁,x₂,x₃,x₄,x₅,x₈,x₉,x₁₀), x₂² = (x¹,x₄,x₅,x₆,x₉,x₁₀), x₃² = (x¹,x₃,x₄,x₅,x₁₀), x₄² = (x¹,x₂,x₅,x₆,x₁₀).

For example, a sub-formula corresponding to the image ab is P₁²(x¹,x₁,x₂,x₃,x₄,x₅,x₈,x₉,x₁₀) = p¹(x¹) & V(x₂,x₅,x₈) & V(x₂,x₁,x₈) & V(x₅,x₄,x₁₀) & V(x₅,x₃,x₁₀) & V(x₈,x₂,x₁₀) & V(x₁₀,x₈,x₅) & V(x₁₀,x₅,x₉) & V(x₁₀,x₈,x₉). The unifier of P₁²(x¹,x₁,x₂,x₃,x₄,x₅,x₈,x₉,x₁₀) with the description of a is an identical substitution, and with the description of b, it is a substitution of x₄,x₅,x₆,x₇,x₈ instead of x₂,x₄,x₅,x₉,x₁₀. Descriptions of images c and d are not unified with it.

The three-level description of the image b takes the form A_b²(x₁²,x₄,x₅,x₆,x₇) = p₁²(x₁²) & V(x₅,x₄,x₇) & V(x₅,x₇,x₆) or A_b²(x₃²,x₄,x₅,x₆,x₇) = p₃²(x₃²) & V(x₃,x₂,x₈) & V(x₅,x₄,x₇) & V(x₅,x₇,x₆).

Given a “box” inside a complex contour image containing t nodes, the proof the sequence from S(ω) of elementary conjunction P¹(x₁,x₂,x₃,x₄,x₅,x_9,x₁₀) defining the first-level predicate p¹(x¹) and the denotation of variables x₁,x₂,x₃,x₄,x₅,x_9,x₁₀ would be done in O(t⁷) steps by an exhaustive algorithm and in O(s¹¹) steps by a logical algorithm.

Elementary conjunctions P₁²(x₁¹), P₂²(x₁¹), P₃²(x₁¹), P₄²(x₁¹) contain respectively only 1, 1, 0, 1 “new” variables (not containing in the first-level variables) and 7, 4, 4, 5 “new” atomic formulas. The proof of the sequence from S¹(ω ) of these elementary conjunctions defining the second-level predicates p₁²(x₁²), p₂²(x₂²), p₃²(x₃²), p₄²(x₄²), and the denotation of the “new” variables would be done in O(t) steps by an exhaustive algorithm and in O(s⁷) steps by a logical algorithm.

Elementary conjunctions obtained from the class description by means of second-level predicates instead of the corresponding sub-formulas contain respectively 2, 0, 2, 2 “new” variables and 7, 4, 11, 16 “new” atomic formulas. The proof of the sequence from S²(ω ) of these elementary conjunctions and the denotation of the “new” variables would be done in O(t²) steps by an exhaustive algorithm and in O(s¹⁶) steps by a logical algorithm.

As O(t⁷) + O(t) + O(t²) = O(t⁷) < O(t¹⁰) and O(s¹¹) + O(s⁷) + O(s¹⁶) = O(s¹⁶) < O(s³⁷) then both an exhaustive algorithm and a logical algorithm using the built level description of the class of “boxes” make the less number of steps then the same ones using the initial description. At the same time, the decreasing of number of steps of a logical algorithm is more noticeably.

4. Logic-predicate network

Traditional neuron network deals with binary or many-valued characteristics of an object and is an adder of weighted inputs followed by a function mapping the result into the segment [0, 1]. The neuron network configuration is fixed and only the weights may be changed.

A logic-predicate network is described later. The inputs for this network are atomic formulas setting properties of the elements composing an investigated object and relations between them [7]. The proposed model of logic-predicate network has two blocks: a training block and a recognition block. The input of every block is an elementary conjunction of atomic predicate formulas or their negations. Configuration of the recognition block is formed after an implementation of the training block and may be changed with its help.

The training block is a “slowly running” block. At the same time, the recognition block is a “quickly running” one. The base of the proposed predicate network is a logic-objective approach to AI problems and level description of classes.

The scheme of the logic-predicate network is presented in Figure 4

At a training stage of logic-predicate network construction, we have a training set of objects. Let a training set of objects ω₁,…, ω_K be given to form an initial variant of the network training block. Replace every constant ωkjin S(ωk) by a variable xkj(k = 1,…, K, j = 1,…, tk) and substitute the sign & between the atomic formulas. Initial goal formulas A1x¯1,…,AKx¯Kare obtained.

Construct a level description for these goal formulas with the use of algorithm of level description. The first approximation to the recognition block is formed. Formulas Pily¯il(i = 1,…, nl, l = 1,…, L) obtained in the training block (together with the unifiers) are the contents of the cells forming the recognition block. This block runs as it was described in the section level description of classes.

The recognition block tries to identify a new object according to the level description of classes, obtained in the training block.

If after the “recognition block” run an object is not recognized or has wrong classification, then it is possible to train anew the network. The description of the “wrong” object must be added to the input set of the training block. The training block extracts common sub-formulas of this description and previously received formulas forming the recognition block. Some sub-formulas in the level description would be changed. Then, the recognition block is reconstructed.

4.1. Model example of a logic-predicate network construction

Given a training set for the class of contour images of “boxes” presented in Figure 1 (Section 2). Pairwise extraction of common up to the names of variables of elementary conjunctions, corresponding to these images, allows to extract common sub-formulas corresponding to the images presented in Figures 2 and 3 (Section 3). Fragments of the images corresponding to a three-level network are presented in Figure 5.

Given, a new image represented in Figure 6 for recognition, the network would not recognize it because the first-level predicate is not valid.

Add the description of this control image to the input data of the training block. The extraction of common sub-formulas for this description and the formula defining the first-level predicate gives a formula corresponding to the image represented in Figure 7.

New second-level predicates correspond to three images represented in Figure 8.

The set of the third-level predicates coincides with the set of previous second-level predicates. So, the recognition block is constructed anew and represents four-level description of the class. Fragments of the images corresponding to a four-level network are presented in Figure 9.

5. Multi-agent description of an object

A problem of multi-agent description of a complex object is under consideration in this section. It is supposed that every agent knows only a part of an investigated object description. Moreover, she does not know the true names of elements and gives them names arbitrary. It is similar to the parable about tree blind men who feel an elephant. To overcome such a paradox, it is supposed that every two agents have information concerning some common part of an object. The main difficulty in this problem is to find and identify these parts [8].

5.4. Example of a multi-agent description

Let the initial predicates be V and L described in Section 2. Each of the three agents has a description of one of the fragment presented in Figure 10.

According to the item 1 of the algorithm, all constants in the fragment descriptions are replaced by variables in such a way that different constants are changed by different variables and the names of variables in Ii and Ij (i ≠ j) does not coincide. The fragment descriptions take the form:

I′1(x1,…,x6) = V(x1,x2,x4) & V(x1,x5,x4) & V(x1,x3,x2) & V(x1,x3,x5) & V(x1,x3,x4) & V(x2,x1,x3) & V(x2,x3,x5) & V(x3,x2,x1) &V(x3,x6,x2) & V(x3,x6,x1) & L(x2,x1,x5),

I′2(y1,…,y6) = V(y3,y1,y4) & V(y1,y2,y3) & V(y1,y5,y3) & V(y1,y6,y2) & V(y1,y6,y5) & V(y1,y6,y3) & L(y2,y1,y5),

I′3(z1,…,z8) = V(z1,z5,z3) & V(z1,z3,z2) & V(z1,z5,z2) & V(z3,z1,z7) & V(z3,z1,z6) & V(z3,z7,z4) & V(z3,z6,z4) & V(z3,z4,z1) & V(z4,z2,z3) & V(z4,z3,z8) & V(z4,z2,z8) & L(z7,z6,z3).

According to the item 2 of the algorithm, find maximal common up to the names of arguments sub-formula of formulas I′1(x1,…,x6) and I′2(y1,…,y6). It is C12(u0,…,u4) of the form C12(u0,…,u4) = V(u0,u1,u2) & V(u0,u3,u2) & V(u0,u4,u1) & V(u0,u4,u3) & V(u0,u4,u2) & L(u1,u0,u3).

It has unifiers λ_I1,C12—substitution of u0, u1, u4, u2, u3 instead of x1, x2, x3, x4, x5, respectively, and λ_I2,C12—substitution of u0, u1, u2, u3, u4 instead of y1, y2, y3, y5, y6, respectively. Besides,

I′1(u0,u1,u2,u3,u4,x6) = V(u1,u0,u4) & V(u1,u4,u3) & V(u4,u1,u0) & V(u4,x6,u1) & V(u4,x6,u0) & C12(u0, …, u4),

I′2(u0,u1,u2,y4,u3,u4) = V(u2,u0,y4) & C12(u0,…,u4).

Maximal common up to the names of arguments sub-formula of I′2(y1,…,y6) and I′3(z1,…,z8) is C23(v0,v2,v4,v5,v6,v7) of the form

C23(v0,v2,v4,v5,v6,v7) = V(v6,v2,v7) & V(v2,v4,v6) & V(v2,v5,v6) &V(v2,v0,v4) & V(v2,v0,v5).

It has unifiers λ_I2,C23—substitution of v2, v4, v6, v7, v5, v0 instead of y1, y2, y3, y4, y5, y6, respectively, and λ_I3,C23—substitution of v0, v2, v6, v5, v4, v7 instead of z1, z3, z5, z6, z7, z8, respectively. Besides,

I′2(v2,v4,v6,v7,v5,v0) = V(v2,v0,v6) & L(v4,v2,v5) & C23(v0,v2,v4,v5,v6,v7),

I′3(v0,z2,v2,v6,z5,v5,v4,v7) = V(v2,v6,v0) & V(v0,z5,v2) & V(v0,v2,z2) & V(v0,v5,z2) & V(v6,z2,v2) & V(v6,v2,v7) & L(v4,v5,v2) & C23(v0,v2,v4,v5,v6,v7).

As I′2(v2,v4,v6,v7,v5,v0) contains V(v2,v0,v6) and I′3(v0,z2,v2,v6,z5,v5,v4,v7) contains V(v2,v6,v0) and according to the definition of the predicate V, the formula V(x,y,z) & V(x,z,y) is a contradiction, so substitutions with this unifiers cannot give a consistent description of the object. After deleting from I′2(y1,…,y6) and I′3(z1,…,z8), the variables y1 and z3, respectively, a new maximal common up to the names of arguments their sub-formula C’23(v0,v2,v4,v5,v6,v7) of the form C’23(v0,v1,v2) = L(v1,v0,v2) will be received with the unifiers λ_I2,C’23— substitution of v0, v1, v2 instead of y1, y2, y3, respectively, and λ_I3,C’23—substitution of v2, v0, v1 instead of z3, z6, z7, respectively. Besides,

I′2(v0,v1,v2,y4,y5,y6) = V(v2,v0,y4) & V(v0,v1,v2) & V(v0,y5,v2) & V(v0,y6,v1) &V(v0,y6,y5) & V(v0,y6,v2) & C’23(v0,v1,v2),

I′3(z1,z2,v2,z4,z5,v0,v1,z8) = V(z1,z5,v2) & V(z1,v2,z2) & V(z1,z5,z2) & V(v2,z1,v1) & V (v2,z1,v0) & V(v2,v1,z4) & V(v2,v0,z4) & V(v2,z4,z1) & V(z4,z2,v2) & V(z4,v2,z8) & V(z4,z2,z8) & C’23(v0,v1,v2).

Maximal common up to the names of arguments sub-formula of I1(x1,…,x6) and I3(z1,…,z8) is C13(w0, …,w6) in the form

C13(w0, …,w6) = V(w2,w4,w6) & V(w2,w5,w6) & V(w2,w0,w4) & V(w2,w0,w5) & V(w0,w1,w2).

It has unifiers λ_I1,C13— substitution of w2, w4, w0, w6, w5, w6 instead of x1, x2, x3, x4, x5, x6, respectively, and λ_I3,C13—substitution of w0, w2, w6, w1, w5, w2 instead of z1, z3, z4, z5, z6, z7, respectively. Besides,

I′1(w2,w4,w0,w6,w5,w1) = V(w2,w0,w6) & V(w0,w1,w4) & V(w0,w4,w2) & L(w2,w4,w5) & C13(w0,…,w6),

I′3(w0,z2,w2,w6,w1,w5,w4,z8) = V(w0,w2,w3) & V(w0,w1,w3) & V(w2,w6,w0) & V(w6,w3,w2) & V(w6,w2,w7) & V(w6,w3,w7) & C13(w0,…,w6).

As I′1(w2,w4,w0,w6,w5,w1) contains V(w2,w0,w6), I3(w0,z2,w2,w6,w1,w5,w4,z8) contains V(w2,w6,w0) and according to the definition of the predicate V, the formula V(x,y,z) & V(x,z,y) is a contradiction, so substitutions with this unifiers cannot give a consistent description of the object.

After deleting from I′1(x1,…,x6) and I′3(z1,…,z8) literals with the variables x1 and z3, respectively, a new maximal common up to the names of arguments their sub-formula

C′13(w0,w1,w2) of the form C’13(w0,w1,w2) = L(w1,w0,w2)

will be received with the unifiers λ_I1,C’13—substitution of w0, w1, w2 instead of x1, x2, x5, respectively, and λ_I3,C’13—substitution of w2, w1, w0 instead of z3, z4, z5 respectively. Besides,

I′1(w0,w1,x3,x4,w2,x6) = V(w0,w1,x4) & V(w0,w2,x4) & V(w0,x3,w1) & V(w0,x3,w2) & V(w0,x3,x4) & V(w1,w0,x3) & V(w1,x3,w2) & V(x3,w1,w0) & V(x3,x6,w1) & V(x3,x6,w0) & C’13(w0,w1,w2),

I′3(z1,z1,w2,w1,w0,z6,z7,z8) = V(z1,w0,w2) & V(z1,w2,z2) & V(z1,w0,z2) & V(w2,z1,z7) & V(w2,z1,z6) & V(w2,z7,w1) & V(w2,z6,w1) & V(w2,w1,z1) & V(w1,z2,w2) & V(w1,w2,z8) & V(w1,z2,z8) & C′13(w0,w1,w2).

According to the item 4 of the algorithm, we identify new variables substituted instead of the same initial variable. That is we identify the following variables:

1. u0 and w0 (are substituted instead of the variable x1),

2. u1 and w1 (are substituted instead of the variable x2),

3. u2 and w2 (are substituted instead of the variable x4),

4. u0 and v0 (are substituted instead of the variable y1),

5. u1 and v1 (are substituted instead of the variable y2),

6. u2 and v2 (are substituted instead of the variable y3),

7. v0 and w0 (are substituted instead of the variable z6),

8. v1 and w1 (are substituted instead of the variable z3),

9. v2 and w2 (are substituted instead of the variable z7).

The identified variables denote as α 0, α 1, and α 2. So, we have the equalities u0 = v0 = w0 = α 0, u1 = v1 = w1 = α 1, u2 = v2 = w2 = α 2.

As a result, we have the following descriptions of the fragments:

I″1(α 0, α 1,u4,u2, α 2,x6) = V(α 0, α 1,u2) & V(α 0, α 2,u2) & V(α 0,u4, α 1) & V(α 0,u4, α 2) & V(α 0,u4,u2) & V(α 1, α 0,u4) & V(α 1,u4, α 2) & V(x3, α 1, α 0) & V(u4,x6, α 1) & V(u4,x6, α 0) & L(α 1, α 0, α 2),

I″2(α0, α 1,u2,y4, α 2,u4) = V(u2, α 0,y4) & V(α 0, α 1,u2) & V(α 0, α 2,u2) & V(α 0,u4, α 1) & V(α 0,u4, α 2) & V(α 0,u4,u2) & L(α 1, α 0, α 2),

I″3(z1,z2, α 2,z4,z5, α 0, α 1,z8) = V(z1,z5, α 2) & V(z1, α 2,z2) & V(z1,z5,z2) & V(α 2,z1, α 1) & V(α 2,z1, α 0) & V(α 2, α 1,z4) & V(α 2, α 0,z4) & V(α 2,z4,z1) & V(z4,z2, α 2) & V(z4, α 2,z8) & V(z4,z2,z8) & L(α 1, α 0, α 2).

Their conjunction

V(α0, α 1,u2) & V(α 0, α 2,u2) & V(α 0,u4, α 1) & V(α 0,u4, α 2) & V(α 0,u4,u2) &

V(α 1, α 0,u4) & V(α 1,u4, α 2) & V(x3, α 1, α 0) & V(u4,x6, α 1) & V(u4,x6, α 0) &

V(u2, α 0,y4) & V(z1,z5, α 2) & V(z1, α 2,z2) & V(z1,z5,z2) & V(α 2,z1, α 1) &

V(α 2,z1, α 0) & V(α 2, α 1,z4) & V(α 2, α 0,z4) &V(α 2,z4,z1) & V(z4,z2, α 2) &

V(z4, α 2,z8) & V(z4,z2,z8) & L(α 1, α 0, α 2)

allows to “stick together” the images of fragments according to the same variable. The image corresponding to the result of “sticking” is presented in Figure 11.

If a description of the investigated object is presented in the database, it may be found according the principle “the nearest neighbor” with the use of metric for predicate formulas presented in [13].

6. Conclusion

Logic-predicate approach to an AI problem has a rather powerful capability, essentially when an investigated object is a compound one and is characterized by properties of its elements and relations between them.

Setting of pattern recognition problems considered in Section 2 (except the problem (2)) differs from the classical one. The setting of the problems (1) and (3), in which it is needed to find parts of an investigated object, turns out to be a rather difficult one in the frameworks of a standard approach in the frameworks of which an object is regarded as a whole indivisible one.

In particular, an exponential estimation for number of propositional variables in a formula simulating a predicate formula in a finite domain for planning problems T·|Act|·OP is mentioned in [14]. Here, T is the number of time stages, |Act| is the number of schemes of actions, O is the number of objects in the domain, P is the maximal number of parameters in schemes of actions. In Section 2, the analogous estimate (5′) was received for an exhaustive algorithm solving the problem (4).

The problem (2) is polynomial equivalent to an “open” problem ISOMORPHISM OF GRAPHS [3] and the problems (1) and (3) are NP-complete.

A notion of level description of classes has been introduced in Section 3 in order to decrease the number of steps of algorithms solving these problems. Such a description reduces the solution of the main problem to a series of solutions of the same form problems with the inputs with the essentially less notation lengths. At the same time, the constructing of a level description still deals with big input data. So, a problem with big input data is solving only once, and then the problem with the essentially less input data is solving repeatedly.

The idea of decomposition of a problem to a series of the “less dimension” problems is not a new one and is frequently used. The difficulty consists in a precise definition of the term “common sub-formula of small complexity.”

The development of a precise definition and of an algorithm for the extraction of a common up to the names of arguments sub-formula of two elementary conjunctions (and their unifiers) allows not only to work out an algorithm of level description construction but also to find an approach to the solution of some else AI problems.

Note that the extracted sub-formulas define generalized characteristics of an object. This has an analogy in medical diagnostics: initial characteristics are symptoms and the generalized ones are syndromes.

Level description of classes allowed to introduce the notion of logic-predicate network described in Section 4. Such a network may be regarded as a self-training network which changes its configuration after an additional training. It corresponds to the fact that in the process of a man training, new notions and relations between them are formed in a human brain.

The presence of an algorithm for the extraction of a common up to the names of arguments sub-formula of two elementary conjunctions (and their unifiers) allows to find an approach to a problem of multi-agent description of an object described in Section 5. Just an extraction of such sub-formulas and determining of their unifiers with the input formulas makes possible to “stick together” such parts of descriptions in which different agents gives different names to one element of the whole object.

Note that the formulation of the problem (1) from Section 2 coincides with the one for a well-known problem CONJUNCTIVE BOOLEAN QUERY from [3]. The difference is in the implementation of these problems. While repeated implementation of the problem (1) the premise S(ω) of the sequent Sω⇒∃x¯≠Akx¯is different, while every implementation and the conclusion Akx¯is a constant part. That is why just a collection of class descriptions A1x¯1, …, AKx¯Kpermits to construct a level description.

While repeated implementation of the problem CONJUNCTIVE BOOLEAN QUERY, the premise S(ω) of the sequent Sω⇒∃x¯≠Akx¯is constant while every implementation and queries Akx¯are different while every implementation. An approach to the construction of a level data base is presented in [15].

The possibility of reduction of an object description length by means of adding a formula setting some properties of initial predicates to the premise of a sequent was mentioned in the model example in Section 2. Properties of initial predicates also were used in the item 3 of the algorithm of multi-agent description. In fact, in the both cases instead the sequent of the form (4) Sω⇒∃x¯≠Ax¯it is needed to check another sequent of the form Cy¯Sω⟹∃x¯≠Ax¯, where Cy¯is a set of formulas setting properties of initial predicates. Investigation of computational complexity of such a form sequent may be an interesting problem in the further research.

To solve the problem (2) and to extract a maximal common up to the names of arguments sub-formula of two elementary conjunctions it is needed to check whether two elementary conjunctions are isomorphic. A polynomial in time rough algorithm for such a checking was offered in [12] by Petrov. Numerical experiments with this algorithm give over 99.95% of valid results.