By a conditional equation we mean a symbolic statement of the equality of two sets which, unlike the basic laws of Section of(Venn diagrams.), is not identically valid for arbitrary sets but is valid only for certain sets. Conditional equations arise in the stating of hypotheses and conclusions for theorems and in the statement of problems to be solved in the algebra of sets.

In considering two equations, we will say that the second is derivable from the first if the second can be obtained by applying any one or more of the following four rules to the first.

RULE 1. Any expression in either the left or right member of the equation may be replaced by any expression representing the identical set. That is, operations of simplifying, expanding, etc., may be performed independently on either member of the equation.

RELE 2. The right and left members of the equation may be simultaneously replaced by the respective complementary set.

RULE 3. Each side of the equation may be multiplied by the same set,  or by equal sets.

RULE 4. The same set or equal sets may be added to each side of the equation.

These rules are valid in the sense that if the condition represented by the given equation holds for certain sets, then the condition represented by the derived equation will hold for these sets. The proof of this statement follows from the basic laws in the case of Rule 1, and from the fact that complementation, intersection, and union are uniquely defined, in the case of the other rules. As an example, each of the equations below is derivable from the preceding one, and hence from the first equation:

Y + X = XZ                                  assumed given

(Y + X)' = (XZ)'                                   by Rule 2

X' Y' = X' + Z'                          by Rule 1, using (8a) and (8b)

WX'Y' = W(X' + Z')                             by Rule 3

wX'Y' = WX' + WZ'                     by Rule 1, using (3a)

U+wX'Y' = U+WX'+WZ'                     by Rule 4

Two additional rules apply to sets of equations. The derivation of the rules is obvious.

RULE 5. An equation of the form A + B = 0 may be replaced by the two simultaneous equations A = 0 and B = 0, and conversely.

RULE 6. An equation of the form AB = 1 may be replaced by the two simultaneous equations A = 1 and B = 1, and conversely.

In considering two sets of simultaneous equations, we will say the second set is derivable from the first set if each equation of the second set is obtained from equations of the first set by the application of one or more of Rules 1 through 6.

In addition to specifying operations that may be performed upon equations, it is well to point out two which are not permissible. Neither of the cancellation laws for addition and multiplication is valid in the algebra of sets. That is, from X + Y = X + Z it does not follow that Y = Z, and from XY = XZ and X ≠0 it does not follow that Y = Z.

Since Rules 3 and 4 are not reversible, we need to consider another relationship between sets of equations which is stronger than the relation of derivability. We will say that two sets of equations are equivalent if each set is derivable from the other. Equivalent sets of equations represent identical restrictions on the sets involved in the equations.

The following theorem illustrates the importance of the role of condi-

tional equations in the algebra of sets:

THEOREM. Any given collection of conditions imposed on sets which can be expressed in the notations of the algebra of sets is equivalent to a single equation with right member 0.

Proof. First, note that any condition expressible in algebraic notation must of necessity be either an equation expressing the equality of two sets or a statement of set inclusion. Since the condition X⊆Y is equivalent to the equation XY' = 0, it suffices to consider only collections of equations.

Next we shall prove that every equation is equivalent to an equation with 0 as its right member. An arbitrary equation may be represented by the equation A = B. If both sides of this equation are multiplied by B',  we obtain AB' = 0. Multiplying both sides by A', we obtain A'B = 0.  Adding these equations gives the equation                   AB' + A'B = 0, an equation with 0 as its right member which is derivable from the given equation.

Conversely, if we assume that AB' + A'B = 0, we may multiply both sides by B' to obtain AB' = 0. If the complement of both sides of AB' + A'B = 0 is taken, we obtain    AB + A'B' = 1. 'Now, multiplying both sides by B, we have AB = B. Upon adding this to the equation AB' = 0, we obtain AB + AB' = B, or A(B + B') = B, or A = B. Hence theequation A = B is derivable from AB' + A'B = 0, and with the first part of the proof this shows that the two equations are equivalent.

Finally, if each equation of the given collection is replaced by the appropriate equation of the form X = 0, these equations may be combined,  by Rule 5, to form a single equation with 0 as its right member. This completes the proof.

In the course of the above proof a method was derived for converting an equation of the form A = B into an equivalent equation of the form C = 0. Since this was not a part of the statement of the theorem, it is listed for easy reference in the following corollary.

COROLLARY. The equation A = B is equivalent to the equation AB'+A'B=O.

EXAMPLE 1. Replace the set of conditions (a) X ⊆ Y, (b) X + Y = Z,  and (c) Z + W= 1 by a single equivalent condition of the form A = 0.

Solution.

X ⊆ Y is equivalent to X Y' = 0.

X + Y = Z is equivalent to (X + Y)Z' + (X + Y)'Z = 0, by the corollary.

Z + W = 1 is equivalent to Z'W' = 0, by taking complements of both sides.

Adding these equations, we find that the required condition is X Y' + XZ' + YZ' + X'Y'Z + Z'W' = 0. This condition might also be written in other forms.

EXAMPLE 2. Show that the following set of conditions is inconsistent:

(a) A' ⊆B, (b) A = B, (c) A' + B' = 1.

Solution. To test a set of equations or conditions for consistency, we will replace the set by an equivalent equation with 0 on the right. If the equation

reduces to 1 = 0, the given set is clearly inconsistent. Otherwise, the equation simply represents a simplification of the given set of conditions. In this case we

replace (a) by A'B' = 0, replace (b) by AB' + A'B = 0, and replace (c) by

AB = 0. Then, upon adding, we obtain AB + AB' + A'B + .A'B' = 0.

The left side reduces to 1 and hence the given conditions are equivalent to the equation 1 = 0, which shows that the conditions were inconsistent.