predicates

predicate

a proposition whose inputs can take values other than true/false, such as numeric values

predicate definition example: adult

adult(s): for some x, age(s, x) ∧ x ≥ 18 adult(s) ≡ ∃x,(age(s, x) ∧ x ≥ 18)

predicate definition example: prime

prime(x): for all k, factor(k, x) ⇒ k = 1 xor k =x prime(x) ≡ ∀k,(factor(k, x) ⇒ k = 1 xor k =x) (underlying logic: any number k that is a factor of x, is equal to either 1 or x, but not both as 1 is not a prime number)

existential forumula

denoted ∃x, p(x) a formula that is considered true as long as it is true for at least one value equal to a chain of statements linked by ∨: ∃x, p(x) ≡ p(1) ∨ p(2) ∨ p(3) ∨ . . .

universal formula

denoted ∀x, p(x) a formula that is considered true only if it is true for all values equal to a chain of statements linked by ∧: ∀x, p(x) ≡ p(1) ∧ p(2) ∧ p(3) ∧ . . .

quantifier

the symbol ∃ or ∀

de morgan's law and quantifiers

de morgan's law extends to quantifiers ¬(∃x, p(x)) ≡ ∀x, ¬p(x) ¬(∀x, p(x)) ≡ ∃x, ¬p(x)

restricting values of a quantified statement

∀x,(r(x) ⇒ p(x)) "for all x of type r, p(x)" ∃x,(r(x) ∧ q(x)) "for some x of type r, q(x)"

de morgan's law and predicates

¬(∃x,(r(x) ∧ p(x)) ≡ ∀x,(r(x) ⇒ ¬p(x)) ¬(∀x,(r(x) ⇒ p(x)) ≡ ∃x,(r(x) ∧ ¬p(x))