Predicate Logic Involving Data Structure as a Knowledge Representation Language

I Introduction

In order to analyze and design large systems, a structured analysis and design methodology has to be employed. This involves the concept of multiple levels of abstraction where at each level of abstraction, the system is viewed composed of a network of entities. Abstract entities at the next higher level of ab­ straction is formed as the collection of these entities. At the highest level of abstraction, the system is ~ single entity while at the lowest level, the system is composed of primitive entities, Each primitive entity has some functionality which is specified, in advance, for each object system. Systems of more complex functionality are composed of them. Here by functionality, we include various con­ cepts other than the structural relation­ ships, such as attribute, property, func­ tion etc. of an entity. When to define the abstract entity at a level of abstrac­ tion, the internal structure of the entity at the next lower level need not be known, but these entities can be thought of as primitives at that level of abstraction. Some entities at the same level are inter­ connected to each other to form the net­ work of entities. Thus the specification of the structure of a system is recursive in nature.

A system directly by can be specified either specifying its structure or

PREDICATE LOGIC INVOLVING DATA STRUCTURE AS A KNOWLEDGE REPRESENTATION LANGUAGE

Setsuo Ohsuga

Institute of Interdisciplinary Research Faculty of Engineering, The University of Tokyo 4-6-1 Komaba, Meguro-ku, Tokyo 153, Japan

indirectly by specifying its behavior, Generally speaking, to analyze a system is to obtain the behavior of the system given its structure. Hence the structure of the system has to be specified in terms of the primitive entities before it can be analyzed. On the other hand, to design a system is to obtain the structure of the system given the behavior. In general, to find the complex structure to have the specified behavior is not an easy task. One needs to generate a tentative struc­ ture and examine it whether it has the specified behavior. The system can be specified by specifying the structure and the functionality of the primitive en­ tities at the lowest level. But very often it is necessary to give the explicit description on (part of) functionality of an entity at an arbitrary level, Thus, each abstract entity has three parts: (1) the components, (2) the interconnection between the entities in the same level and (3) the description on functionality. These parts are represented in the system described below by the hierarchical struc­ ture for (1) in which each entity at any level of abstraction is represented by a node and each node in the collection at the lower level is linked to the upper node, by the table of connection for (2) and by the logical formula for (3).

In this paper, we will discuss a knowledge representation language designed to deal with this structure. Unlike many of the CAD lnguage involving the hardware description language [3 ,4], this language is designed to use engineering knowledge to support the automatic transformation between the structure of the system and

its behavior.

This language is based on the predi­ cate logic because it is suited for de­ scribing the interconnections between the entities in the table form and func­ tionality of an abstract entity. The entity-comp6nent relation also can be rep­ resented by providing the system with an atomic formula of the form (COMPONENT x y) meaning that x is a component of y. How­ ever, then, the representation of the complex structure of the system will be composed of a number of instances of the atomic formula and synthesizing, restruc­ turing and analyzing the structure should be achieved by means of the logical infer­ ence. It is an inefficient way of pro­ cessing the structure. Because these processing can be formalized to a large extent by viewing the entity-components relation as the set-elements relation, an efficient procedure to deal with the : structure can be defined without loss of generality. For this purpose we modify the syntax of predicate logic to restrict the scope of the quantifiers just to the i~f~renced structure. We call this system multi layered logic (MLL in short).

II Expression in MLL

The definition of MLL is mostly the same with the ordinary first order logic except the scope of each variable is restricted to a specified set and also the set can be an abstract entity in the hierarchical structure mentioned in the last section viewing the collection of the lower level entities as the set.

There is the concept of predicate logic with the restricted domain of variables, named many sorted logic (MSL in short). Here, the formula (l;tx) [(MAN x) ~(MORTAL x)] in the ordinary first order logic is written as (l;t x/man) (MORTAL x) where the variable x is restricted to the set 'man'.

Now referring to the hierarchical structure of (upper half of) Fig.!, let's consider an expression "There is some polygon in the polyhedron H such that, for every edge line in this polygon, its length is ~1". This is the case where the object being described is an edge line which is referred to not directly but indirectly entities (polygon). through the known entity H via at the intermediate level Let's try to represent it by using MSL. "Some polygon in H" part is denoted (3x/H), where x represents some pol ygon in H, while "for every edge line in this polygon" part, in the spirit of MSL, should be written as (Vy/x), resulting in the formula,

Note that x is a variable representing a polygon in H and at the same time a domain of another variable y (edge line). That is, the prefix of the formula reflects the given hierarchical structure. Thus MLL is the natural extension of MSL to allow an object being any abstract entity in the structure.

This idea is extended to the case where the structure is not specified but it is asked to find such a structure, given the set of primitive entities, to satisfy the specified condition. This is the case of automatic synthesis of the structure using the set of components L. In the syntax of multi layered logic, a symbol * is used to denote a power-set. Let *L denote the power-set of L (but the empty set is excluded). For example, if L is a set of lines, then *L can be interpreted as a set comprising all poly­ gons compos·d of lines in L. Similarly, *(*L) defines a set that comprises all polyhedra composed of L. In general, n­ th order power-set is defined recursively *nL=* (*"11-1 L).

Suppose to ask the system to synthe­ size a polyhedron of the volume ~b by using the given set of the lines L as the edge lines. Then the system should obtain at first the set s of polygons as the subset of *L, and then, a set of polyhedra v as the subset of *S which, in turn, is a subset of *2L. The condition of an element x of *L being a polygon is that a chain of lines contained in x forms an elementary cycle and every line in this chain is on the same plane. Let the con­ dition be represented (POLYGON x). Simi­ larly, the condition of an entity y in *2L being a polyhedron is that y satisfies Eular equation. Let the condition be represented (POLYHED y x) · Then the requirement is represented, (3y/*ZL) (Vx/y) [(POLYHED y x)A

(POLYGON X)(\ (VOLUME y ~b) 1. ($2)

III Properties of Multi Layered Logic

Suppose, for example, say X and Y, are composed of primitive components, Fig.l. Then both (Yx/Xl (Yy/x) (F y) two structures, of the same set L, as shown in ($3a)

<Vu/Y) (l;iV/u) ('rjw/v) (F w) are legal expressions and are to ( \;/ z/L) (F z) which contains essential information involved We .call it the base expression. t~~ system should obtain expression for the formula like ($3b) equivalent only the therein. Then the base ( $3) ·

Assume that there is a common ground level and a level is assigned to each entity relative to this ground level. An i-th level entity is denoted x< ·

We call hereafter the quantifier­ variable-domain triple, (Q x/X), QVD in short where Q represents either 'rj or 3 . As shown in ($3), the representation of the prefix part becomes different even with the same matrix, depending on the structure referenced by the formula. Hence the set of the variables, sa~X, be­ longing to a structure and appearing in the prefix is not equel to the set X' of the variables in the same structure but appearing in the matrix. Let the highest level and the lowest level of the vari­ ables in X be n and k while those of the variables in X' be m and 1 respectively. For example, in case of ($3b), X={u, v, w\ , X'=\w\, n=i+2, k=i, m=i+l, l=i. In general, n~m and l£k. More than one groups of variables belonging to the different structures can appear in the same formula. The order of QVD in the prefix affects the meaning of the expres­ sion. In case of MLL, however, this order -meaning mapping is not one-to-one as is the case of ordinary predicate logic, because, for the variables belonging to the same structure, the order in the structure, from the top to the bottom, precedes the order in the prefix.

For example, compare (3xi+l /X) (Vy;xi ... l) ( F y) with (Vy/xi+l) (3 xi ... l /X) ( F y) · Both of them are defined in relation to the structure X of Fig.!. The orders of variables in the prefix and the structure referenced coincide in the first one while the orders differ in the second one. However, y can not be specified unless x~l is fixed, and the structural order ac­ quires a priority. Then we interprete the second formula the same as the first one.

Suppose the formula is not in the base form. It is possible to modify the structure, by the following theorems, so that both the highest level and the lowest level of the variables involved in the prefix and in the matrix agree, still keeping the logical equivalence of the formulas.

Theorem : non'-base· There is a base formual for any formula.

Refer to [ 5 ] for the obtain the base formula. procedure to In the following, therefore, we consider only the base formula, that is, m=n and k=l.

IV Inference of MLL

We can obtain an inference rule for MLL as the modification of the resolution principle.

A. Standard Form

A formula of MLL is standardized by the same procedure as the ordinary case except a few differences as the follow­ ings. First, because the order in the prefix of variables belonging to the same structure has no effect, Skorem function replacing a variable comprises only variables belonging to the other structure as the arguments. Second, the domain specified to each variable should be remained. It is kept in the form of the variable-domain pair x/X denoting X is the domain of x.

Then the formula, for example, (l;fx 1 /X) (3y 1 /Y) (lfy 0 /y') (3x 0 /x 1 )

is transformed to (F x 1 /X, g(x 1 /X)/Y, y 0 /g(x 1 /X)). Here xo is replaced by f (yo /y'), but because y 1 another function g (x 1 /X), tuted into yl in f (yo;yt) f(y 0 /g(x 1 /X)). ( F x' xo y' yo ) f (yo /g (x'/X)) /x', the function is replaced by it is substi­ resul ting in

B. Unification

Suppose two sets of clauses are given. A most general unifier has to be found between them. In case of MLL, not only the variables but their domains should be unified.

The pair of formulas are unifiable if ahd only if the condition shown in Table 1 is met on the set-theoretical relation between the domains of the highest level v~riables involved (denoted here X and Y) , as well as the ordinary unifiability condition on terms (variables, functions and constants). Table 1 also shows the unified domain appearing in the resolvent. As an entity is the domain of the next

X,

Q ): combination of quantifires y in both formulas. Y domains of variables

Table 1 Condition on domains for

unifiability ·

lower level variables, that the uppper level variable is unified means that the domains of the next lower level variables are unified and the condition of Table 1 is automatically satisfied. Hence, no consideration on the domain is necessary at all for lower level variables in the same structure.

The condition of unifiability on the domain is XCV and YnW~¢. Then the resolvent is

"'(G a' /X, g(y 1 /Z)/a 1 ,

y 1 /Z, f(g(y 1 /Z)/a 1 )jyl)

where Z.=YnW.

Before closing this section, we break further down the conditions presented . in Table 1. It is necessary when either or both of X and y is of the form x·=*m A, because not X but A is the known quantity and therefore the condition must be expressed in terms of A.

Let xm~l and ym~t denote the highest level known entities and Ai and Bi be the i-th level known entities. Then Table 2 shows how the relations between the domains listed in Table 1 are broken down to those of known quantities. In this table, the symbol ~ xs denotes a set of entities at the level s-r and composing a specific structure xs of the level s. The symbol '--' shows that the relation does not hold.

In Table 2, both non-specific struc­ tures X and Y at the level m+l are assumed being composed of the i-th level entities. In general, however, it is possible that the levels of component sets differ, that is, X=*m-t.,.l c and Y=*m:i·l D, i~j, where C and Dare the known entities of the level i and j respectively. With­ out loss of generality, we assume i< j. Then the test for X-:;,Y, y-:;,x and XnY'f¢ is further broken down to

where D=l D,' , Di , ··· · ·} The new domains in the resolvent for the cases (1) and (3) are *j-l.D and *H(UDk) s.t.(C:Jj-~- 1 DJC') respectively. ~<

Table 2 Equivalent set-theoretical relations and new domains

V Conclusion

A modification of predicate logic, called multi layered logic, has been dis­ cussed. It was designed as the knowledge representation language for describing the systems that uses engineering knowledge to support the hierarchical style of system analysis and design. A multi level data structure was used to represent the complex systems in which an abstract entity at a level of abstraction is formed as the collection of the entities at the next lower level. Multi layered logic adapts to this structure of th~ system and meets the conditions for supporting analysis and design of complex systems.