Scribd
Upload
32 views

IMA_111_Tutorial_1

Uploaded by

cactusvernal123
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
32 views

IMA_111_Tutorial_1

Uploaded by

cactusvernal123
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

IMA 111-Discrete Mathematics: Tutorial 1

August 30, 2024

1. Construct the converse, the inverse, and the contra-positive of the following conditional
statement: “If Calvin gets a hot dog, then Calvin doesn’t get a soda.”

2. Use De Morgan’s Law to write the negation of the following statement, simplifying so that
only simple statements are negated: “If Phoebe buys a pizza, then Calvin buys popcorn.”

3. Explain, without using a truth table, why (p ∨ ¬q) ∧ (q ∨ ¬r) ∧ (r ∨ ¬p) is true when p, q,
and r have the same truth value and it is false otherwise.

4. Explain, without using a truth table, why (p∨q∨r)∧(¬p∨¬q∨¬r) is true when at least one of p, q,
and r is true and at least one is false, but is false when all three variables have the same truth value.

5. What is the value of x after each of these statements is encountered in a computer program, if
x = 1 before the statement is reached?
a) if x + 2 = 3 then x := x + 1
b) if (x + 1 = 3) OR (2x + 2 = 3) then x := x + 1
c) if (2x + 3 = 5) AND (3x + 4 = 7) then x := x + 1
e) if x < 2 then x := x + 1

6. Let P (x) mean “x likes pepperoni”, O(x) mean “x likes onions”, N A(x) mean “x does not
want anchovies”, A(x, y) mean “x is afraid of y ”. Translate each statement into English.
(a) ∀x(P (x) → ¬N A(x))
(b) ∃x(P (x) ∧ N A(x))
(c) ∀x∃y(P (x) ∧ A(x, y))
(d) ¬∃x[∀y(O(x) ∧ N A(y) ∧ A(x, y))]

7. Let P (x) mean “x likes pepperoni”, O(x) mean “x likes onions”, N A(x) mean “ x does not
want anchovies”, A(x, y) mean “ x is afraid of y ”. Translate each statement into logical symbols.
(a) “Some people don’t like pepperoni.”
(b) “Everyone who likes pepperoni likes onions.”
(c) “Everyone likes pepperoni and onions.”

8. Negate the following quantified statements. Simplify your answers so that only simple state-
ments are negated.
(a) ∀x(P (x) → Q(x))
(b) ∀x∀y[x < y → (∃z(x < z < y))]

9. Negate the following quantified statements. Simplify your answers so that only simple state-
ments are negated.
(a) Every student sleeps late on Saturdays.
(b) There is a professor who is afraid of the ducks.

1
10. Let P (x, y) be a propositional function. Show that ∃x∀yP (x, y) → ∀y∃xP (x, y) is a tau-
tology.

11. Let P (x) and Q(x) be propositional functions. Show that ∃x(P (x) → Q(x)) and ∀xP (x) →
∃xQ(x) always have the same truth value.

12. (a) If ∀y∃xP (x, y) is true, does it necessarily follow that ∃x∀yP (x, y) is true?
(b) If ∀x∃yP (x, y) is true, does it necessarily follow that ∃x∀yP (x, y) is true?

13. (a) Find a domain for the quantifiers in ∃x∃y(x ̸= y ∧ ∀z((z = x) ∨ (z = y))) such that
this statement is true.
(b) Find a domain for the quantifiers in ∃x∃y(x ̸= y ∧ ∀z((z = x) ∨ (z = y))) such that this
statement is false.

14. Use existential and universal quantifiers to express the statement “Everyone has exactly two
biological parents” using the propositional function P (x, y), which represents “x is the biological
parent of y.”

15. The quantifier ∃n denotes “there exists exactly n,” so that ∃n xP (x) means there exist ex-
actly n values in the domain such that P (x) is true. Determine the true value of these statements
where the domain consists of all real numbers.
a) ∃0 x (x2 = −1)
b) ∃1 x(|x| = 0)
c) ∃2 x (x2 = 2)
d) ∃3 x(x = |x|)(
(A ∨ ¬C) → B
16. Premises: , Prove: A → D.
¬D → ¬B
(
(A ∧ ¬D)
17. Premises: , Prove: (A → B) → ¬C.
B → (C → D)

(¬B ∨ C) → A


18. Premises: B→D , Prove: A.
C ∨ ¬D

19. Prove that if n is an integer, then 3n2 + n + 14 is even.

20. Prove that if n is an integer, then 2n2 + n + 1 is not divisible by 3 .

21. Obtain the product-of-sums canonical forms of the following formulas.


(a) (P ∧ Q ∧ R) ∨ (¬P ∧ R ∧ Q) ∨ (¬P ∧ ¬Q ∧ ¬R)
(b) (P ∧ Q) ∨ (¬P ∧ Q) ∨ (P ∧ ¬Q)
(c) (P ∧ Q) ∨ (¬P ∧ Q ∧ R)

22. Obtain the principal disjunctive and conjunctive normal forms of the following formulas.
(a) (¬P ∨ ¬Q) → (P ⇄ ¬Q)
(b) Q ∧ (P ∨ ¬Q)
(d) (P → (Q ∧ R)) ∧ (¬P → (¬Q ∧ ¬R))
(c) P ∨ (¬P → (Q ∨ (¬Q → R)))
(c) P → (P ∧ (Q → P ))
(f) (Q → P ) ∧ (¬P ∧ Q),

Which of the above formulas are tautologies?

You might also like