Logic Gates & Boolean Algebra

• NOT, or negation, reverses an input. 0 becomes 1 and 1 becomes 0. It is written as an overline
• AND, or conjunction, returns 1 if both inputs are 1, else it returns 0. It is written as a • between two inputs
• OR, or disjunction, returns 1 if either input is 1. It only returns 0 if both inputs are 0. It is written as a + between two inputs
• XOR, or exclusive disjunction, returns 1 if exactly one input is 1. It returns 0 if both inputs are the same (both 0 or both 1). It is written as a ⊕ between two inputs
• NAND, meaning 'not and', returns 0 if both inputs are 1, else it returns 1. It is written with a • between inputs with an overline above the entire expression
• NOR, meaning 'not or', returns 1 only if both inputs are 0, else it returns 0. It is written with a + between inputs with an overline above the entire expression
• The logic gate for NOT is a right facing triangle pointing into a small circle
• The logic gate for AND is an elongated semicircle - the left side is flat, the right side is curved
• The logic gate for NAND is the same as AND, but with a small circle at the end
• The logic gate for OR is an arrow-like shape with the left side curved inwards and the right side tapering to a point
• The logic gate for XOR is the same as OR, but with an extra curved line to the left
• The logic gate for NOR is the same as OR, but with a small circle at the end
• We can work through a logic gate circuit by creating a truth table, tracking what every output would be for every given input
• We can keep track of each input combination by counting up in binary
• We can write boolean expressions from logic diagrams and vice versa
• A half adder can take a 2-bit input and produce the correct result of a binary addition, using a digit and a carry
• In a half adder, the digit = A ⊕ B, and the carry = A • B. This means:

  0 plus 0 = 0

  1 plus 0 = 1

  0 plus 1 = 1

  1 plus 1 = 0 with a carry
• A full adder combines two half adders and has an additional third input for a carry bit. They can be concatenated together to add large numbers
• A flip-flop has two inputs: the control input, D, and the clock signal, which changes states at frequent intervals
• An edge-triggered D-type flip-flop is a flip-flop that will only change its output if the clock pulse is at a rising edge
• A D-type flip-flop can be used to store a single bit of memory. They can be joined together to store more data. Eg 16 would store 2 bytes. They are present in register memory and static RAM
• Boolean algebra has an order of precedence:

  (highest)

  Brackets

  NOT

  AND

  OR

  (lowest)
• B OR NOT C AND A would have an order of precedence as follows: B OR ((NOT C) AND A)
• A AND A, as well as A OR A, both equal A and can be simplified as such
• Double negation, indicated by two overlines, cancels out so that no negation occurs
• De Morgan's laws state that

  -NOT (A AND B) is the same as (NOT A) OR (NOT B)

  -NOT (A OR B) is the same as (NOT A) AND (NOT B)
• De Morgan's laws can be remembered as 'break the bar, change the sign'
• A OR (NOT A) always equals 1
• A AND (NOT A) always equals 0
• Gates for logic with only ORs or only ANDs can be swapped around without changing the logic. eg X OR (Y OR Z) = (X OR Y) OR Z
• Brackets containing ORs that are ANDed together produce something similar to a cartesian product.

  (W OR X) AND (Y OR Z) = (W AND Y) OR (W AND Z) OR (X AND Y) OR (X AND Z)
• X AND (X OR Y), as well as X OR (X AND Y), will always equal X