(4.6) Fundamentals of computer systems

Question 1

NOT gate

Answer 1

Ā

A Ā
0 1
1 0

It is also known as an inverter. If the input variable is A, the inverted output is known as NOT A.

(A with a bar over the top), A’, ~A, ¬A, are all common notation

Question 1

AND gate

Answer 1

A . B
A B O
1 1 1
0 1 0
1 0 0
0 0 1

A and B must both be equal to 1 for an output of 1.

Question 1

OR gate

Answer 1

A+B
A B O
1 1 1
1 0 1
0 1 1
0 0 0

A, B or both A and B must be equal to 1 for an output of 1

Question 2

XOR gate

Answer 2

A ⊕ B
A B O
1 1 0
1 0 1
0 1 1
0 0 0

Exclusively A or B must be equal to 1 for an output of 1

Question 2

NAND gate

Answer 2

___
A.B
A B O
1 1 0
1 0 1
0 1 1
0 0 1

For an output of 1, A and B cannot both be 1.
(This is the opposite of the AND gate)

Question 3

NOR gate

Answer 3

_____
A + B
A B O
1 1 0
1 0 0
0 1 0
0 0 1

If either A or B are equal to 1 the output is 0.
(This is the opposite of the OR gate)

Question 4

Order of operations in boolean expressions of logic gates

Answer 4

NOT
XOR
AND
OR

Question 4

de Morgan’s first law

Answer 4

─…─….───
A . B = A+B
The inversion of the product is the same as the sum of the inversions.

Question 4

de Morgan’s second law

Answer 4

───….─..─
A . B = A+B
The inversion of the sum is the same as the product of the inversions.

Question 4

General boolean identities (1)
X . 0 =
X . 1 =
X . X =
X . ¬X =

Answer 4

X . 0 = 0
X . 1 = X
X . X = X
X . ¬X = 0

Question 5

General boolean identities (2)
X + 0 =
X + 1 =
X + X =
X + ¬X =
¬¬X =

Answer 5

X + 0 = X
X + 1 = 1
X + X = X
X + ¬X = 1
¬¬X = X

Question 5

Boolean algebra commutative rule

Answer 5

X . Y = Y . X
X + Y = Y + X

Question 5

Boolean algebra associative rule

Answer 5

X . (Y . Z) = (X . Y) .Z
X + (Y + Z) = (X + Y) + Z

Question 5

Boolean algebra distributive law

Answer 5

X . (Y + Z) = X . Y + X . Z
(X+ Y) (W + Z) = X . W + X . Z + Y . W + Y . Z

Question 5

Boolean algebra absorbtion rules

Answer 5

X + (X . Y) = X
X . (X + Y) = X

proof:
X + (X . Y) = X . 1 + (X . Y)
= X . (1 + Y)
= X . 1 = X

Question 5

half-adder logic circuit

Answer 5

Half-adder circuit: takes a 2-bit input and produces a 2-bit output which is the correct result of a binary addition of the two inputs

Digit = ¬A.B + A.¬B / A xor B
Carry = A.B

ex:
A B D C
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

Question 6

full-adder logic circuit combines two half adders. Uses a 3-bit input (including inputs A and B as well as carry bit C).

Answer 6

Full adder circuit: combines two half adders. Uses a 3-bit input (including inputs A and B as well as carry bit C). An extra OR gate outputs the carry bit.

A+B+C D C
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

Question 6

Use of the edge-triggered D-type flip-flop’ as a memory unit

Answer 6

What is a flip-flop?
A basic circuit which can store one bit and flip it between 1 and 0. It has two inputs.

Input 1: Control input (normally labelled D)
Input 2: Clock signal

D-type flip-flops:

• Are positive edge-triggered (meaning output can only be changed from 1 to 0 or 0 to 1 when clock pulse is at a ‘rising’ or positive edge)

-if clock is not ‘rising’ or at positive edge, output value is held and does not change

-They can be used as a memory cell to store the state of a single bit

Control Clock Output
1 0 0
1 1 1
0 0 1
0 1 0