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.