1.4.3 - Boolean Algebra

Question 1

What does ¬ mean?

Answer 1

NOT

Question 2

What does V mean?

Answer 2

OR

Question 3

What does ^ mean?

Answer 3

AND

Question 4

What does ⊻ mean?

Answer 4

XOR

Question 5

What is a Karnaugh map?

Answer 5

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.

Question 6

What are the outputs of an AND gate?

Answer 6

The output is true ONLY if both inputs are true (1,1 or 0,0)

Question 7

What are the outputs of the OR gate?

Answer 7

The output is true if either or both of the inputs are true. (1,1, 1,0 = 1 but 0,0 = 0)

Question 8

What are the outputs of the NOT gate?

Answer 8

The output is the negative of the input (1 = 0, 0 = 1)

Question 9

What are the outputs of a NAND gate?

Answer 9

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)

Question 10

What are the outputs of a NOR gate?

Answer 10

The output is true if both the inputs are false (0,0 = 1, anything else = 0)

Question 11

What are the outputs of an XOR gate?

Answer 11

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)

Question 12

What are de morgan’s laws

Answer 12

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.

Question 13

What is the distribution law?

Answer 13

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)

Question 14

What is the association law?

Answer 14

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

Question 15

What is the commutation law?

Answer 15

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

Question 16

What is the double negation law?

Answer 16

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

Question 17

What are the three logic circuits we need to know?

Answer 17

D-Type Flip Flops, Half Adders and Full Adders.

Question 18

What is a flip flop?

Answer 18

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.

Question 19

What is an adder?

Answer 19

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.

Question 20

What is a half adder?

Answer 20

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)

Question 21

What is a full adder?

Answer 21

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)