MTH 305 Final, Fall 2010
Lebanese American University · Probability and Statistics · 9 pages
More MTH 305 files
Show the text of this final exam
Lebanese American University
Fall 2010
Byblos
Discrete Structure I
Final Exam
Name:
Date: 27/01/2011
Duration: 2h
ID:
Part I: Problems (70 pts)
1. [10 pts] Find a resolution proof and a formal proof for the following proposi-
tional logic formula:
{A −! B ; ¬A −! C ; C −! D} ` ¬B −! D
1
L.S.F
2
L.S.F
2. [15 pts] Prove, by induction, the following:
(a) 36n − 26n is always divisible by 35 for all n 2 N⇤.
(b)
n
X
k=1
1
k2 2 − 1
n.
3
L.S.F
4
L.S.F
3. [10 pts] Solve using pigeonhole principle the following two independent ques-
tions:
(a) A computer network consists of eight computers. Each computer is di-
rectly connected to at least one of the other computers. Show that there
are at least two computers in the network that are directly connected to
the same numbers of other computers.
(b) 1335 people are seated in a row of 2001 chairs. Prove that there are 3
consecutive non-empty chairs.
5
L.S.F
4. [10 pts] We consider the following program (input is n and output is r):
r:=0;
if n > 0 then
begin r := 1;
i := 1;
while i < n do
begin i := i + 1;
r := r + 3*i*i - 3*i + 1;
end;
end;
(a) Find the output of the program for n = 1, n = 2 and n = 3.
(b) Which function computes the program?
6
L.S.F
5. [15 pts] Verify, in the following cases, if the binary relation R defined over the
set X is an equivalence relation or not. If R is an equivalence relation then
find the set of classes ⇡R.
(a) X = R and x R y i↵ |x| + |y| = |x + y|.
(b) X = R⇤ and x R y i↵ xy > 0.
(c) X = R and x R y i↵ x2 − xy + 2x − 2y = 0.
7
L.S.F
8
L.S.F
6. [10 pts] Find for the following two ordered sets the maximal, minimal, greatest
and least elements (if any):
(a) X = {2, 3, 6, 12, 18, 24} and the order is x R y i↵ x divides y.
(b) X = {{2}, {2, 3}, {2, 4}, {1, 3, 4}, {2, 3, 4}} and the order is x R y i↵ x ✓ y.
9
L.S.F