Induction of Concepts in the Predicate Calculus
Proceedings of the Fourth International Joint Conference on Artificial Intelligence. Learning Debugging And Automatic Programming. Pages 281-286.
© 1975 International Joint Conferences on Artificial Intelligence
Abstract
Positive and negative instances of a concept are assumed to be described by a conjunction of literals in the predicate calculus, with terms limited to constants and universally quantified variables. A ~raph representation of a conjunction of literals, called a "product graph", is introduced. It is desirable to merge positive instances by generalization, while maintaining discrimination against negative instances. This is accomplished by an induction procedure which operates on the product graph form of these positive and negative instances. The correctness of the procedure is proven, together with several related results of direct practical significance. This work is directed to the goal of providing a formal model for the inductive processes which are observed in artificial intelligence studies in specialized areas.
- Banerji, R.B. Theory of Problem Solving, chapter 5, "Learning and Generalization", American Elsevier, 1969, pp. 153-177.
- Brown, J.S. Steps Toward Automatic Theory Formation. Proceedings of the Third lntl. Joint Conference on Artificial Intefl~e, 1973, pp.-r21-129. IJCAI
- Evans, T.G. A Program for the Solution of Geometric-Analogy Intelligence Test Questions . Semantic Information Processing, M. Minsky (ed.), MIT Press, 1968, pp. 271- 353.
- Hunt, E.B., Marin, J. and Stone, P.J. Experi- ments in Induction. Academic Press, 1966.
- Kling, R.E. Reasoning by Analogy with Applications to Heuristic Problem Solving: A Case Study. Ph.D. thesis, Stanford University, 1971.
- Meltzer, B. Generation of Hypotheses and Theories. Nature, Vol. 225, March 7, 1970.
- Michalski, R.s:--Learning by Inductive In- ference. NATO Seminar on Computer Oriented Learning Processes, Aug. 26-Sept. 7, 1974.
- Plotkin, G.D. Automatic Methods of Inductive Inference. Ph.D. thesis, Dept. of Machine Intelligence and Perception, University of Edinburgh, 1971.
- Towster, E. Several Methods of Concept- Formation by Computer. Ph.D. thesis, University of Wisconsin, 1970.
- Webster's Third New Intl. Dictionary of the English Language, Merriam, 1969.
- Williams, D.S. Computer Program Organization Induced from Problem Examples. Representa- tion and Meaning, H.A. Simon and L. Siklossy (eds.), Prentice-Hall, 1972, pp. 143-205.
- Winston, P.H. Learning Structural Descrip- tions from Examples. Ph.D. thesis, Massachusetts Institute of Technology, 1970.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1. Introduction
Induction may be broadly defined as "reason ing from a part to a whole, from particulars to generals, or from the individual to the universal" (10]. Consistent with this, we view "induction" as a computational process, and a "generalization" as a statement computed by that process.
The present work is guided by the belief that general purpose induction procedures can hu for mulated which would be independent of the arti ficial intelligence problem domain. It is speci fically concerned with the induction of concepts from positive and negative instances described in the predicate calculus, with terms limited to con stants and universally quantified variables.
Inductive processes in artificial intelli gence have been studied from several aspects: visual analogies (3], propositional logic concept learning [4,9], analogies in predicate calculus theorem proving [5], IQ test completion problems (11], theory formation from a data base [2], visual concept learning from examples [12], and induction as a dual of deductive theorem proving in the predicate calculus [1,6,8], or in a gen erali zati C·J : .;,f the predicate calculus [7]. The present work may be regarded as a continuance of the concept learning research of Hunt and Towster, amongs others, to the predicate calculus. Its viewpoint and many of the concepts are derived
from Plotkin.
Throughout, each positive and negative in stance of a concept is assumed to be described by a conjunction of literals in the predicate calcu lus (not necessarily first order). Section 2 de fines terminology to be employed, of which the most significant is the concept of a "maximal, consistent, unifying generalization", and contains some general observations on generalizations. With this background, a problem statement is then
Steven A. Vere* Department of Information Engineering University of Illinois at Chicago Circle
given in the defined vocabulary. Section 3 intro duces the "product graph", a graph representation of a conjunction of literals, which serves as a convenient medium for the discussion of the induc tion process. This process is accomplished by straightforward operations on these product graphs. Section 4 considers the application of product graphs to the question of the "consis tency" of a generalization in view of negative in stances. Section 5 contains concluding remarks.
2. Generalization in the Predicate Calculus
2.1 lntroductoff Definitions; Properties of Generalizat1ons
An n-ary predicate will be represented by a list of n + 1 elements: (tl t 2 ... tn+l). tl understood to repre~ent th~ predicate symool, but is other~ise undistinguished from other elements. Each ti is a term, which may be either a constant, represented by lower case Roman letters, or a variable, represented by upper case Roman letters. All variables are assumed to be universally quan tified. A literal is such a list of terms, optionally prefixed by the logical inverse oper ator " - "· For example, (a X c) and -(e f) are both l)terals. A product is a conjunction of lit erals.
where each ti is a term, each Vi is a variable, and each ii 1s a list of positive integers. A consistency restriction is made that if the same term appears to the left of the slash in two dif ferent elements of the substitution set, then the associated lists must be disjoint. For example, {a/X(l,4,5), b/Y(2), a/Z(2,3)} is a legitimate substitution but {a/X(l,4,5), a/Z(2,3,4)} is not.
If p is a product and a is such a substitu tion, pa represents the product obtained from p by simultaneously replacing the occurrences of term t., in the positions specified by the list 1., by tAe variable v .. For example, for a= {a/X(l,2), b/Y(l)}, the Efiglish interpretation reads: "Re place the first and second occurrences of a by X
and the first occurrence of b by Y." Thus if
Note especially that the third occurrence of a in p remains unchanged.
* This work was partially supported by DIIEI': Grant No. US-PHS-ROl-MB-00114-01.
An additional restriction will be placed on substitutions: no variable in p may appear to the right of the slash in a substitutio~ ap~lied to P· For example, if 6 = {a/X(l)}, appltcat1on of e2 to p = (p a X) ii prohibited since X already 2 · · · · ry to occurs in p . Th1s restr1ct1on 1s necessa ensure that 2 p is always an instance of p6. A use ful convention is to allow the list ~ . to be omitted if all occurrences of t. are ~o be re placed by v.-.- It should also b~ clear that a substitutioA in general presumes a particular left to riBht ordering of the literals of a product .
Let p CP · denote that the literals compris ing producfp 1 ire a subset of t~e literals CC?ft'Pr~s inB product p . A product ~ 1s a gene:al1~at1on of a product~ iff there exths a subst1tut1on e such that p c 2 p e. This will be denoted by p < p 2 . PArexlmple, (p X Y) ~ (p a b) A (q a c) slnce (p X Y) ~ (p X Y) A (q X c) (p a b) A (q a c) {a/X, b/Y}
A product p is a unifying ~eneralization for a set of productt {p 1 , p 2 , ... ,p~ .iff Pa . ~ ~i' 1 < i < r. For example, (p a XJ 1s a un1fy1ng &eneralization for (p a b), (p a c), and (p a g).
A substitution 6 il an alphabetic variant substitution, written 6 v, iff each ele~nt g~ the substitution has the form Vi 1 /Vi 2, that 1s 6 merely chanBeS the names of the variables in a product in a consistent manner. If P 1 and P2 are two arbitrary products, three elementary and easily demonstrable properties of generalizations . are:
Pl: av (Pt ~ p2) 'iv(p2 ~ P1? ~ (pl = P2 6 . ~ for some e . In th1s case p 1s a tr1v1al &eneralization of p~ and convArsely.
P2: If p 1 ~ p 2 and no ~ v exists such that P1 = p eav either p c p 2 e 1 for some 6l, or pi= p;62, wherA e Is not an alph betic var1ant substitutian. This situation will be denoted by p 1 < p 2 .
P3: (transitivity) (P 1 ~ P2) A (p2 ~ P3)
As examples of the above,
(p a b) < (p a b) A (q a c)
(p X b) < (p a b) _
where {U/X, Z/Y} is an alphabetic variant substitution.
If -y~ p and -y 1 ~ p 2 , -yl is a ~aximal unifying &enerllization of p 1 nd P 2 1ff no pro duct r 2 exists such that r 1 < -y2, ~ 2 ~ P 1 , and y < p . There may be a numbet o~d1st1nct max i~ai ~ifying generalizations of two products, ignoring variants caused by alphabetic variant substitutions. Let MG(p 1 , p 2 ) represent the set of all generalizations y such that:
- y is a maximal unifying generalization of Pl and p2; av
- no &ener~lization y' and 6 exiiS such that y' £ MG(p 1 , p 2 ) andy= y'6
Theorem 1: A product y 1 is a unifying generaliza tion of products p 1 and p iff there
exists a product ym £ M�(~ 1 · p 2 ) such Proof:
that y 1 < -y . (+) If -y- iW a unifying generalization of p an! p , it must be either max imal1or non~maximal. If it is max imal, there is a product y £ h . meav MG(p 1 , p 2 ) such tat Y 1 . = Ym · . Hence, Yt ~ y . If Yt 1s non-max1mal, it is becausemanother unifyinB gener alization y2 exists such that Yt < 'Y2· Y2 must have more literals or fewer variables than y 1 , or both. No uni fying generalization may have more literals or fewer variables than the extrema of these parameters for Pt and p 2 , which are of course finite. Consequently, there will in ~eneral be a finite chain of generalizations y < y < · · · < y , wh~re ~ is a mAxima~ unifying geWeral1zat1~n. By the transitivity property, Y1 ~ Ym· From the definition of MG(P 1 · P2), Ym is either an element of this set or an alphabetic vari~nt of ~n ~lement. (~) y is a max1mal un1fy1ng Beneralizati~n of Pt and P2· and Yl ~ Y~· Since ym ~ Pt and Ym ~ P2· ransl tivity gives. Yt ~ Pt and Yt . ~ Pz· and so y 1 is a unifying &eneral1zat1on of Pt and P2·
Thus any of the potentially larBe number of all unifying generalizations of p and p 2 can be ob tained by generalizing some element of MG(p 1 ,p 2 ), a much smaller set .
2.2 Problem Statement--Simplification of Concepts by Induction
A concept may be defined "in extension" by exhibiting positive and negative instances of the concept. It is assumed here that each instance is described by a product in the subset of the predi cate calculus defined in subsection 2.1 . Hence forth, let P· represent a product describing a positive ins!ance, and vi a product describing a negative instance. Then the followin& di sjunctive normal form expressions can represent a concept K:

If for some indices i 1 and i 2 , Pi = vi 2 ' .the rep resentation is incons1stent. Eac~ Pi is a posi tive product; each vi is a negative produc~ On the other hand, a nesative literal is a predicate pre fixed by " - "; a positiye literal is a predicate not not prefixed by " '" "·
In the above context, a useful generalization will be one which unifies at least two posit ive products or two negative products, since the con cept repre~entation is thereby simplified . How ever, it is essential that this ~eneralization not destroy discrimination between K and -K. Because of problem symmetry, henceforth only generaliza tions of positive products will be discussed ; iden tical arguments will apply to generalization of ncsative products . If y is a seneralization of a product Pit· y is consistent iffY L vi for all i .
.Problem: Given a concept definition in extension, as in (1), how can consistent, unifying generalizations of the positive products be computed in order to simplify the def inition?
It is to this specific problem that the following discussions are addressed .
3. The Product Graph as an Induction Medium
In this section an induction procedure is for mulated with respect to a graph representation of products, called a "product graph" . Unlike some earlier graph representations of relational infor mation, the product graph is not limited to binary relations. It represents literals of arbitrary dimension in a uniform manner. The overall effect of the induction procedure is to merge pairs of positive products. It may be iteratively applied until all positive products have been merged, or until no mnximnl consistent generalizations exist for any pair of products. This procedure is pre cisely described and its correctness is proven.
The product graph representation has proper ties that make it useful as an induction medium. If a product PI is · generalization of another pro duct p 2 , the product graph of PI is isomorphic to a sub graph of the product graph of p 2 . A "great est common subgraph" of two product graphs is the graph of a maximal unifying generalization of thOS( two products. Thus the problem of computing max imal unifying generalizations is transformed to the computation of maximal isomorphic subgraphs.
3. 1 Product Graphs
A product graph is a 6-tuple system (L, C, cS, a, K, a), where
- L is a finite set of literal nodes;
- C is a finite set of constant nodes;
- cS is the literal dimension function: L + Z , where Z+ is the set of positive integers; +
- 4 . a is the literal sign function : L + {+, -};
- K is the literal content partial function : L x Z + C, such that
i f ( R., i , c) e: ~ , then i e: { 1 , 2 , ... , cS( R.) }
- a is the literal adjacency relation, a finite subset of Z x Z x L x L, such that
- (i 1 , i 2 : t 1 ,·t2)£ a iff (i2, i 1 , t 2 , t 1 )e: ala symmetry property);
- if (i 1, i 2 , t 1 , t~)e: a and (i2, i 3 , R.2, R.~): a then (I 1, I 3, t 1 , t 3 )e: a (a tran s~t~vity property);
- for all t 1, 12, e: L and i 1 i e: z if . ' 2 +. (R.l' Il· Cl) e: K and (R,2, i 2, . c2)e: K then (~ 1 , i2, R.l, R.2)e: a iff c1 = c2 (a con sistency property).
Each literal in a product will be represented .bY a unique node in L. Each distinct constant appearing in a product will be represented by a unique element of C. Variables appearing in a pro· duct will have no explicit representation. Recall that the variables are universally quantified and thus are dummy variables: their names have no significance . The literal dimension function c specifies the number of terms in each literal. For ex~ple, if >.. 1 = (abc), cS(>..) = 3. The lit eral sign function a serves to distinguish posi tive and neg·ative literals. For example, with >.. 1
as above and >..2 = - (e f), a (>.. 1 ) = + and G (>.. 2 ) = -.
The purpose of the content function K is to specify the identity and position cf constants which appear in the literals of a product. Spe cifically, if >.. 1 £Land c 1 e: C, Ki(>..l) = c1 iff the constant c 1 appears in the ith position in >.. 1 . For example, >.. 1 = (c Y e) causes the following specification of K: K1(>.. 1 ) = c and K 3 (>.. 1 ) = c.
If the same term appears in two literals of a product, these literals are adjacent in the pro duct graph. For example, the two literals in the product (a b c) A (c d e) are adjacent, since the constant c appears in both. To describe precisely the adjacency of two literals, the position of the common term in each literal must be specified. If >.. 1 ~nd >.. 2 are adjacent literals, the adjacency relation ai j(>.. 1 , >.. 2 ) represents the fact that a term whic~ appear~ in the ith position in >.. 1 also appears in the jth position in >.. 2. By the ~ym metry property of adjacencies, ai i(>.. 1, >.. 2) ++ a · . (A , >.. 1 ) for all i,j ,>.. 1 ,>.. 2 . 'consequently, it i~'pos~ible to disregard adjacencies for which i > j as redundant information.
A literal may be adjacent to itself, causing a sling in the product graph. If the same term appears in position i and position j in literal >..1, ai . (>..}' >.. 1 ) is significant. However, if i = j,'6o Information is provided, since this rela tion holds universally; it sill be ignored.
These adjacency relations are the arcs be tween literal nodes in the product graph. In an obvious way, these arcs can partition the literal nodes into disjoint blocks, with the nodes in each block forming a connected subgraph of the complete product graph. These connected subgraphs will be important in the concept of a "vacuous" general ization, which is discussed in subsection 3.4.
3.2 Product Graph Example
As an example, Figure 1 shows the product graph for the product (g X Y c) A -(c Y e) A (c f), with the individual literals identified by >..1, >..2, a1~d >.. 3 respectively. Constant nodes are shown as squares; literal nodes are shown as circles. This example incidentally demonstrates that an adja cency relation due to a common constant in two lit· erals is redundant information, which could be de rived from the content function information. This mild and occasional redundancy contributes to the desirable properties of product graphs which are next discussed.
3.3 Properties of Product Graphs
Two product graphs g1 and g 2 are isomorphic, written gl; g 2 , iff they are identical except for their literal node identifiers. That g1 is a sub graph of g 2 will be denoted by g1 £ 11 2 · That g1 is isomorphic to a subgraph or a proper subgrapfi of g 2 wi 11 be denoted by g 1 £ g 2 or g 1 c g 2 respectively. G(p) will denote the graph of prod uct p.
Product graphs have the following eas i ly demonstrable properties:
- P4 : G(p 1 ) ;;; G(p 2 ) iff Pl = p 2 eav for some eav, i.e., if product graphs are isomorphic,thecor responding products are alphabetic variants;
·...

PS: G(p 1 )£ G(p2) iff Pt ~ p2
P6: G(p1) ~ G(p 2 ) iff Pt ~ P2
P7: A product y is a maximal, unifying general ization o! P1 and p2 iff:
1. G(y) S G(Pl)
2. G(y) <; G(p 2 )
a. G(y) c g 4 b. g4 ~ G(pl)
3. no graph g~ exists such that
c. g4 ~ G(Pz) The first tw-o conditions specify that y is a unifying generalization; the third specifies that y is maximal.
The properties PS, P6, and P7 are significant for showing that generalizations may be computed with product graphs, as elaborated below.
3.4 Computing Maximal Unifying Generalizations
The procedure for obtaining the graph of a maximal unifying generalization requires a few additional concepts. Two literal nodes Al and A2 are thtentially similar, written psim (A 1 , A 2 ), iff t ey meet these conditions:
Cl: o (At) = o (A2). i.e., Al and A 2 have the same sign;
C2: ~ (A1) = ~CA2 >, i.e . , Al and A 2 have the same number of terms;
C3 : Al and A 2 appear in separate products. C3 afftrms that only literal nodes in separate product graphs shall be eliRible: we do not wish to merge literals in the same product.
Two literal nodes which are potentially similar will be called a pair. Two pairs which have a node in common are alternative pairs. For example, Pt = (A 1 , A2) and p 2 = (A 1 , A 3 ) areal ternative pairs since At is a constituent of both. Let P (pl, p2) denote the set of all pairs for two arbitrary products n 1 and p 2 . Certain subsets of P(pl· Pz) will be of special importance. We de fine s c CP(p 1 , n 2 ) iff:
1. s <; P(pl, P2)
- no two pairs in s are alternative pairs. Stated differently, each element of CP(p 1 , p) represents a possible 1-1 mapping between liferal nodes of Pt and Pz subject to the restriction that matched nodes have the same sign and dimension.
There is a class of generalizations which wi 11 be here calle(l "vacuous". A vacuous gener alization y is one for which a connected subgraph of G(Y) contains no constant nodes. For example, if Pt = (a b c) A (d a) and p 2 = (c a q) A (e c), the only maximal unifying generalization is (X Y Z) A (U V). It seems desirable to exclude such gen eralizations. Their exclusion will also speed the computation of the remaining non-vacuous general ization. For these advantages, we will weed out additional elements of CP(p 1 , Pz) with the con cept of "simi 1 ad ty".
Lets= {p, p 2 , .·. , Pm} be an element of CP(p 1 , P2). ·. Lel p = (A 1 , A 2 ) rep~e~ent an ~rbi trary pair 1n s. Al and A 2 are s1mtlar, wr1tten sim(A 1 , A 2 ), iff these conditions hold· · C4A(CS~C6), where
C4: psim(A 1 , A 2 )
CS: 3 i Ki(A 1 ) =.Ki(A2), i.~.! A1_and A2 have a common term 1n some pos1t1on 1.
C6: 3 i, j and (A 3 , A 4 ) £ s such that ~i,j(Al· A 3 )Aai j(A 2 , A 4 )As~m(A 3 , ~4), 1.e., AI and A 2 ~ave an tdenttcal adJacency to similar nodes.
Now let SP(p 1 , Pz) be defined such that s £ SP(p 1 , Pz) iff .
1. s r CP(p1 , Pz)
- Vi (piEs)+ sim(pi), i.e., every pair of literal nodes in s is similar;
- no s' exists such that s' £ SP(p 1 , Pz) and s cs'.
From each aggregate of pairs s in SP(p 1 , p 2 ), a product graph R can be obtained by this construc tion:
- Each pair ins is a literal node of g.
- For all pairs Pi = (A1, Az) £ s if 3j Kj(A 1 ) Kj(A2), then K·(A 1 ) is a constant node of g, and the contenl function Kj(pi) = Kj(A 1 ) is defined.
- For all pairs p = (A 1 , A2), Pb = (A 3 , A4) in s, if anl nz(A 1~ A 3 )A~l n2(A 2 , A 4 ) then the adjacency'relation ~l,nz(Pa· pb) ts defined for g.
In this way g reflects all common features of the pairs in s. Let G'(SP(p 1 , p 2 )) denote the set of graphs g constructed in this way from the pair aggregates of SP(p 1 , p 2 ), and let G(SP(p}' n2 )) denote a reduced subset of G'(SP(P 1 , p 2 ) such that g £ G(SP(p1, P2)) iff:
1. g £ G'(SP(p 1 , p 2 )), and
2. n~_g' £ G'(SP(p 1 , pz)) exists such that g cIt'.
Theoref!, 2 : Proof: A product y is a maximal, non-vacuous, unifying generalization of products n 1 and P 2 iff G(y) ; g 1 for some g 1 £ GtSP(p 1 , p 2 )). (+)Define G'(p 1 ) and G'(Pzl ~~ch that G(y) ;; G' (Pt) <; G(p 1 ) and G(y); G'(p2) <; G(p 2 )
Then of course G' (p 1 ) ;; G' (Pz). Let G(y), G' (p 1 ) and G'(Pz) be partitioned into their connected subgranhs :
G(y) = G1 (Y)UG 2 (y) U ... UGr(Y)
G' (Pl) = Gl (pl) U G2(Pt) U · · · u�~(pl)
G' (Pz) = Gj (Pz) U G:i(p2) U , , . VG' (P 2 ) ·
r It follows that the number of suhRraohs in f.(y), G'(Pt). and G'(Pz) are identical, as indicated, and Vi G!(y) ~ �~(p) ~ _ �i(P 2 ). (2) Let L(g) ~epresen! the literal nodes of an arbi trary product graph ~·
Let L(Gi(Y)) = {).Oi l· ).Q . 2 , ... , ).0. }, L(Gi(p)) = {).ti' 1 , ).li~· ' 2 , . .. , ).1~·~~}. and ( ,r {' ,. ·I L Gi (p2)) = >-2i 1' " i 2 · · · · · A2. · } · Because of (2), it must be possible to eft~lish a 1 to 1 correspondence between the nodes of these connected subgraphs. Let the binary predicate m (for match) indicate that its arguments are estab lished in this correspondence. Then V i,j m().Oi j· A~i,j,)Am(AO· ., 1.2i ·)Am(A1·,·, A2i,j). · Swce y 1s non--\rol:uous ,' ~ach (,i (yj ~ust c.:ontain dt least one constant node, and so Vi :~j 1 ,j 2 Kj 1 (A0i,j 2 ) = Kjl().li,j 7 ) = Kj 1 ().2i j 2 ) Then by condition C4 for similarity, yt simt>.Ii · , ).2i · ). Since each of these subgraphs is connect~d, con~J 2 dition CS will cause the similarity to propagate throughout the subgraphs, giving
For all i and j, let p·. = (Al· . , ).2 . . ) , and let s represent this set o}Jpairs.I'2learlyJnone of these pairs is an alternative to any other. Be fore determining if s E SP(~ 1 · p 2 ), we construct g from s in accordance with the specified construc tion:
To determine if sis in SP(p1 , p 2 ), the three conditions for membership must be examined. The first is satisfied, since the nodes matched in confirming isomorphism must necessarily be of the same sign and dimension, and be non-alternative. s was seen to be composed of such pairs. The second condition requires that each pair have the s imilarity property. This was found to be true in (3) above. To test the third condition, suppose s' exists such that s C s 1 and s'<; SP(pl, P?). Let g 1 represent the graph constructed from s . g' is non-vacuous since it is constructed from similar pairs. Since s C s 1 , it follows that g C g 1 , but g ~ G(y), so G(y) (' g 1 , which im plies that y is not maximal, contrary to fact. Thus no such s 1 can exist. Consequently, s E SP(p 1 , p?), and hence g E G'(SP(p 1 , p 2 )). Since y is maximal, no g 1 exists such that g C g', and so~ E G(SP(pl· p 2 )) also. (+) This half of the proof is accomplished by show ing that a) g 1 is the graph of a unifying general ization of p 1 and P2;
- no graph g' can exist such that reg' and g' is the graph of a unifying generalization of OJ. and
- P2· c) g satisfies the requirements for the non-vacuous property.
- It is necessary to show g 1 SG(p 1 ) and gl <;G (pz)· For all i, if).i F.: L(gl) there exists a pan ().j· ).k). where).· E L(G(p 1 )) and ).k E L (G(p2)), and sim (>-j· ~k). Th i s follows from the fact that gl is constructed from pairs of literal nodes from G(PJ) and G(p 2 ) . Then a one to one match can be established m().i· )..), m().i· ).k). This match relation then ha~ the property that
- (K n (). i) =J Kn(). .J) Finally, since g 1 is co~structed to reflect all identical adjacencies of paired nodes, V n 1· n 2 · i 1 · i 2 an 1 · n (). i ). i ) ... 2 1· 2 [ :of j 1· j 2 an 1 n ( A j A j ) A ~kl,k2 an'n2().kl·).k2)1 l· 2 1· 2 where m ( ). i 1 , ). J. ) , m ( ). i 2 ). J. ) , m ( ). i ). k ) 1 · 2 1 · 1 · and so gl ~ G(p ) and g1 ~�( p ). b) A g 1 is ass~d to ~ist sucif that g C g 1 , g' c G(p 1 ), and g 1 c G(p 2 ). Then G" lP 1) and G" (p 2 ) exist that g I ;; G" ( p ) c G ( p ) I ~ G"( 1);;: G( 1) g,. P2::'P2
The literal nodes of G"(p 1 ) and G"(p 2 ) may be paired to form a set s 1 E SP( p 1 , p 2 ) . From s 1 can be constructed a graph g" ~ G"( p 1 ) ~ G"(p 1 ) ~ g'. However if gC: g 1 ~ g", then g is not in G(CP( p 1 , P z)), which is contrary to fact. Thus no such g 1 can exist, and hence y is maximal.
- Since G{y) ~ g 1 E �{CP{pl'p 2 ))£� 1 (CP~ 1 ,p 2 )). and all graphs in G' (CP ( p 1 , p 2 )) are con structed from similar pairs, y is non-vacuous.
3 · 5 Example -- Computation of Maximal IJni fying Generalizations
For two simp]P hut nontrivial products, the sets P(p 1 , p 2 ), CP(p 1 , p~), SP(p 1 , P2), G'(SP(p1 , P2)) and G(SP(Pt· P2)) Will be exhibited. Suppose Pt~ 2 + K, where
Pt = (b x2) A (w x3) A (~: x2 r) A (s x3 x2)
P(P1, P 2 ) = {Pl, P2, P3, P4, PS, P6, P7, PS}, where
Pl (b x2), (w x6) PS (c x2 r), (s x6 xS)
P2 (b x2), (b xS) P6 ( c x2 r) , ( d x6 e)
P3 (w x3), (w x6) P7 (s x3 x2), (s x6 xS)
P4 (w x3), (b xS)
PS (s x3 x2), (d x6 e)
Alternative pairs are: P1/P2, Pl/P3, P3/P4, P2/P4, PS/P6, P6/P8, and P7/8.
11ence CP (p 1 , p 2 ) consists of the six combinations:
(Pl, P4, PS, P7), (Pl, P7, PS, PS),
(Pl, P4, P6, P7), (P2, P3, PS, P7),
(P2, P3, PS, PS) and (P2, P3, P6, P7),
as well as their subsets. The set CP is always very large, and has significance only as a theo retical construct. In practice, only SP(p 1 , P2) need be computed. SP(p1, p 2 ) = {sl, s 2 }, where s1 = {P2, P3, P7}, and s 2 = {P2, P3, P8}. The pro· duct graphs constructed from sl and s2 are shown in Figures 2a and 2b respectively. Here each lit eral node has been labelled with the pair name from which it derives. Since 2b is a subgraph of 2a, 2a constitutes the only element of G(SP(p1, p 2 )), and thus represents the only maximal, non vacuous, unifying generalization of Pl and p 2 . The linear form of 2a may then be obtained to give: (w Y) A (b Z) A (s Y Z) + K

Figure 2o Graph constru<:ted from IP2, P3, P7l

4. Determining the Consistency of a Generalization
Recall from subsection 2.2 that a generaliza tion of positive instances of a concept is incon sistent if it is also a generalization of a nega tive instance. Property P6 of subsection 3.3 sug gests a way to determine consistency.
Theorem 3: If y is a generalization of positi"~ products, y is consistent iff �(y)~ G(vi) for all i.
Proof:
If y is consistent, no vi exists such that y ~ vi· and so by pro~erty P6 no vi exists such that G(y) s; G(vi).
In other words. consistency of a generalization can be determined by verifying that its product graph is not isomorphic to a subgraph of any negative product.
The following lemma and theorem demonstrate the significance of maximal generalizations in determining the existence of ~ consistent generalization.
le11111a 1:
Proof :
Theorem 4:
Proof:
If y 1 is an inconsistent generaliza tion, no generalization of Yl is con sistent.
Yl ~ P1· Y2 ~ P2· and a negative pro duct vi exists such that .y1 ~ vi 1 · If y2 i~ any generalization of Yl· Y2 ~ Yl ~ Vi 1 or Y2 ~ Vi 1, and so y2 is also inconsistent.
If for all gk £ G(SP(p1, p 2 )), a negative product Vik exists such that gk ~ G(vi ) , then no consistent gen eralizatio~ of p 1 and P2 exists . Define Yk such that G(yk) = gk. By theorem 1, if Ya is any unify1ng generalization of p1 and P2· then y~~ Yk for some yk. However, G(yk) ;gk~ G(vik) and so by theorem 3 Yk is incon· sistent. Hence by lemma 1, Ya is also inconsistent.
To continue the example of subsection 3.5, suppose a negative product is known: vl + -K, where v 1 = (c x8 r)A(b xS)A(w x9). The product graph of v 1 is given in Figure 3. In li&ht of thi~ additional information, is the generalization graphed in Figure 2a consistent? Yes, since it is readily determined that Figure 2a is not iso morphic to a subgraph of Fi,ure 3.

5. Concluding Remarks
A precise yet mathematically parsimonious induction procedure has been described for con cepts in the predicate calculus. The product graph representation accommodates literals having an arbitrary number of terms. the computation of generalizations and the testin& of their consis tency has been achieved by comparison operations on these product graphs. The information supplied by negative instances of a concept determines if a generalization is consistent, and may serve to select between a number of distinct maximal gen eralizations. If all maximal generalizations are inconsistent, it has been shown that no consistent generalization exists. If a maximal generaliza tion is consistent, it may then be generalized further, holding short of the point where it would "cover" a negative product. A SNOBOL4 pro&ram has been written which implements and confirms the methods of this paper. Exploration of its capa bilities is in progress.
Because a generalization replaces just two products, and a number of distinct maximal &en eralizations may exist, there remains the question of strategies in the application of the induction procedure in an iterative manner to a lar&e number of positive .products.
Worthwhile departures from present theory would include concepts which are iterative orpoten tially infinite, such as the sequence abbcccdddd ··. , as well as hierarchial and recursive concepts, all of which seem essential to human perception and thought.
Acknowledgment
The author appreciatively acknowledges a number of helpful criticisms by Professor Roger Conant and the IJCAI-75 referees of an earlier version of this work.
@inproceedings{ijcai1975p43,
title = {Induction of Concepts in the Predicate Calculus},
author = {Vera, S.},
booktitle = {Proceedings of the Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-75}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Patrick Winston and Carl Hewitt},
pages = {281--286},
year = {1975},
note = {Learning Debugging And Automatic Programming},
url = {https://ijcai.org/proceedings/1975/43},
}
TY - CPAPER TI - Induction of Concepts in the Predicate Calculus AU - Vera, S. T2 - Proceedings of the Fourth International Joint Conference on Artificial Intelligence, IJCAI-75 PB - International Joint Conferences on Artificial Intelligence PY - 1975 SP - 281 EP - 286 UR - https://ijcai.org/proceedings/1975/43 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: