Predicates and Quantifiers

Math for CS · Axiom Academy

Predicates & Propositional Functions From fixed statements to functions that depend on variables In propositional logic, statements like "5 is prime" are simply true or false. But many important statements depend on a variable: "x is prime," "n is even," "the string s has length > 10." These are predicates . Let P(x) = " x is a prime number" with domain ^+ . P(x) alone is neither true nor false — it depends on what x is Predicates can have multiple variables: Q(x, y) = " x + y = 10 ." Then Q(3, 7) is true and Q(2, 5) is false. Domain = (real numbers): true for every x Domain = (complex numbers): not always meaningful (complex numbers aren't ordered) Think of an open statement as a function that returns a Boolean, and a closed statement as a specific Boolean value . All logical connectives still work with predicates: P(x) Q(x) — " x is prime AND x is odd" P(x) Q(x) — " x is prime OR x is even" P(x) Q(x) — "IF x is prime THEN x is odd" (false only at x = 2 ) These compound predicates are still open statements — they become propositions only when you substitute a value or add a quantifier. An open statement P(x) can be turned into a closed proposition in two ways: Substitution: Plug in a specific value — P(5) Quantification: Bind the variable with ("for all") or ("there exists") A predicate P(x) is a Boolean-valued function — true or false once you fill in the variable. The domain specifies allowed values — always state it explicitly.

This is the written version of the interactive lesson above. See the full Math for CS course.