Monday, April 19, 2010

how to prove it - ch2, sec2.1(quantifiers) ex

This section introduces the two well known quantifiers, universal($\forall$) meaning "for all" and existential($\exists$) meaning "there exists".

It also says that quantifier "binds" a variable, that is, a variable that is bound by a quantifier can always be replaced with a new variable without changing the meaning of the statement. For example $\forall x P(x)$ = $\forall y P(y)$

One statement can also contain more than one quantifier, for example, $\forall x \exists y (x + y = 5)$ is a valid statement that means, for all values of x there exists at lease one y such that (x + y = 5).
It may be best in these cases to think about the quantifiers one at a time , in order.

Quantifiers have higher precedence than conditional/biconditional which means $\forall x P(x) \rightarrow Q(x)$ means $[\forall x P(x)] \rightarrow Q(x)$ and not $\forall x [P(x) \rightarrow Q(x)]$


Ex-1(a) $\forall x [\exists y F(x,y) \rightarrow S(x)]$
where F(x,y) means x has forgiven y
S(x) means x is a saint

Ex-1(b) $\lnot \exists x C(x) \land [\forall y D(y) \land S(x,y)]$
C(x) means, x is in Calculus class
D(y) means, y is in discrete math class
S(x,y) means, x is smarter than y

Ex-1(c) $\forall x L(x, Mary) \land \lnot(x = Mary)$
L(x,Mary) means, x likes Mary
x = Mary means, x is Mary

Ex-1(d) $ [\exists x P(x) \land S(Jane, x)] \land [\exists y P(y) \land S(Roger,y)]$
P(x) means, x is a police officer
S(x,y) means, x saw y

Ex-1(e) $ \exists x P(x) \land S(Jane, x) \land S(Roger, x)$

Ex-2(a) $ \forall x [B(x,Cash) \rightarrow \exists y R(y) \land U(y,x)]$
B(x,y) means, x bought a Rolls Royce with y
R(y) means, y is Rich
U(y,x) means, y is Uncle of x

Ex-2(b) This statement says, "If anyone in the dorm has the measles, then everyone who has a friend in the dorm will have to be quarantined."

$\exists x (D(x) \land M(x)) \rightarrow \forall z [ \exists y (F(z,y) \land D(y)) \rightarrow Q(z) ]$

D(x) means, x lives in the form
F(x,y) means, x and y are friends
M(x) means, x has measles
Q(x) means, x has to be quarantined

Ex-2(c) This statement says, "If there does not exists anyone who failed the test, then everybody with grade A will tutor someone with grade D"

$\lnot \exists x F(x) \rightarrow \forall y (A(y) \rightarrow \exists z D(z) \land T(y,z))$

F(x) means, x has failed the test
A(y) means, y got grade A
D(z) means, z got grade D
T(y,z) means, y will tutor z

Ex-2(d) $ \exists x D(x) \rightarrow D(Jones)$
D(x) means, x can do it

Ex-2(e) $ D(Jones) \rightarrow \forall x D(x)$

Ex-3(a) $\forall z [(z>x) \rightarrow (z > y)]$

this statements is about x and y, that is values of x,y fix the True/False value of the statement.. x,y are the free variables

Ex-3(b) $\forall a \exists x [(ax^2 + 4x -2 = 0) \leftrightarrow (a \geq -2)]$

clearly, there is no free variable.

Ex-3(c) $\forall x [(x^3 - 3x < 3) \rightarrow x < 10]$
no free variables

Ex-3(d) $[\exists x (x^2 + 5x = w)] \land [\exists y (4 - y^2 = w)] \rightarrow -10 < w < 10$
w is the free variable

Ex-4(a) Every unmarried man is unhappy.

Ex-4(b) y is a sibling(sister) of one of x's parent.

Ex-5(a) Every prime number except 2 is odd.

Ex-5(b) There exists a perfect number such that all the other perfect numbers are either less or equal to it.

Ex-6(a) It means, there exists atleast one person who is parent of everyone. clearly its False.

Ex-6(b) It means, Everyone is a parent. clearly its False.

Ex-6(c) It means, There does not exist anyone who is parent of someone. clearly its False.

Ex-6(d) It means, There exists someone who is parent of none. its True.

Ex-6(e) It means, There exists someone who is not parent of someone. its True.

Ex-7(a) using $y = 2x$ we can find a y for any x, clearly its True.

Ex-7(b) It means, there exists a y such that for all x, $2x - y = 0$. clearly its False.

Ex-7(c) Using y = x/2, for odd x there would not be any y which is a natural number. so its False. This would be true if universe of discourse was real numbers.

Ex-7(d) True

Ex-7(e) holds true for y = z = 50; y = 40 , z = 60 ..etc. Clearly its True.

Ex-7(f) This statement will fail for x = 100, there is no y which is greater than 100 for which there exists some (natural number)z such that $y + z = 100$. Clearly its False.

Ex-8(a) True

Ex-8(b) False

Ex-8(c) True

Ex-8(d) False

Ex-8(e) True

Ex-8(f) True

Ex-9(a) True

Ex-9(b) False

Ex-9(c) False

Ex-9(d) True

Ex-9(e) True

Ex-9(f) True


  1. This comment has been removed by the author.

  2. This comment has been removed by the author.

  3. Ex-2(b)
    I think that the correct answer is:
    ∃x(D(x) ∧ M(x)) → ∀z[∃y(F(z,y) ∧ D(y)) → Q(z)]

    ∀x∃yP(x,y): Everyone *is* a parent.
    The statement is False.

    Let x = 9.9 < 10 and y = 9.8 < x. Then y > 9. Thus, the statement is False.

    The universe of discourse is Z, not C (complex numbers).
    (a) True
    (b) False
    (c) False
    (d) True
    (e) True
    (f) True

  4. This is my take on 2 (b). I think this right is because

    for all x ,if there exists a y in the dorm and y friends with x and a person z in the dorm with measles, then x needs to be quarantined. This fits the single if then statement in the question.

    1. In this statement the word "anyone" meant "someone". Your answer is wrong. Turn to page 60 and read the example 4 again,

    2. Yes, I agree I was wrong. Maybe you could explain why the next one 2(c) is:


      instead of:


      I was thinking that the statement doesn't work because it is saying if no one failed then for every person with an A there exists someone with a D and y will tutor them. But maybe one person getting an A does not imply that someone else got a D? thanks, sry I find these tricky.

    3. The word "someone" tips us off that we should use ∃ instead of ∀.

    4. I had ¬∃xF(x)→∀y(A(y)→∃zD(z)∧T(y,z)) initially for my answer for 2(c), but I changed it to:


      I found that the initial statement, which said "If y got an A then at least one person z got a D and y will tutor z, didn't sound right. How does someone who received an A cause someone to get a D?

      This new statement says "For every person y ∃z[(A(y)∧D(z)]→T(y,z)) is true. In other words, for every person y, there is at least one person z in this statement. The statement then reads "If y got an A and z got a D, then y will tutor z."

      I think this sounds more logical. Tell me if I'm wrong.

  5. This comment has been removed by the author.

  6. This comment has been removed by the author.

  7. 6(b) I agree is false. if we take all the people in the world, there exist at least one person such that x is y's parent. let x be a 4 year old child, counterexample.

    and what Stavros Mekesis said for 8,9.

  8. I guess Stavros is correct in
    2(b), 6(b), 8(d) and 9.

    updating all the answers in the original post. Thanks.