Mathematics for Computer Science

(Frankie) #1

3.6. Predicate Formulas 55


example, let the domain be the integers andP.x;y/meanx > y. Then the hy-
pothesis would be true because, given a value,n, forywe could choose the value
ofxto benC 1 , for example. But under this interpretation the conclusion asserts
that there is an integer that is bigger than all integers, which is certainly false. An
interpretation like this which falsifies an assertion is called acounter modelto the
assertion.


Problems for Section 3.1


Practice Problems


Problem 3.2.
Let the propositional variablesP,Q, andRhave the following meanings:


P DYou get an A on the final exam.

QDYou do every exercise in the book.

RDYou get an A in this class.

Write the following propositions usingP,Q, andRand logical connectives.
(a)You get an A in this class, but you do not do every exercise in the book.

(b)You get an A on the final, you do every exercise in this book, and you get an
A in this class.


(c)To get an A in this class, it is necessary for you to get an A on the final.

(d)You get an A on the final, but you don’t do every exercise in this book; never-
theless, you get an A in this class.


Class Problems


Problem 3.3.
When the mathematician says to his student, “If a function is not continuous, then it
is not differentiable,” then lettingDstand for “differentiable” andCfor continuous,
the only proper translation of the mathematician’s statement would be


NOT.C/ IMPLIES NOT.D/;

or equivalently,
D IMPLIES C:

Free download pdf