Discrete Mathematics for Computer Science

Truth and Logical Truth 107

The reader should note that, intuitively, (p A q) -* p "asserts" that if p and q are both

T, then p is T. Thus, we expect it to be a tautology.

Example 5. Construct a truth table to show that p -- (p V r) is a tautology.

Solution. The truth table for p -+ (p v r) is

p r pvr (p-+ (pvr))

T T T T

T F T T

F T T T

F F F T

Again, all entries in the final column are T, so the formula is a tautology. U

This tautology also "asserts" an obvious truth. If p is T, then it is true that either p is
T or r is T (or both).
The next two examples show how logical connectives can be expressed in terms of
each other.

Example 6. Construct a truth table to show that (p --* q) ++ (-p V q) is a tautology.

Solution. This formula shows how -- can be expressed using v and -.

p q p--+q -p -ppVq (p-+q) *(-pVq)

T T T F T T

T F F F F T

F T T T T T

F F T T T T

Since the formula involving only -). is T(F) if and only if the formula involving - and V

is T(F), all the entries in the final column are T, so the formula is a tautology. U

Example 7. Construct a truth table to show that

(p +- q) --* ((p -+ q) A (q -÷ p))

is a tautology.

Solution. This formula shows how to express +* in terms of A and -+.

(p •* q) +-

p q p*+q p--+q q-+p (p-q) A(q--.p) ((p --+ q) A (q - p))

T T T T T T T

T F F F T F T

F T F T F F T

F F T T T T T

All the entries in the final column are T, so the formula is a tautology. U