Discrete Mathematics - Practice Midterm (Solutions)
K. Subramani
LCSEE,
West Virginia University,
Morgantown, WV
{[email protected]}
1
Problems
1. Propositional Logic.
Show that the following arguments are valid.
(a) A0 ∧ (B → A) → B 0 .
(b) (A ∧ B) → (A → B 0 )0 .
Solution:
(a) Consider the following proof sequence:
(i)
(ii)
(iii)
(iv)
(v)
(vi)
B → A hypothesis.
B 0 ∨ A (i), implication.
A ∨ B 0 (ii), commutativity.
A0 → B 0 (iii), implication.
A0 hypothesis.
B 0 (iv), (v), Modus Ponens.
(b) We use an intuitive argument. Consider the following two cases:
(i) A is true - In this case, the given argument boils down to B → B which is trivially true.
(ii) A is false - In this case, the antecedent is false and hence the argument itself is true.
2
2. Predicate Logic.
(a) Show that the argument (∀x)[P (x) ∨ Q(x)] → [[(∃x)P (x)]0 → (∀x)Q(x)] is valid.
(b) Consider the verbal argument:Some plants are flowers. All flowers smell sweet. Therefore, some plants smell
sweet. Is it valid?
Solution:
(a) Using the deduction method, we can rewrite the given argument as:
[(∀x)[P (x) ∨ Q(x)] ∧ [(∃x)P (x)]0 ] → (∀x)Q(x)
Consider the following proof sequence:
(i) [(∃x)P (x)]0 hypothesis.
(ii) P (a)0 (i), e.i.
(iii) (∀x)[P (x) ∨ Q(x)] hypothesis.
1
(iv)
(v)
(vi)
(vii)
P (a) ∨ Q(a) (iii), u.i.
P (a)0 ∨ Q(a) (iv), implication.
Q(a) (ii), (v), Modus Ponens.
(∀x)Q(x) u.g.
The last step is justified, since Q(a) was not deduced from a hypothesis in which a is a free variable nor has Q(a)
been deduced by existential instantiation from a formula in which a is a free variable.
(b) Let P (x) ≡ “x is a plant”, F (x) ≡ “x is a flower” and S(x) ≡ “x smells sweet.” Accordingly, the verbal
argument can be symbolized as follows:
(∃x)[P (x) ∧ F (x)] ∧ (∀x)[F (x) → S(x)] → (∃x)[P (x) ∧ S(x)]
Consider the following proof sequence:
(i)
(ii)
(iii)
(iv)
(v)
(vi)
(vii)
(viii)
(ix)
(∃x)[P (x) ∧ F (x)] hypothesis.
P (a) ∧ F (a) (i), ei.
(∀x)[F (x) → S(x)] hypothesis.
F (a) → S(a) (iii), ui.
F (a) (ii), simplification.
S(a) (iv), (v) Modus Ponens.
P (a) (ii), simplification.
P (a) ∧ S(a) (vi), (vii), Conjunction.
(∃x)[P (x) ∧ S(x)] (viii), eg.
2
3. Non-Inductive Proof.
Prove the following two conjectures.
Pn
(a) Let A = n1 · i=1 xi . Is it necessarily true that at least one of the xi s is greater than or equal to A?
(b) Prove that log2 5 is not rational.
Solution:
(a) Yes, it is necessarily
Pn true. Assume the contrary and let xi < A, ∀i = 1, 2 . . . , n. Then,
hence, A > n1 i=1 xi , thereby contradicting the hypothesis.
Pn
i=1
xi < n · A and
(b) Assume that log2 5 is rational. Then, we can write log2 5 = pq , where p and q are integers, q 6= 0 and gcd(p, q) =
1.
Observe that,
log2 5
=
p
q
⇒5
=
2q
⇒ 5q
=
2p
p
Since 2 | 2p , 2 must divide 5q . However, 5 is a prime number, therefore 2 must divide 5, which is a contradiction.
2
4. Inductive Proof. Prove that
Pn
1
i=1 i2
< 2 − n1 , n ≥ 2.
2
Solution: BASIS : n = 2.
LHS
=
=
=
<
=
=
2
X
1
2
i
i=1
1 1
+
1 4
5
4
3
2
1
2−
2
RHS
Thus the basis is proven.
I NDUCTIVE S TEP : Assume that
k+1
X
i=1
1
i2
Pk
1
i=1 i2
=
<
=
=
=
=
<
=
=
< 2 − k1 , for some k ≥ 2. Observe that,
k
X
1
1
+
2
i
(k
+
1)2
i=1
1
1
)+
, by inductive hypothesis
k
(k + 1)2
1
1
2−( −
)
k (k + 1)2
(k + 1)2 − k
2−(
)
k(k + 1)2
k 2 + 2k + 1 − k
2−(
)
k(k + 1)2
k2 + k + 1
2−(
)
k(k + 1)2
k2 + k
2−(
), subtracting a smaller number
k(k + 1)2
k(k + 1)
2−
k(k + 1)2
1
2−
k+1
(2 −
We have thus shown that, if the conjecture is true for any k ≥ 2, then it must also be true for (k + 1). Using the first
principle of mathematical induction, we conclude that the presented conjecture is true for all n ≥ 2. 2
5. Recurrences.
(a) Solve the recurrence:
S(1)
=
1
S(n)
= S(n − 1) + n, n ≥ 2
(b) Show that [F (n + 1)]2 = [F (n)]2 + F (n − 1) · F (n + 2), ∀n ≥ 2.
3
Solution:
(a) The given recurrence is a first-order, linear recurrence. The parameters of the recurrence are: k0 = 1, c = 1 and
g(i) = i.
As per the formula discussed in class,
S(n)
=
1n−1 · 1 +
n
X
1n−i · i
i=2
=
1+
n
X
i
i=2
=
n
X
i
i=1
=
n · (n + 1)
, as proved in class
2
(b) Observe that,
[F (n + 1)]2
=
[F (n) + F (n − 1)]2 , by definition
=
[F (n)]2 + [F (n − 1)]2 + 2 · F (n) · F (n − 1)
=
[F (n)]2 + F (n − 1) · [F (n − 1) + 2 · F (n)]
=
[F (n)]2 + F (n − 1) · [F (n − 1) + F (n) + F (n)]
=
[F (n)]2 + F (n − 1) · [F (n + 1) + F (n)], by definition
=
[F (n)]2 + F (n − 1) · F (n + 2), by definition
2
4
© Copyright 2024 ExpyDoc
