Bridge to Abstract Mathematics: Mathematical Proof and Structures

66 LOGIC, PART I: THE PROPOSITIONAL CALCULUS Chapter '2

Solution We construct truth tables as shown in Figures 2.7~ and 2.7b:

Figure 2.7 Truth table proofs of two important equivalences.

In both examples the conclusion that the given biconditional statement

is a tautology follows from the column of T's at the right of both tables.

In Figure 2.7a we obtain the values in the final column by linking the

fifth and sixth columns by the connective ++. In Figure 2.7b we make

the same final step, linking columns 5 and 8.

p

.- --

--

MATHEMATICAL SIGNIFICANCE OF EQUIVALENCES

• -- F,? - -- - - F.1 - F [ T 1 LI ILL

PA-9

F

• -- T -
  F

F

F

T

F

Tautologies involving the biconditional as main connective (i.e., logical
equivalences) have an important bearing on theorem-proving in mathe-
matics. The connection is: A mathematical statement having a given log-
\ ical form may be proved by proving any corresponding statement whose

q

TTT

TFT - - - -

FTT

FFT

• TTF

TFF

FTF

(p"-q)-+r

T

.- - T

T

T

T -

F

T

T

.- -- T

T

1-

T

-- - T

T

T

r

.- --

qvr

T

-.

T

T

• T
  T

F

T

p-,(qvr)

--- - -- T

T T T T F -

T

-9

F T F T F T F