Description
1. For each of the following statements use a truth table to determine whether it is a tautology,
a contradiction, or a contingency.
(a) ((p ∨ r) ∧ (q ∨ r)) ↔ ((p ∧ q) ∨ r)
(b) (p ⊕ q) ∧ (p ⊕ ¬q)
(c) (p → (q → r)) ↔ (p → (q ∧ r))
(d) (p ∧ (¬q → ¬p)) → q
2. For each of the following logical equivalences state whether it is valid or invalid. If invalid then
give a counterexample (e.g., based on a truth assignment). If valid then give an algebraic proof
using logical equivalences from Tables 6, 7, and 8 from Section 1.3 of textbook.
(a) (p → r) ∧ (q → r) ≡ (p ∧ q) → r
(b) (p → q) ∨ (p → r) ≡ (p ∨ q) → r
(c) (((p ∨ q) ∧ (p → r) ∧ (q → r)) → r) ≡ T
(d) (((p → q) ∧ (q → r)) → (p → r)) ≡ T
3. Which of the following conditions are necessary, and which conditions are sufficient for the
natural number n to be divisible by 6. The natural numbers are N = {0, 1, 2, . . . , }.
(a) n is divisible by 3.
(b) n is divisible by 9.
(c) n is divisible by 12.
(d) n = 24
(e) n
2
is divisible by 3.
(f) n is even and divisible by 3.
4. 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?
If the file system is not locked, then new messages will be queued.
If the file system is not locked, then the system is functioning normally, and conversely.
If new messages are not queued, then they will be sent to the message buffer.
If the file system is not locked, then new messages will be sent to the message buffer.
New messages will not be sent to the message buffer.
1 Comp 232
5. Suppose the domain of the propositional function P(x, y) consists of pairs x and y, where x
= 1, 2, or 3, and y = 1, 2, or 3. Write out the propositions below using disjunctions and
conjunctions only.
(a) ∃x P(x, 3)
(b) ∀y ¬P(2, y)
(c) ∀x ∃y P(x, y)
(d) ∃x∀y ¬P(x, y)
6. Let the domain for x be the set of all students in this class and the domain for y be the set of all
countries in the world. Let P(x, y) denote “student x has visited country y” and Q(x, y) denote
“student x has a friend in country y.” Express each of the following using logical operations
and quantifiers, and the propositional functions P(x, y) and Q(x, y).
(a) Carlos has visited Bulgaria.
(b) Every student in this class has visited the United States.
(c) Every student in this class has visited some country in the world.
(d) There is no country that every student in this class has visited.
(e) There are two students in this class, who between them, have a friend in every country in
the world.
(f) Nobody in this class has visited a country in which they did not have a friend.
7. For each part in the previous question, form the negation of the statement so that all negation
symbols occur immediately in front of predicates. For example:
¬(∀x(P(x) ∧ Q(x))) ≡ ∃x(¬((P(x) ∧ Q(x))) ≡ ∃x((¬P(x)) ∨ (¬Q(x)))
8. Negate the following statements and transform the negation so that negation symbols immediately precede predicates. (See example in Question 7.)
(a) (∃x ∃y P(x, y)) ∨ (∀x∀y Q(x, y))
(b) ∀x∀y (Q(x, y) ↔ Q(y, x))
(c) ∀y ∃x ∃z (T(x, y, z) ∧ Q(x, y))
2 Comp 232
