CSCE 222 Chapter 1.3

From Notes
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