Mathematics for Computer Science

Chapter 3 Logical Formulas64

(a)xconsists of three copies of some string.

(b)xis an even-length string of 0’s.

(c)xdoes not contain both a 0 and a 1.

(d)xis the binary representation of 2 kC 1 for some integerk 0.

(e)An elegant, slightly trickier way to defineNO-1S.x/is:

PREFIX.x; 0 x/: (*)

Explain why (*) is true only whenxis a string of 0’s.

Problem 3.15.
For each of the logical formulas, indicate whether or not it is true when the do-
main of discourse isN, (the nonnegative integers 0, 1, 2,... ),Z(the integers),Q
(the rationals),R(the real numbers), andC(the complex numbers). Add a brief
explanation to the few cases that merit one.

9 x:x^2 D 2

8 x: 9 y:x^2 Dy

8 y: 9 x:x^2 Dy

8 x¤0: 9 y:xyD 1

9 x: 9 y:xC2yD 2 AND2xC4yD 5

Problem 3.16.
Show that

. 8 x 9 y: P.x;y//!8z: P.z;z/

is not valid by describing a counter-model.

Homework Problems

Problem 3.17.
Express each of the following predicates and propositions in formal logic notation.
The domain of discourse is the nonnegative integers,N. Moreover, in addition to
the propositional operators, variables and quantifiers, you may define predicates