From: William J. Rapaport (rapaport@buffalo.edu)
Date: Sep. 12, 2009
Subj: Propositional Logical Equivalences
Here's another example of how to show that 2 propositions are logically
equivalent. (I can't type the triple-bar symbol for "is logically
equivalent to", so I'll use the made-up word "equiv". And I'm using "-"
for the negation sign.)
Show (p ^ q) equiv -(-p v -q):
First, construct a truth-table for (p^q):
p q (p^q)
T T T
T F F
F T F
F F F
Second, construct a truth-table for -(-p v -q)
[Here, I'll write the computed truth-values under the principal
connective of each molecular proposition]:
1 2 3 4 5 = (3v4) 6 = -5
p q -p -q (-p v -q) -(-p v -q)
T T F F F T
T F F T T F
F T T F T F
F F T T T F
Because the output columns of both truth tables are identical, we can
say that, for all rows of the truth tables, the truth value of (p^q) is
identical to the truth value of -(-p v -q),
i.e., tval(p^q)=tval(-(-p v -q)).
Note, by the way, that this is also a proof that conjunction(^) can be
defined in terms of negation(-) and inclusive disjunction(v). In other
words, if we have negation and disjunction, we don't really "need"
conjunction.