Prove Theorem part (e).TheoremProof(a) was proved in Example 1 and (b) was proved in Examp...

Prove Theorem part (e).

Theorem

Proof

(a) was proved in Example 1 and (b) was proved in Example 2. Notice that (b) says a conditional statement is equivalent to its contrapositive.

(d) gives an alternate version for the negation of a conditional statement. This could be proved using truth tables, but it can also be proved by using previously proven facts. Since (p ⇒ q) ≡ ((∼p) ∨ q), the negation of p ⇒ q must be equivalent to ∼((∼p) ∨ q). By De Morgan’s laws, ∼((∼p) ∨ q) ≡ (∼(∼p)) ∧ (∼q) or p ∧ (∼q). Thus, ∼(p ⇒ q) ≡ (p ∧∼q).

The remaining parts of Theorem 2 are left as exercises.

Example 1

The conditional statement p ⇒ q is equivalent to (∼p) ∨ q. Columns 1 and 3 in the following table show that for any truth values of p and q, p ⇒ q and (∼p)∨q have the same truth values.

Example 2

Compute the truth table of the statement (p ⇒ q) ⇔ (∼q ⇒~p).

Solution

The following table is constructed using steps 1, 2, and 3 as given in Section. The numbers below the columns show the order in which they were constructed.

Section

Step 1 The first n columns of the table are labeled by the component propositional variables. Further columns are included for all intermediate combinations of the variables, culminating in a column for the full statement.

Step 2 Under each of the first n headings, we list the 2n possible n-tuples of truth values for the n component statements.

Step 3 For each of the remaining columns, we compute, in sequence, the remaining truth values.