Predicates P and Q are defined below. The domain of discourse is the set of all positive integers.

P(x): x is prime

Q(x): x is a perfect square (i.e., x = y2, for some integer y)

Indicate whether each logical expression is a proposition. If the expression is a proposition, then give its truth value.

(a)

∃x Q(x)

(b)

∀x Q(x) ∧ ¬P(x)

(c)

∀x Q(x) ∨ P(3)

(d)

∃x (Q(x) ∧ P(x))

(e)

∀x (¬Q(x) ∨ P(x)

A proposition is a statement (or predicate) whose truth value can be always decided (and is fixed). The quantifiers "there exists (∃)" and "for all (∀)" transform predicates into propositions: the predicate R(y) is not a proposition, its true value depends on y. However ∃y R(y) is a proposition, because its truth value depends of the domain of discourse of y, thus it is fixed for any y.

a) This is true. If we take x=5, as 5 is a prime number we see that Q(5) is true. Since there exists x=5 such that Q(x) is true, ∃x Q(x) is true.

b) Take x=6. 6 is not a perfect square, then Q(6) is false. A conjunction (R∧S) is only true when R and S are both true. Then Q(6)∧¬P(6) is false (despite that ¬P(6) is true). Therefore, we have found some x such that Q(x) ∧ ¬P(x) is not true, hence it is false that for all x, Q(x) ∧ ¬P(x) holds.

c) Choose any positive integer x. P(3) is true (3 is prime) then S∨P(3) is true for any proposition S (The disjunction R∨S is true if either R or S is true). In particular, Q(x) ∨ P(3) is true for all x. Then ∀x Q(x) ∨ P(3) is true.

d) This is false. If it were true, there would exist some x such that Q(x) and P(x) are true, that is, x is a perfect square and x is prime. But, if x is a perfect square, then x=1 (which cannot be, since 1 is not prime) or x=a² for some integer a>1. Hence a divides x, which means that x is not prime, a contradiction. Then the statement must be false.

e) Consider x=9=3². 9 is a perfect square, then Q(9) is true, which means that ¬Q(9) is false. Furthermore, 9 is not a prime number, then P(9) is false. Since ¬Q(9) and P(9) are both false, we have that ¬Q(9) ∨ P(9) is false. So there is some x, (x=9) such that ¬Q(x) ∨ P(x) does not hold, therefore it is false that for all x, ¬Q(x) ∨ P(x) is true.