Predicate Logic

• Variables: $x, y, z$
• Predicates: $P(x), M(x)$
• Quantifiers

Propositional Functions

• A generalized version of propositions
  • Contain variables and a predicate (e.g. $P(x)$)
  • Variables can be replaced with elements from their domain

Quantifiers

• Universal Quantifier: $\forall x P(x)$: $P(x)$ is true for every $x$ in the domain
  • Equivalent to the conjunction of all inputs in the domain
• Existential Quantifier: $\exists x P(x)$: $P(x)$ is true for some $x$ in the domain
  • Equivalent to the disjunction of all inputs in the domain
• You can restrict the scope of a quantifier by the use of a predicate and a logical connective
  • $\forall$ goes with $\rightarrow$
  • $\exists$ goes with $\land$

Predicate Equivalences

• Statements involving predicates and quantifiers are equivalent if and only if they have the same truth value
  • for every predicate substituted into the statement
  • for every domain used for the variables

References

• Course slides §4.1: Predicates, Quantifiers, and De Morgan Laws
• Course slides §4.2: Distributing Quantifiers over Conjunctions and Disjunctions