2.3.4: Disjunctive Normal Form and the Sheffer Stroke
- Page ID
- 1672
Now that we understand logical equivalence, we can use it to put any sentence into a form which shows very clearly what the sentence says. As usual, we will start by looking at an example. Start with the truth table for Av~B:
| Case | A | B | ~B | Av~B |
|---|---|---|---|---|
| 1 | t | t | f | t |
| 2 | t | f | t | t |
| 3 | f | t | f | f |
| 4 | f | f | t | f |
The truth table tells us that 'Av~B' is true in cases 1, 2, and 4. We can easily say what case 1 says using a sentence of sentence logic. Case 1 just says that 'A' and 'B' are both true, which we can say with 'A&B'. In the same way, case 2 says that 'A' is true and 'B' is false, which we say in sentence logic with 'A&~B'. Finally, '~A&~B' says that case 4 holds, that is, that 'A' is false and 'B' is false. Of course, none of these things says what 'Av-B' says, which was that either case 1 is true or case 2 is true or case 4 is true. But, clearly, we can say this in sentence logic by using the disjunction of the three sentences, each one of which describes one of the cases covered by 'Av-B'. That is
'AV~B' is logically equivalent to '(A&B)v(A&~B)v(~A&~B)'
'(A&B)v(A&~B)v(~A&~B)'. '(A&B)v(A&~B)v(~A&~B)' is said to be in Disjunctive Normal Form, and it says that either 'A' and 'B' are both true or 'A' is true and 'B' is false or 'A' is false and 'B' is false. This disjunction is logically equivalent to 'Av~B' because the disjunction says just what 'Av-B' says, as shown by its truth table.
Here is a slightly different way of putting the same point. The truth table shows us the possible cases in which the sentence under study will be true. We can always write a logically equivalent sentence in disjunctive normal form by literally writing out the information contained in the truth table. For each case in which the original sentence comes out true, write the conjunction of sentence letters and negated sentence letters which describe that case. Then take the disjunction of these conjunctions. This sentence will be true in exactly those cases described by the disjuncts (in our example, in the cases described by 'A&B', by 'A&-B', and by '-A&-B'). But the original sentence is true in just these same cases-that is what its truth table tells us. So the sentence in disjunctive normal form is true in exactly the same cases as the original, which is to say that the two are logically equivalent.
I want to give you a formal summary description of disjunctive normal form. But first we must deal with three troublesome special cases. I will neutralize these troublesome cases with what may at first strike you as a very odd trick.
Consider the atomic sentence 'A'. As I have so far defined disjunctions and conjunctions, 'A' is neither a disjunction nor a conjunction. But because 'A' is logically equivalent to 'AvA', it will do no harm if we extend the meaning of 'disjunction' and say that, in a trivial way, 'A' will also count as a disjunction-that is, as a degenerate disjunction which has only one disjunct.
We can play the same trick with conjunctions. 'A' is logically equivalent to 'A&A'. So we do no harm if we extend the meaning of 'conjunction' and say that, in a trivial way, 'A' also counts as a conjunction-the degenerate conjunction which has only one conjunct.
Finally, we will want to say the same thing, not just about atomic sentence letters, but about any sentence, X, atomic or compound. Whatever the form of X, we can always view X as a degenerate disjunction with just one disjunct or as a degenerate conjunction with just one conjunct.
What is the point of this apparently silly maneuver? I am working toward giving a definition of disjunctive normal form which will work for any sentence. The idea of disjunctive normal form is that it involves a disjunction of conjunctions. But what should we say, for example, is the disjunctive normal form of the sentence 'A&B'? If we allow degenerate disjunctions with one disjunct, we can say that 'A&B' is already in disjunctive normal form-think of it as '(A&B)v(A&B)'. Again, what should we say is the disjunctive normal form of 'A'? Let's count 'A' as a degenerate conjunction with just one conjunct (think of 'A&A') and let's count this conjunction as a degenerate disjunction, as in the last example. So we can say that 'A' is already in disjunctive normal form and still think of disjunctive normal form as a disjunction of conjunctions.
We still have to discuss one more special case. What should we say is the disjunctive normal form of a contradiction, such as 'A&~A'? We will allow repetitions of sentence letters with and without negation signs, so that, again, 'A&~A' will itself already count as being in disjunctive normal form.
Now we can say very simply:
A sentence is in Disjunctive Normal Form if it is a disjunction, the disjuncts of which are themselves conjunctions of sentence letters and negated sentence letters. In this characterization we allow as a special case that a disjunction may have only one disjunct and a conjunction may have only one conjunct.
For any sentence, X, of sentence logic, the disjunctive normal form of X is given by a sentence Y if Y is in disjunctive normal form and is logically equivalent to X. Except for contradictions, the disjunctive normal form of a sentence is the sentence's truth table expressed in sentence logic.
The fact that every sentence of sentence logic is logically equivalent to a sentence in disjunctive normal form helps to show something interesting about the connectives. All our sentences are put together using '&', 'v', and '~'. But are these connectives all we really need? Could we say new things if we added new connectives? The answer is no, if we limit ourselves to sentences which can be given in terms of a truth table. Because we can write any truth table in disjunctive normal form, using only '&', 'v' and '~', anything which we can express using a truth table we can express using just these three connectives. In other words, '&', 'v', and '~' are enough if we limit ourselves to a logic all the sentences of which are truth functions of atomic sentence letters. We say that '&', 'v', and '~' are, together, Expressively Complete. For given the truth table of any sentence which we might want to write, we can always write it with a sentence in disjunctive normal form.
Even more interestingly, '&', 'v' and '~' are more than we need. Using De Morgan's laws and double negation, we can always get rid of a conjunction in favor of a disjunction and some negation signs. And we can always get rid of a disjunction in favor of a conjunction and some negation signs. (Do you see how to do this?) Thus any sentence which can be represented by a truth table can be expressed using just '&' and '-'. And any such sentence can be expressed using just 'v' and '~'. So '&' and '~' are expressively complete, and 'v' and '-' are also expressively complete.
We have just seen that anything that can be represented with truth tables can be expressed with a sentence using just two connectives. Could we make do with just one connective? Clearly, we can't make do with just '&', with just 'v', or with just '~'. (Can you see why?) But perhaps we could introduce a new connective which can do everything all by itself. Consider the new connective 'I*, called the Sheffer Stroke, defined by
| X | Y | X|Y |
|---|---|---|
| t | t | f |
| t | f | f |
| f | t | f |
| f | f | t |
Work out the truth table and you will see that X|X is logically equivalent to ~X. Similarly, you can prove that (X|Y)|(X|Y) is logically equivalent to XvY. With this new fact, we can prove that '|' is expressively complete. We can express any truth function in disjunctive normal form. Using De Morgan's law and the law of double negation, we can get rid of the '&'s in the disjunctive normal form. So we can express any truth function using just 'v' and '~'. But now for each negation we can substitute a logically equivalent expression which uses just '|'. And for each disjunction we can also substitute a logically equivalent expression which uses just '|'. The final result uses '|' as its only connective. Altogether, the sentence in disjunctive normal form has been transformed into a logically equivalent sentence using just '1'. And because any truth function can be put in disjunctive normal form, we see that any truth function, that is, any sentence which could be given a truth table definition, can be expressed using just '|'.
The important idea here is that of expressive completeness:
A connective, or set of connectives, is Expressively Complete for truth functions if and only if every truth function can be represented using just the connective or connectives.
Actually, the really important idea is that of a truth function. Understanding expressive completeness for truth functions will help to make sure you have the idea of a truth function clearly in mind.
Put the following sentences in disjunctive normal form. You can do this most straightforwardly by writing out truth tables for the sentences and then reading off the disjunctive normal form from the truth tables. Be sure you know how to work the problems this way. But you might have more fun trying to put a sentence in disjunctive normal form by following this procedure: First, apply De Morgan's laws to drive all negations inward until negation signs apply only to sentence letters. Then use other laws to get the sentence in the final disjunctive normal form.
a) ~(A&B)
b) ~[(A&B)v(~A&C)]
3-9. Suppose you are given a sentence in which 'v' occurs. Explain in general how you can write a logically equivalent sentence in which 'v' does not occur at all. Similarly, explain how a sentence in which '&' occurs can be replaced by a logically equivalent sentence in which '&' does not occur. (Hint: You will, need to appeal to De Morgan's laws.)
3-10. Define a new connective, '*', as representing the following truth function:
| Case | X | Y | X*Y |
| 1 | t | t | f |
| 2 | t | f | t |
| 3 | f | t | t |
| 4 | f | f | t |
Show that '*' is expressively complete.
3-11. Show that '&' is not expressively complete. That is, give a truth function and show that this truth function cannot be expressed by using '&' as the only connective. Similarly, show that 'v' is not expressively complete and show that '~' is not expressively complete. (You may find this problem hard, but please take a few minutes to try to work it.)
Once again, you will find below the important terms which I have introduced in this chapter. Make sure you understand all of them by writing out a short explanation of each. You should refer to the text to make sure that you have correctly explained each term. Please keep your explanations of these terms in your notebook for reference and review.
- Logical Equivalence
- Venn Diagram
- Law of Double Negation
- De Morgan's Laws
- Distributive Laws
- Law of Substitution of Logical Equivalents
- Law of Transitivity of Logical Equivalence
- Commutative Laws
- Associative Law
- Law of Redundancy
- LogicalTruth
- Contradiction
- Law of Logically True Conjunct
- Law of Contradictory Disjunct
If you have read section 3-4, also explain
- Disjunctive Normal Form
- Expressively Complete
- Sheffer Stroke