1.4.3 - Boolean Algebra Flashcards
What does ¬ mean?
NOT
What does V mean?
OR
What does ^ mean?
AND
What does ⊻ mean?
XOR
What is a Karnaugh map?
Are a visual method for simplifying logical expressions.
They show all the outputs on a grid of all possible outcomes.
The method is to create blocks of 1s as large as possible so that the 1s are covered by as few blocks as possible and
no 0s are included.
The blocks can wrap around the diagram if necessary, in both directions, from side to side or from top to bottom.
The rules for using Karnaugh maps are:
no 0s (zeros) allowed
no diagonal blocks
groups as large as possible
every 1 must be within a block
overlapping allowed
wrap around allowed
the smallest possible number of groups.
What are the outputs of an AND gate?
The output is true ONLY if both inputs are true (1,1 or 0,0)
What are the outputs of the OR gate?
The output is true if either or both of the inputs are true. (1,1, 1,0 = 1 but 0,0 = 0)
What are the outputs of the NOT gate?
The output is the negative of the input (1 = 0, 0 = 1)
What are the outputs of a NAND gate?
The output is true if one or both of the inputs are false (0,0 = 1, 1,0 = 1, 0,1 = 1, 1,1 = 0)
What are the outputs of a NOR gate?
The output is true if both the inputs are false (0,0 = 1, anything else = 0)
What are the outputs of an XOR gate?
The output is true if only one of the inputs is true, but not both (1,1 = 0, 1,0 = 1, 0,1= 1, 0,0 = 0)
What are de morgan’s laws
Involve breaking a negation and changing the operator between two inputs.
¬(A V B) ≡ ¬A ∧ ¬B
¬(A ∧ B) ≡ ¬A V ¬B
They are used when a negation applies to the whole of an operator between two inputs, and result in two negated inputs acted upon by a different operator.
What is the distribution law?
Another two useful laws, distribution applies to conjunction over disjunction as well as disjunction of conjunction. You can think of these as being similar to expanding brackets.
Conjunction over disjunction: A ∧ (B V C) ≡ (A ∧ B) V (A ∧ C)
Disjunction of conjunction: A V (B ∧ C) ≡ (A V B) ∧ (A V C)
It’s also important to note that distribution can be carried out over the same operator:
A ∧ (B V C) ≡ (A ∧ B) V (A ∧ C)
A V (B ∧ C) ≡ (A V B) ∧ (A V C)
What is the association law?
Associative laws involve the addition or removal of brackets and reordering of inputs in a
Boolean expression.
(A ∧ B) ∧ C ≡ A ∧ (B ∧ C) ≡ A ∧ B ∧ C
(A V B) V C ≡ A V (B V C) ≡ A V B V C
What is the commutation law?
Laws of commutation show that the order of inputs around an operator does not matter, in the same way that
3 + 2 = 5 = 2 + 3.
A ∧ B ≡ B ∧ A
A V B ≡ B V A
What is the double negation law?
If you negate an input twice, you can remove both negations and retain the same truth value. NOT NOT A is the same as A.
¬(¬ A) ≡ A
What are the three logic circuits we need to know?
D-Type Flip Flops, Half Adders and Full Adders.
What is a flip flop?
A flop flop is a type of logic circuit which can store the value of one bit. A flip flop has two inputs, a control signal and a clock input. A clock is a regular pulse generated by the CPU which is used to coordinate the computers’ components.
A clock pulse rises and falls, with edges labelled rising or falling. The output of a D-type flip flop can only change at a rising edge, the start of a clock tick.
What is an adder?
An adder is a logic circuit which adds together the number of inputs which are true, and outputs that number in binary. There are two adder circuits you need to know: half and full.
What is a half adder?
A half adder has two inputs, A and B, and two outputs, Sum and Carry. The circuit is formed from just two logic gates: AND and XOR. (AND is the CARRY and the SUM is the XOR)
What is a full adder?
A full adder is similar to a half adder, but has an additional input, allowing for carry in to be represented.
The full adder logic circuit is formed from two XOR gates, two AND gates and an OR gate as shown in the diagram.
Because the full adder has a carry input, the circuits can be chained together to form an adder with as many inputs as is required.
Cout (is the carry bit)
Cin, A, B (are the inputs)
S (the sum)
