Predicates & Quantifiers Flashcards
When is ∀xP(x) true?
When P(x) is true for every x
When is ∀xP(x) false?
When there is an x for which P(x) is false.
What is ∃xP(x)?
The existential quantifier.
When is ∃xP(x) true?
When there is an x for which P(x) is true.
When is ∃xP(x) false?
When P(x) is false for every x.
P(x1) ∧ P(x2) ∧ … ∧ P(xn)
Is equivalent to which quantifier?
The universal quantifier, when all elements in the domain can be listed.
P(x1) ∨ P(x2) ∨ … ∨ P(xn)
Is equivalent to which quantifier?
The existential quantifier, when all elements in the domain can be listed.
What is ∃!xP(x)?
The uniqueness quantifier.
When is ∃!xP(x) true?
When there is exactly one and only one solution.
The restriction of a universal quantifier is the same as what?
As the universal quantification of a conditional statement.
E.g.
∀x
What takes precedence for Quantifiers and other logical operations?
The order of precedence is
∀ ∃ before every other logical operation.
Then the usual order of precedence of logical operators.
What is ∀x(P(x) ∧ Q(x)) equivalent to?
∀xP(x) ∧ ∀xQ(x)
In other words, universal quantifiers distribute over a conjunction.
What can existential quantifiers distribute over?
A disjunction.
What can’t you distribute either existential or universal quantifiers over?
Universal: can’t be distributed over a disjunction.
Existential: can’t be distributed over a conjunction.
What is ∀xP(x)?
The universal quantifier
