Journal de Chaource

Part I
Part II

If we are given information as universally quantified statements ("All objects satisfy properties A, B, ...") together with existentially quantified statements ("Some objects satisfy properties C, D, ..."), and we are asked to derive a statement of the form "All objects satisfy properties X, Y, ...", we are compelled to use only the universally quantified part of the given information. We cannot use the information of the form "Some objects are ..." to derive "All objects are ...".

We already know that our universally quantified information is equivalent to a formula of the form "For all x : [ F(x) ]", with a single variable "x" and a Boolean formula F that depends on various predicates. Let us now see what we can do with such a formula to derive consequences from it.

Consider two examples:

1. "All bald creatures are conceited. All aardvarks are bald creatures."

Denote aardvarks = A, bald creatures = B, conceited creatures = C. Then the universally quantified part of the information looks like this expression:

For all x : [B(x) -> C(x)] [A(x) -> B(x)].

Now, we can easily see that the desired consequence is "For all x : A(x)->C(x)", but we would like to avoid any heuristics that require us to guess how to proceed. We would like to obtain consequences from the given expression by an algorithm, and not by "inspecting" a graphical diagram, by guessing how to build a derivation tree, or by other heuristic methods.

We note that the formula after the quantifier can be seen as a Boolean expression F(A,B,C) in the variables A, B, and C: that is, we can temporarily ignore the fact that these are predicates depending on "x". We can then simplify this Boolean expression using the rules of Boolean algebra and bring it to the conjunctive normal form or to the disjunctive normal form:

(B -> C)(A -> B) = (B' + C)(A' + B) = B'A' + CA' + CB =: F(A,B,C).

(Here for brevity we use the notation that A+B is the logical "or", i.e. the disjunction, and AB is the logical "and", i.e. the conjunction. Recall that X->Y is the same as "Y is true as long as X is true", i.e. "Y or not X", i.e. X'+Y.)

We know that the desired consequence is a formula not containing B, so now we would like to exclude B from F(A,B,C). To do this, we use a trick: The formula F(A,B,C) is true for all x if we substitute A=A(x), B=B(x), and C=C(x). For a given x, either B(x)=0 or B(x)=1. Thus, for all x we have that either F(A,0,C)=1 or F(A,1,C)=1, or both, but we don't know which. We can write this fact concisely as a disjunction,

F(A,0,C)+F(A,1,C),

or in more verbose notation,

For all x : [ F(A(x),0,C(x)) + F(A(x), 1, C(x)) ].

This is surely a consequence of the original formula. So now we have obtained a universally quantified formula that does not contain the predicate B, which is exactly what we wanted.

Let us apply this trick to our example:

F(A,0,C)+F(A,1,C) = A' + CA' + CA' + C = A' + C = (A -> C).

Thus, we get the desired consequence, "All aardwarks are conceited".

The transformation of the formula F(A,B,C), i.e. the substitution trick that eliminates one of the variables is the cornerstone of getting consequences from Boolean expressions. This seems to be exactly what is needed to obtain solutions to all syllogisms and soriteses without any guessing.

(I have read somewhere that this substitution trick is actually a theorem due to Boole himself. The theorem can be stated as F(A)->F(0)+F(1) where F(A) is any Boolean function of a Boolean variable A.)

2. Consider an example where several predicates are used at once on an object: "All small green persons are Martians. All green Martians are intelligent."

[This kind of example is a "sorites" rather than a syllogism.]

Let us see what consequences of the form "All persons are ..." we could derive from this information.

Denote by G = "green persons", I = "intelligent persons", M = "Martians", S = "small persons". The universally quantified part of our information is

For all x : [G(x)S(x) -> M(x)] [G(x)M(x) -> I(x)].

We rewrite this formula as "For all x : F(G,I,M,S)" where F is defined as the Boolean expression

F(G,I,M,S) := (G' + S' + M)(G'+M'+I).

(Recall that (XY)' = X' + Y' in Boolean algebra.)

Now we could apply Boole's theorem to eliminate some variables, but we are perhaps not sure which variables. Let's just try to eliminate each variable, one by one. What if we eliminate G? We find already F(G=0, I, M, S)=1 ("true"), so

F(G=0,I,M,S)+F(G=1,I,M,S) = 1.

Well, this is certainly a valid consequence, but a trivial one. Let us eliminate S:

F(G,I,M,S=0)+F(G,I,M,S=1) = G'+M'+I + (G' + M)(G'+M'+I) = G' + M' + I = (GM->I).

(We used the handy Boolean identity X+XY=X to simplify the expression more quickly. However, it does not matter how we simplify expressions, as long as we reduce them to a normal form.)

This time we got a consequence, GM->I, which is the same as one of the original pieces of information. This is again a valid but trivial consequence. Similarly, we can see that eliminating "I" will not bring anything nontrivial either.

Let us finally eliminate M and simplify:

F(G,I,M=0,S) + F(G,I,M=1,S) = (G' + S') + (G'+I) = G' + S' + I = (GS->I).

This statement reads "All small green persons are intelligent." This is certainly a consequence of the initial information that Carroll would accept as the desired solution of the sorites. (There are no further consequences: if we eliminate any more variables from a disjunct such as G' +S'+I, we just get 1, i.e. "true", as a consequence.)

Note also that the desired consequence was obtained by eliminating the predicate M, which occurs twice in the formula F(G,I,M,S): once as M and once as M'. No other predicates occur in F(G,I,M,S) in this manner. This could be a useful heuristic for determining which variables need to be eliminated in order to obtain nontrivial consequences. However, this heuristic is certainly specific to the form of the statements that come from syllogisms and sorites. We do not need to use any heuristics; we have now an algorithm that will give all the consequences for information given in that form or in any other form as a Boolean formula of the admitted type. We merely need to exclude the trivial consequences from the list of all consequences.

After achieving a good understanding of how to derive consequences from the universally quantified part of the information, it is only a small step to get consequences for the existentially quantified parts.

To be continued