Chapter 12 Discrete Mathematics

Practice questions

How is [(p → q) ∧ ¬q] → ¬p classified?

  1. A contradiction
  2. A contingency
  3. A tautology
  4. 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?

  1. (p ∧ q) ∨ (¬p ∧ ¬q)
  2. (p ∨ q) ∧ ¬(p ∧ q)
  3. (p → q) ∨ (q → p)
  4. 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?

  1. p
  2. q
  3. p ∨ q
  4. 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 ∨ 𝔽)?

  1. ¬(p ∧ q) ∨ (p ∧ 𝕋)
  2. (p ∧ q) ∨ (p ∧ 𝕋)
  3. ¬(p ∧ q) ∨ (p ∧ 𝔽)
  4. ¬(p ∨ q) ∨ (p ∨ 𝕋)
Answer and explanation

Answer: A

Interchange ∧ and ∨ and replace 𝔽 by 𝕋, leaving ¬ unchanged: ¬(p ∧ q) ∨ (p ∧ 𝕋).

Which of these is a contradiction?

  1. (p ∧ q) ∨ ¬p
  2. p → (q → p)
  3. p ↔ q
  4. (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?

  1. T, T, F, F
  2. T, F, T, F
  3. F, F, T, T
  4. 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?

  1. q → p
  2. ¬q → ¬p
  3. ¬p → ¬q
  4. 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. 1
  2. 2
  3. 3
  4. 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?

  1. Rows (1, 1) and (0, 1)
  2. Rows (1, 1) and (0, 0)
  3. Rows (0, 0) and (0, 0)
  4. 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?

  1. 0
  2. 1
  3. 3
  4. 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?

  1. 4
  2. 2
  3. 7
  4. 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 ℝ?

  1. a ∗ b = max(a, b)
  2. a ∗ b = a/b
  3. a ∗ b = a² + b²
  4. 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?

  1. −2
  2. −2/3
  3. 1/2
  4. −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)?

  1. 8 and 10
  2. 10 and 10
  3. 10 and 8
  4. 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?

  1. A tautology
  2. A contradiction
  3. A contingency
  4. 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)?

  1. ¬p → ¬q
  2. ¬p ∧ q
  3. q → p
  4. 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)?

  1. ¬p ∧ ¬q
  2. ¬p ∨ ¬q
  3. p ∨ q
  4. ¬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 ∨ 𝕋)?

  1. p ∨ (q ∧ 𝔽)
  2. p ∨ (q ∧ 𝕋)
  3. ¬p ∨ (¬q ∧ 𝔽)
  4. 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?

  1. A contradiction
  2. A tautology
  3. A contingency
  4. 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?

  1. p ∧ q
  2. p ↔ q
  3. p ⊻ q
  4. ¬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.

Privacy · Terms · Refunds · Delivery