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
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
This comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteEx-2(b)
ReplyDeleteI think that the correct answer is:
∃x(D(x) ∧ M(x)) → ∀z[∃y(F(z,y) ∧ D(y)) → Q(z)]
Ex-6(b)
∀x∃yP(x,y): Everyone *is* a parent.
The statement is False.
Ex-8(d)
Let x = 9.9 < 10 and y = 9.8 < x. Then y > 9. Thus, the statement is False.
Ex-9
The universe of discourse is Z, not C (complex numbers).
(a) True
(b) False
(c) False
(d) True
(e) True
(f) True
Yes. I got the same answer for 2(b)
DeleteThis is my take on 2 (b). I think this right is because
ReplyDelete∀x[(∃yD(y)∧F(x,y))∧(∃zD(z)∧M(z))→Q(x)]
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.
In this statement the word "anyone" meant "someone". Your answer is wrong. Turn to page 60 and read the example 4 again,
DeleteYes, I agree I was wrong. Maybe you could explain why the next one 2(c) is:
Delete¬∃xF(x)→∀y(A(y)→∃zD(z)∧T(y,z))
instead of:
¬∃xF(x)→∀y(A(y)→∀zD(z)∧T(y,z))
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.
The word "someone" tips us off that we should use ∃ instead of ∀.
DeleteI had ¬∃xF(x)→∀y(A(y)→∃zD(z)∧T(y,z)) initially for my answer for 2(c), but I changed it to:
Delete¬∃xF(x)→∀y∃z[(A(y)∧D(z)]→T(y,z))
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.
This comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDelete6(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.
ReplyDeleteand what Stavros Mekesis said for 8,9.
6(b) Every one has at least one child.
DeleteThis false.
I guess Stavros is correct in
ReplyDelete2(b), 6(b), 8(d) and 9.
updating all the answers in the original post. Thanks.