Chapter 12 Discrete Mathematics
Practice questions
How is [(p → q) ∧ ¬q] → ¬p classified?
- A contradiction
- A contingency
- A tautology
- Equivalent to p
Answer and explanation
Answer: C
Rows (p, q): TT gives (T ∧ F) → F = F → F = T; TF gives (F ∧ T) → F = T; FT gives (T ∧ F) → T = T; FF gives (T ∧ T) → T = T. All T, so it is a tautology.
Which formula is logically equivalent to p ↔ q?
- (p ∧ q) ∨ (¬p ∧ ¬q)
- (p ∨ q) ∧ ¬(p ∧ q)
- (p → q) ∨ (q → p)
- p ∧ q
Answer and explanation
Answer: A
p ↔ q is true exactly when p and q are both true or both false, which is what (p ∧ q) ∨ (¬p ∧ ¬q) says. (p ∨ q) ∧ ¬(p ∧ q) is exclusive or, and (p → q) ∨ (q → p) is a tautology.
Which formula is p ∨ (¬p ∧ q) equivalent to?
- p
- q
- p ∨ q
- p ∧ q
Answer and explanation
Answer: C
Distributive law: p ∨ (¬p ∧ q) ≡ (p ∨ ¬p) ∧ (p ∨ q). Complement law: p ∨ ¬p ≡ 𝕋. Identity law: 𝕋 ∧ (p ∨ q) ≡ p ∨ q.
What is the dual of ¬(p ∨ q) ∧ (p ∨ 𝔽)?
- ¬(p ∧ q) ∨ (p ∧ 𝕋)
- (p ∧ q) ∨ (p ∧ 𝕋)
- ¬(p ∧ q) ∨ (p ∧ 𝔽)
- ¬(p ∨ q) ∨ (p ∨ 𝕋)
Answer and explanation
Answer: A
Interchange ∧ and ∨ and replace 𝔽 by 𝕋, leaving ¬ unchanged: ¬(p ∧ q) ∨ (p ∧ 𝕋).
Which of these is a contradiction?
- (p ∧ q) ∨ ¬p
- p → (q → p)
- p ↔ q
- (p ∨ q) ∧ (¬p ∧ ¬q)
Answer and explanation
Answer: D
¬p ∧ ¬q ≡ ¬(p ∨ q) by De Morgan, so the formula is (p ∨ q) ∧ ¬(p ∨ q), which is always F. p → (q → p) is a tautology, and the other two are contingencies.
p: "7 is a prime number" and q: "√4 is irrational". What are the truth values of p ∨ q, p → q, q → p and p ↔ q, in that order?
- T, T, F, F
- T, F, T, F
- F, F, T, T
- T, F, F, T
Answer and explanation
Answer: B
p is T and q is F (√4 = 2). p ∨ q = T; p → q = T → F = F; q → p = F → T = T; p ↔ q = F because the values differ.
What is the converse of the contrapositive of p → q?
- q → p
- ¬q → ¬p
- ¬p → ¬q
- p → q
Answer and explanation
Answer: C
The contrapositive of p → q is ¬q → ¬p. Swapping its hypothesis and conclusion gives the converse ¬p → ¬q, which is the inverse of the original.
In the truth table of (p ∧ q) → ¬r, how many rows have the truth value F?
- 1
- 2
- 3
- 7
Answer and explanation
Answer: A
A conditional is false only when its hypothesis is true and its conclusion false: p ∧ q true needs p = q = T, and ¬r false needs r = T. That is exactly one of the 8 rows.
A has rows (1, 0) and (0, 0), B has rows (0, 1) and (0, 0), and C has rows (1, 1) and (0, 1). What is (A ∨ B) ∧ C?
- Rows (1, 1) and (0, 1)
- Rows (1, 1) and (0, 0)
- Rows (0, 0) and (0, 0)
- Rows (1, 0) and (0, 1)
Answer and explanation
Answer: B
A ∨ B has rows (1∨0, 0∨1) = (1, 1) and (0, 0). Meeting with C: (1∧1, 1∧1) = (1, 1) and (0∧0, 0∧1) = (0, 0).
How many x in ℤ₆ = {0, 1, 2, 3, 4, 5} satisfy 2 ×₆ x = 4?
- 0
- 1
- 3
- 2
Answer and explanation
Answer: D
2 × 2 = 4 and 2 × 5 = 10 = 6 + 4, while 2 × 0, 2 × 1, 2 × 3, 2 × 4 give 0, 2, 0, 2 modulo 6. So x = 2 and x = 5: two solutions. This happens because 2 has no inverse under ×₆.
Under multiplication modulo 9 on {1, 2, 4, 5, 7, 8}, what is the inverse of 7?
- 4
- 2
- 7
- 5
Answer and explanation
Answer: A
7 × 4 = 28 = 3 × 9 + 1, so 7 ×₉ 4 = 1, the identity. Hence the inverse of 7 is 4.
Which rule is NOT a binary operation on ℝ?
- a ∗ b = max(a, b)
- a ∗ b = a/b
- a ∗ b = a² + b²
- a ∗ b = |a| b
Answer and explanation
Answer: B
a/b is not defined when b = 0, so a ∗ b is not defined for every pair of real numbers. The other three always give a real number.
On ℚ \ {−1}, a ∗ b = a + b + ab, whose identity is 0. What is the inverse of 2?
- −2
- −2/3
- 1/2
- −1/3
Answer and explanation
Answer: B
We need 2 + b + 2b = 0, so 3b = −2 and b = −2/3, which lies in ℚ \ {−1}. Check: 2 + (−2/3) + 2(−2/3) = 2 − 2/3 − 4/3 = 0.
On ℤ, a ∗ b = ab + 1. What are (1 ∗ 2) ∗ 3 and 1 ∗ (2 ∗ 3)?
- 8 and 10
- 10 and 10
- 10 and 8
- 7 and 7
Answer and explanation
Answer: C
1 ∗ 2 = 2 + 1 = 3, so (1 ∗ 2) ∗ 3 = 3 × 3 + 1 = 10. 2 ∗ 3 = 6 + 1 = 7, so 1 ∗ (2 ∗ 3) = 1 × 7 + 1 = 8. Since 10 ≠ 8, ∗ is not associative.
How is p → (p ∧ q) classified?
- A tautology
- A contradiction
- A contingency
- Equivalent to p
Answer and explanation
Answer: C
When p is T and q is F, p ∧ q is F, so the conditional is T → F = F. In the other three rows it is T. A column with both T and F is a contingency.
Which formula is logically equivalent to ¬(p → q)?
- ¬p → ¬q
- ¬p ∧ q
- q → p
- p ∧ ¬q
Answer and explanation
Answer: D
p → q ≡ ¬p ∨ q, so ¬(p → q) ≡ ¬(¬p ∨ q) ≡ ¬¬p ∧ ¬q ≡ p ∧ ¬q by De Morgan and double negation. A conditional is false exactly when p is true and q is false.
Which formula is logically equivalent to ¬(p ∧ q)?
- ¬p ∧ ¬q
- ¬p ∨ ¬q
- p ∨ q
- ¬p ∧ q
Answer and explanation
Answer: B
By De Morgan's law, the negation of a conjunction is the disjunction of the negations: ¬(p ∧ q) ≡ ¬p ∨ ¬q.
What is the dual of p ∧ (q ∨ 𝕋)?
- p ∨ (q ∧ 𝔽)
- p ∨ (q ∧ 𝕋)
- ¬p ∨ (¬q ∧ 𝔽)
- p ∧ (q ∨ 𝔽)
Answer and explanation
Answer: A
Replace ∧ by ∨, ∨ by ∧ and 𝕋 by 𝔽, keeping the variables (and any ¬) unchanged: p ∨ (q ∧ 𝔽).
What kind of statement is p ∨ ¬p?
- A contradiction
- A tautology
- A contingency
- Equivalent to p
Answer and explanation
Answer: B
p and ¬p always have opposite truth values, so one of them is true and p ∨ ¬p is always T. It is a tautology.
p: 2 + 3 = 5 and q: 4 is an odd number. Which compound statement is true?
- p ∧ q
- p ↔ q
- p ⊻ q
- ¬p ∨ q
Answer and explanation
Answer: C
p is true and q is false. p ⊻ q is true because exactly one of them is true. p ∧ q is false, p ↔ q is false (different values), and ¬p ∨ q is F ∨ F = F.