# CMPUT272 Lecture Notes - Lecture 7: Propositional Calculus, Empty Set, Vacuous Truth

September 23 2014

ETLC 2-001

Predicate Logic

Allows us to talk about an 'infinite' number of things, where as with

propositional logic, it would require an infinite number of statements.

Quantifiers

Predicates, are basically functions

Variables, and a domain. By quantifying a predicate,

we will have an expression that is either true or false

: Universal, For allā

x, P(x)ā

x D, P(x)ā ā

: Extestential, For some, for at least one.ā

x, P(x)ā

x D, P(x)ā ā

Given: x D, P(x) ... We need to know the domain and what the functionā ā

P is.

If P(x) is true for all x in domain D. then the predicate is true

Given: x D, P(x) ... We need to know the domain and what the function ā ā

P is.

If P(x) is true for at least one x in domain D, the the predicate is

true

Negation

( x D, P(x) ) = x D, P(x)ā¼ ā ā ā ā ā¼

( x D, P(x) ) = x D, P(x)ā¼ ā ā ā ā ā¼

Examples

x , y , x + y = 0 is Trueā āā¤ ā āā¤

y , x , x + yā āā¤ ā āā¤ = 0 is False

The order of quantifiers are important!

y , x , x + yā āā¤ ā āā¤ = 0 is True

The type of quantifiers are important!

y , x , x * yā āā¤ ā āā¤ = 0 is True

y , x , x + yā āā¤ ā āā¤ is Trueā ā¤

The function being applied is important!

x +, y +, x + y = 0 ā āā¤ ā āā¤ is False

The domain is important!

## Document Summary

Allows us to talk about an "infinite" number of things, where as with propositional logic, it would require an infinite number of statements. By quantifying a predicate, we will have an expression that is either true or false. : universal, for all x, p(x) x d, p(x) : extestential, for some, for at least one. x, p(x) x d, p(x) If p(x) is true for all x in domain d. then the predicate is true. Given: x d, p(x) we need to know the domain and what the function. If p(x) is true for at least one x in domain d, the the predicate is. Negation ( x d, p(x) ) = x d, p(x) ( x d, p(x) ) = x d, p(x) , x + y = 0 is true. Every student in this class has studied history. Some student in this class has visited mexico. Vacuous truth of universal statements over empty domains.