Logic gates

• A little bit of theory
  • An algebra
  • Boolean algebra - formal definition
  • AND, OR and NOT rules
  • Why we take care about this algebra
  • Functionally complete set of Boolean operators
    • Completeness of NAND gate set
    • Completeness of OR and NOT gates set
• A little bit of application
  • Example 1
    • Identity comparator
    • Magnitude comparator
    • Verify magnitude comparator
• A little bit of practice
  • Step 1: What do we want our logic circuit will do?
  • Step 2: Define input-output relationship
  • Step 3: Find Boolean expressions equivalent to our truth table
    • Boolean expression for carry out output
    • Boolean expression for value output
  • Step 4: Simplify Boolean expressions
  • Step 5: Prepare logic circuit based on Bolean expressions
  • Step 6: Use real chips to implement logic circuit we have found
• Exercise 1
• Exercise 2

• set $B$,
• two binary operations over elements from set $B$ called AND ($\cdot$) and OR (+),
• one unary operation called NOT (line over symbol, like $\overline{x}$) and,
• two distinct elements 0 and 1; both from set $B$.

Sometimes instead of AND we use $\cdot$, instead of OR we use $+$ and instead of NOT we use a line over a symbol like $\overline{x}$.
Next, for all elements $a$, $b$ and $c$ of $B$, define a set $A$ of the following axioms
\begin{align*}
a + (b + c) &= (a + b) + c & a \cdot (b \cdot c) &= (a \cdot b) \cdot c & \text{associativity}\\
a + b &= b + a & a \cdot b &= b \cdot a & \text{commutativity}\\
a + 0 &= a & a \cdot 1 &= a & \text{identity}\\
a + (b \cdot c) &= (a + b) \cdot (a + c) & a \cdot (b + c) &= (a \cdot b) + (a \cdot c) & \text{distributivity}\\
a + \overline{a} &= 1 & a \cdot \overline{a} &= 0 & \text{complements}
\end{align*}
Notice that above axioms shows some duality: every time we replace $+$ by $\cdot$ and 0 by 1 or reverse, we obtain second form. For example from $a + 0 = a$ we obtain $a \cdot 1 = a$. Boolean algebra is a six-tuple $T$ such that all the axioms from set $A$ hold.

With the axioms we can proof many different things and formulas. All of them are important, but one is very often used: De Morgan's laws
\begin{align*}
\overline{a + b} &= \overline{a}\cdot \overline{b}\\
\overline{a \cdot b} &= \overline{a} + \overline{b}
\end{align*}
From our point of view the most important is the simplest Boolean algebra, the two-element Boolean algebra, which has only two elements, 0 and 1.

NOT 1 = 0

Proof:

a OR     0 = a

a OR NOT a = 1

substituting a := 1 we obtain
1 OR     0 = 1

1 OR NOT 1 = 1
and in consequence
NOT 1 = 0
NOT 0 = 1

Proof: By analogy we can proof NOT 0 = 1
================================================================================
0 AND 0 = 0

Proof:

0 AND 0 = [from identity] = (0 AND 0) OR 0 =

        = [from complements] = (0 AND 0) OR (0 AND (NOT 0)) =

        = [from NOT 0 = 1] = (0 AND 0) OR (0 AND 1) =

        = [from distributivity] = 0 AND (0 OR 1) =

        = [from comutativity] = 0 AND (1 OR 0) =

        = [from identity] = 0 AND 1 =

        = [from NOT 0 = 1] = 0 AND (NOT 0) =

        = [from complements] = 0
0 AND 1 = 0

Proof: from identity a AND 1 = a
1 AND 0 = 0

Proof: from comutativity a AND b = b AND a and next we have previous case
1 AND 1 = 1

Proof: from identity a AND 1 = a
================================================================================
0 OR 0 = 0

Proof: from a OR 0 = a
0 OR 1 = 1

Proof: from comutativity a OR b = b OR a and next we have next case
1 OR 0 = 1

Proof: from a OR 0 = a
1 OR 1 = 1

Proof:

By analogy to 0 AND 0 = 0

What is interesting, Bool introduced his algebra in a book The Mathematical Analysis of Logic (1847), and set forth more fully in his An Investigation of the Laws of Thought (1854). What could be realy depressing for any of us who wants to be a famous scientist is a fact that, during his lifetime, his work seemed to have no practical applications at all. It took a few decades to find application for this algebra. In 1930s Claude Shannon encountered it while studying at MIT, and in 1938 he published a paper describing how Boolean analysis could be applied to circuits using relays. This had immediate practical applications, as telephone networks were growing rapidly, creating complicated switching problems.

a o1(a) o2(a) o3(a) o4(a)

0 1     0     1     0

1 1     1     0     0

o1 - verum (afirmative operator; tautology)

o2 - assertion (projection)

o3 - operator NOT (negation)

o4 - falsum

a b  o1  o2  o3  o4  o5  o6  o7  o8  o9 o10 o11 o12 o13 o14 o15 o16

0 0  0   1   0   1   0   1   0   1   0   1   0   1   0   1   0   1

0 1  0   0   1   1   0   0   1   1   0   0   1   1   0   0   1   1

1 0  0   0   0   0   1   1   1   1   0   0   0   0   1   1   1   1

1 1  0   0   0   0   0   0   0   0   1   1   1   1   1   1   1   1

 o1 - contradiction

 o2 - NOR = NOT OR

 o3 - converse nonimplication

 o4 - negation

 o5 - material nonimplication

 o6 - negation

 o7 - XOR (exclusive disjunction)

 o8 - NAND = NOT AND

 o9 - AND

o10 - XNOR

o11 - projection function

o12 - material implication (rule of interference)

o13 - projection function

o14 - converse implication

o15 - OR

o16 - tautology

Generally, in computer science, among all of logic functions we use six of them
AND, OR, NOT, NAND, NOR, XOR
These logic functions were defined by logic operators in previous section: AND as o9, OR as o15, NOT as o3, NAND as o8, NOR as o2, XOR as 07.
In electronics, these logic functions are implemented as logic gate wich are a physical devices implementing a Boolean function. The following set of symbols is used to denote appropriate logic gate (realising appropriate logic function)

Having a given logic circuit (a set of connected logic gates) we can say, how this set will react in response to input signals. Other words, based on logic gates connections schema we can create input-output relationship table (truth table for this circuit).

The question is if all of them are unique in a sense that are not replaceable by combination of two or more other operators.

In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression. A well-known complete set of connectives is { AND, NOT } and OR, NOT. What can be surprising, the singleton sets NAND and NOR are also functionally complete. Other words, there is a combination of only NAND (or only NOR) gates such that behaves like AND gate, other combination to get OR gate behavior and third combination to get NOT gate functionality.

From the point of view of digital electronics, functional completeness means that every possible logic gate can be realized as a network of gates of the types prescribed by the set. In particular, all logic gates can be assembled from either only binary NAND gates, or only binary NOR gates.

• NOT
  
  $$
  NAND(a, a) = NOT(AND(a, a)) = NOT(a)
  $$
  or the same in other form
  $$
  \overline{a \cdot a} = \overline{a}.
  $$
• AND
  
  \begin{align*}
  NAND(NAND(a, b), NAND(a, b)) &= NOT(AND(NAND(a, b), NAND(a, b))) = NOT(NAND(a,b))\\
  &= NOT(NOT(AND(a,b)))
  \end{align*}
  or the same in other form
  $$
  \overline{\overline{a \cdot b} \cdot \overline{a \cdot b}} = \overline{\overline{a \cdot b}} = a \cdot b.
  $$
• OR
  
  \begin{align*}
  NAND(NAND(a, a), NAND(b, b)) &= NOT(AND(NOT(a), NOT(b))) = OR(NOT(NOT(a)), NOT(NOT(b)))\\
  &= OR(a, b)
  \end{align*}
  or the same in other form
  $$
  \overline{\overline{a \cdot a} \cdot \overline{b \cdot b}} = \overline{\overline{a} \cdot \overline{b}} = \overline{\overline{a}} + \overline{\overline{b}} = a + b.
  $$

There are two main types of digital comparator available and these are.

1. Identity comparator - an identity comparator is a digital comparator that has only one output terminal for when $x = y$.
2. Magnitude comparator - a magnitude comparator is a digital comparator which has three output terminals, one each for equality ($x = y$), greater than ($x > y$) and less than ($x < y$).

How to verify correctness of these circuits I will show explaining magnitude comparator below.

Please check Exercise 1 where you will find close to real magnitude comparator circuit I made in Tinkercad.

x=0   x=0   x=1   x=1

y=0   y=1   y=0   y=1

                   +--------- carry signal (carry out)

                   |

                   1

  0     0     1     1     -- x

  0 +   1 +   0 +   1 +   -- y

----- ----- ----- -----

  0     1     1    10

Now we will incorporate into above carry signal from previous position

carry_in=0

x=0   x=0   x=1   x=1

y=0   y=1   y=0   y=1

  0     0     0     0     -- carry in

  0     0     1     1     -- x

  0 +   1 +   0 +   1 +   -- y

----- ----- ----- -----

  0     1     1    10
carry_in=1

x=0   x=0   x=1   x=1

y=0   y=1   y=0   y=1
  1     1     1     1     -- carry in

  0     0     1     1     -- x

  0 +   1 +   0 +   1 +   -- y

----- ----- ----- -----

  1    10    10    11

• carry out is 1 when carry in is 0, x=1, y=1,
• or when carry in is 1, x=0, y=1,
• or when carry in is 1, x=1, y=0,
• or finally when carry in is 1, x=1, y=1.

Other words we can write that as

c_out = 1 if and only if (

  (c_in, x, y) = (0, 1, 1) or

  (c_in, x, y) = (1, 0, 1) or

  (c_in, x, y) = (1, 1, 0) or

  (c_in, x, y) = (1, 1, 1)

)

c_out = 1 if and only if (

  (NOT(c_in), x, y) = (1, 1, 1) or

  (c_in, NOT(x), y) = (1, 1, 1) or

  (c_in, x, NOT(y)) = (1, 1, 1) or

  (c_in, x, y) = (1, 1, 1)

)

• For three-tuple $(c_{in}, x, y) = (0, 1, 1)$ we obtain
  $$
  c_{out} = \overline{c_{in}}xy + c_{in}\overline{x}y + c_{in}x\overline{y} + c_{in}xy = \overline{0}11 + 0\overline{1}1 + 01\overline{1} + 011 = 111 + 001 + 010 + 011 = 1 + 0 + 0 + 0 = 1.
  $$
• For three-tuple $(c_{in}, x, y) = (1, 0, 0)$ we obtain
  $$
  c_{out} = \overline{c_{in}}xy + c_{in}\overline{x}y + c_{in}x\overline{y} + c_{in}xy = \overline{1}00 + 1\overline{0}0 + 10\overline{0} + 100 = 000 + 110 + 101 + 100 = 0 + 0 + 0 + 0 = 0.
  $$

1. For every Boolean expression, we can take one of its term and repeat it as many times as we want, for example
   \begin{align*}
   a & = a + a + a + a\\
   a \cdot b & = a \cdot a \cdot a \cdot b \cdot b
   \end{align*}
   In this case we did it with a term $c_{in}xy$.
2. Simply rearange terms.
3. Grup terms with brackets.
4. Use distributivity to extract common term.
5. Compute values in brackets.
6. Use identity.

Formula for $v$:
\begin{align*}
v & = \overline{c_{in}}\overline{x}y + \overline{c_{in}}x\overline{y} + c_{in}\overline{x}\overline{y} + c_{in}xy\\
& \overset{(1)}{=} \overline{c_{in}}(\overline{x}y + x\overline{y}) + c_{in}(\overline{x}\overline{y} + xy)
\end{align*}
where

1. Use distributivity to extract common term.

Now it is important to notice that introducing new symbols $a$ and $b$ such that
\begin{align*}
a &= \overline{x}y + x\overline{y}\\
b &= \overline{x}\overline{y} + xy
\end{align*}
we obtain that
$$
\overline{a} = b
$$
Proof of this is not difficult (we will use De Morgan's laws: $\overline{x + y} = \overline{x}\cdot \overline{y}$ and $\overline{x \cdot y} = \overline{x} + \overline{y}$)
$$
\overline{\overline{x}y + x\overline{y}} = \overline{(\overline{x}y)} \cdot \overline{(x\overline{y})} = (\overline{x} + y) \cdot (x + \overline{y}) = (x+\overline{y})x + (x+\overline{y})y = \overline{x}\overline{y}+xy.
$$
Finally we get
$$
v = \overline{c_{in}}a + c_{in}\overline{a}.
$$

download Logisim project

Finally you can use real components to create this circuit.

Circuit for carry signal is presented below:

Test for: carry_in=1, x=0, y=1, GREEN led is ON.

Test for: carry_in=0, x=1, y=0, RED led is ON.

Full circuti is presented below:

c_in = green cable, y = orange cable, x = white cable

AND	OR	NOT
CD4081BE datasheet	CD4071BE datasheet	CD4049 datasheet

More information about adders you can find in this great article Binary Adder

Test for: x=0, y=1.

Test for: x=0, y=1.

Test for: x=1, y=0.

Test for: x=1, y=1.