# chemistry

strength

CSIS 2050 – Fall 2014 Final Exam: (100 points) Chapters – 9, 11, and 12

Instructions: Please read thoroughly.

Note: You must supply all details for full credit. Partial credit will be given only when sufficient details have been supplied. Correct answers with no explanation or a procedure will be counted as wrong. Perform all computations and do not give inconclusive results. When finding Boolean expressions, these must be given in reduced form. Note that some problems have multiple questions, so make sure you answer each question posed. You must return the exam and solution sheets with your full name printed on the first page of both. You are allowed to use Blackboard for the power point notes, solutions to both quizzes and practice problems, and any supplementary material I may have provided. However, the use of the Internet for other purposes is not allowed (i.e., search engines, chats, or email).

1. Consider the rooted tree shown in Figure 1. Write the expression using

(1a) Preorder traversal. (6 points).

(1b) Inorder traversal. (7 points).

(1c) Postorder traversal. (7 points).

Write parentheses where appropriate. Show all your work.

∗

+

− +

−

−

/

+∗

C D D A B

A B

BA

C

Figure 1: Tree for problem 1.

2. Consider the following alarm problem. The alarm will ring if the alarm switch is turned on and the door is not closed, or it is after 6:00 P.M. and the window is not closed. Identify all the variables and answer the following questions. Show all your work.

(2a) Construct a truth table of inputs and outputs. (6 points).

(2b) Write a standard sum-of-products expression for the output (Boolean expression). (7 points).

(2c) Draw a circuit diagram of the system. (7 points).

1

3. A switching circuit has two control inputs (C1 and C2), two data inputs (X1 and X2), and one output (Y ). The circuit performs one of the logic operations AND, OR, EQU (equivalence), or XOR (exclusive or) on the two data inputs. The function performed depends on the control inputs as shown in Table 1 below.

Table 1: Switching circuit truth table.

C1 C2 Function Performed by Circuit

0 0 OR 0 1 XOR 1 0 AND 1 1 EQU

The type of functions performed by the circuit are described in the truth tables shown in Table 2 below. The gate symbols are shown in Figure 2. Answer the following questions. Show all your work.

(3a) Construct an expanded truth table of inputs and outputs. (6 points).

(3b) Write a standard sum-of-products expression for the output (Boolean expression). (7 points).

(3c) Draw a circuit diagram of the system. (7 points).

Table 2: Truth tables for logic operations.

AND Truth Table OR Truth Table

X1 X2 X1 ·X2

0 0 0 0 1 0 1 0 0 1 1 1

X1 X2 X1 +X2

0 0 0 0 1 1 1 0 1 1 1 1

XOR Truth Table EQU Truth Table

X1 X2 X1 ⊕X2

0 0 0 0 1 1 1 0 1 1 1 0

X1 X2 X1 ≡ X2

0 0 1 0 1 0 1 0 0 1 1 1

2

ORAND

XOR EQU

+

Figure 2: Gates for problem 3.

4. When binary data is transmitted or stored, an extra bit (called a parity bit) is fre- quently added for the purpose of error detection. For example, if data is being trans- mitted in groups of 7 bits, an eighth bit can be added to each group of 7 bits to make the total number of 1’s in each block of 8 bits an odd number. An example is shown in Figure 3 below.

Y Parity

Checker

Data

Input Output

X

01101101 10101011 01110000

Clock

00000001

7 Data Bits ︷ ︸︸ ︷

Parity Bits

︸ ︷︷ ︸

8-Bit Word

00000010

Figure 3: Parity checker concept.

If any single bit in the 8-bit word is changed from 0 to 1 or from 1 to 0 during transmission, the parity is no longer odd. Thus, if any single bit error occurs in transmission of a word with odd parity, the presence of this error can be detected because the number of 1 bits in the word have been changed from odd to even. Design a parity checker for serial data. Serial implies that the data enters the circuit sequentially, one bit at a time. This is to be a sequential circuit with one input X (in addition to the clock) as shown in Figure 3. When a sequence of 0’s and 1’s is applied to the X input, the output of the circuit should be Y = 1 if the total number of 1’s received is odd. That is, the output should be 1 if the parity is odd. On the other hand, if data which originally had odd parity is transmitted to the circuit, a final output of Y = 0 indicates that an error in transmission has occurred (i.e., the number of 1’s is even). The sequential circuit must remember whether the total number of 1 inputs received is even or odd; therefore, only two states are required, S0 and S1, corresponding to an even number of 1’s received and an odd number of 1’s received, respectively. The circuit should start at state S0 since no 1’s have been received and zero is an even number. Use D flip-flops. Answer the following questions. Show all your work.

3

(4a) Construct a state transition diagram. Use a Moore model so that the output depends on the state. (5 points).

(4b) Create a truth table containing the present state, inputs, next state, D flip-flop, and output. (5 points).

(4c) Write a standard sum-of-products expression for the D flip-flop and output (Boolean expressions). (5 points).

(4d) Draw a circuit diagram of the system. (5 points).

5. Design a Mealy sequential system with one input X and one output Y such that Y = 1 if and only if the sequence 101 has been detected. Otherwise the output is Y = 0. Use D flip-flops. Answer the following questions. Show all your work.

(5a) Construct a state transition diagram. Use a Mealy model so that the output depends on the input. (5 points).

(5b) Create a truth table containing the present state, inputs, next state, D flip-flops, and output. (5 points).

(5c) Write a standard sum-of-products expression for the D flip-flops and output (Boolean expressions). (5 points).

(5d) Draw a circuit diagram of the system. (5 points).

4

1

01 11 10

00

01

11

10

00 01 11 10

00

01

11

10

00 01 11 10

00

01

11

10

00 01 11 10

00

01

11

10

00 01 11 10

00

01

11

10

00 01 11 10

00

01

11

10

0 1

0

1

0 1

0

1

0 1

0

1

0 1

0

1

00

01

11

10

00

01

11

10

00

01

11

10

00

01

11

10

0 1 0 1 0 1 0 1

00

01

11

10

00

01

11

10

00

01

11

10

00

01

11

10

0 1 0 1 0 1 0

00

5

0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1

0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1

0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

6

Q1 Q0 x Q +

1 Q +

0 D1 D0 Y

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

Q1 Q0 x Q +

1 Q +

0 D1 D0 Y

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

Q1 Q0 x Q +

1 Q +

0 D1 D0 Y

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

Q1 Q0 x Q +

1 Q +

0 D1 D0 Y

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

Q x Q+ D Y

0 0 0 1 1 0 1 1

Q x Q+ D Y

0 0 0 1 1 0 1 1

Q x Q+ D Y

0 0 0 1 1 0 1 1

Q x Q+ D Y

0 0 0 1 1 0 1 1

7

x

C

Q

Q̄

y

Q̄C

D

Clock

D Q

8

x

C

Q

Q̄

y

Clock

D

9

10

11

Print Full Name

Solve problem 1 here.

12

Solve problem 1 here.

13

Solve problem 2 here.

14

Solve problem 2 here.

15

Solve problem 3 here.

16

Solve problem 3 here.

17

Solve problem 4 here.

18

Solve problem 4 here.

19

Solve problem 5 here.

20

Solve problem 5 here.

21

Formulas and Definitions:

1. Section 9.1:

(1a) Definition 9.1.1: A (free) tree T is a simple graph satisfying the following: If v and w are vertices in T , there is a unique simple path from v to w. A rooted tree is a tree in which a particular vertex is designated as the root.

2. Section 9.2:

(2a) Definition 9.2.1: Let T be a tree with root v0. Suppose x, y, and z are vertices in T and that (v0, v1, v2, . . . , vn) is a simple path in T . Then

(2a− 1) v n−1 is a parent of vn.

(2a− 2) (v0, v1, . . . , vn−1) are ancestors of vn.

(2a− 3) v n is a child of v

n−1.

(2a− 4) If x is an ancestor of y, then y is a descendant of x.

(2a− 5) If x and y are children of z, then x and y are siblings.

(2a− 6) If x has no children, then x is a terminal vertex (leaf).

(2a− 7) If x is not a terminal vertex, then x is an internal (or branch) vertex.

(2a− 8) The subtree of T rooted at x is the graph with vertex set V and edge E, where V is x together with the descendants of x and

E = {e | e is an edge on a simple path from x to some vertex in V }.

(2b) Theorem 9.2.3: Let T be a graph with n vertices. The following are equivalent.

(2b− 1) T is a tree.

(2b− 2) T is connected and acyclic.

(2b− 3) T is connected and has n− 1 edges.

(2b− 4) T is acyclic and has n− 1 edges.

Note: an acyclic graph is a graph with no cycles. A connected graph is a graph in which we can get from any vertex to any other vertex on a path.

3. Section 9.5:

(3a) Definition 9.5.1: Binary Tree: A binary tree is a rooted tree in which each vertex has either no children, one child, or two children. If a vertex has one child, that child is designated as either a left child or a right child (but not both). If a vertex has two children, one child is designated a left child and the other child is designated a right child.

(3b) Theorem 9.5.4: If T is a full binary tree with i internal vertices, then T has i+ 1 terminal vertices and 2i+ 1 total vertices.

(3c) Theorem 9.5.6: If a binary tree of height h has t terminal vertices, then

log2 t ≤ h.

22

(3d) Definition 9.5.8: A binary search tree is a binary tree T in which data are associated with the vertices. The data is arranged so that, for each vertex v in T , each data item in the left subtree of v is less than the data item in v, and each data item in the right subtree of v is greater than the data item in v.

4. Section 9.6:

(4a) Preorder traversal: (root/left/right)

(4b) Inorder traversal: (left/root/right)

(4c) Postorder traversal: (left/right/root)

5. Chapters 11 and 12: Laws and Theorems of Boolean Algebra:

(5a) x+ 0 = x

(5b) x · 1 = x

(5c) x+ 1 = 1

(5d) x · 0 = 0

(5e) x+ x = x

(5f) x · x = x

(5g) ¯̄x = x

(5h) x+ x̄ = 1

(5i) x · x̄ = 0

(5j) x+ y = y + x

(5k) x · y = y · x

(5l) (x+ y) + z = x+ (y + z) = z + y + z

(5m) (x · y) · z = x · (y · z) = x · y · z

(5n) x(y + z) = xy + xz

(5o) x+ y · z = (x+ y)(x+ z)

(5p) xy + xȳ = x(y + ȳ) = x

(5q) (x+ y)(x+ ȳ) = x

(5r) x+ xy = x(y + 1) = x

(5s) x(x+ y) = x

(5t) (x+ ȳ)y = xy

(5u) xȳ + y = x+ y

(5v) (x+ y)(x̄+ z) = xz + x̄y

(5w) xy + x̄zy = (x+ z)(x̄+ y)

(5x) xy + yz + x̄z = xy + x̄z

(5y) (x+ y)(y + z)(x̄ + z) = (x+ y)(x̄+ z)

23