1.4.3 Boolean Algebra Flashcards
What is this gate, what are the rules and what is the truth table associated?
- AND gate
- Both inputs must be on for the output to be 1
What is this gate, what are the rules and what is the truth table associated?
- OR gate
- 1 input must be on for the output to be on
What is this gate, what are the rules and what is the truth table associated?
- XOR gate
- If both inputs are on or off, the output is 0
What is this gate, what are the rules and what is the truth table associated?
- NOT gate
- It reverses the input
What is the main reason for using binary and name examples?
- Easy to build electronic circuits with just 2 states:
- RAM: Voltage or no voltage
- Hard Disks: Polarity
- Optical: Pits and lands
What is the symbol used for NOT and what is a rule with this?
- ¬
- Negation
What is the symbol used for AND and what is the rule associated?
- ∧
- Conjunction
What is the symbol used for the OR gate and what is the rule associated?
- ∨
- Disjunction
What is the symbol for the XOR gate and what is the rule associated?
- Exclusive Disjunction
Exam Question: What is the difference between an OR and an XOR gate?
- OR gate outputs true if at least 1 of its inputs is true.
- XOR gate outputs true if one and only 1 of its inputs are true.
What is the Boolean Expression for this?
What is the Boolean expression for this?
Why is important to use as few expressions as possible?
- Reduce the size of the circuit
- Reduce the cost of manufacturing
- Reduce the power consumption
- Execute instructions as quickly as possible, reducing the need to fetch variables from memory
What does the Karnaugh map illustrate
B is false
The expression is NOT B (¬B)
What does this Karnaugh map illustrate?
- A is true and B is true
- A ∧ B
What are some rules on the boxes in Karnaugh maps?
- Boxes must be rectangles or squares
- No diagonal boxes
- Boxes can only contain 1s
- Boxes must be as large as possible
- Boxes can overlap
- Smallest possible number of boxes
- Boxes must be 2n = 1, 2, 4, 8, 16
What are the rules and laws of Boolean simplification?
- De Morgan’s law
- Distribution
- Association
- Commutation
- Double Negation
What is De-Morgan’s Law
- Way of simplifying Boolean expressions by inverting all the variables ANDs and ORs and vice versa and inverting the whole expression
What is the answer to these:
- X ∧ 0
- X ∧ 1
- X ∧ X
- X ∧ ¬X
- X ∨ 0
- X ∨ 1
- X ∨ X
- X ∨ ¬X
- 0
- X
- X
- 0
- X
- 1
- X
- 1
What are the 2 versions of the De Morgan’s Law?
- First Law: NOT (A AND B) is the same as (NOT A) OR (NOT B)
- Second Law: NOT(A OR B) is the same as (NOT A) AND (NOT B)
How do you apply the De Morgan’s Law, what are the rules?
- Change OR to AND (or vice versa)
- NOT the terms on each side of the operator
- Invert result by adding NOT to everything that has changed
- Get rid of any double negation and unnecessary brackets
Apply De Morgan’s Law on this expression:
¬(A V B)
- ¬(A ∧ B)
- ¬(¬A ∧¬B)
- ¬¬(¬A ∧ ¬B)
- ¬A ∧ ¬B
What is Double Negation?
- If you reverse something twice you get back to what you started
What is Association?
- To remove brackets from an expression and regroup variables
What is Commutation?
- The order of application of 2 separate terms is not important
- A V B is the same as B V A
What is Distribution?
- Allows us to multiply or factor out an expression
- A ∧ (B V C) is the same as (A ∧ B) V (A ∧ C)
What is the logical circuitry called when using Binary Addition?
- Half and Full Adders
What is the process of producing a Half Adder?
- Adding 2 numbers (A and B) together will produce 2 outputs, Digit and Carry bit out (C out)
- Consider both the digit and Carry bit out separately. This produces an XOR and AND gate
- Then add them together into a circuit
What is the process of producing a Full Adder?
- Instead of only considering 2 digits, consider 3 (A, B, and Cin (Carry bit in)
- Use the first half adder and label the output X
- Use 2nd half adder and add X with Cin to give digit
- They have created a carry bit - this must be fed into the next calculation
What is conjunction and disjunction?
- Conjunction: Both sides of the proposition must be true
- Disjunction: Either side of the proposition must be true
What is negation and implication?
- Negation: Reverse the truth of a proposition
- if something is true, we can infer that something else is also true
Why are flip flops required?
- Full adders provide us with important processing functions but don’t allow us to maintain a state
- As well as performing calculations, computers must be able to store and recall values
- They need to preserve data over time, flip - flop is used
What is a flip flop?
- Fundamental logic circuit that can store 1 bit and flip it between 1 and 0
- Has 2 inputs - a single bit data input (D) and a clock signal (C) - clock signal provided by another circuit that changes state at time intervals
- Has 2 outputs - a single bit data output (Q) and the inverse of the data output (¬Q)
What type of gate does a Flip-Flop use?
- NAND gates
- (NOT AND) - reverse the output of AND gates
Why is a D-type flip flop a positive edge triggered circuit?
- The output can only be changed when the clock pulse is at rising or positive edge
- If the clock is not rising or positive edge, the output value is held and does not change
How does a D-Type Flip-Flop store values?
- The clock pulses are at regular intervals. There is a delay between high 1 and low 0s
- A D type flip-flop circuit only receives high signal at the rising edge - the circuit perceives its input more accurately from the clock changing states
- Small fraction that signal reads 1 before falling back to 0, only takes reading at rising edge
How do D type - Flip-flops maintain values?
- The single bit data input is set to 0
- The clock pulse is high and is at its rising edge
- Output of Q is 0
- Output of NOT Q is 1
Summarise a D-type flip flop:
- Circuit used as a memory unit for registers and static memory to hold the state of a single bit
- 2 inputs: D and clock input
- At rising edge, output of Q is set to current value in D
- Q will remain static and locked in place - even if D changes until the next clock pulse (rising edge)
Exam Question:
State the purpose of a flip-flop (1)
- To store the state of a bit
