Kleshchev A.S., Artemjeva, Gavrilova T.L., Surov V.V. Application of logical relationship systems for expert systems development

APPLICATION OF LOGICAL RELATIONSHIP SYSTEMS FOR EXPERT SYSTEMS DEVELOPMENT^¹

ABSTRACTA new class of the declarative models is defined. Every model of this class is called a logical relationship system. It is shown how a logical relationship system may be used as a domain model. A criterion of adequacy of a domain model to the domain is suggested. For the tasks solved by expert systems mathematical specifications of the tasks in terms of logical relationship systems are discussed. Several approaches to working out the methods for solving these tasks are considered. Finally, it is analyzed in what manner these mathematical models can be used for designing and implementing expert systems.

When any sufficiently complicated computer program for solving an applied task is developed, a mathematical model of the program is worked out before the beginning of designing and implementing the program. A mathematical model of a program consists of a domain model, of a task specification in terms of the domain, and of a method for solving the task. Declarative domain models are most often used when an applied task is solved. The declarative models are the systems of equations, of inequalities, and of all the other types of relationships among unknowns. A relationship description language always corresponds to every class of the declarative models. The declarative semantic of the language determines the solutions of any relationship system as a collection of values whose substitution for all the unknowns turns these relationships into identically true ones. A mathematical task specification in terms of such a model consists of a description of the input data, of the task conditions, and of a specification of the output data in terms of the relationship system unknowns. A method for solving the task may be represented as an algorithm or a calculus. It must be proved that the set of all the results obtained by the method is the same as the set of all the task solutions. If a computer is used for solving the task then the method has to be described by a programming language that unnecessarily is an algorithmic one.

Working out a mathematical model of a program has some advantages. There are possibilities of using the domain analysis techniques corresponding to particular classes of the declarative models, of detecting and eliminating many errors of the applied program developers before the beginning of designing and implementing the program, and of decreasing the labour-consuming character of the implementation. These advantages are due to the following facts. For every domain a model can be built in such a class in which all the domain properties important for solving the task can be best represented; the class can be selected on the basis of collections of conditions of this class models applicability. If a class of the declarative models has been selected then all the important properties of the domain can be extracted and used for building a declarative model of the domain (the domain can be analyzed by using the conditions of applicability of this class models). Inadequacy between the domain and its declarative model can be detected. Methods for solving the task can be worked out on the basis of the mathematical specification of the task and properties of these methods can be mathematically investigated.

Expert systems are among important classes of the applied programs [1]. Since many expert systems were usually developed for such domains where knowledge has a declarative character it would have been natural to expect working out the mathematical models of these expert systems before their designing and implementing. However, no class of the declarative models has been proposed yet that would allow us to represent all the domain properties important for solving the tasks of expert systems. That is a reason why the developers of expert systems have to use informal descriptions of the tasks of expert systems instead of their mathematical specifications. Only the methods for solving the tasks of expert systems are always described in a formal manner by a knowledge representation language (as either a set of rules, a set of frames, or a semantic network). But every knowledge representation language is a language with procedural semantics that is implemented by an expert system shell (i.e. a programming language) rather then a language with declarative semantics (i.e. a language for description of declarative models). Therefore, the modern practice of expert system development does not include the stage of working out a mathematical model. At the same time, the complexity of many domains for which expert systems are developed is very large. As a result: analysis of such domains is usually considered as an art; the amount of errors made during developing an expert system, as a rule, is extremely large; the labour-consuming character of implementing an expert system is higher than the labour-consuming character of implementing programs of many different classes. In this connection one may expect that the profit of working out mathematical models of the expert system before their designing and implementing would be very considerable.

The aim of this article is to provide the basis for working out mathematical models of expert systems before their designing and implementing. A new class of the declarative models is defined. Every model of this class is called a logical relationship system. It is shown how a logical relationship system may be used as a domain model. A criterion of adequacy of a domain model to the domain is suggested. For the tasks solved by expert systems mathematical specifications of the tasks in terms of logical relationship systems are discussed. Several approaches to working out the methods for solving these tasks are considered. Finally, it is analyzed in what manner these mathematical models can be used for designing and implementing expert systems.

The models of mathematical logic are fundamental declarative models underlying all the other declarative models [2]. However, the models of mathematical logic have the following disadvantages in comparison with the other declarative models used in applied mathematics (equations, inequalities, and so on). For every model of mathematical logic all the symbols of the signature are interpreted in the same algebraic system whereas for every declarative model of any other type all the symbols of the signature are usually divided into three groups. All the symbols of the first group (the constants, the signs of operations, and the signs of relations) are interpreted in one algebraic system (usually fixed). All the symbols of the second group (the unknowns) are interpreted in another algebraic system (all the solutions of the relationship system belong to the set of such algebraic systems). And all the symbols of the third group (the parameters) are interpreted in the third algebraic system (usually given). From this point of view, all the symbols of the signature in every model of mathematical logic can be considered as unknowns (objective, functional, and predicative) but there are no constants, signs of operations, signs of relations, and parameters. For the models of mathematical logic, algebraic systems having infinite universes are usually considered as solutions though in the case of expert systems, algebraic systems having finite universes are quite sufficient to be considered. This section defines logical relationship systems as a special class of the models of mathematical logic.

For n> any set S =S₀ È S₁È ... È S_n will be called a signature of n-th order if S_i Ç S_j= Æ for i ¹ j and S_i is a signature for i=1,...,n. All the objective symbols of S₀ will be namedconstants, all the functional symbols of S₀ will be named signs of operations or functions, and all the predicative symbols of S₀ will be named signs of relations. The symbols of S₁ will be called objective, functional and predicative unknowns. For i>1 all the symbols of the signature S_i will be called parameters (objective, functional and predicative) of the (i-1)-th order. We will consider either couple W¹= <F, A₀> (if n=1) or tuple Wⁿ= <F, A₀, A₂,..., A_n> (if n>1) as a logical relationship system of the n-th order and of the signature S. Here F is a finite set of quantor-free logical formulas written by predicate calculus language of the signature S. This language is the first stage one if n=1 and the second stage one if n>1. A₀=<U₀, J₀> is an algebraic system of the signature S₀, where U₀ is its universe and J₀ is its interpretation of all the symbols of the signature S₀. For i=2,...,n A_i= <U_i, J_i> is an algebraic system of signature S_i where U_i is its universe and J_i is its interpretation of all the symbols of the signature S_i. We will consider the interpretation of all the functional and predicative symbols of S₀ as calculable functions and predicates. We will also call an algebraic system A_a = <U_a, J_a > of the signature S₁ (where U_a is the universe of A_a and J_a is the interpretation of all the symbols of S₁) as appropriate for a logical relationship system Wⁿ if U_a is a finite subset of U₀. The universe U₂ of the algebraic system A₂ consists of all the objective symbols of the signature S₀ and of all the symbols of the signature S₁. For i=3,...,n the universe of A_i is the union of the universe of A_i-1 and the signature S_i. For i=2,...,n the interpretations of all the functional and predicative symbols of all the signatures S_i are functions and predicates with finite domains of definition. Therefore, all these functions and predicates can be represented by finite tables. Every variable being a member of any formula of F has an order, i.e. an integer between 1 and n, and a range of values. If the order of a variable is equal to 1 then its range of values is a subset of the universe of A₀. If the order of a variable is i and i is more than 1 then range of values of the variable is a subset of the universe of A_i. A substitution l = {v₁/a₁, ..., v_k/a_k} is appropriate for a formula j Î F and an algebraic system A_a of the signature S₁, if all the variables being members of j are included in the set {v₁,..,v_k} and if for any j=1,..,k the value a_j belongs either to intersection of the range of values of v_j and the universe of A_a (if the order of v_j is equal to 1) or to the range of values of v_j (if the order of v_j is more than 1). A formula j Î F is in agreement with an algebraic system A_a if j is true for any appropriate substitution when all the symbols of S₀ are interpreted in the algebraic system A₀, all the symbols of S₁ are interpreted in the algebraic system A_a, all the symbols of S₂ are interpreted in the algebraic system A₂, ..., and all the symbols of S_n are interpreted in the algebraic system A_n. The set of all the appropriate substitutions is a finite one. We will consider an appropriate algebraic system A_a as a solution for Wⁿ if all the formulas entering F are in agreement with A_a.

We will consider a logical relationship system of a signature S₀ È S₁ È S'₂ È ...È S'_m and a logical relationship system of a signature S₀È S₁ È S"₂È ...È S"_n as equivalent systems if the solution sets of them are identical to one another. The theorem about decreasing the order of logical relationship systems has been proved: if n>1 and Wⁿ is a logical relationship system of the n-th order then the logical relationship system of (n-1)-th order exists being equivalent to Wⁿ. The theorem allows us to replace any logical relationship system of a high order by the equivalent logical relationship system of the first order. Below a logical relationship system of the second order will be considered as example. In the next section it will be shown this system is simplified declarative models of the medical domain [3].

Example 1. Let's give a logical relationship system of the second order. The objective symbols of the signature S₀ are all the numerical constants and also all the elements of the finite set of scalar constants {e₀, e₁,..., e₆}. The functional symbols of the signature S₀ are all the signs of arithmetic operations, and the predicative symbols of this signature are the signs "=", "¹", ">", "<", "£" and "³". The algebraic system A₀ defines the generally accepted interpretation of the symbols of S₀. The set of the objective symbols of the signature S₁ consists of the only objective unknown "x", the set of the functional symbols of this signature consists of the functional unknowns y₁, y₂, y₃, the set of the predicative symbols of this signature consists of the predicative unknowns z₁, z₂, z₃. The set of the objective symbols of the signature S₂ is empty, the set of the functional symbols of this signature consists of the functional parameters b₁, b₂, b₃, and the set of the predicative symbols of this signature consists of the predicative parameters c₁, c₂,..., c₆. The interpretation of all the symbols of the signature S₂ in the algebraic system A₂ is defined as follows.

c₁(y₁, e₂) = true, c₁(y₁, e₃) = true, c₁(y₂, e₄) = true, c₁(y₂, e₅) = true,

c₁(y₂, e₆) = true, c₁(y₃, e₄) = true, c₁(y₃, e₅) = true, c₁(y₃, e₆) = true,

c₄(e₁, y₁, 1, e₃) = true, c₄(e₁, y₁, 2, e₂) = true, c₄(e₁, y₂, 1, e₄) = true,

c₄(e₁, y₂, 2, e₅) = true, c₄(e₁, y₃, 1, e₆) = true, c₄(e₁, y₃, 2, e₄) = true,

( 1.5 ) c₅(v₁) & v₁(v₂,v₃,v₄) & v₁(v₂-1,v₅,v₆) &v₂>1 ® v₃=v₆

( 1.7 ) c₅(v₁) & v₁(v₂,v₃,v₄) & v₁(v₂, v₅,v₆) ® v₃=v₅& v₄=v₆

( 1.10) x ¹ e₀& c₆(v₁) & Ø c₃(x,v₁) &v₁(v₂)=v₃ ® c₂(v₁ ,v₃)

& v₃£ b₄(x,v₁) ® v₅-v₄>b₁(x,v₁,v₃) &v₅-v₄£b₂(x, v₁,v₃)

We will consider that a domain is characterized by a professional activity. This activity consists in solving different tasks. Task solving needs professional knowledge, the same for all the tasks. The professional knowledge and also input and output data for every task can be represented verbally. We will consider the set of domain objects, the domain reality and domain knowledge as the main domain components. Information about the domain objects is used as input, output and intermediate data of the tasks of the professional activity. The professional activity runs in the domain reality and the professional knowledge is the basis of the activity.

We will consider that every domain object belongs to a magnitude. A magnitude is a set of domain objects that a realizable univalent mapping of the set onto a set M exists for. Such a set M will be further called a scale. The result of the mapping of an object belonging to the magnitude will be called the value corresponding to the object on the scale M (the scale value). A mapping will be considered realizable if for all the objects belonging to the magnitude a procedure exists to obtain the values corresponding to these objects on the scale M. The constants of the scales are used for designating the scale values.

Relations exist among objects of the domain. If Â is such a relation then such a computable relation R among scale values exists that if <₁,..., _n> Î Â (where ₁ Î ₁,..., _nÎ_n) then ₁(₁),..., _n(_n)> Î R. All the relations among scale values are polymorphic, i.e. if R is n-adic relation among scale values then such a set P_R and such functions q₁^R,...,q_n^R exist that every q₁^R,...,q_n^R maps the set P_R into the union of all the scales, RÍq₁^R(p) ´ ... ´ q_n^R(p) and R Ç q₁^R(p) ´ ... ´ q_n^R(p)¹Æ for any p Î P_R. If a relation among objects of the domain is a functional one then the corresponding relation among scale values is functional one too.

The set of all the scales used in the domain will be called the domain scale system. S₀ consists of all the constants of all the scales and also of the signs of all the relations (functional and unfunctional). The algebraic system A₀ simulates the domain scale system together with the relations among the scale values, i.e. the universe of A₀ is the union of all the scales, the interpretation of every scale constant is a scale value, and the interpretation of every sign of a relation (functional or unfunctional) is a relation (functional or unfunctional). Scales and scale values are used in professional activity instead of magnitudes and magnitude objects and also relations among scale values are used instead of relations among objects. The domain scale system allows us to represent mathematical properties of the domain objects in the domain model. Systems of dimensional, nominal, ordinal, space (coordinate), geographical, geometric scales and also systems of scale of sets, of role frames [4], of sequences, of chemical formulas are some examples of scale systems. In particular, in the Example 1 the domain scale system consists of the dimensional scale ''hours'', of the dimensionless scale, and also of two nominal scales ''diseases'' consisting of e₀, e₁,... and ''data'' consisting of e₂, e₃, e₄, e₅, e₆,.... Here e₀ designates ''healthy'', e₁ designates ''pancreatitis'', e₂ designates ''presence'', e₃ designates ''absence'', e₄ designates ''normal'', e₅ designates ''high'', and e₆ designates ''low''.

We will consider the reality as an infinite set of separated situations. Each situation is represented by the information related to a task. For example, in the medical domain every situation relates to a case of disease and is represented by the information about the case. This information concerns with a finite set of domain objects represented by scale values. Every domain object belonging to this set will be called a situation object. In addition, the domain reality has a finite set of roles, a finite set of notions, and a finite set of relations among situation objects. Any of these three sets may be empty but not all. For every situation each role defines an object of this situation. For every situation each notion defines a set (maybe empty) of objects of this situation. And also for every situation each relation among situation objects defines a set (maybe empty) of k-tuples (where k>1) consisting of objects of this situation. These relations may be functional or unfunctional. For a functional relation among situation object every set of k-tuples represents a functional mapping. If a relation does not satisfy this condition then it is unfunctional. Thus, every situation has a structure. This structure consists of roles, notions, and relations of the situation. The diagnosis of a patient is an example of a role, and correspondences between time moments of examining some patient signs and values of these signs at this time moments are examples of functional relations in the medical domain.

The objective symbols of the signature S₁ are designations of the reality roles. The functional symbols of S₁ are designations of the functional relations of the reality. The monadic predicative symbols of S₁ are the designations of the reality notions. The polyadic predicative symbols of S₁ are the designations of the unfunctional relations of the reality. In particular, in Example 1 x is the designation of the role meaning ''diagnosis''. It is supposed that any patient is either healthy or ill with a disease. Here a disease is considered as a process elapsing with time. The values of the patient signs may change with time. Therefore, every sign is represented by a monadic functional relation connecting time moments (on the dimensional scale ''hours'') of the sign examination with values of the sign at these time moments. y₁ is the designation of the monadic functional relation meaning ''strain of abdomen muscles''. Its values belong to the scalar scale {e₂, e₃}. y₂ is the designation of the monadic functional relation meaning ''blood pressure''. Its values belong to the scalar scale {e₄, e₅, e₆}. y₃ is the designation of the monadic functional relation meaning ''daily diuresis''. Its values belong to the scalar scale {e₄, e₅, e₆}. For every sign the whole space of time corresponding to a situation is divided into a few dynamics periods. For any sign these periods are indexed by positive integers according to their sequence beginning with 1. Therefore, for any sign dynamics periods form a triadic unfunctional relation connecting dynamics period indexes, their beginnings, and their ends. z₁ is the designation of the triadic unfunctional relation meaning ''dynamics periods of strain of abdomen muscles'', z₂ is the designation of the triadic unfunctional relation meaning ''dynamics periods of blood pressure'', and z₃ is the designation of the triadic unfunctional relation meaning ''dynamics periods of daily diuresis''.

If a logical relationship system is a model of a domain then a model of any domain situation a is an algebraic system A_a appropriate for the logical relationship system. In this case the universe of the algebraic system A_a is a model of the situation object set and the interpretation of all the symbols of the signature S₁ in A_a is a model of the situation structure.

Any domain can have a few models. Logical relationship systems of different orders may be among these models.

At first, we will consider the case when a logical relationship system of the first order is a model of a domain. In this case the domain knowledge can be considered as a finite set of statements about properties of all the situations of the reality in terms of the names of the roles, of the notions, and of the relations among situation objects of the domain. The set of logical formulas F is a model of the knowledge: any statement of the domain knowledge is represented by a formula jÎF as its model. The logical relationship systems of the first order have a disadvantage when they are used as domain models. The disadvantage is that for any complex domain having a large amount of knowledge every model of the knowledge consists of excessively large amount of logical formulas. Moreover, adding new knowledge leads to increasing the amount of formulas in the knowledge model. This circumstance makes such domain models difficult for building, surveying, and using.

Further, we will consider the case when a logical relationship system of the second order is a model of a domain. The objective symbols of S₀ and all the symbols of S₁ will be called terms of the first order. The domain knowledge will be considered as a finite set of facts and a finite set of agreements about domain representation. Every fact can be represented by a tuple consisting of terms of the first order. The facts having a similar sense and represented by m-tuples (m>0) form a relation among terms of the first order. We will distinguish functional and unfunctional relations among terms of the first order. If m is equal to 1 then such a relation can be considered as a domain metanotion. The agreements about domain representation (metaknowledge) can be divided into three groups. The first one consists of the agreements about properties of the domain roles, of the domain notions, and of the domain relations among situation objects. The second one consists of the agreements about properties of the domain relations among terms of the first order. The third one consists of the agreements about interdependence between the domain reality and the domain relations among terms of the first order. For every domain situation and for any agreement about properties of the domain roles, of the domain notions, and of the domain relations among situation objects, it may be ascertain whether or not the agreement is true with respect to the situation. For the domain relations among terms of the first order and for any agreement about properties of the domain relations among terms of the first order, it may be ascertain whether or not this agreement is true with respect to the domain relations among terms of the first order. For the domain relations among terms of the first order, for every domain situation, and for any agreement about interdependence between the domain reality and the domain relations among terms of the first order, it may be ascertain whether or not this agreement is true with respect to the domain relations among terms of the first order and the situation. The functional and predicative symbols of the signature S₂ are the designations of the functional and unfunctional relations among terms of the first order. The universe of the algebraic system A₂ is the set of terms of the first order. The interpretation of a functional (predicative) symbol of S₂ in A₂ is a table of the relation among terms of the first order designated by the symbol. The set F of logical formulas is a model of the set of agreements about domain representation.

In Example 1 the symbols of the signature S₂ have the following meaning. The triadic functional symbol b₁ means ''the low limit of the duration of a dynamics period''. The triadic functional symbol b₂ means ''the high limit of the duration of a dynamics period''. The monadic functional symbol b₃ means ''dynamics periods corresponding to a sign''. The biadic predicative symbol c₁ means ''possible value of a sign''. The biadic predicative symbol c₂ means ''normal value of a sign''. The biadic predicative symbol c₃ means ''the clinical picture''. The 4-adic predicative symbol c₄ means ''a value of a dynamics period''. The monadic predicative symbol c₅ means ''dynamics periods''. The monadic predicative symbol c₆ means ''signs''.The relations ''dynamics periods'' and ''signs''are the examples of the medical domain metanotions. In this Example the interpretation of the symbol b₁ represents the following facts. For pancreatitis the low limit of the duration of the first dynamics period of strain of abdomen muscles is equal to 24 hours, the low limit of the duration of the second one is equal to 1 hour, the low limit of the duration of the first dynamics period of blood pressure is equal to 1 hour, the low limit of the duration of the second one is equal to 1 hour, the low limit of the duration of the first dynamics period of daily diuresis is equal to 48 hours, the low limit of the duration of the second one is equal to 1 hour. The interpretation of the symbol b₂ represents the following facts. For pancreatitis the high limit of the duration of the first dynamics period of strain of abdomen muscles is equal to 48 hours, the high limit of the duration of the second one is equal to 144 hour, the high limit of the duration of the first dynamics period of blood pressure is equal to 24 hours, the high limit of the duration of the second one is equal to 144 hour, the high limit of the duration of the first dynamics period of daily diuresis is equal to 72 hours, the high limit of the duration of the second one is equal to 144 hours. The interpretation of the symbol b₃ represents the following facts. The unfunctional relations among the situation objects ''dynamics periods of strain of abdomen muscles'', ''dynamics periods of blood pressure'', and ''dynamics periods of daily diuresis'' correspond to the functional relations ''strain of abdomen muscles'', ''blood pressure'', and ''daily diuresis'' respectively. The interpretation of the symbol c₁ represents the following facts. The possible values of the sign ''strain of abdomen muscles'' are ''presence'' and ''absence''. The possible values of the sign ''blood pressure'' are ''normal'', ''high'', and ''low''. The possible values of the sign ''daily diuresis'' are ''normal'', ''high'', and ''low''. The interpretation of the symbol c₂ represents the following facts. The normal value of the sign ''strain of abdomen muscles'' is ''absence''. The normal value of the sign ''blood pressure'' is ''normal''. The normal value of the sign ''daily diuresis'' is ''normal''. The interpretation of the symbol c₃ represents the following facts. The clinical picture of the disease pancreatitis consists of signs ''strain of abdomen muscles'', ''blood pressure'', and ''daily diuresis''. The interpretation of the symbol c₄ represents the following facts. For pancreatitis the possible value of the sign ''strain of abdomen muscles'' for the first dynamics period is ''absence'', the possible value for the second one is ''presence'', the possible value of the sign ''blood pressure'' for the first dynamics period is ''normal'', the possible value for the second one is ''high'', the possible value of the sign ''daily diuresis'' for the first dynamics period is ''low'', the possible value for the second one is ''normal''. The interpretation of the symbol c₅ represents the following facts. The class ''dynamics periods'' consists of unfunctional relations ''dynamics periods of strain of abdomen muscles'', ''dynamics periods of blood pressure'', and ''dynamics periods of daily diuresis''. The interpretation of the symbol c₆ represents the following facts. The class ''signs'' consists of functional relations ''strain of abdomen muscles'', ''blood pressure'', and ''daily diuresis''.

Let's comment on the formulas belonging to the set F. Formula (1.1) means that every normal value of any sign is a possible value of the sign too. Formula (1.2) means that for any disease each possible value of every sign within a dynamics period is a possible value of the sign. Formula (1.3) means that for any disease the high limit of the duration of every dynamics period of each sign is more then the low limit of the duration of the dynamics period of the sign. Formula (1.4) means that the time moment of the beginning of the first dynamics period for any sign is 0. Formula (1.5) means that for any dynamics period (except for the first one) of every sign, the time moment of the beginning of the period is equal to the time moment of the end of the previous dynamics period of the sign. Formula (1.6) means that for any dynamics period of every sign, the time moment of the end of the period is later then the time moment of the beginning of the period. Formula (1.7) means that for any dynamics period of every sign, the number of the period uniquely determines the time moments of the beginning and the end of the period. Formula (1.8) means that at any time moment of examination of every sign only a possible value of the sign may be obtained. Formula (1.9) means that if a patient is healthy then at any time moment of examination of every sign, only a normal value of the sign may be obtained. Formula (1.10) means that if a patient is ill with a disease and a sign does not belong to the clinical picture of the disease then at any time moment of examination of the sign, only a normal value of the sign may be obtained. Formula (1.11) means that if a patient is ill with a disease, a sign belongs to the clinical picture of the disease, and a time moment belongs to a dynamics period of the sign then the value examined at the moment is a possible value of the sign for the period and for the disease. Formula (1.12) means that if a patient is ill with a disease and a sign belongs to the clinical picture of the disease then the duration of a dynamics period of the sign is more then the low limit of the period (with the same index) for the disease and is less then the high limit of the period.

When logical relationship systems of the second or a higher order are used as domain models they do not have the disadvantage pointed above for the logical relationship systems of the first order. In this case the knowledge model includes few logical formulas. In Example 1 the knowledge model includes 12 logical formulas. Certainly, for any real domain model the knowledge model may include a few tens formulas. But if new knowledge is added then the amount of formulas in the knowledge model does not change. Only the amount of facts increases in the knowledge model. This circumstance makes such domain models more preferable.

Building a domain model in the form of a logical relationship system needs an analysis of the domain. As results of the analysis the domain scale system, all the domain roles, domain notions, and domain relations among situation objects should be identified. If the domain model is built in the class of logical relationship systems of the first order then all the statements about properties of all the situations of the reality should be identified. If the domain model is built in the class of logical relationship systems of the second or a higher order then all the domain relations among terms of the first or a higher order and also all the agreements about the domain representation should be identified. This analysis has to precede an acquisition of all the facts about the domain necessary for filling all the tables of the relations among terms of the first or a higher order. The experience of the authors has shown that analysis of a complex domain usually has less labour-consuming character if a domain model is built in the form of a logical relationship system of the second or a higher order.

After building a domain model, it is necessary to be sure that this model is adequate to the domain. For this purpose, it is necessary to have a criterion of adequacy of a model to the domain. Such a criterion may be as follows: a logical relationship system is an adequate model of a domain if the solution set of the system is an adequate model of the domain reality. It means that every situation of the reality has an adequate model belonging to the solution set and every solution is an adequate model of a situation of the reality. Since the set of situations of the reality is infinite, for practical purposes the following criterion of inadequacy can be used: a logical relationship system is not an adequate model of the domain if such a situation exists in the reality that the adequate model of the situation does not belong to the solution set.

We will represent every specification of any task for a logical relationship system Wⁿ as a 4-tuple TF = < Wⁿ, D, Y, P>. Wⁿ is a logical relationship system of the signature S. D is a set of quantor-free formulas written by the first stage predicate calculus language whose signature is the union of S₀ and S₁. Moreover, every formula includes at least one symbol of S₁. D is a representation of the input data and the conditions of the task. Y is a predicate defined on the set of all the solutions of Wⁿ. Y is a representation of the optimization criterion of the task. If the task has no optimization criterion then we will assume Y is identically true. P is a set of therms and formulas written by the first stage predicate calculus language whose signature is the union of S₀ and S₁ . Moreover, every therm and every formula includes at least one symbol of S₁. P is a specification of the output data of the task.

To define a task solution we will build a new logical relationship system W_tⁿ of the signature S as the tuple <F_t, A₀, A₂,..., A_n> where F_t = F È D. The solution set of W_tⁿ is a subset of the solution set of Wⁿ. Let S_t be a designation of the set consisting of such a solution of W_tⁿ for which Y is true. If S_t is empty then the task has no solutions. Otherwise, if A_t Î S_t then a task solution is the set of the values of all the therms and formulas of P obtained under the condition that all the symbols of the signature S₁ are interpreted in the algebraic system A_t.

Example 2. We will consider a task of medical diagnostics in terms of the medical domain model of Example 1. In the task the values of some signs of a patient obtained at some time moments are given and a diagnosis of the patient should be ascertained. The formal specification of the task may be represented by the 4-tuple TF = <Wⁿ, D, Y, P> where Wⁿ is the logical relationship system of Example 1, D={y₁(12) = e₃, y₁(36) = e₃, y₁(60) = e₂, y₂(12) = e₄, y₂(36) = e₅, y₂(60) = e₅, y₃(12)=e₆, y₃(36) = e₆, y₃(60) = e₄}, Y º true, P = {x}. A solution of the task is x=e₁ (pancreatitis).

Examples of an optimization criterion being not identically true are the maximum of the certainty factor for many diagnostic expert systems and the minimum of cost in planning and designing expert systems. All the tasks solved by the existing expert systems can be represented in such a form.

The possibility of investigating methods for solving the tasks of expert systems, the possibility of improving these methods, and the possibility of developing new methods for solving the tasks are the three main advantages of the approach suggested.

Practice of expert system development was that methods for solving tasks were worked out on the basis of informal specifications of these tasks. Usually such a method was represented in a form of a set of rules of a calculus. Therefore, the question about a correspondence between the set of task solutions and the set of results given by the method was meaningless. Working out a formal specification of the task gives a possibility of an investigation of any method for solving the task.

It is natural to describe a method for solving a task in terms of the domain model, i.e. in terms of the signature S. If the domain model is a logical relationship system of the first order then any investigation of the method is very difficult. The reason is the domain model includes too many logical formulas and the method description consists of too many rules. If the domain model is a logical relationship system of the second or a higher order then any investigation of the method is considerably easier.

Investigation of methods consists in proving theorems like the following: the set of results given by a method is equal to the set of task solutions for the same input data. The methods having this property are usually called correct with respect to the task specification. Another direction of investigation of methods may be building complexity estimates of these methods.

To improve a method means to modify it in such a way in order to decrease its complexity. There are three main sources for improving methods. The first one is an adaptation of methods to particular properties of logical relationship systems. It means that the reason of decreasing complexity of a method is taking into account some particular properties of the corresponding logical relationship system. The second source for improving methods is an adaptation of methods to particular properties of the input data of the task. It means that the reason of decreasing complexity of a method is taking into account some particular properties of the input data of the task. The third source of improving a method described in terms of a logical relationship system of a high order is a transformation of the method to ones described in terms of the equivalent logical relationship system of the first order on the basis of the theorem about decreasing order. If the task is solved by a method described in terms of a logical relationship system of a high order then data processed by the method consist of input data of the task and of the set of all the facts of the knowledge model. Since the set of all the facts includes extremely many facts then complexity of solving the task by the method is extremely large. It has been found experimentally that going from a method described in terms of a logical relationship system of a high order to a method described in terms of the logical relationship system of the first order significantly decreases complexity of solving the task [3].

However, it is more important that the suggested approach allows us to work out new methods for solving tasks in the form of an algorithm.

Example 3. Let's give a method for solving the task of Example 2 in the form of an algorithm. To do this, let's divide the source task into the following subtasks.

1. To test the hypothesis that the patient is healthy (on the basis of formula (1.9)).

2. If the hypothesis of subtask 1 is refuted then for every disease v₁, to test the hypothesis that the patient is ill with the disease v₁ (on the basis of formulas (1.4)-(1.7) and (1.10)-(1.12)). This subtask can be divided into the following subtasks.

2.1. For every sign not belonging to the clinical picture of the disease v₁, to test the hypothesis that this sign has only normal values (on the basis of formula (1.10)). If at least for one such sign this hypothesis is refuted, then the hypothesis of subtask 2 is also refuted.

2.2. If all the hypotheses of subtask 2.1 are verified then for every sign v₂ belonging to the clinical picture of the disease v₁, to test the hypothesis that all examined values of the sign v₂ are in agreement with the description of the clinical manifestation for this sign and for the disease v₁ (on the basis of formulas (1.4)-(1.7), (1.11) and (1.12)). If all the hypotheses are verified then the hypothesis of subtask 2 is verified too. This subtask can be divided into the following subtasks.

2.2.1. It follows from formulas (1.4)-(1.7), (1.12) that every time moment can belong to a set of possible dynamics periods. We will represent any set of possible dynamics periods by the set of indexes of these periods The subtask is to form the set of indexes of possible dynamics periods for every time moment of examining the sign v₂.

2.2.2. It follows from formula (1.11) that every time moment can belong to another set of possible dynamics periods (this set may differ from the set defined for the same time moment by subtask 2.2.1). The subtask is to form the set of indexes of possible dynamics periods for every time moment of examining the sign v₂. If at least one of these sets is empty then the hypothesis of subtask 2 is refuted.

2.2.3. If the hypothesis of subtask 2 is not refuted yet then for every time moment of examining the sign v₂, to obtain the intersection of the two set defined by subtasks 2.2.1 and 2.2.2. If at least one of these intersections is empty then the hypothesis of subtask 2 is refuted.

2.2.4. If the hypothesis of subtask 2 is not refuted yet then for every time moment of examining the sign v₂, to strike off such elements from the set of indexes defined by subtask 2.2.3 that disagree with formula (1.5). For every time moment t_i we will designate the set defined by this subtask as z_i. If at least one of z_i is empty then the hypothesis of subtask 2 is refuted.

2.2.5. Let's introduce some auxiliary functions (v) is the index of examining a sign v. y(v,i) is the time moment of examining a sign v and this time moment has the index i of the increasing sequence of all the time moments of examining the sign v. These two functions can be determined by the input data of the task. For any two positive integers n and N let's designate X(n,N) = {x: [1,n] ® [1,N] | i>j ® x(i) ³ x(j)}, i.e. X(n,N) is the set of all the monotone nondecreasing functions mapping the integer-valued interval [1,n] into the integer-valued interval [1,N]. For any disease v₁ and any sign v₂ belonging to the clinical picture of v₁ if n = (v₂) and N=b₄(v₁, v₂) then the set Z(v₁, v₂) is a subset of the set X(n,N). Now if the hypothesis of subtask 2 is not refuted yet then the subtask is to form the set Q ={x Î X(n,N) | x(i) Î z_i, iÎ[1,n]}, where N is the number of dynamics periods of the sign v₂ for the disease v₁, n = (v₂).

2.2.6. For every x Î Q, to form a system of inequalities consisting of two parts. The first part does not depend on x and is the set of the following inequalities

{ x₁ > b₁(v₁, v₂, 1), x₂ – x₁ > b₁(v₁, v₂, 2), ..., x_n – x_n-1> b₁(v₁, v₂, n),

x₁ < b₂(v₁, v₂, 1), x₂ – x₁ < b₂(v₁, v₂, 2), ..., x_n – x_n-1< b₂(v₁, v₂, n)}

2.2.7. If such x exists that for it the system of inequalities defined by subtask 2.2.6 has a solution then subtask 2.2 has the positive solution, i.e. the hypothesis is verified that all the examined values of the sign v₂ are in agreement with the description of the clinical manifestation for this sign and for the disease v₁. If for all c Î X every system of inequalities does not have any solution then the hypothesis is refuted.

It may appear that the algorithm given in Example 3 is specialized for the domain model of Example 1 and for the task specification of Example 2. But in fact, the algorithm is connected with a form of description of regularities of varying qualitative processes with time. This form is used in many domains. So, the algorithm is widely applicable. Besides, it is obvious that a representation of a method for solving a task of an expert system in the form of an algorithm allows us to obtain more effective implementation of the expert system than a representation of the method in the form of a calculus.

6.THE IMPACT OF THE SUGGESTED APPROACH ON TECHNOLOGY OF EXPERT SYSTEM DEVELOPMENT

A way of producing of an output is usually called a technology if the way permits to produce the output of an admissible cost. From this point of view, there is no technology of expert system development for complex domains and tasks yet. At the same time, any idea allowing us to do expert system development cheaper can be considered as a contribution to working out such a technology. Let's discuss in what manner the suggested approach permits to do expert system development cheaper.

The more complex the domain, the more labour-consuming is the knowledge acquisition. Building a domain model in the form of a logical relationship system of the second or a higher order can significantly decrease the labour-consuming character of the knowledge acquisition. Really, the acquisition of all the facts about a domain for filling all the tables of all the relations among terms of the first or a higher order should be executed after a domain analysis. For any domain a specialized knowledge base editor can be developed on the basis of a description of these relations. The editor can acquire these facts from an expert in an interactive manner without any knowledge engineer. Moreover, the editor asks all the necessary questions to the expert and represents his answers formally in a computer readable form. Thereby, any intellectual efforts of a knowledge engineer are eliminated to acquire all the facts from the expert, to formalize them, and to represent them in a computer readable form. At the same time, developing such an editor is of a very low labour-consuming character because the generator of such editors has been developed [3]. The generator forms any editor automatically using a description of all the domain relations among terms of the first or a higher order.

The labour-consuming character of expert system development may be considerably decreased if processes of knowledge acquisition and of expert system implementation are separated in time. It will be possible if computer stocks of knowledge are formed that are not closely connected to concrete expert system development. In this case the knowledge base of an expert system may be obtained from such stocks. Since such stocks are intended for reusing knowledge in different expert systems solving different tasks, the form of knowledge in these stocks have to be a declarative one. One of approaches to forming such stocks may be the following. For several domains, their models are built in the form of a logical relationship system of the second or a higher order. Every such model should represent as many features of the domain as possible. The knowledge stocks may consist only of the domain relations among terms of the first or a higher order. For any particular expert system a domain model is worked out that is a simplification of the model from a stock. This simplified model has a more simple set of agreements about domain representation then the domain model from the stock has. The relation tables of the simplified model can be obtained from the relation tables from the stock by extracting necessary tuples from the stock and extracting necessary information from these tuples.

A factor of simplifying a domain model is the use of a scale system adequate to the domain. The factor is especially considerable for such domains where objects have a complex structure and also are represented by values on specialized scales such as geographical scales for domains connected with geography, chemical scales for domains connected with chemistry, geometrical scales for domains connected with geometry, and so on. In addition, the complexity of expert system implementations can be considerably decreased and efficiency of methods for solving tasks can be considerably increased if operations on values of such scales are used. At the same time, since scales are of universal nature (i.e. usually are used in more then one domain) these scales can be implemented independently of particular expert systems. The programs implementing the operations and relations on the scales may be a part of shells or of specialized application packages (unfortunately, a majority of the modern expert system shells include only the programs implementing the operations and relations on the dimensional and nominal scales and sometimes on the scales of role frames). Such an approach also makes the development of expert systems cheaper.

In Section 4 it was noted that transition from a method described in terms of a logical relationship system of a high order to the method described in terms of the logical relationship system of the first order significantly decreases complexity of solving the task. Such a transition can be made by a special computer program called a compiler of relations among terms of the first or a higher order to a rule base. Developing such a compiler is of a very low labour-consuming character because the macrogenerator of rule bases has been developed [3].

If two different expert systems solve two tasks belonging to the same class of tasks then the same method can be used to solve the both tasks. The fact that the both tasks belong to the same class and can be solved by the same method can be detected only if a formal description of the class of tasks is connected with the method. Besides, one of the ways of working out methods for solving tasks is decomposition of an initial task into subtasks. In this case different tasks can have the same subtasks. So, one of the sources of decreasing the labour-consuming character of expert system implementation is collecting methods for solving tasks and subtasks. These methods in the form of computer programs can be a part of special application packages to be reused.

Finally, one of the very labour-consuming stages of expert system development is expert system validation. The criterion of adequacy suggested above can be the basis of the stage.

The results of this article are a generalization of the authors' experience of developing expert systems and shells since the 1970's. The results were published in Russian.

This work was carried out with financial support from the Russian Fund of Fundamental Investigations (project 96-01-00175).

[1]. Hayes-Roth F., Jacobstein N. The state of knowledge-based systems // Com.ACM. -1994.-Vol. 37. -N 3. -P.27-39.

[2]. Newell A. The Knowledge Level // Artificial Intelligence. 1982. -Vol.18. -N 1. -P. 87-127.

[3]. Kleshchev A.S. Expert Systems Based on Metaknowledge. // Institute for Automation \& Control Processes, Far Eastern Division of Russian Academy of Sciences. Vladivostok. 1994. 13 p.

[4]. Minsky M. A Framework for Representing Knowledge. // The Psychology of Computer Vision, McGraw-Hill, 1975.

1 Was published in: Application of Advanced Information Technologies, Proceeding of 4 World congress on expert systems, ITESM Mexico City Campus March 16–20 1998, pp. 500–510