Logic: Propositional Logic
Exercises
Acknowledgment: All course slides are either referenced to Rosen Book online presentations
(with certain amendments) or are personally developed by the instructor.
Previously,
• A proposition is a statement that is either true or false.
– A proposition has a truth value.
– A truth value can only be true or false; it can not be none or both
– A statement is not a proposition if it is:
o A question, command, or contain unknown variable(s).
– It can be assigned to a propositional variable.
• New compound proposition can created as a result of applying logical
connectives on one or more propositions.
– Negation ¬ NOT
– Conjunction ∧ AND
– Disjunction ∨ OR (inclusive or)
– Exclusive OR ⊕ XOR (both is not accepted)
2 2 Discrete Structures for Cybersecurity First Semester - 1447
Previously,
• To find the truth value of a given compound proposition, we create a
truth table.
– Start with a column for every propositional variable in the preposition.
– #rows = 2#variables
3 3 Discrete Structures for Cybersecurity First Semester - 1447
Exercise 2 pp 13 @[KB 8 ed]
2. Which of these are propositions? What are the truth values of those
that are propositions?
a) Do not pass go.
b) What time is it?
c) There are no black flies in Maine.
d) 4 + x = 5.
e) The moon is made of green cheese.
f) 2n ≥ 100.
4 4 Discrete Structures for Cybersecurity First Semester - 1447
Exercise 5 - 7 pp 13 @[K ٍ R 8 ed]
5-7. What is the negation of each of these propositions?
5b) There is no pollution in New Jersey.
6a) Jennifer and Teja are friends.
6b) There are 13 items in a baker’s dozen.
6c) Abby sent more than 100 text messages yesterday.
7c) 7 ⋅ 11 ⋅ 13 = 999.
7d) Diane rode her bicycle 100 miles on Sunday.
5 5 Discrete Structures for Cybersecurity First Semester - 1447
Exercise 14 pp 16 @[KR 8 ed]
14. Let p, q, and r be the propositions
p: You have the flu.
q: You miss the final examination.
r: You pass the course.
Express each of these propositions as an English sentence.
b) ¬q r
c) q → ¬r
e) (p → ¬r) ∨ (q → ¬r)
6 6 Discrete Structures for Cybersecurity First Semester - 1447
Exercise 16 pp 14 @[KR 8 ed]
16. Let p, q, and r be the propositions
p: You get an A on the final exam.
q: You do every exercise in this book.
r: You get an A in this class.
Express the following propositions using propositional algebra.
a) You get an A in this class, but you do not do every exercise in this
book.
c) To get an A in this class, it is necessary for you to get an A on the
final.
f) You will get an A in this class if and only if you either do every
exercise in this book or you get an A on the final.
7 7 Discrete Structures for Cybersecurity First Semester - 1447
Exercise 18 - 20 pp 14 @[KR 8 ed]
18-20. Determine whether each of these statements is true or false.
18a) 2 + 2 = 4 if and only if 1 + 1 = 2.
18d) 0 > 1 if and only if 2 > 1.
19c) If 1 + 1 = 3, then 2 + 2 = 5.
20d) If 1 + 1 = 2, then dogs can fly.
8 8 Discrete Structures for Cybersecurity First Semester - 1447
Exercise 29 - 30 pp 16 @[KR 8 ed]
29-30. State the converse, contrapositive, and inverse of each of these
conditional statements.
29a) If it snows today, I will ski tomorrow.
30b) I go to the beach whenever it is a sunny summer day.
30c) When I stay up late, it is necessary that I sleep until noon.
9 9 Discrete Structures for Cybersecurity First Semester - 1447
Exercise 31 - 32 pp 16 @[KR 8 ed]
31-32. How many rows appear in a truth table for each of these
compound propositions?
31a) p → ¬p.
32c) (p → r) ∨ (¬s → ¬t) ∨ (¬u → v).
10 10 Discrete Structures for Cybersecurity First Semester - 1447
Exercise 33 - 38 pp 16 @[KR 8 ed]
33-38. Construct a truth table for each of these compound
propositions.
34c) p ⊕ (p ∨ q).
36c) p ⊕ ¬p.
38e) (p ∨ q) ∧ ¬r
11 11 Discrete Structures for Cybersecurity First Semester - 1447
Exercise 6 pp 38 @[KR 8 ed]
6. Use a truth table to verify the first De Morgan law.
¬(p ∧ q) ≡ ¬p ∨ ¬q.
12 12 Discrete Structures for Cybersecurity First Semester - 1447
Exercise 8 pp 38 @[KR 8 ed]
8. Use De Morgan’s laws to find the negation of each of the following
statements.
b) Yoshiko knows Java and calculus.
d) Rita will move to Oregon or Washington.
13 13 Discrete Structures for Cybersecurity First Semester - 1447
Exercise 13 pp 38 @[KR 8 ed]
13. Show that each of these conditional statements is a tautology
without using truth tables.
b) p → (p ∨ q).
f) ¬(p → q) → ¬q.
14 14 Discrete Structures for Cybersecurity First Semester - 1447
Exercise 26 pp 38 @[KR 8 ed]
26. Show that (p → q) ∧ (p → r) and p → (q ∧ r) are logically equivalent.
15 15 Discrete Structures for Cybersecurity First Semester - 1447
Exercise 32 pp 38 @[KR 8 ed]
32. Show that p q and ¬p ¬q are logically equivalent.
16 16 Discrete Structures for Cybersecurity First Semester - 1447
Exercise 66 pp 40 @[KR 8 ed]
66. Determine whether each of these compound propositions is
satisfiable.
a) (p ∨ q ∨ ¬r) ∧ (p ∨ ¬q ∨ ¬s) ∧ (p ∨ ¬r ∨ ¬s) ∧
(¬p ∨ ¬q ∨ ¬s) ∧ (p ∨ q ∨ ¬s).
17 17 Discrete Structures for Cybersecurity First Semester - 1447
