Discrete Mathematics
Lecture 3
Propositional Logic - proof of 1 famous
I could say
“prove a law of
Distributivity: p (q r) (p q) (p r) distributivity.”
p q r qr p (q r) pq pr (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
3/25/2024
Propositional Logic - proof
Show that [p (p q)] q is a tautology without using
truth table.
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 complement
(p q) q identity
(p q) q substitution for
(p q) q DeMorgan’s
p (q q ) associative
p T Complement
T Identity
3/25/2024
Use the logical equivalences to show that ¬(p ∨ ¬(p ∧ q)) is
a contradiction. Or show that ¬(p ∨ ¬(p ∧ q)) is a
contradiction without using truth table.
3/25/2024
Predicate Logic - everybody loves somebody
Proposition, YES or NO?
3+2=5 YES
X+2=5 NO
X + 2 = 5 for any choice of X in {1, 2, 3} YES
X + 2 = 5 for some X in {1, 2, 3} YES
3/25/2024
Predicate Logic - everybody loves somebody
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.
…
3/25/2024
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.
3/25/2024
Predicates
Suppose Q(x,y) = “x > y”
Proposition, YES or NO?
Q(x,y) NO
Q(3,4) YES Predicate, YES or NO?
Q(x,9)
NO Q(x,y) YES
Q(3,4) NO
Q(x,9)
YES
3/25/2024
Predicates - the universal quantifier
Another way of changing a predicate into a proposition.
Suppose P(x) is a predicate on some universe of discourse.
Ex. B(x) = “x is carrying a backpack,” x is set of CSER1209 students.
The universal quantifier of P(x) is the proposition:
“P(x) is true for all x in the universe of discourse.”
We write it x P(x), and say “for all x, P(x)”
x P(x) is TRUE if P(x) is true for every single x.
x P(x) is FALSE if there is an x for which P(x) is false.
3/25/2024
Predicates - the universal quantifier
Let A = {1, 2, 3, 4, 5}. Determine the truth value of each of the
following statements:
(a) (∀x ∈ A)(x + 3 < 10)
(b) (∀x ∈ A)(x + 3 ≤ 7)
(a) True. For every number in A satisfies x + 3 < 10.
(b) False. For if x = 5, then x + 3 is not less than or equal
7. In other words, 5 is not a solution to the given condition.
3/25/2024
Predicates - the existential quantifier
Another way of changing a predicate into a proposition.
Suppose P(x) is a predicate on some universe of discourse.
Ex. C(x) = “x has a candy bar,” x is set of cser1209 students.
The existential quantifier of P(x) is the proposition:
“P(x) is true for some x in the universe of discourse.”
We write it x P(x), and say “for some x, P(x)”
x P(x) is TRUE if there is an x for which P(x) is true.
x P(x) is FALSE if P(x) is false for every single x.
3/25/2024
Predicates - the existential quantifier
Let A = {1, 2, 3, 4, 5}. Determine the truth value of each of
the following statements:
(a) (∃x ∈ A)(x + 3 = 10)
(b) (∃x ∈ A)(x + 3 < 5)
(a) False. For no number in A is a solution to x + 3 = 10.
(b) True. For if x0 = 1, then x0 + 3 < 5, i.e., 1 is a solution.
3/25/2024
Predicates - more examples
L(x) = “x is a lion.” Universe of discourse
is all creatures.
F(x) = “x is fierce.”
C(x) = “x drinks coffee.”
All lions are fierce. x (L(x) F(x))
Some lions don’t drink coffee. x (L(x) C(x))
Some fierce creatures don’t drink coffee.
x (F(x) C(x))
3/25/2024
Predicates - more examples
B(x) = “x is a hummingbird.”
L(x) = “x is a large bird.” Universe of discourse
H(x) = “x lives on honey.” is all creatures.
R(x) = “x is richly colored.”
x (B(x) R(x))
All hummingbirds are richly colored.
No large birds live on honey. x (L(x) H(x))or
x (¬L(x) ¬H(x))
Birds that do not live on honey are poorly colored.
x (H(x) R(x))
3/25/2024
Let P (x) be "x is
perfect";
let F(x) be "x is your
Translate each of these statements into logical expressions
friend";
using predicates, quantifiers, and logical connectives.
a) No one is perfect. x P(x)
b) Not everyone is perfect. x P (x)
c) All your friends are perfect. x(F(x) P (x))
d) At least one of your friends is perfect. x(F(x) P (x))
e) Not everybody is your friend or someone is not
perfect.
(x F(x)
(xP(x))
THANK YOU
