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

34 views4 pages
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!
Unlock document

This preview shows page 1 of the document.
Unlock all 4 pages and 3 million more documents.

Already have an account? Log in

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.

Get access

Grade+20% OFF
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers