Predicate Logic
CSE2321 Foundations 1
Now were are going to start using the language of math to describe things.
Predicates
A predicate is just something where a variable appears. These range from being sentences to being fully mathematical.
- \(P(x) =\) “x is greater than 4”
- \(G(x, y) =\) “x + y is a real number”
We need predicate logic because most languages are super messy when it comes to explaining mathematical concepts. By having a language just for math, we can eliminate a lot of ambiguity.
Universe of Discourse
A Universe of Discourse is simply just something to define what range we are talking about. This lets us know all the possible values of a variable in a predicate.
- All things of type \(A\) are also of type \(B\)
- There exist a solution
Quantifiers
Universal Quantifier \(\forall\)
This quantifier asserts that for every single thing
Existential Quantifier \(\exists\)
This quantifier asserts that there exists some thing where something else is true.
Negating a Quantifier
We have two rules for when we run into a situation where we negate a quantified statement.
- \(\neg (\forall x \in \mathbb{N}, f(x) ) \equiv \exists x \in \mathbb{N}, \neg (f(x))\)
- This is basically just saying there is something were this doesn’t exist.
- \(\neg (\exists x \in \mathbb{N}, f(x)) = \forall x \in \mathbb{N}, \neg (F(x))\)
- The opposite is that there is something that fulfills this property is that nothing fulfills this property.