Week 1
What is the negation of the propositions in 1–4?
1. Abby has more than 300 friends on Facebook.
2. Alissa owns more quilts than Federico.
3. A messaging package for a cell phone costs less than $20 per month.
4. 4.5 + 2.5 = 6
In questions 5–9, determine whether the proposition is TRUE or FALSE.
5. 1 + 1 = 3 if and only if 2 + 2 = 3.
6. If it is raining, then it is raining.
7. If 1 < 0, then 3 = 4.
8. If 2 + 1 = 3, then 2 = 3 − 1.
9. If 1 + 1 = 2 or 1 + 1 = 3, then 2 + 2 = 3 and 2 + 2 = 4.
10.Determine whether p → (q → r) and p → (q ∧ r) are equivalent.
12.Determine whether (p → q) ∧ (¬p → q) ≡ q.
11.Determine whether p → (q → r) is equivalent to (p → q) → r.
13.Write a proposition equivalent to p ∨ ¬q that uses only p, q, ¬, and the
connective ∧.
14.Write a proposition equivalent to ¬p ∧ ¬q using only p, q, ¬, and ∨.
15.Prove that (q ∧ (p → ¬q)) → ¬p is a tautology using propositional
equivalence and the laws of logic.
Convert the following 16-20 to “If……, then….”
16.A implies B.
17.It is hot whenever it is sunny.
18.To get a good grade it is necessary that you study.
19.Studying is sufficient for passing.
20.The team wins if the quarterback can pass.
21.Explain why the negation of “Al and Bill are absent” is not “Al and Bill are
present.”
In 22–27 P (x, y) means “x + 2y = xy,” where x and y are integers.
Determine the truth value of the statement.
22.P (1, −1)
23. P (0, 0)
24.∃ y P (3, y)
25.∀x∃y P (x, y)
26.∃x∀y P (x, y)
27.∀y∃x P (x, y)
28. (¬p ∨ ¬q) ∧ (p → q)
Determine whether the compound propositions in 28–29 are satisfiable.
29. (p → q) ∧ (q → ¬p) ∧ (p ∨ q)
In 30-33 suppose the variable x represents students and y represents courses,
and
U(y): y is an upper-level course
M(y): y is a math course
F(x): x is a freshman
B(x): x is a full-time student
T (x, y): student x is taking course y.
Write the statement using predicates and needed quantifiers.
30.Eric is taking MTH 281.
31.All students are freshmen.
32.Every freshman is a full-time student.
33.No math course is upper level.
34.Using c for “it is cold” and d for “it is dry” write “It is neither cold nor
dry” in symbols.
35.Translate the given statement into propositional logic using the
propositions provided: On certain highways in the Washington, DC metro
area you are allowed to travel on high occupancy lanes during rush hour
only if there are at least three passengers in the vehicle.
Express your answer in terms of r: “You are traveling during rush hour.”
t: “You are riding in a car with at least three passengers.” and h: “You can
travel on a high occupancy lane.”
36.A set of propositions is consistent if there is an assignment of truth
values to each of the variables in the propositions that makes each
proposition true. Is the following set of propositions consistent?
(i) The system is in multiuser state if and only if it is operating
normally.
(ii) If the system is operating normally, the kernel is functioning.
(iii) The kernel is not functioning, or the system is in interrupt mode.
(iv) If the system is not in multiuser state, then it is in interrupt mode.
(v) The system is in interrupt mode.
Solution
1. Abby has fewer than 301 friends on Facebook.
2. Allisa does not own more quilts than Federico.
3. A messaging package for a cell phone costs at least $20 per month.
4. 4.5 + 2.5 ≠ 6
5. True
6. True
7. True
8. True
9. False
10. Not equivalent. Let q be false and p and r be true.
11. Not equivalent. Let p, q, and r be false.
13. ¬ (¬p ∧ q)
12. Both truth tables are identical: hence equivalent.
14. ¬ (p ∨ q)
15. (q ∧ (p → ¬q)) → ¬p
(q ∧ (¬p ∨ ¬q)) → ¬p ( p → q is equivalent to ¬p ∨ q)
((q ∧ ¬p) ∨ (q ∧ ¬q)) → ¬p
(q ∧ ¬p) → ¬p (p ∨ F is equivalent to p)
(distribution law)
¬ (q ∧ ¬p) ∨ ¬p
(¬q ∨ p) ∨ ¬p
¬q ∨ (p ∨ ¬p) is always true, and hence the given proposition is a
Tautology.
16. If A, then B.
17. If it is sunny, then it is hot.
18. If you don't study, then you don't get a good grade (equivalently, if you
get a good grade, then you study).
19. If you study, then you pass.
20. If the quarterback can pass, then the team wins.
21. Both propositions can be false at the same time. For example, Al could
be present and Bill could be absent.
22. True
23. True
24. True
25. False
26. False
27. False
Hint: For 28-29, a compound proposition is satisfiable if it is not a
contradiction.
28. Setting p = F and q = T makes the compound proposition true; therefore
it is satisfiable.
29. Setting q = T and p = F makes the compound proposition true; therefore
it is satisfiable.
30. T (Eric, MTH 281)
31. ∀ x F(x)
32. ∀ x (F(x) → B(x))
34. ¬c ∧ ¬d
33. ∀ y (M(y) → ¬U(y))
35. (r ∧ t) → h
36. Using m, n, k, and i , there are three rows of the truth table that have all
five propositions true: the rows T T T T, F F T T, F F F T for m; n; k; i .
Note: A list of system specification is said to be consistent if there is at
least one set of truth values assigned to atomic propositions which make
all compound propositions of the list to be True.
