Tutorial Questions 1 Dr. John O. Mubenwafor

MTH2125: Discrete Mathematics

Tutorial Questions 1 Dr. John O. Mubenwafor

Logic and Propositions

1. Assume that you are a logician! If someone should ask you: “Do you like tea or coffee?”; what will be your answer?

2. Which of the following is/are propositions?

Ice floats in water
China is in Europe
2 + 2 = 4
2 + 2 = 5
Where are you going?
Do your homework

[Answer: a, b, c, d]

3. Which of the following is/are propositions; and which is/are true?

Washington, D.C. is the capital of the USA
Toronto is the capital of Canada
1 + 1 = 2
2 + 2 = 3

[Answer: All are propositions; a and c are true]

4. Let p ^ q be a CONJUNCTION. Classify each of the following sentences as either true or false:

(a) The sentence: “2 + 2 = 4 and 2 + 3 = 5".

(b) The sentence: “2 + 2 = 4 and π is rational".

5. Let p ˅ q be a DISJUNCTION. Decide which of the following sentences is true and which is false:

(a) The sentence: “2 + 2 = 2 or 1 + 3 = 5".

(b) The sentence: “2 + 2 = 4 or π is rational".

6. Write the negation of the following sentences:

(a) “2 + 2 ≠ 4"

(b) “π is rational"

7. Let p → q be a CONDITIONAL statement. Determine which of the following sentences is true and which is false:

(a) The sentence: “if 2 + 2 = 2, then 1 + 3 = 5"

(b) The sentence: “if 2 + 2 = 4, then π is rational"

8. Let p ↔ q be a DOUBLE CONDITIONAL sentence. Classify the following statements as either true or false:

(a) The sentence: “2 + 2 = 4 if and only if π is irrational"

(b) The sentence: “2 + 2 ≠ 4 if and only if π is rational"

9. Summarize the following “truth table":

p / q / p ^ q / p ˅ q / ~p / p → q / p ↔ q
T
T
F
F / T
F
T
F

10. Find the bitwise OR, bitwise AND, and bitwise XOR of the bit strings:

01 1011 0110 and 11 0001 1101

11. Find the bitwise OR, bitwise AND, and bitwise XOR of each of these pairs of bit strings:

(a) 101 1110, 010 0001

(b) 1111 0000, 1010 1010

(d) 11 1111 1111, 00 0000 0000

12. Evaluate each of these expressions:

(a) 1 1000 ˄ (0 1011 ˄ 1 1011)

(b) (0 1111 ˄ 1 0101) ˄ 0 1000

(d) (1 1011 ˅ 0 1010) ˄ (1 0001 ˅ 1 1011)

13. Construct a truth table for each of these compound propositions:

(a) p ¬ q (b) p (p ˅ q)

(d) (p ˅ q) → (p q)

(e) (p ↔ q) (p ↔ ¬ q)

(f) (p q) → (p ¬ q)

(g) (p q) ˄ (p ¬ q)

(f) (p ↔ q) (¬ p ↔ ¬ q)

Propositional Equivalences

1. Show that the following propositions are logically equivalent:

(a) ¬ (p ˄ q) and ¬ p ˅ ¬ q

(b) ¬ (p ˅ q) and ¬ p ˄ ¬ q

(d) p ˅ (q ˄ r) and (p ˅ q) ˄ (p ˅ r)

2. Show that the following propositions are logically equivalent:

(a) ¬ (p → q) and p ˄ ¬ q

(b) ¬ [p ˅ (¬ p ˄ q)] and ¬ p ˄ ¬ q

3. Show that the following are logically equivalent:

(a) p → q and ¬ q → ¬ p

(b) ¬ (p q) and p ↔ q

4. Verify that the proposition: p ˅ ¬ (p ˄ q) is a tautology.

5. Show that each of these conditional statements is a tautology by using truth tables:

(a) (p ˄ q) → p (b) p → (p ˅ q)

(e) ¬ (p → q) → p (f) ¬ (p → q) → ¬ q

6. Determine whether each of the following is a tautology:

(a) [¬ p ˄ (p → q)] → ¬ q

(b) [¬ q ˄ (p → q)] → ¬ p

7. Determine the validity of each of the following arguments:

(a) p → q, ¬ p ├ ¬ q

(b) p → q, ¬ p ├ ¬ p

8. Show that the following argument is a fallacy: p → q, ¬ p ├ ¬ q

9. Prove that the following argument is valid: p → ¬ q, r → q, r ├ ¬ p

10. Test the validity of each of the following arguments:

(a) If 7 is less than 4, then 7 is not a prime number.

7 is not less than 4.

7 is a prime number.

(b) If two sides of a triangle are equal, then the opposite angles are equal.

Two sides of a triangle are not equal.

The opposite angles are not equal.

It did not rain.

John was not sick.

(d) If the teacher is absent, Martha will complete her homework.

Martha did not complete her homework.

The teacher was not absent.

Predicates and Quantifiers

1. Let P(x) denote the statement “x > 3.” What are the truth values of P(4) and P(2)?

[Answer: true, false]

2. Let Q(x, y) denote the statement “x = y + 3.” What are the truth values of the propositions Q(1, 2) and Q(3, 0)?

[Answer: false, true]

3. Let R(x, y, z) denote the statement “x + y = z.” What are the truth values of the propositions R(1, 2, 3) and R(0, 0, 1)?

[Answer: true, false]

4. Let P(x) denote the statement “x ≤ 4.” What are these truth values?

(a) P(0) (b) P(4) (c) P(6)

[Answer: (a) true (b) true (c) false]

5. Let P(x) be the statement “the word x contains the letter a.” What are these truth values?

(a) P(orange) (b) P(lemon) (c) P(true) (d) P(false)

[Answer: (a) T (b) F (c) F (d) T]

6. Let Q(x, y) denote the statement “x is the capital of y.” What are these truth values?

(a) Q(Denver, Colorado)

(b) Q(Detroit, Michigan)

(d) Q(New York, New York)

[Answer: (a) T (b) F (c) T (d) F]

7. Let P(x) denote the statement “x + 1 > x.” What is the truth value of the quantification: , where the domain consists of all real number?

[Answer: true]

8. Let Q(x) be the statement “x < 2.” What is the truth value of the quantification: , where the domain consists of all real number?

[Answer: false]

9. Let P(x) be the statement “x > 3.” What is the truth value of the quantification: , where the domain consists of all real number?

[Answer: true]

10. Let Q(x) denote the statement “x = x + 1.” What is the truth value of the quantification: , where the domain consists of all real number?

[Answer: false]

11. Let the numbers 1, 2, 3, 4, 5, be the domain. Determine the truth value of each of the following quantifications:

(a) , where Q(x) is the statement “x + 3 ≤ 7.”

(b) , where Q(x) is the statement “x + 3 ˂ 5.”

(d) , where Q(x) is the statement “x + 3 ˂ 7.”

(e) , where Q(x) is the statement “x2 + 3 ≤ 20.”

(f) , where Q(x) is the statement “x2 + 3 ≤ 20.”

[Answer: (a) (b) (c) (d) (e) (f)]