1.15 Boolean Algebra

Question 1

AND Gate

Answer 1

=D-
- Only both fields
|A|B|Y|
|0|0|0|
|0|1|0|
|1|0|0|
|1|1|1|

Question 2

OR Gate

Answer 2

• One or the other, or both
  |A|B|Y|
  |0|0|0|
  |0|1|1|
  |1|0|1|
  |1|1|1|

Question 3

XOR Gate

Answer 3

• Only one or the other, not both
  |A|B|Y|
  |0|0|0|
  |0|1|1|
  |1|0|1|
  |1|1|0|

Question 4

Combining Boolean Operations

Answer 4

• Boolean equations made by combining Boolean operators
• Done in the same way standard mathematical operators are combined
• Every boolean equation can be represented with a truth table

Question 5

Manipulating Boolean Expressions

Answer 5

• Sometimes a long Boolean expression has the same truth table as another shorter expression
• Better to use the shorter versions
• Variety of methods which can be used to simplify expressions

Question 6

Karnaugh Maps

Answer 6

• Tables filled in corresponding to expression’s truth table
• Can be used for a truth table with 2/3/4 variables
• Important that the values in the columns and rows are written using Gray code
• Columns and rows only ever differ by one bit, including wraparound
• To simplify a Boolean expression:
  
  • Write your truth table as a Karnaugh map
  • Highlight all of the 1s in the map with a rectangle. (Larger = better)
  • Only groups of 1s with edges equal to a power of 2 (1, 2, 4 in a row) can be highlighted
  • Remove variables which change within these rectangles from the expression

Question 7

D Type Flip Flop

Answer 7

• Logic circuit which can store the value of one bit
• 2 inputs, control signal & clock
  
  • Clock: Regular pulse generated by CPU, used to coordinate computers’ components
  • Clock pulse rises & falls ___I‾‾‾‾‾I___
  • Edges classified rising or falling
  • Output of a D-type flip flop can only change at a rising edge, the start of a clock tick

● Logic circuit uses 4 NAND gates
● Updates the value of Q to the value of D whenever the clock (CLK) rises
● The value of Q is the stored value

Question 8

Adder

Answer 8

• Adder: A logic circuit which adds together the number of inputs which are True
• Outputs result in binary

Question 9

Half Adder

Answer 9

• Two inputs, A and B
• Two outputs, Sum and Carry
• Formed from two logic gates: AND and XOR
• When both A and B are False, both outputs are False
• When one of A or B is True, Sum (S) is True
• When both inputs are True, Carry (C) is True

|A|B|C|S|
|0|0|0|0|
|0|1|0|1|
|1|0|0|1|
|1|1|1|0|

Question 10

Full Adder

Answer 10

• Similar to a half adder, but has an additional input
• Allows carry in to be represented
• Formed from two XOR gates, two AND gates and an OR gate
• Can be chained together to form a ripple adder with many inputs

|A|B|Cin|Cout|S|
|0|0| 0 | 0 |0|
|0|0| 1 | 0 |1|
|0|1| 0 | 0 |1|
|0|1| 1 | 1 |0|
|1|0| 0 | 0 |1|
|1|0| 1 | 1 |0|
|1|1| 0 | 1 |0|
|1|1| 1 | 1 |1|