10. Logical completeness

• We say that a set of gates

  • {AND, OR, NOT}

  is logically complete, if we are able to:

  1. draw a set of programmable connections between gates without any other kind of gate, and

  2. completely satisfy the requirements of the truth table.

   

• We may also say that such set of gates {AND, OR, NOT}

  • is sufficient to build an implementation of a given truth table, and

  • we don't need any other gates to do the job.