Discrete Exams

Q1: Which of these are propositions? What are the truth values of those that
are propositions?.
a) Do not pass go.
b) What time is it?
c) There are no black flies in Maine.
d) 4+x=5.
e) The moon is made of green cheese.
f) 2n≥ 100.
Ans:
a) Is NOT a proposition;
b) Is NOT a proposition;
c) Is a proposition; with the truth value False.
d) Is NOT a proposition; as its truth value Unknown.
e) Is a proposition; with the truth value False.
f) Is NOT a proposition; as its truth value Unknown.

Q2. What rule of inference is used in each of these arguments?

a) Alice is Mathematics major. Therefore, Alice is either mathematics major or a
computer science major.
b) Jerry is mathematics major and a computer sciencemajor. Therefore, Jerry is
mathematics major.
C). If it is rainy, then the pool will be closed. It is rainy. Therefore, the pool is closed
d) If it snows today, the university will close. The university is not closed today.
Therefore, it did not snow today.
Ans:
a) Addition.
b) Simplification.
c) Modus ponens.
d) Modus tollens
Q.3: Give as good a big-O estimate as possible for each of these functions.
a) (n²+8) (n+1)
b) (2n+n2) (n3 + 3")
c) nn+n2n+5") (n! +5")

Q4. Convert the binary expansion of each of these to a decimal, an octal and
hexadecimal expansion.
A )(1111 0111) 2
b) (1010 1010 1010) 2
c) (111 0111 0111 0111)2
Ans:

Denary Hexadecimal Octal Binary

(base 10) (base 16) (base 8) (base 2)

0 0 000 00000000
1 1 001 00000001
2 2 002 00000010
3 3 003 00000011
4 4 004 00000100
5 5 005 00000101
6 6 006 00000110
7 7 007 00000111
8 8 010 00001000
9 9 011 00001001
10 A 012 00001010
11 B 013 00001011
12 C 014 00001100
13 D 015 00001101
14 E 016 00001110
15 F 017 00001111

a).
(11110111)2 = (247)10
Step by step solution
Step 1: Write down the binary number:
11110111
Step 2: Multiply each digit of the binary number by the corresponding power of two:
1x27 + 1x26 + 1x25 + 1x24 + 0x23 + 1x22 + 1x21 + 1x20
Step 3: Solve the powers:
1x128 + 1x64 + 1x32 + 1x16 + 0x8 + 1x4 + 1x2 + 1x1 = 128 + 64 + 32 + 16 + 0 + 4 + 2
+1
Step 4: Add up the numbers written above:
128 + 64 + 32 + 16 + 0 + 4 + 2 + 1 = 247.
So, 247 is the decimal equivalent of the binary number 11110111.

(11110111)2 = (367)8
Step by step solution
Step 1: Write down the binary number
(011110111)2
Group all the digits in sets of three starting from the LSB (far right). Add zeros to the left
of the last digit if there aren't enough digits to make a set of three.
011 110 111
Step 2: Use the table below to convert each set of three into an octal digit. In this case,
011=3, 110=6, 111=7.
So, the number 367 is the octal equivalent to 11110111 in binary.
To convert from binary to octal use the following table:
Bin: 000 001 010 011 100 101 110 111
Octal: 0 1 2 3 4 5 6 7

(11110111)2 = (F7)16
Step by step solution
Step 1: Write down the binary number:
11110111
Step 2: Group all the digits in sets of four starting from
the LSB (far right). Add zeros to the left of the last digit
if there aren't enough digits to make a set of four:
1111 0111
Step 3: Use the table below to convert each set of
three into an hexadecimal digit:
1111 = F, 0111 = 7
So, F7 is is the hexadecimal equivalent to the decimal
number 11110111.
To convert from binary to hexadecimal use the
following table:
Bin: 0000 0001 0010 0011 0100 0101 0110 0111
Hexa: 0 1 2 3 4 5 6 7
Bin: 1000 1001 1010 1011 1100 1101 1110 1111
Hexa: 8 9 A B C D E F
b).
(101010101010)2 = (2730)10
Step by step solution
Step 1: Write down the binary number:
101010101010
Step 2: Multiply each digit of the binary number by the
corresponding power of two:
1x211 + 0x210 + 1x29 + 0x28 + 1x27 + 0x26 + 1x25 +
0x24 + 1x23 + 0x22 + 1x21 + 0x20
Step 3: Solve the powers:
1x2048 + 0x1024 + 1x512 + 0x256 + 1x128 + 0x64 +
1x32 + 0x16 + 1x8 + 0x4 + 1x2 + 0x1 = 2048 + 0 +
512 + 0 + 128 + 0 + 32 + 0 + 8 + 0 + 2 + 0
Step 4: Add up the numbers written above:
2048 + 0 + 512 + 0 + 128 + 0 + 32 + 0 + 8 + 0 + 2 + 0
= 2730.
So, 2730 is the decimal equivalent of the binary
number 101010101010.

(101010101010)2 = (5252)8
Step by step solution
Step 1: Write down the binary number
(101010101010)2
Group all the digits in sets of three starting from the
LSB (far right). Add zeros to the left of the last digit if
there aren't enough digits to make a set of three.
101 010 101 010
Step 2: Use the table below to convert each set of
three into an octal digit. In this case,
101=5, 010=2, 101=5, 010=2.
So, the number 5252 is the octal equivalent to
101010101010 in binary.
To convert from binary to octal use the following table:
Bin: 000 001 010 011 100 101 110 111
Octal: 0 1 2 3 4 5 6 7

(101010101010)2 = (AAA)16
Step by step solution
Step 1: Write down the binary number:
101010101010
Step 2: Group all the digits in sets of four starting from
the LSB (far right). Add zeros to the left of the last digit
if there aren't enough digits to make a set of four:
1010 1010 1010
Step 3: Use the table below to convert each set of
three into an hexadecimal digit:
1010 = A, 1010 = A, 1010 = A
So, AAA is is the hexadecimal equivalent to the
decimal number 101010101010.
To convert from binary to hexadecimal use the
following table:
Bin: 0000 0001 0010 0011 0100 0101 0110 0111
Hexa: 0 1 2 3 4 5 6 7
Bin: 1000 1001 1010 1011 1100 1101 1110 1111
Hexa: 8 9 A B C D E F

c).
(111 0111 0111 0111)2

(111011101110111)2 = (30583)10

(111011101110111)2 = (73567)8

(111011101110111)2 = (7777)16

(111011101110111)2 = (30583)10
Step by step solution
Step 1: Write down the binary number:
111011101110111
Step 2: Multiply each digit of the binary number by the corresponding power of two:
1x214 + 1x213 + 1x212 + 0x211 + 1x210 + 1x29 + 1x28 + 0x27 + 1x26 + 1x25 + 1x24 + 0x23 +
1x22 + 1x21 + 1x20
Step 3: Solve the powers:
1x16384 + 1x8192 + 1x4096 + 0x2048 + 1x1024 + 1x512 + 1x256 + 0x128 + 1x64 +
1x32 + 1x16 + 0x8 + 1x4 + 1x2 + 1x1 = 16384 + 8192 + 4096 + 0 + 1024 + 512 + 256 +
0 + 64 + 32 + 16 + 0 + 4 + 2 + 1
Step 4: Add up the numbers written above:
16384 + 8192 + 4096 + 0 + 1024 + 512 + 256 + 0 + 64 + 32 + 16 + 0 + 4 + 2 + 1 =
30583.
So, 30583 is the decimal equivalent of the binary number 111011101110111.

(111011101110111)2 = (73567)8
Step by step solution
Step 1: Write down the binary number
(111011101110111)2
Group all the digits in sets of three starting from the LSB (far right). Add zeros to the left
of the last digit if there aren't enough digits to make a set of three.
111 011 101 110 111
Step 2: Use the table below to convert each set of three into an octal digit. In this case,
111=7, 011=3, 101=5, 110=6, 111=7.
So, the number 73567 is the octal equivalent to 111011101110111 in binary.
To convert from binary to octal use the following table:
Bin: 000 001 010 011 100 101 110 111
Octal: 0 1 2 3 4 5 6 7

(111011101110111)2 = (7777)16
Step by step solution
Step 1: Write down the binary number:
0111011101110111
Step 2: Group all the digits in sets of four starting from the LSB (far right). Add zeros to
the left of the last digit if there aren't enough digits to make a set of four:
0111 0111 0111 0111
Step 3: Use the table below to convert each set of three into an hexadecimal digit:
0111 = 7, 0111 = 7, 0111 = 7, 0111 = 7
So, 7777 is is the hexadecimal equivalent to the decimal number 111011101110111.
To convert from binary to hexadecimal use the following table:
Bin: 0000 0001 0010 0011 0100 0101 0110 0111
Hexa: 0 1 2 3 4 5 6 7
Bin: 1000 1001 1010 1011 1100 1101 1110 1111
Hexa: 8 9 A B C D E F
Q.5 Let P(n) be the statement that a postage of n cents can be formed using
just 3-cent and 5-cent stamps. The parts of this exercise outline a strong
induction proof that P(n) is true for n ≥ 8.
(a) Show that the statements P(8), P(9), and P(10) are true, completing the basis step
of the proof.
(b) What is the inductive hypothesis of the proof?
(c) What do you need to prove in the inductive step?
(d) Complete the inductive step for k ≥ 10.
(e Extra credit 2 pts.) Is P(n) true for n ≥ 8 if you have only one 5-cent stamp? only two
5-cent stamps?
Solution.
(a) 8 = 3 +5, 9 = 3+3+3, 10 = 5+5, so that P(8), P(9), and P(10) are true.
(b) The inductive hypothesis is that P(n) is true for 8 ≤ n ≤ k, where k ≥ 10. (Notice that
this is a strong induction proof, which requires a stronger hypothesis.)
(c) We need to prove in the inductive step that P(k + 1) is true.
(d) If k ≥ 10, then k + 1 = (k −2)+3. Since k −2 ≥ 8, by the induction hypothesis we have
that P(k − 2) is true, i.e., a postage of2 k−2 cents can be paid by using 3-cent and 5-
cent stamps. Adding one 3-cent stamp, we can pay a postage of k+1 cents, i.e., P(k+1)
is true.
(e) Of course, in this question, it is assumed that 3-cent stamps are also available,
because otherwise only postage of 5 or 10 cents can be paid. The answer to the first
question is “no”, e.g., a postage of 10 cents cannot be paid if we are allowed to use no
more than one 5-cent stamp. The answer to the second question is “yes”, because we
obtain 8, 9, and 10 using no more than two 5-cent stamps (and, perhaps, some 3-cent
stamps), and the argument in the inductive step shows that we can obtain all other
amounts from 8, 9, or 10 by just adding a certain number of 3-cent stamps. (Any integer
is congruent to either 8 or 9 or 10 modulo 3.)
Q.6 A coin is flipped 10 times where each flip comes up either heads or tails.
How many possible outcomes.
a) are there in total?
b) contain exactly two heads
c) contain at most three tails?

Ans:
A) are there in total ?

2^10 = 1024

B) contain exactly two heads?

C(10,2)= (10!/(2!*8!))

The answer is 45.

C) contain at most three tails?

C(10,3)+C(10,2)+C(10,1)+C(10,0)

=((10!/(3!*7!)) + (10!/(2!*8!)) + (10!/(1!*9!)) + (10!/(0!*10!))

= 120 + 45 + 10 + 1

The answer is 176.

8). Solve the recurrence relations together with the initial conditions given.
an = 5an−1 − 6an−2 for n ≥ 2, a0 = 1, a1 = 0
Solution:
Characteristic equation: r2 − 5r + 6 = 0
Determinant: 52 − 4(1)(6) = 25 − 24 = 1
Since our determinant is greater than 0, we know we can use Theorem 1.
Find the characteristic root.
We can factor r2 − 5r +6 = 0 into (r −2)(r −3) = 0.
So our roots are r1 = 2 and r2 = 3.
Use Theorem 1 to find our general solution: an = α12n + α23n for some constants α1
and α2.
Find α1 and α2 by using our initial conditions.
For a0 = 1 1 =α120 +α230
1 =α1+α2
For a1 = 0
0 =α121 +α231
0 =2α1 +3α2
Solve the system of equations:
α1 = 1−α2
0=2(1−α2)+3α2
0=2−2α2+3α2
0=2+α2
α2=−2
α1=1−(−2)
α1=3
Our solution is an=3·2n−2·3n

***************************