3.2: Substitution of Logical Equivalents and Some More Laws

We can't do much with our laws of logical equivalence without using a very simple fact, which our next example illustrates. Consider

(1) ~~AvB

'~~A' is logically equivalent to 'A'. This makes us think that (1) is logically equivalent to

(2) AvB.

This is right. But it is important to understand why this is right. A compound sentence is made up of component sentences, which in turn may be made up of further component sentences. How do subsentences (components, or components of components, or the like) affect the truth value of the original sentence? Only through their truth values. The only way that a subsentence has any effect on the truth values of a larger sentence is through the subsentence's truth value. (This, again, is just what we mean by saying that compound sentences are truth -functions.) But if only the truth values matter, then substituting another sentence which always has the same truth value as the first can't make any difference.

I'll say it again in different words: Suppose that X is a subsentence of some larger sentence. Suppose that Y is logically equivalent to X, which means that Y and X always have the same truth value. X affects the truth value of the larger sentence only through its (i.e., X's) truth value. So, if we substitute Y for X, there will be no change in the larger sentence's truth value.

But this last fact is just what we need to show our general point about logical equivalence. The larger sentence will have the same truth value before and after the substitution; that is, the two versions of the larger sentence will be logically equivalent:

The Law of Substirurion of Logical Equivaknts (SLE): Suppose that X and Y are logically equivalent, and suppose that X occurs as a subsentence of some larger sentence Z. Let Z* be the new sentence obtained by substituting Y for X in Z. Then Z is logically equivalent to Z*.

Let's apply these laws to an example. Starting with the sentence

~[(~Av~B)&(~AvB)]

we can apply one of De Morgan's laws. This sentence is the negation of a conjunction, with the conjuncts '~Av~B' and '~AvB'. De Morgan's law tells us that this first line is logically equivalent to the disjunction of the negation of the two original conjunct&:

~(~Av~B)v~(~AvB) DM

(The 'DM' on the right means that this line was obtained from the previous line by applying one of De Morgan's laws.)

Did you have trouble understanding that one of De Morgan's laws applies to the sentence? If so, try using the idea of the main connective introduced in chapter 1. Ask yourself: "In building this sentence up from its parts, what is the last thing I do?" You apply the negation sign to '(~Av-B)&(~AvB)'. So you know the original sentence is a negation. Next, ask yourself, what is the last thing I do in building '(~Av~B)&(~AvB)' up from its parts? Conjoin '~Av~B' with '~AvB'. So '(~Av~B)&(~AvB)' is a conjunction. The original sentence, then, is the negation of a conjunction, that is, a sentence of the form ~(X&Y), where, in our example, X is the sentence '~Av~B' and Y is the sentence '~AvB'. Applying De Morgan's law to ~(X&Y) gives ~Xv~Y; in other words, in our example, '~(~Av~B)v~(~AvB)'.

Next, we can apply De Morgan's law to each of the components, '~(-Av~B)' and '~(~AvB)', and then use the law of substitution of logical equivalents to substitute the results back into the full sentence. Doing this, we get

(~~A&~~B)v(~~A&~B) DM, SLE

(As before, 'DM' on the right means that we have used one of De Morgan's laws. 'SLE' means that we have also used the law of substitution of logical equivalents in getting the last line from the previous one.)

Now we can apply the law of double negation (abbreviated 'DN') to '~~A' and to '~~B' and once more substitute the results into the larger sentence. This gives

(A&B)v(A&-B) DN, SLE

We have only one more step to do. If you look carefully, you will see that the distributive law (abbreviated 'D') applies to the last line. So the last line is logically equivalent to

A&(Bv~B) D

This might not be clear at first. As I stated the distributive law, you might think it applies only to show that the very last line is logically equivalent to the next to last line. But if X is logically equivalent to Y, then Y is logically equivalent to X! Logical equivalence is a matter of always having the same truth value, so if two sentences are logically equivalent, it does not matter which one gets stated first. Often students only think to apply a law of logical equivalents in the order in which it happens to be stated. But the order makes no difference-the relation of logical equivalence is symmetric, as logicians say.

Let's put all the pieces of this problem together. In the following summary, each sentence is logically equivalent to the previous sentence and the annotations on the right tell you what law or laws give you a line from the previous one.

~[(~Av-B)&(~AvB)]

~(~Av-B)v~(~AvB) DM

(~~A&~~B)v(~~A&~B) DM, SLE

(A&B)v(A&~B) DN, SLE

A&(Bv~B) D

Actually, all I have really proved is that each of the above sentences is logically equivalent to the next. I really want to show that the first is logically equivalent to the last. Do you see why that must be so? Because being logically equivalent just means having the same truth value in all possible cases, we trivially have

The Law of Trarrcitivity of Logical Equivaltnce (TLE): For any sentences X, Y, and Z, if X is logically equivalent to Y and Y is logically equivalent to Z, then X is logically equivalent to Z.

Repeated use of this law allows us to conclude that the first sentence in our list is logically equivalent to the last. Many of you may find this point obvious. From now on, transitivity of logical equivalence will go without saying, and you do not need explicitly to mention it in proving logical equivalences.

Here are some more easy, but very important, laws:

The Commutative Law (CM): For any sentences X and Y, X&Y is logically equivalent to Y&X. And XvY is logically equivalent to YvX.

In other words, order in conjunctions and disjunctions does not make a difference. Note that the commutative law allows us to apply the distributive law from right to left as well as from left to right. For example, '(A&B)vC' is logically equivalent to '(AvC)&(BvC)'. You should write out a proof of this fact using the commutative law and the distributive law as I stated it originally.

Next, the Associate Law tells us that 'A&(B&C)' is logically equivalent to '(A&B)&C'. To check this, try using a Venn diagram, which in this case gives a particularly quick and clear verification. Or simply note that both of these sentences are true only when 'A', 'B', and 'C" are all true, and are false when one or more of the sentence letters are false. This fact shows that in this special case we can safely get away with dropping the parentheses and simply writing 'A&B&C', by which we will mean either of the logically equivalent 'A&(B&C)' or '(A&B)&C'. Better yet, we will extend the way we understand the connective '&'. We will say that '&' can appear between any number of conjuncts. The resulting conjunction is true just in case all of the conjuncts are true, and the conjunction is false in all other cases.

The same sort of generalization goes for disjunction. 'Av(BvC)' is logically equivalent to '(AvB)vC'. Both of these are true just in case one or more of 'A', 'B', and 'C' are true and false only if all three of 'A', 'B', and 'C' are false. (Again, a Venn diagram provides a particularly swift check.) We extend our definition of 'v' so that it can appear between as many disjuncts as we like. The resulting disjunction is true just in case at least one of the disjunction is true and the disjunction is false only if all the disjunction are false.

The Associative Law (A): For any sentences X, Y, and Z, X&(Y&Z), (X&Y)&Z, and X&Y&Z are logically equivalent to each other. And Xv(YvZ), (XvY)vZ, and XvYvZ are logically equivalent to each other. Similarly, conjunctions with four or more components may be arbitrarily grouped and - similarly for disjunctions with four or more disjuncts.

Here is yet another easy law. Clearly, X&X is logically equivalent to X. Likewise, XvX is logically equivalent to X.

The Law of Redundancy (RD): For any sentence X, X&X is logically equivalent to X. Similarly, XvX is logically equivalent to X

Let us apply this law in a little example. Again, each line is logically equivalent to the next (RD stands for the law of redundancy):

~(A&B)&(~Av~B)

(~Av~B)&(~Av~B) DM, SLE

~Av~B RD

Before asking you to practice these laws, let me give you a more extended example which illustrates all the laws I have introduced so far:

~(Av~B)v[(CvB)&(Cv~A)]

~(Av~B)v[CV(B&~A)] D, SLE

~(Av~B)v[(B&~A)vC] CM, SLE

[~(Av~B)v(B&~A)]vC A

[~(Av~B)v(~A&B)]vC CM, SLE

[~(Av~B)v(~A&~~B)]vC DN, SLE

[~(Av~B)v~(Av~B)]vC DM, SLE -

(Av~B)vC RD, SLE.

Exercise

3-2. Prove the following logical equivalences. Write out your proofs as I did in the text specifying which laws you use in getting a line from the previous line. You can use the abbreviations for the laws found in the text. Until you feel comfortable with the easy laws, please include all steps. But when they begin to seem painfully obvious, you may combine the following laws with other steps and omit mentioning that you have used them: double negation, the associative law, the commutative law, and the law of substitution of logical equivalents. You must explicitly specify any other law you use.

a) 'Bv~A' is logically equivalent to '~(A&~B)'.

b) '(A&B)vC' is logically equivalent to '(AvC)&(BvC)'. (Show all steps in this problem.)

c) 'A&(~~CVB)' is logically equivalent to '(A&C)v(A&B)'.

d) '~[(A&~B)v(C&~B)]' is logically equivalent to '(~A&~C)vB'.

e) '(AvB)&(CVD)' is logically equivalent to '(A&C)v(B&C)v(A&D)v(B&D)'.

f) '(A&B)v(C&D)' is logically equivalent to '(AvC)&(BvC)&(AvD)&(BvD)'.

g) '(C&A)V(B&C)V[C&~(~B&~A)]' is logically equivalent to 'C&(AvB)'.

h) 'C&~A' is logically equivalent to 'C&[~Av~(~CVA)]'.

i) '~A&B&C' is logically equivalent to C&{~(Av~B)v[B&-(~CVA)])'.

3-3. Give a formal statement of De Morgan's laws in application to negations of conjunctions and disjunctions with three components. Model your formal statement on the formal statement in the text. It should begin as follows:

De Morgan's Laws: For any sentences X, Y, and Z . . .