| Same values |
| |
p | q | pq | ~(pq) | ~p | ~q | (~p)(~q) |
T | T | T | F | F | F | F |
T | F | F | T | F | T | T |
F | T | F | T | T | F | T |
F | F | F | T | T | T | T |
|
Since the ~(pq) column and (~p)(~q) column agree, we conclude that they are equivalent.
Before we go on...The statement ~(pq) can be read as "It is not the case that both p and q are true" or "p and q are not both true." We have just shown that this is equivalent to "Either p is false or q is false."
Example 7 Applying DeMorgan's Law
Let p: "The President is a Democrat," and q: "The President is a Republican." Then ~(pq): "The President is not both a Democrat and a Republican." This is the same as saying: "Either the President is not a Democrat, or he is not a Republican, or he is neither," which is (~p)(~q).
Before we go on... This is not the same as "The President is a Republican or a Democrat," which would be qp.
Here are the two equivalences known as DeMorgan's Laws:
DeMorgan's Laws
If p and q are statements, then
Mechanically speaking, this means that, when we distribute a negation sign, it reverses and , and the negation applies to both parts.
|
Example 7P Practice with DeMorgan's Laws
A compound statement is a tautology if its truth value is always T, regardless of the truth values of its variables. It is a contradiction if its truth value is always F, regardless of the truth values of its variables. Notice that these are properties of a single statement, while logical equivalence always relates two statements.
Example 8 Tautologies
Show that the following are tautologies:
(a) p(~p).
(b) (pq)[(~p)(~q)]
Solution
Before we go on..."You are sad," the Knight said in an anxious tone: "let me sing you a song to comfort you. . . Everybody that hears me sing it either it brings the tears into their eyes, or else "
"Or else what?" said Alice, for the Knight had made a sudden pause.
"Or else it doesn't, you know."
When a statment is a tautology, we also say that the statement is tautological. In common usage this sometimes means simply that the statement is convincing. We are using it for something stronger: the statement is always true, under all circimstances. In contrast, a contradiction, or contradictory statement, is never true, under any circumstances.
Example 9 Contradiction
Show that the statement (pq)[(~p)(~q)] is a contradiction.
Solution
Before We Go On ...
In common usage we sometimes say that two statements are contradictory. By this we mean that their conjunction is a contradiction: they cannot both be true. For example, the statements pq and (~p)(~q) are contradictory, since we've just shown that their conjunction is a contradiction. In other words, no matter what the truth values of p and q, it is never true that both pq and (~p)(~q) are true at the same time. (Can you see why this is so from the meaning of pq?)
Note that most statements are neither tautologies nor contradictions, as in the first three examples in this section.
Sometimes we can "recognize" a tautology or contradiction immediately. Roughly speaking, tautologies are statements that are "obviously true" while contradictions are "obviously false".
Example 10 Practice in Spotting Tautologies and Contradictions
Answer the following. If in doubt, use a truth table. (The truth tables for these examples appear in the exercises.)
Before turning to the exercises for this section, we give a list of some important logical equivalences, most of which we have already encountered. (The verification of some of these appear as exercises.) We shall add to this list as we go along.
Example 11 Simplifying Expressions
Simplify the following statements
(a) p~(~q)
(b) ~([p(~q)]r)
(c) p[~(~pq)]
Solution
By "simplify" we mean "find a simpler equivalent statement."
(a) We immediately recognize a double negation ~(~q). By the Double Negative Law, this is the same as q. Thus, the given expression can be written more simply as
pq.
(b)
We can analyze this statement from the outside in. It is first of all a negation, but further it is the negation ~(AB), where A is (p(~q)) and B is r. To see this, look for the "principal connective," the last logical operator you would evaluate in forming the truth table. Now one of De Morgan's Laws is:
Applying this here gives:
~([p(~q)]r) (~[p(~q)])(~r).
We can apply DeMorgan's law again, this time to the statement ~(p(~q)). Doing this gives us:
~[p(~q)] (~p)~(~q) (~p)q.
Notice that we've also used the Double Negative law. Finally, this gives
~([p(~q)]r) (~[p(~q)])(~r) ((~p)q)(~r),
or just
(~p)q(~r),
since the Associative Law tells us that we can forget about which two expressions we "or" first.
(c) The expression ~(~pq) on the right is a negation of the form ~(AB) where A is ~p and B is q. Let us start with that.
~(~pq) | |
~(~p)(~q) | | De Morgan |
| |
p(~q) | | Double Negative |
We can now complete the simplification of the entire given statement:
p[~(~pq)] | |
p[p(~q)] | | From above |
| |
[pp](~q) | | Associateive Law |
| |
p(~q) | | Absorption Law |
Example 11P Practice with Simplifying
For each of the given statements, supply a simpler equivalent statement. To enter them, use "AND" for and "OR" for . For instance, you could enter - (pq)(~r)
as - (p OR q) AND ~r
or- (p OR q) AND (~r)
Example 12 Simplifying a Statement
Consider: "You will get an A if either you are clever and the sun shines, or you are clever and it rains." Rephrase the condition more simply.
Solution
Last Updated: September, 2001 Copyright © 1996 StefanWaner and Steven R. Costenoble
Top of Page
|