Flashcards

∧ is AND, ∨ is OR, ¬ is NOT and ⊻ is XOR (exclusive OR).

2ⁿ rows, one for each combination of inputs. Three inputs need 8 rows.

¬(A ∧ B) ≡ ¬A ∨ ¬B and ¬(A ∨ B) ≡ ¬A ∧ ¬B. To remove a ¬ from outside a bracket, change the operator and negate each term inside.

¬¬A ≡ A. Negating a value twice gives the original value.

A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C) and A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C).

Commutation: the order of the inputs does not matter, A ∧ B ≡ B ∧ A. Association: the grouping does not matter when the operator is the same, (A ∨ B) ∨ C ≡ A ∨ (B ∨ C).

A. If A is 1 the whole expression is 1, and if A is 0 then A ∧ B is also 0 (absorption).

This is Gray code order: neighbouring cells differ in only one variable, so a group of neighbouring 1s shows which variables do not affect the output.

Groups are rectangles of 1, 2, 4, 8 or 16 cells. Make them as large as possible and use as few as possible. Groups may overlap and wrap around the edges. Every 1 must be in a group, and no 0 can be. In each group's term, a variable that is 0 throughout is written with ¬.

Sum S ≡ A ⊻ B and carry C ≡ A ∧ B.

A full adder has a third input, the carry in from the previous column, so full adders can be chained to add multi-bit numbers. It can be built from two half adders and an OR gate.

On the rising edge of the clock pulse, the output Q takes the value of the data input D. At all other times Q holds its value, so it stores one bit.

Equivalence, read "is equivalent to" or "if and only if": the expressions on each side give the same output for every combination of inputs, e.g. ¬(A ∨ B) ≡ ¬A ∧ ¬B.

AND: flat back with a round, D-shaped front. OR: curved back with a pointed front. NOT: a triangle with a small circle at its point. XOR: an OR shape with an extra curved line across the inputs.

Inputs: data (D) and clock. Outputs: Q, the stored bit, and ¬Q, which is always its opposite.

One half adder adds A and B. A second adds that sum to the carry in, giving the final sum. An OR gate combines the two half adders' carries to give the carry out.

Groups whose size is not a power of two (such as 3 or 6), groups containing a 0, and groups that are not a single rectangle, such as diagonals and L-shapes. Groups may overlap and wrap around the edges.