Revision Exercises and Answers

1 – Propositional logic / 10
2 – Predicate logic / 24
3 – Inference rules / 20
4 – Proof Methods / 20
Discrete Structure - Review Exercises and Answers

1 Propositional logic — 10 points

Part A — 5 points
Show that the compound proposition below is a contradiction:
(p ∨ q) ∧ (¬p ∨ q) ∧ (p ∨ ¬q) ∧ (¬p ∨ ¬q)

Via truth tables:

p q p ∨ q ¬p ∨ q p ∨ ¬q ¬p ∨ resu
¬q lt
T T T T T F F
T F T F T T F
F T T T F T F
F F F T T T F

Via
equivalences (p ∨ q) ∧ (¬p ∨ q) ∧ (p ∨ ¬q) ∧ (¬p ∨ ¬q)
: ≡ ((p ∧ ¬p) ∨ q) ∧ ((p ∧ ¬p) ∨ ¬q)
≡ (F ∨ q) ∧ (F ∨ ¬q)
≡ q ∧ ¬q
≡ F

2
Discrete Structure - Review Exercises and Answers

Part B — 5 points

You go to your digital circuit lab to implement a boolean function

represented by the fol- lowing compound proposition: (p ∧ q) ∨ (¬q ∧ p) ∨
(r ∧ p) ∨ (q ∧ r).
However, you realise that you only have 2 AND-gates (binary) and 2
OR-gates (binary) in your knapsack.
Give a circuit that implements the boolean function and uses only the
gates available in your knapsack. Indeed, you will get a bonus 2
points if you use only 2 gates in total.

(p ∧ q) ∨ (¬q ∧ p) ∨ (r ∧ p) ∨ (q ∧ r)
≡ (p ∧ (q ∨ ¬q)) ∨ (r ∧ p) ∨ (q ∧ r)
≡ (p ∧ T ) ∨ (r ∧ p) ∨ (q ∧ r)
≡ p ∨ (r ∧ p) ∨ (q ∧ r)

The above solution is acceptable, but for bonus marks, can be simplified
further to:

p ∨ (r ∧ p) ∨ (q ∧ r)
≡ (p ∧ T ) ∨ (p ∧ r) ∨ (q ∧ r)
≡ (p ∧ (r ∨ T )) ∨ (q ∧ r)
≡ (p ∧ T ) ∨ (q ∧ r)
≡ p ∨ (q ∧ r)

Note that the drawing of the circuit is not included here but was expected in
your solution.

3
Discrete Structure - Review Exercises and Answers

2 Predicate logic — 24 points

Part A — 12 points
Circle true or false
1. ∀x∃y(x2 = y), where the domain is the set of real numbers. [true] [false]
2. ∃x∀y((y /= 0) → (xy = 1), where the domain is the set of real [true] [false]
numbers.
3. The following are logically equivalent: ¬(p ∧ ¬q) and (p → q) [true] [false]
4. The following are logically equivalent: ∀x¬Q(x) and ¬∃x¬Q(x) [true] [false]
5. ∃xP (x) ∧ ∀x¬Q(x) logically implies ∃x(P (x) ∨ Q(x)) [true] [false]
6. Consider the domain of discourse to be the set {1, 2, 3}, and
Q(x, y) =“y ≥ x”, [true] [false]
and R(y) =“y is odd”. Then ∀y((∀xQ(x, y)) → R(y)) is true.

Justification not required, but given here for your understanding:

1. ∀x, take y = x2.
2. Obviously wrong. 2

For example, if y = 2, then the only x satisfying xy = 1 is x =1/2

.
If y = 3, however,
the only x satisfying xy = 1 is x = 1/3,

Thus, there is no one x for all y.

3. ¬(p ∧ ¬q) ≡ (¬p ∨ q) ≡ (p → q).
4. ∀x¬Q(x) ≡ ¬¬∀x ¬Q(x) ≡ ¬∃xQ(x) /≡ ¬∃x¬Q(x).
5. ∃xP (x) ∧ ∀x¬Q(x) implies ∃xP (x), which implies ∃x(P (x) ∨ Q(x)).
6. ∀xQ(x, y) is only satisfied for y = 3, and R(3) is true, so the predicate holds.

4
Discrete Structure - Review Exercises and Answers

Part B — 12 points

Consider the following statements:

B(x): “x is a baby”
L(x): “x is logical”
M (x) “x is able to manage a crocodile”
D(x): “x is despised”
Suppose the domain consists of all people.

B1 Express each of the following statements using quantifiers,

logical connectives and the propositional functions given above.
phrase in English logical statement
1 Babies are illogical. ∀x(B(x) → ¬L(x))
.
2 Nobody despised who can manage ¬∃x(D(x) ∧ M (x)) ≡ ∀x(D(x) → ¬M
. a crocodile. (x))
3 Illogical persons are despised. ∀x(¬L(x) → D(x))
.
Babies cannot manage crocodiles. ∀x(B(x) → ¬M (x))

B2 Does 4. follows from 1., 2., 3. ?

If yes, justify your
argument. If no,
explain why it doesn’t.

Using 1, 2, 3 by universal instantiation, for an arbitrary a:

1. B(a) → ¬L(a)
2. D(a) → ¬M (a)
3. ¬L(a) → D(a)

Applying the transitivity of → on 1 and 3, we get B(a) → D(a). Applying

transitivity again on this and 2, we get B(a) → ¬M (a). Since the choice
of a was arbitrary, we have that:
∀x(B(x) → ¬M (x)).

5
Discrete Structure - Review Exercises and Answers

3 Inference rules — 20 points

Part A — 10 points Using inference rules, show that the hypotheses:

• If a student likes chocolate then he/she answers the questions.
• If a student doesn’t like chocolate then he/she is not motivated to go to
class.
• If a student is not motivated to go to class then

he/she fails the course. lead to the conclusion:

• If a student doesn’t like chocolate then he/she fails the course.

Answer:
Define the
following:
l : student likes chocolate student
a : answers the question

m : student is motivated to go to class

f : student fails the course

We translate the hypotheses and conclusion into propositions as follows:

1. l → a
2. ¬l → ¬m
3. ¬m → f
4. ¬l → f

Formal argument:

1. ¬l → ¬m hypothesis
2. ¬m → f hypothesis
3. ¬l → f hypothetical syllogism of 1, 2

6
Discrete Structure - Review Exercises and Answers

Part B — 10 points Justify the rule of universal transitivity,

which states that
If x(P (x)  Q(x)) and x(Q(x)  R(x)) are true
then x(P (x)  R(x)) is true, where the domain of all quantifiers is the
same.

Step Justification
1. ∀x(P (x) → Q(x)) hypothesis
2. P (a) → Q(a) universal instantiation for arbitrary a
3. ∀x(Q(x) → R(x)) hypothesis
4. Q(a) → R(a) universal instantiation for arbitrary a
5. P (a) → R(a) hypothetical syllogism for 2, 4
6. ∀x(P (x) → R(x)) universal generalization

7
Discrete Structure - Review Exercises and Answers

4 Proof Methods — 20 points

For this question you will need the definitions of odd and even, seen in class.
DEFINITION: An integer n is even if there exists an integer k
such that n = 2k. An integer n is odd if there exists an integer
k such that n = 2k + 1.

Part A — 10 points Prove that if m + n and n + p are even numbers, then m +

p is even.
Answer
Let m, n, p be integers such that m + n is even and n + p is even.
By definition of odd, there exist k and kt such that
m + n = 2k and
n + p = 2kt.
Thus, m = 2k - n and p = 2kt - n.
This gives:
m + p = (2k − n) +
(2kt -n)
= 2k − n + 2kt − n
Therefore m + p is even. = 2(k + kt − n)

8
 Part B — 10 points
Prove the following:
For any integer number n, if n2 + 5 is odd then n is even, using:
B1 (5 points) a proof by contraposition.
B2 (5 points) a proof by contradiction.
Answer
B1. Contrposition: p  q q  p
p: n2 + 5 is odd
q: n is even
Assume n is odd, and show n2 + 5 is even.
Let n be an odd number. Thus, n = 2k + 1 for some integer k. Then:
n2 + 5 = (2k + 1)2 + 5
= 4k2 + 4k + 1 + 5
= 4k2 + 4k + 6
= 2(2k2 + 2k + 3)

Thus, n2 + 5 is an even.
B2.
Contradiction: p  q  a contradiction
p: n2 + 5 is odd
q: n is even
Assume n2 + 5 is odd and n is odd and reach a contradiction.

Let n be an odd number (q) such that n2 + 5 is odd (p).

Thus, there exist k, kt such that n = 2k + 1 and n2 + 5 = 2kt +
1.
Thus, n2 + 5 = (2k + 1)2 + 5 = 2kt + 1,
so 4k2 + 4k + 6 = 2kt + 1,
i.e. 5 = 2kt - 4k2 - 4k = 2(kt - 4k2 - 4k).
This implies that 5 is an even number, which is a contradiction.

*******