Transcript Document

Discrete Mathematics
Propositional Logic
A
proposition
is a declarative statement that’s either TRUE or
What’s
a proposition?
FALSE (but not both).
Propositions
Not Propositions
3 + 2 = 32
Bring me coffee!
CS173 is Bryan’s favorite
class.
CS173 is her favorite
class.
Every cow has 4 legs.
3+2
There is other life in the
universe.
Do you like Cake?
4/6/2016
Propositional Logic - negation
Suppose p is a proposition.
The negation of p is written p and has meaning:
“It is not the case that p.”
 Ex. CS173 is NOT Bryan’s favorite class.
Truth table for negation:
p
p
T
F
F
T
Notice that
p is a
proposition!
4/6/2016
Propositional Logic - conjunction
Conjunction corresponds to English “and.”
p  q is true exactly when p and q are both true.
 Ex. Amy is curious AND clever.
Truth table for conjunction:
p
q
pq
T
T
F
F
T
F
T
F
T
F
F
F
4/6/2016
Propositional Logic - disjunction
Disjunction corresponds to English “or.”
p  q is when p or q (or both) are true.
 Ex. Michael is brave OR nuts.
Truth table for disjunction:
p
q
pq
T
T
F
F
T
F
T
F
T
T
T
F
4/6/2016
Propositional Logic - logical equivalence
To answer, we need the notion of
“logical equivalence.”
p is logically equivalent to q if their truth tables
are the same. We write p  q.
4/6/2016
Propositional Logic - implication
Implication: p  q corresponds to English “if p
then q,” or “p implies q.”
 If it is raining then it is cloudy.
 If there are 200 people in the room, then I am
the Easter Bunny.
 If p then 2+2=4.
Truth table for implication:
p
q
pq
T
T
F
F
T
F
T
F
T
F
T
T
4/6/2016
Propositional Logic - logical equivalence
Challenge: Try to find a proposition that is equivalent
to p  q, but that uses only the connectives , ,
and .
p
q
pq
p
q
p
q  p
T
T
F
F
T
F
T
F
T
F
T
T
T
T
F
F
T
F
T
F
F
F
T
T
T
F
T
T
4/6/2016
Logical equivalence
4/6/2016
Propositional Logic - proof of 1 famous 
Distributivity:
p  (q  r)  (p  q)  (p  r)
I could say
“prove a law of
distributivity.”
p
q
r
qr
p  (q  r)
pq
pr
(p  q)  (p  r)
T
T
T
T
T
T
T
T
T
T
F
F
T
T
T
T
T
F
T
F
T
T
T
T
T
F
F
F
T
T
T
T
F
T
T
T
T
T
T
T
F
T
F
F
F
T
F
F
F
F
T
F
F
F
T
F
F
F
F
F
F
F
F
F
4/6/2016
Propositional Logic - special definitions
One of the pair of
propositions is
equivalent.
Contrapositives: p  q and q  p
 Ex. “If it is noon, then I am hungry.”
“If I am not hungry, then it is not noon.”
Converses: p  q and q  p
 Ex. “If it is noon, then I am hungry.”
“If I am hungry, then it is noon.”
Inverses: p  q and p  q
 Ex. “If it is noon, then I am hungry.”
“If it is not noon, then I am not hungry.”
p  q  q  p
4/6/2016
Propositional Logic - 2 more defn…
A tautology is a proposition that’s always TRUE.
A contradiction is a proposition that’s always FALSE.
p p p  p p  p
T
F
T
F
F
T
T
F
4/6/2016
Propositional Logic
(p  q)  q  p  q
(p  q)  q

(p  q)  q
DeMorgan’s

(p  q)  q
Involution

p  (q  q)
Associativity

p  q
Idempotent
4/6/2016
Propositional Logic - one last proof
 Show that [p  (p  q)]  q is a tautology.
 We use  to show that [p  (p  q)]  q  T.
[p  (p  q)]  q
 [p  (p  q)]  q
substitution for 
 [(p  p)  (p  q)]  q
distributive
 [ F  (p  q)]  q
 (p  q)  q
 (p  q)  q
 (p  q)  q
 p  (q  q )
 p  T
T
complement
identity
substitution for 
DeMorgan’s
associative
Complement
Identity
4/6/2016
Predicate Logic - everybody loves somebody
Proposition?
YES
3+2=5
X+2=5
NO
X + 2 = 5 for any choice of X in {1, 2, 3}
X + 2 = 5 for some X in {1, 2, 3} YES
YES
4/6/2016
Predicate Logic
…
Alicia eats pizza at least once a week.
Garrett eats pizza at least once a week.
Allison eats pizza at least once a week.
Gregg eats pizza at least once a week.
Ryan eats pizza at least once a week.
Meera eats pizza at least once a week.
Ariel eats pizza at least once a week.
4/6/2016
Predicates
…
Alicia eats pizza at least once a week.
Define:
EP(x) = “x eats pizza at least once a week.”
Universe of Discourse - x is a student in CSER1209
A predicate, or propositional function, is a
function that takes some variable(s) as
arguments and returns True or False.
Note that EP(x) is not a proposition, EP(Alicia) is.
4/6/2016
Predicates
Suppose Q(x,y) = “x > y”
Proposition?
NO
Q(x,y)
Q(3,4)
YES
Q(x,9)
NO
Predicate?
Q(x,y) YES
Q(3,4) NO
Q(x,9)
YES
4/6/2016
THANK YOU