CSCE 222 Chapter 1.3
Jump to navigation
Jump to search
« previous | Sunday, February 20, 2011 | next »
Predicates
A "function" that takes one or more inputs and evaluates to either true or false
- EX: Let ; ;
Quantifiers
- Higher precedence than all logical operators
- Distribute across parenthesized terms:
Universal Quantification
If a predicate is true for all values of in the domain,
To be contradicted, we need to find only one value of such that is false.
Existential Quantification
If a predicate is satisfiable for at least one value of in the domain,
To be contradicted, every value of has to be false.
Variable Binding
A variable is bound if a quantifier is used on that variable. For example, in , is bound, but is free (not bound). To fix this, we would write .
Negating Quantifiers
"Every student in your class has taken a course in calculus" could be written as .
Negation would be "There is a student in your class who has not taken a course in calculus", which could be written