Predicates and Quantifiers Flashcards
Define variables
To denote subjects
Define predicates
to denote a property of a subject
Define quantifiers
To quantify over subjects
What is a universal Quantifier (∀x)
asserts P(x) is true for every value of x in the domain
What is an Existential Quantifier (∃x)
assers P(x) is true for some values of x in the domain
Example (Quantifiers): If P(x) denotes “x is even” and U then integer then:
∀x. P(x) is false, but
∃x. P(x) is true.
What precedence do the ∀x ∃x have over other logical operators
They have a higher precedence than all the logical operators
What do truth values depend on
The predicate (P(x)) and the domain (U)
If U is the positive integers and P(x) is the statement “x < 2” then what are the truth values for ∀x and ∃x
For ∃x P(x) is true but for ∀x P(x) is false
What is very important in nested quantifiers
the order (the first two doesn’t matter but the second 2 does (2,3)
Define argument in propositional logic
a sequence of propositions
When is the argument valid
when the premises imply the conclusion
What is the last statement called in proportional logic
the conclusion
What does this statement in english ∀x∀y P(x, y) ≡ ∀x∀y (x + y = 0)
For all real numbers x and y, x + y = 0
ExEy what does this mean in English
There exists x, there exists y
p –> q, what is a trivial proof in this case
if q is true
p –> q, what is a vacuous proof in this case
if p is false
p –> q, what is a direct proof in this case
Assume p then show q
p –> q, what is proof by contraposition in this case
¬q and show ¬p
Example of direct proof: If n is an odd integer, then n^2 is odd, n = 2k +1
Proof. Assume that n is odd.
* Then n = 2k + 1 for an integer k.
* Thus,
n
= (2k + 1)^2 = 4k^2 + 4k + 1
= 2(2k^2 + 2k) +1
= 2r + 1
therefore always odd
