Logic Circuits

1. INTRODUCTION

George Boole (1815-1864), a logician, developed an algebra, known as Boolean algebra to examine a given set of propositions (statements) to check their logical consistency and simplify them by removing redundant statements or clauses. He used symbols to represent simple propositions. Compound propositions were expressed in terms of these symbols and connectives. For example, 'Ram is intelligent and he dose well in examinations' is a compound proposition consisting of two simple ones connected by the connective AND.

     Let the proposition 'Ram is intelligent' be represented by the symbol  A  and left the symbol  B  represent the proposition 'Ram does well in examinations'. A symbolic way of representing the whole statement will be A  AND  B. Similarly, the proposition 'My friend gives me a box of sweets or a greeting card for my birthday' contains the contains the symbols C  and  D, we can write C  OR  D  to refer to the whole statement.

        The use of symbols to represent propositions, connectives, and their truth and falsity led to the name symbolic Logic for this subject.

         In 1938,  Shannon discovered that a simplified version of Booleam algebra can be used in the analysis and synthesis of telephone switching networks where a large number of electromechanical relays and switches were used. The one-to-one correspondence betweensymbolic logic on the one hand and switching circuits on the other hand is explained in the next section.

2. SWITCHING CIRCUITS

Consider a switch which is either 'closed' or 'open'. This is similar to the situation in Propositional Calculus, where a proposition is either 'true' or 'false'. In we have two switches A and B which are normally open. They are connected in series with a battery and a lamp. The lamp will light only when both A and B are closed. Notice the similarity between this and a compound proposition in which an AND connective is used.

      Now consider the arrangement of switches shown in where two switches C  and D  are connected in parallel.  The lamp will light when either C  or  D  or both are closed. We recognize the similarity between this and the truth of a compound proposition when the OR connective is used. We can now see a one-to-one correspondence between 'closed' and 'true'. Similarly, 'open' corresponds to 'false;. Because of this analogy, we call these switching circuits as logic circuits. 

The Logic OR Function function states that an output action will become TRUE if either one “OR” more events are TRUE, but the order at which they occur is unimportant as it does not affect the final result.

For example, A + B = B + A. In Boolean algebra the Logic OR Function follows the Commutative Law the same as for the logic AND function, allowing a change in position of either variable.

The OR function is sometimes called by its full name of “Inclusive OR” in contrast to the Exclusive-OR function we will look at later in tutorial six.

The logic or Boolean expression given for a logic OR gate is that for Logical Addition which is denoted by a plus sign, (+). Thus a 2-input (A B) Logic OR Gate has an output term represented by the Boolean expression of:  A+B = Q.

Switch Representation of the OR Function

 

Here the two switches A and B are connected in parallel and either Switch A OR Switch Bcan be closed in order to put the lamp on. In other words, either switch can be closed, or at logic “1” for the lamp to be “ON”.

Then this type of logic gate only produces and output when “ANY” of its inputs are present and in Boolean Algebra terms the output will be TRUE when any of its inputs are TRUE. In electrical terms, the logic OR function is equal to a parallel circuit.

Again as with the AND function there are two switches, each with two possible positions open or closed so therefore there will be 4 different ways of arranging the switches.

As well as the logic symbols “0” and “1” being used to represent a digital input or output, we can also use them as constants for a permanently “Open” or “Closed” circuit or contact respectively.

A set of rules or Laws of Boolean Algebra expressions have been invented to help reduce the number of logic gates needed to perform a particular logic operation resulting in a list of functions or theorems known commonly as the Laws of Boolean Algebra.

Boolean Algebra is the mathematics we use to analyse digital gates and circuits. We can use these “Laws of Boolean” to both reduce and simplify a complex Boolean expression in an attempt to reduce the number of logic gates required. Boolean Algebra is therefore a system of mathematics based on logic that has its own set of rules or laws which are used to define and reduce Boolean expressions.

The variables used in Boolean Algebra only have one of two possible values, a logic “0” and a logic “1” but an expression can have an infinite number of variables all labelled individually to represent inputs to the expression, For example, variables A, B, C etc, giving us a logical expression of A + B = C, but each variable can ONLY be a 0 or a 1.

Examples of these individual laws of Boolean, rules and theorems for Boolean Algebra are given in the following table.

Truth Tables for the Laws of Boolean

Boolean Expression	Description	Equivalent Switching Circuit	Boolean Algebra Law or Rule
A + 1 = 1	A in parallel with closed = “CLOSED”		Annulment
A + 0 = A	A in parallel with open = “A”		Identity
A . 1 = A	A in series with closed = “A”		Identity
A . 0 = 0	A in series with open = “OPEN”		Annulment
A + A = A	A in parallel with A = “A”		Idempotent
A . A = A	A in series with A = “A”		Idempotent
NOT A = A	NOT NOT A (double negative) = “A”		Double Negation
A + A = 1	A in parallel with NOT A = “CLOSED”		Complement
A . A = 0	A in series with NOT A = “OPEN”		Complement
A+B = B+A	A in parallel with B = B in parallel with A		Commutative
A.B = B.A	A in series with B = B in series with A		Commutative
A+B = A.B	invert and replace OR with AND		de Morgan’s Theorem
A.B = A+B	invert and replace AND with OR		de Morgan’s Theorem

The basic Laws of Boolean Algebra that relate to the Commutative Law allowing a change in position for addition and multiplication, the Associative Law allowing the removal of brackets for addition and multiplication, as well as the Distributive Law allowing the factoring of an expression, are the same as in ordinary algebra.

Each of the Boolean Laws above are given with just a single or two variables, but the number of variables defined by a single law is not limited to this as there can be an infinite number of variables as inputs too the expression. These Boolean laws detailed above can be used to prove any given Boolean expression as well as for simplifying complicated digital circuits.

A brief description of the various Laws of Boolean are given below with A representing a variable input.

Description of the Laws of Boolean Algebra

• Annulment Law – A term AND´ed with a “0” equals 0 or OR´ed with a “1” will equal 1
•  
  • A . 0 = 0    A variable AND’ed with 0 is always equal to 0
  • A + 1 = 1    A variable OR’ed with 1 is always equal to 1
•  
• Identity Law – A term OR´ed with a “0” or AND´ed with a “1” will always equal that term
•  
  • A + 0 = A   A variable OR’ed with 0 is always equal to the variable
  • A . 1 = A    A variable AND’ed with 1 is always equal to the variable
•  
• Idempotent Law – An input that is AND´ed or OR´ed with itself is equal to that input
•  
  • A + A = A    A variable OR’ed with itself is always equal to the variable
  • A . A = A    A variable AND’ed with itself is always equal to the variable
•  
• Complement Law – A term AND´ed with its complement equals “0” and a term OR´ed with its complement equals “1”
•  
  • A . A = 0    A variable AND’ed with its complement is always equal to 0
  • A + A = 1    A variable OR’ed with its complement is always equal to 1
•  
• Commutative Law – The order of application of two separate terms is not important
•  
  • A . B = B . A    The order in which two variables are AND’ed makes no difference
  • A + B = B + A    The order in which two variables are OR’ed makes no difference
•  
• Double Negation Law – A term that is inverted twice is equal to the original term
•  
  • A = A     A double complement of a variable is always equal to the variable
•  
• de Morgan´s Theorem – There are two “de Morgan´s” rules or theorems,
•  
• (1) Two separate terms NOR´ed together is the same as the two terms inverted (Complement) and AND´ed for example:  A+B = A . B
•  
• (2) Two separate terms NAND´ed together is the same as the two terms inverted (Complement) and OR´ed for example:  A.B = A + B

 

Other algebraic Laws of Boolean not detailed above include:

• Distributive Law – This law permits the multiplying or factoring out of an expression.
•  
  • A(B + C) = A.B + A.C    (OR Distributive Law)
  • A + (B.C) = (A + B).(A + C)    (AND Distributive Law)
•  
• Absorptive Law – This law enables a reduction in a complicated expression to a simpler one by absorbing like terms.
•  
  • A + (A.B) = A    (OR Absorption Law)
  • A(A + B) = A    (AND Absorption Law)
•  
• Associative Law – This law allows the removal of brackets from an expression and regrouping of the variables.
•  
• A + (B + C) = (A + B) + C = A + B + C    (OR Associate Law)
• A(B.C) = (A.B)C = A . B . C    (AND Associate Law)