Logic Gates, Boolean Algebra, and Minimization Techniques

Contents

**Describe Basic Logic Gates: AND Gate ,OR Gate, and NOT Gate** 1

**Differentiate Basic Logic Gates and Universal Gates** 7

**Describe: NAND Gate and NOR Gate** 10

**Construct Basic Logic Gates using Universal Gates** 11

**Describe Boolean Algebra Operations** 14

**Discuss Sum-of-Product (SOP) and Product-of-Sum (POS) forms and their expansion to Standard forms** 17

**Convert a Boolean Expression to Logic Diagram and Vice-Versa** 17

**Explain the NAND and NOR Logic Implementation** 18

**Explain the realisation of functions using K-Map** 19

**Explain Prime Implicants and Essential Prime Implicants.** 19

**Describe Redundant Prime implicants** 19

**Explain False Prime Implicants and Essential False Prime Implicants** 19

**Describe Redundant False prime Implicants** 19

**Describe the Quine–McCluskey Method (Q-Map) to reduce Boolean Expression.** 19

**Explain the realisation of functions using Q-Map** 19

**Describe Basic Logic Gates: AND Gate ,OR Gate, and NOT Gate**

The AND gate is so named because, if 0 is called “false” and 1 is called “true,” the gate acts in the same way as the logical “and” operator. The following illustration and table show the circuit symbol and logic combinations for an AND gate. (In the symbol, the input terminals are at left and the output terminal is at right.) The output is “true” when both inputs are “true.” Otherwise, the output is “false.” In other words, the output is 1 only when both inputs one AND two are 1.

The *OR gate* gets its name from the fact that it behaves after the fashion of the logical inclusive “or.” The output is “true” if either or both of the inputs are “true.” If both inputs are “false,” then the output is “false.” In other words, for the output to be 1, at least input one OR two must be 1.

The *XOR* ( *exclusive-OR* ) *gate* acts in the same way as the logical “either/or.” The output is “true” if either, but not both, of the inputs are “true.” The output is “false” if both inputs are “false” or if both inputs are “true.” Another way of looking at this circuit is to observe that the output is 1 if the inputs are different, but 0 if the inputs are the same.

A logical *inverter*, sometimes called a *NOT gate* to differentiate it from other types of electronic inverter devices, has only one input. It reverses the logic state. If the input is 1, then the output is 0. If the input is 0, then the output is 1.

The *NAND gate* operates as an AND gate followed by a NOT gate. It acts in the manner of the logical operation “and” followed by negation. The output is “false” if both inputs are “true.” Otherwise, the output is “true.”

The *NOR gate* is a combination OR gate followed by an inverter. Its output is “true” if both inputs are “false.” Otherwise, the output is “false.”

**Describe Ex-OR Ex-NOR Gates**

Basically the “Exclusive-NOR Gate” is a combination of the Exclusive-OR gate and the NOT gate but has a truth table similar to the standard NOR gate in that it has an output that is normally at logic level “1” and goes “LOW” to logic level “0” when **ANY** of its inputs are at logic level “1”.

However, an output “1” is only obtained if **BOTH** of its inputs are at the same logic level, either binary “1” or “0”. For example, “00” or “11”. This input combination would then give us the Boolean expression of: Q = (A ⊕ B) = A.B + A.B

Then the output of a digital logic Exclusive-NOR gate **ONLY** goes “HIGH” when its two input terminals, A and B are at the “**SAME**” logic level which can be either at a logic level “1” or at a logic level “0”. In other words, an even number of logic “1’s” on its inputs gives a logic “1” at the output, otherwise it is at logic level “0”.

Then this type of gate gives an output “1” when its inputs are “*logically equal*” or “*equivalent*” to each other, which is why an **Exclusive-NOR** gate is sometimes called an **Equivalence Gate**.

The logic symbol for an Exclusive-NOR gate is simply an Exclusive-OR gate with a circle or “inversion bubble”, ( ο ) at its output to represent the NOT function. Then the **Logic Exclusive-NOR Gate** is the reverse or “*Complementary*” form of the Exclusive-OR gate, (A ⊕ B) we have seen previously.

The Exclusive-NOR Gate, also written as: “Ex-NOR” or “XNOR”, function is achieved by combining standard gates together to form more complex gate functions and an example of a 2-input Exclusive-NOR gate is given below.

The Digital Logic “Exclusive NOR” Gate

**2-input Exclusive NOR Gate**

Giving the Boolean expression of: Q = AB + AB

The logic function implemented by a 2-input Ex-NOR gate is given as “when both A AND B are the SAME” will give an output at Q. In general, an Exclusive-NOR gate will give an output value of logic “1” ONLY when there are an **EVEN** number of 1’s on the inputs to the gate (the inverse of the Ex-OR gate) except when all its inputs are “LOW”.

Then an Ex-NOR function with more than two inputs is called an “even function” or modulo-2-sum (Mod-2-SUM), not an Ex-NOR. This description can be expanded to apply to any number of individual inputs as shown below for a 3-input Exclusive-NOR gate.

**3-input Exclusive NOR Gate**

Giving the Boolean expression of: Q = ABC + ABC + ABC + ABC

We said previously that the Ex-NOR function is a combination of different basic logic gates Ex-OR and a NOT gate, and by using the 2-input truth table above, we can expand the Ex-NOR function to: Q = A ⊕ B = (A.B) + (A.B) which means we can realise this new expression using the following individual gates.

Ex-NOR Gate Equivalent Circuit

**Differentiate Basic Logic Gates and Universal Gates**

Basic logic gates and universal gates are two types of digital logic gates used in digital circuits.

Basic logic gates are the building blocks of digital circuits and perform basic operations on binary inputs. The three basic logic gates are the AND gate, OR gate, and NOT gate. These gates are simple to understand and implement, and are commonly used in digital circuits.

Universal gates, on the other hand, are gates that can be used to implement any Boolean function, which means that they can be used to implement any of the basic logic gates. Universal gates include NAND (NOT-AND) and NOR (NOT-OR) gates. These gates are more versatile and can be used to create more complex digital circuits.

The main difference between basic logic gates and universal gates is that basic logic gates perform basic operations on binary inputs, while universal gates can be used to perform any Boolean function. This makes universal gates more powerful and versatile, but also more complex to understand and implement.

Here’s a tabular comparison between basic logic gates and universal gates:

Feature | Basic Logic Gates | Universal Gates |

Types of Gates | Basic logic gates include NOT, AND, OR, NAND, NOR, XOR, and XNOR gates. | Universal gates include NAND and NOR gates. |

Functionality | Perform basic logical operations on inputs. | Can be used to implement any Boolean function. |

Representation | Represented by individual symbols for each gate. | Represented by a single symbol for the universal gate. |

Construction | Basic logic gates are constructed using transistors or electronic components. | Universal gates can be constructed using basic logic gates. |

Usefulness | Widely used in various digital systems and circuits. | Particularly useful in digital circuit design and optimization. |

Implementation | Each gate has its specific function and purpose. | Universal gates can be combined to implement any Boolean function. |

Complexity | Basic logic gates have varying levels of complexity. | Universal gates may have a higher level of complexity due to their versatility. |

Cost | Cost depends on the type and complexity of the gate. | Cost may be higher for universal gates due to their versatility. |

Examples | AND gate, OR gate, NOT gate, etc. | NAND gate, NOR gate. |

Basic Logic Gates:

Basic logic gates are fundamental building blocks of digital circuits. They perform specific logical operations, such as AND, OR, NOT, NAND, NOR, XOR, and XNOR, based on their inputs. These gates are widely used in various digital systems and are represented by individual symbols.

Universal Gates:

Universal gates, specifically NAND (NOT-AND) and NOR (NOT-OR) gates, have the unique property of being able to implement any Boolean function. They can be used to construct any logic gate or circuit, making them highly versatile. Universal gates can be represented by a single symbol and are particularly useful in digital circuit design and optimization. They can be constructed using combinations of basic logic gates.

While basic logic gates have specific functions, universal gates offer more flexibility and can simplify circuit design by reducing the number of gate types required. However, universal gates may have a higher level of complexity and potentially higher cost compared to basic logic gates.

**Describe: NAND Gate and NOR Gate**

The NAND gate operates as an AND gate followed by a NOT gate. It acts in the manner of the logical operation “and” followed by negation. The output is “false” if both inputs are “true.” Otherwise, the output is “true.”

The NOR gate is a combination OR gate followed by an inverter. Its output is “true” if both inputs are “false.” Otherwise, the output is “false.”

**Construct Basic Logic Gates using Universal Gates**

Universal gates are those gates which can be used to implement any other gate. The two most commonly used universal gates are NAND and NOR gates.

Here is how to construct basic logic gates using these universal gates:

**NOT Gate using NAND Gate:**

A NOT gate has only one input and one output. Its output is the inverse of its input.

The truth table for a NOT gate is:

A NAND gate has two inputs and one output. Its output is the inverse of the AND function of its inputs.

The truth table for a NAND gate is:

To construct a NOT gate using a NAND gate, connect both inputs of the NAND gate together and use that as the input to the NOT gate. The output of the NAND gate is the output of the NOT gate.

NOT Gate using NAND Gate Circuit:

**NOT Gate using NOR Gate:**

To construct a NOT gate using a NOR gate, connect both inputs of the NOR gate together and use that as the input to the NOT gate. The output of the NOR gate is the output of the NOT gate.

NOT Gate using NOR Gate Circuit: