boolean algebra

[ 1.4.3 ]

what are the two possible outputs of a boolean equation?

what are the two possible outputs of a boolean equation?

True or False (or 1/0)

why do we use karnaugh maps?

to simplify boolean expressions

how do you find the simplified expression from a completed karnaugh map?

1. take each box in any order

2. take each variable in any order

3. if the digit for the variable in the heading stays the same, keep the variable

4. if the digit for the variable in the heading changes, discard the variable

what are the 8 rules for drawing boxes on a karnaugh map?

1. boxes must be rectangles or squares

2. no diagonal boxes

3. boxes must only contain 1s

4. boxes must be as large as possible

5. boxes can only be made of 2ⁿ 1s ( e.g 1, 2, 4, 8 etc)

6. boxes can overlap

7. use the smallest amount of boxes possible

8. boxes can ‘wrap around’ the edges of the map

why do we simplify boolean expressions?

• decreases considerably the cost of the hardware

• reduces the heat generated by the chip

• most importantly, increases speed

de morgan’s laws

¬(A V B) ≡ ¬A Λ ¬B

¬(A Λ B) ≡ ¬A V ¬B

distribution

A V (B Λ C) ≡ (A V B) Λ (A V C)

A Λ (B V C) ≡ (A Λ B) V (A Λ C)

*note that this works for only AND and only OR as well

association

(A Λ B) Λ C ≡ A Λ (B Λ C) ≡ A Λ B Λ C

(A V B) V C ≡ A V (B V C) ≡ A V B V C

commutation

A V B ≡ B V A

A Λ B ≡ B Λ A

double negation

¬¬A ≡ A

absorption

A Λ (A V B) ≡ A

draw the truth table and symbol for the logic gate AND.

Λ

draw the AND gate and describe it’s function.

• applied to two literals to produce one output

• only outputs true (1) when both literals are true

• can be thought of as applying multiplication to its inputs

draw the truth table and symbol for the logic gate OR.

V

draw the OR gate and describe it’s function.

• applied to two literals to produce one output

• outputs true (1) when one or more literals are true

• can be thought of as applying addition to its inputs

draw the truth table and symbol for the logic gate NOT.

¬

draw the NOT gate and describe it’s function.

• applied to one literal (input) to produce a single output

• ‘flips‘ the value of the input

draw the truth table and symbol for the logic gate XOR.

⊻

draw the XOR gate and describe it’s function.

• applied to two literals (inputs) to produce a single output

• similar to OR, differs when both inputs are true

• only outputs true when exactly one input is true

describe a half-adder and draw the circuit.

• a logic circuit that adds two bits together

• outputs a digit (sum) and a carry bit (remainder)

• does not provide input for a carry bit from a previous addition

describe a full-adder circuit and its function.

• a logic circuit that adds two bits, and a carry bit (Cin) together

• outputs a digit (sum) and a carry bit (remainder)

• can be combined to add larger numbers together (e.g a byte) by feeding the carry bit of the previous addition into the next one

describe a D type flip-flop and it’s function.

• a logic circuit that stores the state of a bit, and can ‘flip’ between 0 and 1

• it has two inputs: a single bit data input (D) and a clock signal

• the output of the circuit (Q) only changes when the clock pulse is at a rising edge

• when this occurs the output is changed to the value of D at that moment