predicate
a sentence template with variables; functions that return T/F. After choosing the domain(s) for variables and plugging in values, the predicate becomes a proposition
unary vs binary predicate
unary involves 1 variable, while binary involves 2 variables, possibly from different domains
the need for quantifiers
predicates need a way to discuss some or all values in the domain. Propositional logic is built to handle finite amounts of statements, but quantifiers can generalize infinite cases into one statement
3 types of quantifiers
- universal (∀xP(x)): holds for every x
- existential (∃xP(x)): holds for at least one x
- unique existential (∃!xP(x)): holds for exactly one x
formal definition of unique existential quantifier
∃x[P(x) ∧ ∀y(P(y) → y = x)]
there exists an x that satisfies P (existence), and if there is a y that satisfies P, then y must be none other than x (uniqueness)
when does order of quantifiers matter, and when does it not
matters when different quantifiers are involved: ∀x∃y (for every x there exists a y such that…) ≠ ∃y∀x (there exists a y such that for every x…)
does not matter when all quantifiers are of the same type
de morgan’s laws for quantifiers (how to push negation through quantifiers)
¬(∀x P(x)) = ∃x ¬P(x)
“no x satisfies P(x)” = “there is an x that doesn’t satisfy P(x)”
¬(∃x P(x)) = ∀x ¬P(x)
“there isn’t an x that satisfies P(x)” = “every x doesn’t satisfy P(x)”
quantifiers over finite domains/universes, such as {a1, a2, .., an} for universal and existential
∀xP(x) = P(1) ∧ P(2) ∧ … ∧ P(n)
∃xP(x) = P(1) v P(2) v … v P(n)
how to prove/disprove a universal statement
prove over finite: check all for true
prove over infinite: show for arbitrary
disprove: give a counterexample
how to prove/disprove an existential statement
prove: give a witness
disprove: check all for false
what happens if a universal quantifier is restricted
an implication is made, for protection from counterexamples
what happens if an existential quantifier is restricted
a conjunction is made, for witnesses that satisfy both the restriction and the predicate
is this valid: ∀x(P(x) ∧ Q(x)) = ∀x(P(x)) ∧ ∀x(Q(x))
yes, ∀ distributes over AND
is this valid: ∀x(P(x) v Q(x)) = ∀x(P(x)) v ∀x(Q(x))
no, ∀ distributes over AND, not OR
is this valid: ∃x(P(x) v Q(x)) = ∃x(P(x)) v ∃x(Q(x))
yes, ∃ distributes over OR
is this valid: ∃x(P(x) ∧ Q(x)) = ∃x(P(x)) ∧ ∃x(Q(x))
no, ∃ distributes over OR, not AND
divisibility definition (no remainders)
∀a ∈ Z{0}, ∀b ∈ Z : a|b ↔ ∃k ∈ Z (b=ak)
“for all non-zero ints a and ints b, a divides b if and only if there is an int k such that b = ak.”
a: divisor, b: dividend, k: whole quotient
euclidean division (division algorithm/theorem, includes remainders)
∀a ∈ Z, ∀b ∈ Z{0}, ∃!q, r ∈ Z such that a = bq + r and 0 ≤ r < |b|
“for all ints a and non-zero ints b, there exist unique ints q, r such that a = bq + r and 0 ≤ r < |b|.”
a: dividend, b: divisor, q: quotient, r: remainder
