Mathematics for Computer Science

3.3. Equivalence and Validity 43

If I am grumpy then I am hungry, and if I am hungry then I am grumpy.

are equivalent to the single statement:

I am grumpy iff I am hungry.

Once again, we can verify this with a truth table.

P Q .PIMPLIESQ/ AND .QIMPLIESP/ PIFFQ

T T T T T T

T F F F T F

F T T F F F

F F T T T T

The fourth column giving the truth values of

.PIMPLIESQ/AND.QIMPLIESP/

is the same as the sixth column giving the truth values ofPIFFQ, which confirms
that theANDof the implications is equivalent to theIFFstatement.

3.3.2 Validity and Satisfiability

Avalidformula is one which is always true. The simplest example is

POR NOT.P/:

You can think about valid formulas as capturing fundamental logical truths. For
example, a property of implication that we take for granted is that if one statement
implies a second one, and the second one implies a third, then the first implies the
third. The following valid formula confirms the truth of this property of implication.

Œ.PIMPLIESQ/AND.QIMPLIESR/çIMPLIES.PIMPLIESR/:

Equivalence of formulas is really a special case of validity. Namely, statements
FandGare equivalent iff the statementFIFFGis valid. For example, the equiv-
alence of the expressions 3.2 and 3.1 means that

.AORB/IFF.AOR.NOT.A/ANDB//

is valid. Of course validity can also be viewed as an aspect of equivalence. Namely,
a formula is valid iff it is equivalent toT.
Asatisfiableformula is one which can sometimes be true. One way satisfiabil-
ity comes up is when there are a collection of system specifications. The job of