identify the quantifiers for all negative x and y where xy=yx
Answers
Answer:
Quantifiers are expressions that indicate the scope of the term to which they are attached, here predicates. A predicate is a property the subject of the statement can have.
For example, in the statement “the sum of x and y is greater than 5”, the predicate ‘Q’ is- sum is greater than 5,
and the statement can be represented as Q(x, y) where x and y are variables.
The scope of a quantifier or a quantification is the range in the formula that the quantifier engages in.
Types of quantification or scopes:
Universal(∀) – The predicate is true for all values of x in the domain.
Existential(∃) – The predicate is true for at least one x in the domain.
To know the scope of a quantifier in a formula, just make use of Parse trees. Two quantifiers are nested if one is within the scope of the other.
Example-1:
∀x ∃y (x+y=5)
Here ‘∃’ (read as-there exists) and ‘∀’ (read as-for all) are quantifiers for variables x and y.
The statement can be represented as-
∀x Q(x)
Q(x) is ∃y P(x, y) Q(x)-the predicate is a function of only x because the quantifier applies only to variable x.
P(x, y) is (x + y = 5)
Example-2
∀x ∀y ((x> 0)∧(y< 0) → (xy< 0))
(in English)
For every real number x and y, if x is positive and y is negative, implies xy is negative.
again,
∀x Q(x)
where Q(x) is ∀y P(x, y)
Example to convert a statement into a nested quantifiers formula:
“There is a pupil in this lecture who has taken at least one course in Discrete Maths.”
A statement consists of quantifiers and predicates, split it into it's two constituents.
Here x and y are the pupil and the course and their respective quantifiers are attached in front of them.
Write it down as-
For some x pupil, there exist a course in Discrete Maths such that x has taken y.
∃x ∃y P (x, y), where P (x, y) is "x has taken y".
Theorem-1: The order of nested existential quantifiers can be changed without changing the meaning of the statement.
Theorem-2: The order of nested universal quantifiers can be changed without changing the meaning of the statement.
Example-3:
Assume P(x, y) is xy=8,
∃x ∃y P(x, y) domain: integers
Translates to-
There is an integer x for which there is an integer y such that xy = 8,
which is same as-
There is a pair of integers x, y for which xy = 8.
Meaning ∃x ∃y P(x, y) is equivalent to ∃y ∃x P(x, y).
Similarly,
Assume P(x, y) is (xy = yx).
∀x ∀y P(x, y) domain: real numbers
Translates to-
For all real numbers x, for all real numbers y, xy = yx or,
For every pair of real numbers x, y, xy = yx.
again ∀x ∀y P(x, y) is equivalent to ∀y ∀x P(x, y).
However, when the nested quantifiers are not same, changing the order changes meaning of statement.
Example-4:
Assume P(x, y, z) is (x + y = z).
∀x ∀y ∃z P(x, y, z) domain: real numbers
Translates to-
For all real numbers x and y there is a real number z such that x + y = z (True)
∀z ∃x ∃y P(x, y, z) domain: real numbers
There is a real number z such that for all real numbers x and y, x + y = z (False)
Negation of nested quantifiers:
Theorem-3
To negate a sequence of nested quantifiers, you change each quantifier in the sequence to the other type and then negate the predicate.
So the negation of ∀x ∃y : P(x, y) is ∃x ∀y : ~P(x, y)
Example-5:
“ ∃x at Cornell, x is at least 18 years old.”
To disagree with this, you’re negating the statement by flipping the ∃ to ∀ and then
negating the predicate:
“ ∀x at Cornell such that x is not at least 18 years old.”