* Boolean Algebra and Logic Gates

Boolean Algebra (named for its developer, George Boole), is the algebra of digital logic circuits that all computers use.

Digital Logic Gates are the building blocks of any Digital Logic Circuits which perform switching or logical operations based on Boolean Algebra.

Boolean algebra is an algebra hat deals with binary variables and logic operations. A Boolean function described by an algebraic expression consists of binary variables, the constants 0 and 1, and the logic operation symbols. For a given value of the binary variables, the function can be equal to either 1 or 0.

Boolean algebra differs in a major way from ordinary algebra in that Boolean constants and variables are allowed to have only two possible values, 0 or 1. Boolean 0 and 1 do not represent actual numbers but instead represent the state of a voltage variable, or what is called its logic level.

In Boolean algebra, there are three basic logic operations: AND ,OR, and NOT which are carried out by the 3 Fundamental Digital Logic Gates (OR, AND, NOT). These logic gates are digital circuits constructed from diodes, transistors, and resistors connected in such a way that the circuit performs the 3 basic logic operation (OR, AND, NOT) on the inputs. Any digital logic design can be created with these three fundamental Logic Gates: the OR, AND, NOT Logic Gates.

The Digital Logic Gate is the basic building block from which all digital electronic circuits and microprocessor based systems are constructed from. Basic digital logic gates perform logical operations of AND, OR and NOT on binary numbers. In digital logic design only two voltage levels or states are allowed and these states are generally referred to as Logic “1” and Logic “0”, High and Low, or True and False. These two states are represented in Boolean Algebra and in standard truth tables by the binary digits of “1” and “0”respectively. A good example of a digital state is a simple light switch as it is either “ON” or “OFF” but not both at the same time. Then we can summarise the relationship between these various digital states as being:

Most digital logic gates and digital logic systems use “Positive logic”, in which a logic level “0” or “LOW” is represented by a zero voltage, 0v or ground and a logic level “1” or “HIGH” is represented by a higher voltage such as +5 volts, with the switching from one voltage level to the other, from either a logic level “0” to a “1” or a “1” to a “0” being made as quickly as possible to prevent any faulty operation of the logic circuit.

There also exists a complementary “Negative Logic” system in which the values and the rules of a logic “0” and a logic “1” are reversed but in this tutorial section about digital logic gates we shall only refer to the positive logic convention as it is the most commonly used.

A simple circuit performing a switching process similar to Boolean Logic operation. (Switching ON / OFF of a Bulb Z).

When switch A is CLOSED (Logic 1) then bulb Z is ON (Logic 1).

When switch A is OPEN (Logic 0) then bulb Z is OFF (Logic 0).

• In Digital Logic Circuits, logic levels 1 and 0 correspond to voltages:

– “Positive logic” uses a + voltage (e.g., 5 V) for 1 and 0 V for 0.

– Sometimes, “negative logic” (1 = 0V, 0 = +V [e.g., 5V]) is used.

• There are two classes of digital or computer logic:

– Combinational logic – output depends only on the inputs.

– Sequential logic – output depends on the inputs, the internal state of the logic, and possibly a clock or timing mechanism.

Most digital logic gates and digital logic systems use “Positive logic”, in which a logic level “0” or “LOW” is represented by a zero voltage, 0v or ground and a logic level “1” or “HIGH” is represented by a higher voltage such as +5 volts, with the switching from one voltage level to the other, from either a logic level “0” to a “1” or a “1” to a “0” being made as quickly as possible to prevent any faulty operation of the logic circuit.

There also exists a complementary “Negative Logic” system in which the values and the rules of a logic “0” and a logic “1” are reversed but in this tutorial section about digital logic gates we shall only refer to the positive logic convention as it is the most commonly used.

Rules that govern Boolean Algebra

a. NOT, AND, OR operation

b. Boolean Laws (Axioms and postulates)

c. Boolean Theorems

In Boolean algebra, there are 3 basic logic operations: AND ,OR, and NOT.

In Digital Logic Circuits, there are 3 basic Logic Gates: AND, OR and NOT which implement the 3 basic logic operations.

Boolean Algebra is used to analyze and simplify the digital (logic) circuits. It uses only the binary numbers i.e. 0 and 1. It is also refered to as Binary Algebra or logical Algebra. Boolean algebra was invented by George Boole in 1854.

Following are the important rules used in boolean algebra.

Variable used can have only two values. Binary 1 for HIGH and Binary 0 for LOW.

Complement of a variable is represented by a overbar (-) or prime ('). Thus complement of variable B is represented as or B'. Thus if B = 0 then = 1 (B' = 1) and B = 1 then = 0 (B' = 0). This is also known as the NOT operation.

Basic Boolean Operation / Basic Logic Gates

NOT Gate (Inverter Gate) - implementing the Logic NOT operation.

• NOT is the simplest logical function: one input and one output.

• NOT is defined as follows: “The output of NOT, given an input a, is the complement or opposite of the input.” Or :

• Since NOT can have only a 0 or 1 input, the output of NOT is the reverse, or complement of the input.

– If the input of NOT is 1, the output is 0.

– If the input of NOT is 0, the output is 1.

• The NOT function is called inversion, and the digital circuit NOT gate is also known as Inverter. It has one input A and one output Y.

The electronic circuit Diagram symbol for NOT is

NOT Function

IF A = 0 THEN

Y = 1

ELSE

Y = 0

ENDIF

TRUTH TABLE

The TRUTH TABLE completely describes the function of the NOT Gate, which can also be translated to show the Electrical behavior of the Gate, as can be shown below. Here the 0 and 1 values are translated to LO and HI voltage levels, or the 0 and 5 volts level which is the GROUND and Vcc Supply Voltage of the GATE as shown below.

OR Gate - implementing the Logic OR operation.

A circuit which performs an OR operation is shown below. It has n input (n >= 2) and one output.

ORing of the variables is represented by a plus (+) sign between them. For example ORing of A, B, C is represented as A + B + C.

LOGIC DIAGRAM

OR FUNCTION

IF A = 1 OR B = 1 THEN

Y = 1

ELSE

Y = 0

ENDIF

TRUTH TABLE

The following relationships can be easily derived from the OR Gate:

A+Ā = 1

A+A = A

0+A = A

1+A = 1

Below shows the Electrical behavior of an OR GATE.

AND Gate - implementing the Logic AND operation.

A circuit which performs an AND operation is shown in figure. It has n input (n >= 2) and one output.

ANDing of the two or more variable is represented by writing a dot between them such as A.B.C. Sometime the dot may be omitted like ABC.

LOGIC DIAGRAM

AND Function

IF A = 1 AND B = 1 THEN

Y = 1

ELSE

Y = 0

ENDIF

TRUTH TABLE

The following relationships can be easily derived from this circuit:

A.A = A

1.A = A

0.A = 0

A.Ā = 0

A.B = B.A

Below is the ELectrical Behavior of an AND GATE.

An illustration of the Boolean Logic Operation or Switching Process of an AND and OR Logic Gates using FlashLight.

Note their operations can be fully described by their respective TRUTH TABLES.

Boolean Laws (Axioms and postulates) - There are six types of Boolean Laws.

Postulates, Axioms or propositions are self-evident mathematical statements that are stated without proof. These Postulates will be used to develop Boolean Algebra.

COMMUTATIVE LAW

Any binary operation which satisfies the following expression is referred to as commutative operation

Commutative law states that changing the sequence of the variables does not have any effect on the output of a logic circuit.

ASSOCIATIVE LAW

This law states that the order in which the logic operations are performed is irrelevant as their effect is the same.

DISTRIBUTIVE LAW

Distributive law states the following condition.

A + BC = (A + B)(A + C)

AND LAW

These laws use the AND operation. Therefore they are called as AND laws.

OR LAW

These laws use the OR operation. Therefore they are called as OR laws.

INVERSION LAW

This law uses the NOT operation. The inversion law states that double inversion (Involution) of a variable result in the original variable itself.

A = A

Principle of Duality

 Dual of an expression is obtained by:

 Interchanging “0” and “1”

 Interchanging “.” and “+”

 (Exp)D represent dual of (Exp)  examples:

(X+0) D = X.1

(X + Y.Z) D = X.(Y+Z) “**Note: it is not equal to X.Y + Z

 You may recognize the above set of Laws and Postulates are true for duals

Notes on Duality

• Axioms and single-variable theorems are expressed in pairs – Reflects the importance of duality

• Given any logic expression, its dual is formed by replacing all + with ·, and vice versa and replacing all 0s with 1s and vice versa

f(a,b) = a+b dual of f(a,b) = a·b

f(x) = x+0 dual of f(x) = x·1

• The dual of any true statement is also true

Boolean Algebra Theorems

Purpose of Theorems: The Theorems & Postulates are key in our ability to reduce the number of literal (variables) used in a function and therefore reduce the number of gates required to implement a given function. Sometimes they are used to simply rearrange the expression so it is easier to implement.

Example: (X+Y)(X+Y') = X

SINCE (X+Y)(X+Y') = X+(Y.Y') = X(1) = X

It is clear that right-hand-side requires fewer gates to implement compared to the left hand side.

Two methods available for proving theorems

Prove through Boolean Algebra - Use postulates or theorems already proved to show that both sides of theorem are the same.
Prove through Truth Tables - Show that for all possible values on the left hand-side is equal to the right-hand side of the equation. This method works well for a small number of variables.

Theorems and proofs

Theorem 1 “ Double Complementation or Double Negation Theorem”

a) (X')' = X

Theorem 2 “Idempotency Theorem”

a) X+X = X b) X.X = X

Theorem 3 “Identity Element Theorem”

a) X + 1 = 1 b) X.0 = 0

Theorem 4 “Absorption Theorem”

a) X + X.Y=X b) X.(X+Y) = X

Theorem 5 “Associative Theorem”

a) X + (Y+Z) = (X + Y) + Z b) X.(Y.Z) = (X.Y).Z

Theorem 6 “Adjacency Theorem”

a) X.Y + X. Y' = X b) (X + Y).(X + Y ') = X

Theorem 7 “Consensus Theorem”

a) XY + X' Z + YZ = XY + X'Z b) (X + Y).( X' + Z).(Y + Z) = (X + Y).( X' + Z)

Theorem 8 “Simplification Theorem”

a) X + X '.Y = X + Y b) X.( X'+ Y) = X.Y

Theorem 9 “DeMorgan’s Theorem (2-Variable form)”

a) A+B = A. B

b) A.B = A +B

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.
- Indempotent Law – An input AND´ed with itself 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.

Double Negation Law (Involution) – 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.

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.

Distributive Law – This law permits the multiplying or factoring out of an expression.
(i) A(B + C) = AB + AC (ii) A + BC = (A + B)(A + C)
- Associative Law – This law allows the removal of brackets from an expression and regrouping of the variables.
- (i) (A.B).C = A.(B.C) (ii) (A+B) + C = A + (B + C)
- Absorptive Law – This law enables a reduction in a complicated expression to a simpler one by absorbing like terms.
- (i) X + (X . Y) = X (ii) X . (X + Y ) = X
- Uniting
- (i) XY + XY’ = X (ii) (X + Y)(X + Y’) = X
- Adsorption
- (i) (X + Y’)Y = XY (ii) XY’ + Y = X + Y

Elimination Law

(i) X + (X' . Y) = X + Y (ii) X.(X' + Y) = X.Y

Consensus

The theorem states that the AND term YZ can be eliminated from the expression if one of the literals such as Y is ANDed with the true value of another

literal (X) and the other term Z is ANDed with its complement (X').

(i) XY + X’Z + YZ = XY + X’Z (ii) (X + Y)(X’ + Z)(Y + Z) = (X + Y)(X’ + Z)

Shannon Expansion

X.Y + X'Z + Y.Z = X.Y + X'Z + Y.Z (X+X')

X.Y + X'Z + XYZ +X'YZ

X.Y(1+Z) + X'Z (1+Y)

X.Y + X'Z

De Morgan's Theorems – There are two “de Morgan´s” rules or theorems,
(1) Two separate terms NAND´ed together is the same as the two terms inverted (Complement) and OR´ed for example, A.B = A +B.
(2) Two separate terms NOR´ed together is the same as the two terms inverted (Complement) and AND´ed for example, A+B = A. B.
- - - Theorem 1 A.B = A +B
    - De Morgan's Theorem 1 simply states that a NAND GATE can be replaced or is equivalent to a Bubble-OR Gate ( an OR GATE with all its inputs INVERTED). This theorem could be proven using the TRUTH TABLE for each functions, as shown below.

Theorem 2 A+B = A. B

- - De Morgan's Theorem 2 simply states that a NOR GATE can be replaced or is equivalent to a Bubble-AND Gate ( an AND GATE with all its inputs INVERTED). This theorem could be proven using the TRUTH TABLE for each functions, as shown below.

EASIER WAY TO ANALYZE/UNDERSTAND DE MORGANs THEOREM

Bubble Pushing

A shortcut method for forming equivalent logic circuits, based on De Morgan’s theorem, is to use what’s called bubble pushing. Bubble pushing involves the flowing tricks: First, change an AND gate to an OR gate or change an OR gate to an AND gate. Second, add inversion bubbles to the inputs and outputs where there were none, while removing the original bubbles. That’s it. You can prove to yourself that this works by examining the corresponding truth tables for the original gate and the bubble-pushed gate, or you can work out the

Boolean expressions using De Morgan’s theorem.

NAND and NOR gates are inverting gates, and so both the standard and alternate symbols for each will have a bubble on either the input or the output.

AND and OR gates are noninverting gates, and so the alternate symbols for

each will have bubbles on both inputs and output.

Precedence in Boolean Algebra

As with any other branch of mathematics, these operators have an order of precedence. NOT operations have the highest precedence, followed by AND operations, followed by OR operations. Brackets can be used as with other forms of algebra. e.g.

X.Y + Z and X.(Y + Z) are not the same function.

Boolean Algebra Functions Using simple 2-input AND, OR and NOT Gates, we can form 16 possible functions as shown in the following table.

From the above Table, we could see that using the Basic Logic Gates of AND, OR and NOT we can form other Logic Gates such as the

NOR (combining NOT-OR), NAND (Combining NOT-AND), XOR and XNOR (combining NOT-AND-OR) as shown below.

The NOR output is produced by inverting the output of an OR operation.

The NAND output is generated by inverting the output of an AND operation.

Using MOS Transistors to implement LOGIC GATES.

The Exclusive-OR operation (XOR) generates an output of 1 if the inputs are different and 0 if the inputs are the same. The complement of the Exclusive-OR operation is known as the Exclusive-NOR (XNOR).

If we consider all of the above gates, we now have 7 Logic Gates - OR, NOR, AND, NAND, XOR, XNOR and NOT that can form any of the Combinational and Sequential Logic Circuits.

All the LOGIC GATES in LOGIC CIRCUIT

The Electrical behavior of BASIC Logic Gates.

The COMMON SYMBOL and IEEE SYMBOL for LOGIC GATES.

Logic gates are the building blocks of digital electronics. The fundamental logic gates include the INVERT (NOT), AND, NAND, OR, NOR, exclusive OR (XOR), and exclusive NOR (XNOR) gates. Each of these gates performs a different logical operation. The construction of digital gates is best left to the IC manufacturers. There are a number of technologies used in the fabrication of digital logic. The two most popular technologies include TTL (transistor-transistor logic) and CMOS (complementary MOSFET) logic. TTL incorporates bipolar transistors into its design, while CMOS incorporates MOSFET transistors. Both technologies perform the same basic functions, but certain characteristics (e.g., power consumption, speed, output drive capacity, etc.) differ.

Below are some of the 7400 Series TTL devices.

Below is the Physical Specification for the 7400 series Integrated Circuit or chip.Take note that the pin connection number 1 or simply pin-1 is below the white dot which is just besides a small notch (half-moon) at one of the side of the chip. Both the first and last pin connections , pin-1 and pin-14 are besides the notch. Also the last pin, pin-14 is for the supply voltage or Vcc which is usually 5 volts. The pin connection for the ground is at the opposite end of the notch which is the last pin of the same row as pin-1. And this is pin-7, also referred to as the Ground-pin.