A Computational Structure for the Propositional Calculus

1 Introduction

. Despite the l<?~g history and descriptive simpliCity. of. the propos1.honal calculus, practical aspects of .1ts 1mplementahon on the computer remain an achve area of study ([1] - [8]). Boolean logic has always been a powerful tool in its own right, and, mo~e recently, boolean modules have come to play an mtegral role in constraint logic programming ([2], [4], (6], (7]). The methodology described in this paper differs from these others; it does not involve t~n~-rewriting ([3],. [5]), production systems ((7]), or ~1m!lar, symbol-onented approaches ((1]). Rather, 1t lS somewhat of a throwback, relying on a representation in disjunctive normal form. However the r~presentation is not canonical (not unique): and, m exchange, it possesses a flexibility which overc?mes II_lany of the combinatorial problems assoc1ated w1th truth tables and such techniques (c.f., (8]). The algorithm, which has been imple­ mented in PASCAL, successfully solves what are variable so that, for example, in a univer§e of three variables the elementary conjunction ABC (A and B and not C) is internally represented by the three digit binary word 110. A disjunction ("or") of ele­ mentary terms is represented by a list of words, and boolean manipulations of these expressions are accomplished by applying bitwise "and" to pairs of words and concatenating lists. However, a moment's reflection reveals that, even for relatively simple problems, the combinatorial burden can become enormous. For example, in the above con­ text, the simple proposition A (i.e., A is true) would require :{Qur t~ms foLJts representation, A= ABC V ABC V ABC V ABC, whil~ in a universe of N variables it would result in 2 -l terms. In contrast, one's intuitive notion of the proposition A might read: (a) A = 1 and (b) the other variables are "don't care". We propose to formalize this description by introducing a new symbol !. which means "any", i.e., 0 or 1. The proposition A then takes the more succinct form !!.!. (or N !.'s if there are N variables). The "1" is underlined because it no longer represents a single binary digit; each place in this representation must allow for at least three symbols, Q, !, or !.· Although not obvious, it turns out that this representation is sufficiently compact to overcome · the combinatorial difficulties faced in solving most practical problems.

This work was funded by code 221, NUSC, Newport, RI under ONT Code 23 program element 62314N.

2 Representation

We introduce four symbols :£,, Q, !, and !. which, semantically, are intended to stand for "inconsistent (empty)", "false", "true", and "any (true or false)" with respect to a single boolean variable. More precisely, they represent sets of values which the variable may assume

Implementation on a computer requires four numbers which we assign by means of two binary digits:

2 One could use the symbol ¢> instead of !;; to reflect that this is the null set; however , in (1), !;; is visualized as one of four symbols describing the constraints put on the range of a single boolean variable. We reserve for ¢> the more gen­ eral meaning of the null set of values in the (vector space) of all the variables .

Some useful computational aspects of the represen­ tation (2) will be described later. For the moment, we note that it was specifically chosen to possess the following property: set intersections in (1) correspond to a bitwise "AND" of two-digit binary words in (2). That is,

where A is taken to mean either set intersection or bitwise AND, depending on whether we are speak­ ing of the interpretation, (1), or of the internal representation, (2). More precisely, let a two-bit computer word w A represent the set of values of A and wB those of B, then the set of values of A A B is represented by w A AND wB.

More generally, we shall be dealing with N variables, each represented by a "digit" of the form (2) giving a total of N quaternary digits (2N binary digits). As described in the introduction these digits are interpreted as a conjunction ("anding") of the corresponding variables. For_example, with N = 3, the statement AC A B takes the form 1 * 1 A * 0 * = 1 0 1. Denoting these words by lower case letters, we-write general propositional expres­ sions in the form x1 V x 2 V x 3 · · · and store them as lists of words xi. This is simply a disjunctive normal form with conjunctions of variables (terms) represented by words, and a disjunction of terms stored as a list of those words. Thus, if P and Q are two propositions given by P = Vxi -+ list of xi and

where XiY· is the bitwise AND of xi and yi' and the 1 df ... tdb" arrow stan s or 1s represen e y.

The actual construction of a proposition in the computer is straightforward. Negation is passed through to predicate letters which are realized by

where Ak is the k 1 h variable. The expression itself is built up, recursively, by performing A and V opera­ tions on subexpressions according to (4a) and (4b~. Equals and implication are replaced by ~n appropn­ ate combination of-, A, and V. There 1s also some merging of terms as described in the next section.

Let us recapitulate in the form of several remarks:

1. An expression in the above representation may be viewed on three levels: as a proposition involv­ ing predicate variables, as the set of possible values assumed by the variables when they satisfy the pro­ position, or as a list of words with binary (alterna­ tively quaternary) digits. For example, a single vari­ able A, under no constraints is represented by .! = {0, 1} = Q U .! = -A V A. In a world of two vari­ ables this becomes * *. If we add to that world the proposition A = 1, that is constrain ourselves to the set .!.!, then we get~.! A .!.! = .!.!· Next, assert­ ing B = 0 we get AB = .!.!A.!Q = lQ.. Finally, if we insist that also A = 0, we have ABA = 10 A 0 * = ~Q = ,P, the empty set. That is, we have -a cofi­ tradiction. As propositions (constraints) are added, we get nested, decreasing sets of variable values.
2. ii) Adding new variables is no problem since one universe may be embedded in a larger one simply by adding digits with their values set to .! .
3. iii) The reader may have noticed that we did not supply a set of relations similar to (3) for the opera­ tor V. One can do this most easily by taking its dual; namely, transforming by ~-+ .!· Q -+ ,!, 1-+ 0, *-+ E, and A-+ V. However, in the above representation~ the resulting relations are not partic­ ularly useful since they do not extend to words: whereas the conjunction of two words xAy is given by the conjunction of its digits, the disjunction xVy does not equal the disjunction of its digits. That is, Q.! V .!.! -T .!.! even though Q V.! = .! and 1 v. = ·.
4. iv) Nevertheless, it is worth noting that Q V.! = .! . In fact, it is quite natural to speak of set inclu­ sion; e.g., Q ~ .! , .! ~ .! , etc. These relations play a role in reducing the number of terms in an expression.
5. Our representation for a set of values (i.e., for a proposition) is not unique. For example A VB is given by.!.! V .!.! = .!QV .!.! = .!.! V .!Q.
6. vi) A word containing at least one digit ~ implies the null set; i.e., that there is no set of values for the variables in the universe of discourse satisfying the constraints of that word. Said differently, if the set of possible values of at least one component of a vector is empty, then the set of values (i.e., of N­ tuplets) for that vector must also be empty. Words which are tfo are irrelevant when they appear in a dis­ junction, so they are simply omitted in the corresponding list. In symbols, x V tfo = x. If all the words in an expression reduce to ¢J, then that expression is the empty list, and the proposition(s) which it represents contains a contradiction. For example, (A VB) A -B becomes (.!.! V .!.!) A .!Q .:: .!Q V .!~ = .!Q V ¢J = .!Q = A(-B), while A ABA B = .!.!A.!.!A.!Q = .!~ = ¢J ·

This is a consequence of using words to represent conjunc­ tions (intersections) of variables (values). The alternative would be words as disjunctions and lists as conjunctions which would lead to a conjunctive normal form.

3 Merging

Except for the introduction of .! and ~. our representation is fairly trivial. The outstanding question is whether it is sufficiently powerful to overcome the combinatorial difficulties that beset many practical problems. (Since the general prob­ lem is NP-complete, it is in grave doubt whether these difficulties can ever be completely mastered [10].) The answer, as indicated in the introduction, is a qualified "yes". It does, however, seem neces­ sary to remove null words and to include the simple merging operation described below.

When they occur, combinatorial problems exhibit themselves in the length of the "OR" lists. For example, ANDing a list of m words with one of n words has the potential for producing a list of mn words. Some products will be ¢J and, hence, disap­ pear, but, at the very least, we must also remove duplications of words and, preferably, perform other reductions as well. It turns out that for most problems it is sufficient to recognize set inclusions; i.e., if x ~ y, then one replaces x V y with y. Thl~ process is straightforward. In fact, letting x s denote the s 111 digit of x, we have

The implementation of (6) is inexpensive (see sec­ tion 4), and the combinatorial savings are enormous. This is true even though a list of n words can require up to n(n+1) comparisons to check for all inclusions. 4 In fact, experience indicates that testing for inclusion is critical in large problems.

Obviously, many other merging operations are possible. For example, one may consider combining words which differ in a single digit; e.g., Q.!.!.! VQQ.!.! = Q.!.!.!· This computation is only slightly more demanding than inclusion; however, if one wishes to carry the reduction as far as possible, repeated passes on expressions are necessary. More significantly, limited testing seems to indicate that such combining is not particularly beneficial; the increased expense outweighs combinatorial benefits. Still, it does seem reasonable to employ this pro­ cedure at strategic points; for example, as the final operation in incorporating a knowledge base.

4 Implications and Queries

A basic goal of our system is to. prove theorems P =;. Q, or, equivalently, gtven a knowledge base P, to verify a query Q. Proving an implication or establishing a proposition is tan­ tamount to showing that it holds for all values of its variables. More precisely, P =;. Q if and only if the set of values QV -P is the entire universe. The non­ uniqueness of our representation makes direct verifi­ cation difficult, but this causes no inconvenience since we may employ the equivalent statement -Q/\P = </J. Often P will be a knowledge base which has already been input (and reduced). In that case various queries Q can be checked by forming -Q, intersecting it with P, and checking whether the resulting expression is </J. More generally, we can also intersect P with Q, to obtain one of three con­ clusions, "Q follows", "-Q follows", or "Q may nei­ ther be proved true nor false from the data P." Such a system evaluates expressions as logically valid, logically false, or satisfiable but not valid; thus, negation as failure never becomes an issue.

Note that repeated passes are not necessary since one only deletes redundant words, never creating new ones.

There is a projection procedure which allows one to consider only the relevant variables in prov­ ing a proposition and which has the potential to speed up processing, particularly in the presence of a large number of variables. We note that if x con­ tains a variable not appearing in y (i.e., whose digit in y is ~), then the intersection of the two digits is not :g and, hence, may be omitted in the determina­ tion of whether x/\y = </J. Consequently, one would expect to simplify the proof of P = Q by projecting P and Q onto their common variables. This removes irrelevant constraints and, hopefully, a number of terms. In the presence of a large number of vari­ ables requiring several computer words for their representation, computational gains at a more basic level may also be achieved.

Formalizing the above suggestion, we define the varset of a word x to be the set of variables active in (constrained by) x and denote it by

(Note that the null set </J, conceived as a word con­ taining all :g's, has all its variables constrained; each variable's set of values is empty.) Next, the varset of an expression is defined as the union of the varsets of its words

The projection of a proper (non-null) word x on a varset V is defined by

that is, it retains the constraints only on those vari­ ables which are in V. The others become uncon­ strained; they do not appear when the expression is written as a function of predicate letters.._ This is best illustrated by an example. Let x = AC = l.!Q. Then the active variables in x are A and C, and Vx = {1, 3}. Now, suppose that we wish to proiect x on the varset V c = {3}, we have Tiv AC = - c TI{ 3 }(1~Q) = ~~Q = C. Proceeding to propositions, we simplify things by supposing that the words in an expression are always proper; i.e., ~1 words equivalent to <P are removed as they occur. We then define the projection of a proposition P = Vxi onto the varset V by

We remark that TI is a true projection operator (idempotent) and has the property TI 1 TI 2 = TI 2 TI 1 , Also, several useful relationships hold: V 0 = V_ 0 , TI 0 P = TIQ/\Pp, etc.

Finally, we incorporate these concepts into a procedure for testing whether P/\Q = <P: (a) Deter­ mine the varsets of P and Q, and intersect them to form V ~ VpnV 0 . 6 (b) Project P and Q onto V obtaining P' = TivP and Q' = TivQ· (c) Check whether P'/\Q' = </J. (a), (b), and (c) may by for­ mally justified by the following argument: From (7) and (9), with x-;e<P and y-;e¢J, we have xy=<P if and only if 3s s.t. x<s>y<s>=<P which implies x<s>,e~ and y<s>,e~ which is true if and only if s<Vx/\ VY. The remainder follows from (1).

Aside from reducing the number of variables in a proof, projections may be used in their own right. An interesting example lies in their applica­ tion to the so-called fields of production which were introduced in [7]. To get all statements Q which fol­ low from P and which only contain certain variables or contain a particular number of variables (e.g., at most three predicate letters), one simply projects P onto the desired variable space. Other methods for speeding up deductions, such as the special treat­ ment of binary relations between primitives (e.g., A=B and A=B), have not yet been pursued; how­ ever, the bare skeleton, just with inclusion and no projections, seems adequate for solving many, or even most, practical problems efficiently.

5 Software Notes

It is clearly important that the various opera­ tions described in this paper be efficiently imple­ mented. One of the most frequent, but less obvi­ ous, is testing a word for the presence of the digit :g. To facilitate this test our software employs two words of N bits each rather than one word of 2N bits to represent N variables. We designate these words by X 0 and xe to indicate the odd and even digits of x. Under such an implementation, one has

5 Such a scheme is advisable since it results in much more efficient computation. By P - t/1 we shall mean the empty list. Note that a proposition reduces to ¢i if and only if it contains a contradiction.

6 Note that if V =¢, then P ;P Q and P ;P -Q.

where OR is bitwise "or". This representation is also useful for projection. A varset is implemented as a single binary word v of N bits with a bit of 1 indicating the presence of a variable. The even and odd parts of the projection of x onto v are then given by (x 0 OR -v) and (xe OR -v) respectively. Finally, recognizing an inclusion is straightforward: x~y if and only if (x OR y) = y; i.e., this relation must hold for the even and odd parts of x and y respectively.

6 Conclusion

We have presented a practical, structured representation for the propositional calculus. The notation is such that a given expression may be interpreted as a symbolic formula, as a union of sets, or as a list of binary (quaternary) words imple­ mented on a computer. The workability of our methodology, however, is empirical. It springs from the fact that, despite its naivete, the implementation is sufficiently powerful to circumvent the combina­ torial difficulties posed by many problems. It is felt that this approach, which is simple and highly struc­ tured, and perhaps more procedural than many oth­ ers, may be recommended for its ease of interpreta­ tion and for incorporation as a tool in larger sys­ tems.