Boolean algebra and Flip Flops, Physics tutorial

Introduction:

The digital circuit is developed for desired application by the combination of numerous logic gates. This application involving many logic gates may be a simple or complex one. Different users may propose digital circuits by using different combinations of logic gates for same application. In choosing one of these digital circuits for that application, it is essential to remember that chosen digital circuit must have minimum number of logic gates. By seeing the digital circuit, it is not obvious that circuit is minimal or certain gates may be removed from circuit without changing operation. Boolean algebra gives a means by which logic circuitry may be stated symbolically, manipulated and decreased.

Logic gates:

The logic gate is digital circuit that has logical relationship between input and output voltages. There are three basic gates: AND, OR and NOT (also known as inverter) gates.

AND Gate:

The AND gate can be understood by circuit in which there are two switches which are input and bulb is output. Now assign 0 to event when switch is open and 1 to event when switch is closed. Likewise when bulb doesn't glow we call it 0 and when bulb glows we call it 1. With both switches off, bulb doesn't glow.

With one of the switches off and another switch on, once again bulb (Y) doesn't glow. Though, with both switches on, bulb glows. Therefore there are four events that can be summarized in form of table that is known as truth table of this circuit.

Switches A and B, that control input voltage are generally known as input of truth table and Y as output.

1662_Truth Table of AND Gate.jpg

It is clear from the truth table that the output is 1 when both inputs A and B are 1. This state of circuit is distinct from other three states. Circuit is called as AND gate. Symbol of AND gate is given below. For the AND gate output is 1 if and only if all inputs are 1.

969_AND gate.jpg

Electronically AND gate can be realized by using two pn junction diodes. Resistor R is utilized to control current passing through diodes. 0 bit is assigned 0V and 1 bit is assigned 5V. Though, such accurate values of voltage won't always be available at output in electronic circuits. Thus, a 0 bit is assigned the voltage range of 0 to 0.8V and 1 bit is assigned to the voltage range of 2.8 to 5.0V. These voltage ranges are referred to LOW and HIGH respectively. Voltages greater than 0.8V and less than 2.8 V are indeterminate and therefore not used.

OR Gate:

The OR gate operation can be understood by circuit where both switches are off, (0), bulb doesn't glow (0). If one of the switches is on (1) and other is off (0), bulb glows (1). And if both switches are on (1), then also bulb glows (1). These events are summarized in truth table.

Truth Table of OR Gate

2222_Truth Table of OR Gate.jpg

It is clear from truth table that output of OR gate is 0 if both inputs are 0 and output is 1 if any one of inputs or both the inputs are 1.

2435_OR gate.jpg

The OR gate operation is stated as A + B = Y and is read as A OR B = Y.

NOT Gate:

NOT gate can be understood by considering electrical circuit. Assign 0 bit to event when bulb doesn't glow and 1 bit to event when bulb glows, and 0 bit to switch off and 1 bit to switch closed. When switch is closed, no current will pass through bulb and bulb won't glow. This is due to current always flows through path of least resistance. Likewise, when switch is open then whole current will flow through bulb making it glow. If input to circuit is 1, output is 0 and if input is 0 then output is 1. This is NOT gate operation which is summarized in truth table.

1209_Truth table for NOT gate.jpg

NOT gate is also called as inverter. It has only one input.

693_NOT gate.jpg

Input-output relationship is expressed as A = Y.

Combination of Logic Gates:

The AND, OR and NOT gates are primary gates for all digital circuits. These gates can be combined with each other for the particular application. Though, two kinds of combinations are very important.

NAND Gate:

145_Combination of AND and NOT gate.jpg

Symbol of NAND gate

177_NAND gate.jpg

If output of the AND gate is given to input of NOT gate, the resulting circuit is called as NAND gate. The truth table of this gate can written as follows:

1533_Truth table for NAND gate.jpg

Input-output relationship of NAND gate is stated as A.B = Y. NAND gate is called as building block for digital circuits as using NAND gates, one can obtain AND, OR and NOT gates.

NOR gate:

2439_Combination of OR and NOT gate.jpg

Symbol of NOR gate:

592_NOR gate.jpg

If output of OR gate is given to input of NOT gate the resulting circuit is called as NOR gate. The truth table of this gate is as follows:

1376_Truth table for NOR gate.jpg

Input-output relationship of NOR gate is stated as A + B = Y, NOR is also called as building block for the digital circuits as using NOR gates one can get AND, OR and NOT gates.

Boolean algebra:

Boolean algebra provides methodology for reducing the complex digital circuit into simple one. This methodology comprises the following:

1) Logic operations are written in form of Boolean expression.

2) From given truth table, Boolean expression can be attained which may not represent simple circuit having minimum number of gates.

3) Boolean expression may then be simplified to get the digital circuit having minimum number of gates.

Consider digital circuit given below. It has five logic gates of three types -

Three 2-input AND gates, one 2-input OR gate and one 3-input OR gate. Its logic table is also given below.

1781_Digital circuit using five gates.jpg

This circuit can be reduced to one shown below, that has only two logic gates and is significantly cheaper and simple. It fully satisfies the logic Table.

 

2053_Reduced Digital circuit.jpg

1507_Truth table for Digital circuit.jpg

Root of its initial assumptions, called as Boolean postulates, lies in truth tables of logic gates. The AND operation has been explained by sign of multiplication (.), that is, logical multiplication. Similarly OR Operation has been explained by sign of addition (+), that is, logical addition. And NOT operation has been explained as a bar (__) over the variable, that is, logical inversion or complementation. These three operations are basic Boolean operations based on which develop Boolean algebra.

As number of bits utilized in binary system is only two, i.e. 0 and 1, there could be only four possible combination of inputs A and B to 2-input AND and OR gates, and two possible inputs to NOT gate.

Logic tables lead to ten postulates of Boolean algebra, each of which explains input-output relationship of concerned logic gate in form of Boolean expression and is one of the truth table entries for AND, OR, NOT functions. These are:

AND operation      OR operation    NOT operation

0.0 = 0             0 + 0 = 0        0 = 1

0.1 = 0             0 + 1 = 1        1 = 0

1.0 = 0             1 + 0 = 1

1.1 = 1             1 + 1 = 1

It is fairly clear from equations that all the four Boolean equations using AND operation satisfy binary multiplication using bits 0 and 1. Though, in case of OR operation, first three Boolean equation satisfy binary addition, but last equation 1 + 1 = 1 doesn't. It is since in binary arithmetic 1 + 1 = 10. Despite this contradiction between Boolean and binary additions which will be settled later, Boolean operations are very useful in digital circuits.

Consider reduced circuit given above in which A and B are inputs to AND-gate while C is one of the inputs to OR gate. Another input to OR gate is output of AND gate, i.e., AB. Output of this combination is Y, which is

Y = (AB) + C = AB + C

Let us find Y if, say, A = 0, B = 1, and C = 1.

Y = 0.1 +1

Y = 0 + 1= 0 + 1 = 1

Therefore,

Y = 1

Now convert the given Boolean expression in the logic circuit. Say, Y = (A‾. B) + (A.B‾).

Boolean Theorems:

Now we can write several identities or theorems which are used in Boolean algebra. It is also worthwhile to recall that

A. (a) The output of an AND gate is 1 only when all the inputs are 1.

(b) The output of an AND gate is 0 when all or any of the inputs is 0.

B. (a) The output of an OR gate is 0 when all the inputs are 0.

(b) The output of an OR gate is 1 when either of the inputs or all the inputs are 1.

C. The output of a NOT gate is the inversion of its input.

From these conclusions and postulates, we derive the following properties or rules/law/ theorems:

From AND function,

1. X . 0 = 0

2. 0 . X = 0

3. X . 1 = X

4. 1 . X = X

The equation means that Y is output of a 2-input OR gate the inputs t0 which are A‾.B and A.B‾ which in turn are outputs of two AND gates. Inputs to AND gates are A‾ and B and A and B‾ respectively.

479_Conversion of boolean expression in circuit.jpg

D. Double complementation,

2183_Double complementation.jpg= X

E. Commutative laws for multiplication and addition. Such Laws show that order in which two variables are ORed or ANDed together makes no difference.

a) X.Y = Y.X

b) X + Y = Y + X

F. Associative laws for addition and multiplication. It show that while ORing or ANDing many variables, it makes no difference in what order variables are grouped.

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

b) X (YZ) = (XY) Z = XYZ

G. Distributive laws

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

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

v) (W + X) . (Y + Z) = WY + XY + WZ + XZ

Commutative, associative and distributive laws are like ordinary algebra.

H. De Morgan's theorems: First theorem says that complement of the sum is equal to product of complements:

a) (X + Y)‾‾= X‾+ Y‾

Second theorem says that complement of the product is equal to sum of complements.

b) (X.Y) ‾‾= X‾.Y‾

Tutorsglobe: A way to secure high grade in your curriculum (Online Tutoring)

Expand your confidence, grow study skills and improve your grades.

Since 2009, Tutorsglobe has proactively helped millions of students to get better grades in school, college or university and score well in competitive tests with live, one-on-one online tutoring.

Using an advanced developed tutoring system providing little or no wait time, the students are connected on-demand with a tutor at www.tutorsglobe.com. Students work one-on-one, in real-time with a tutor, communicating and studying using a virtual whiteboard technology.  Scientific and mathematical notation, symbols, geometric figures, graphing and freehand drawing can be rendered quickly and easily in the advanced whiteboard.

Free to know our price and packages for online physics tutoring. Chat with us or submit request at info@tutorsglobe.com