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:

**AND Gate using NAND Gate:**

An AND gate has two inputs and one output. Its output is the AND function of its inputs.

The truth table for an AND gate is:

To construct an AND gate using NAND gates, first connect both inputs of the AND gate to the inputs of two separate NAND gates. Then connect the outputs of those NAND gates to a third NAND gate. The output of the third NAND gate is the output of the AND gate.

AND Gate using NAND Gates Circuit:

**OR Gate using NOR Gate:**

An OR gate has two inputs and one output. Its output is the OR function of its inputs.

The truth table for an OR gate is:

**Describe Boolean Algebra**

Boolean algebra is a mathematical system for representing and manipulating binary values (i.e., values that can only be 0 or 1). It was Boolean algebra is a branch of algebra that deals with binary variables and logic operations. It was developed by George Boole in the 19th century and has found numerous applications in computer science, electronics, and other fields.

The fundamental building blocks of Boolean algebra are Boolean variables, which can have one of two possible values: true or false, often represented as 1 or 0, respectively. These variables are combined using Boolean operators, which include AND, OR, NOT, XOR, and NAND, among others.

Boolean algebra operates on these variables and operators using rules of logic, such as the commutative, associative, and distributive properties, as well as the laws of De Morgan. These rules allow Boolean expressions to be simplified and manipulated, which is useful for designing digital circuits and programming logic.

Boolean algebra has many applications, including the design and analysis of digital circuits, computer programming, and the study of formal logic. It is also used in fields such as electrical engineering, telecommunications, and cryptography.

Overall, Boolean algebra provides a rigorous and systematic way to reason about logical propositions and operations, making it an essential tool for many fields that rely on precise and reliable logic.

**Describe Boolean Algebra Operations**

Boolean Algebra is a mathematical system that deals with values that are either true or false, represented as 1 and 0, respectively. The primary operations in Boolean Algebra are:

- AND: This operation returns true if both the inputs are true and false otherwise. It is represented by the symbol “^” or “&”.
- OR: This operation returns true if either of the inputs are true and false if both inputs are false. It is represented by the symbol “v” or “|”.
- NOT: This operation returns the opposite of the input value. If the input is true, the output is false, and vice versa. It is represented by the symbol “!” or “~”.
- XOR: This operation returns true if exactly one of the inputs is true and false otherwise. It is represented by the symbol “⊕”.
- NAND: This operation is the negation of the AND operation and returns false if both inputs are true and true otherwise.
- NOR: This operation is the negation of the OR operation and returns false if either input is true and true otherwise.

These operations are used to design logical circuits and perform various operations in digital electronics. Boolean Algebra has several laws and rules that define how the operations can be performed, such as associativity, commutativity, and distributivity, which are used to simplify Boolean expressions.

**Explain De-Morgan’s Law**

De Morgan’s Law is a fundamental principle in Boolean Algebra that provides a way to simplify Boolean expressions. It consists of two laws that state the relationship between the logical operations of NOT, AND, and OR.

The first law states that the negation of the logical AND operation is equal to the logical OR operation of the negations of the inputs. It can be written as:

!(A ∩ B) = !A ⋃ !B

The second law states that the negation of the logical OR operation is equal to the logical AND operation of the negations of the inputs. It can be written as:

!(A ⋃ B) = !A ∩ !B

These laws allow us to simplify Boolean expressions by applying negations to the inputs of the logical operations, effectively changing the AND operation to OR and vice versa. This can be useful in digital circuit design when creating logic gates or reducing the complexity of a Boolean expression.

For example, if we have an expression A ∩ B, we can use De Morgan’s Law to simplify it as !(!A ⋃ !B), which can be further simplified based on the rules of Boolean Algebra.

**Describe Duality Theorem**

The Duality Theorem is a fundamental principle in Boolean Algebra that states that the dual of a Boolean expression is obtained by swapping the AND and OR operations and negating all the literals. In other words, the dual of a Boolean expression is obtained by interchanging the AND and OR operations and complementing all literals in the original expression.

For example, if we have a Boolean expression A ∩ B, its dual would be !A ⋃ !B. Similarly, if we have a Boolean expression A ⋃ B, its dual would be !A ∩ !B.

The Duality Theorem is useful because it provides a way to simplify Boolean expressions by transforming them into their dual forms. By doing so, we can take advantage of the properties of the AND and OR operations to simplify the expression.

In addition, the Duality Theorem provides a connection between the logical and physical representations of Boolean expressions. For example, AND gates and OR gates are dual to each other in their physical implementation, and this connection is reflected in the Duality Theorem.

The Duality Theorem is an important concept in digital electronics and computer science, as it provides a way to simplify Boolean expressions, reduces the complexity of logic circuits, and facilitates the design of digital systems.

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

Sum-of-Product (SOP) and Product-of-Sum (POS) forms are two ways of representing Boolean functions in terms of their inputs.

The Sum-of-Product (SOP) form is a representation of a Boolean function as a sum of products of its inputs. In SOP form, a Boolean function is represented as the sum of minterms, where each minterm is a product of the input variables. For example, the Boolean function f(A, B, C) = A B + A C can be represented in SOP form as f(A, B, C) = AB + AC.

The Product-of-Sum (POS) form is a representation of a Boolean function as a product of sums of its inputs. In POS form, a Boolean function is represented as the product of maxterms, where each maxterm is a sum of the input variables. For example, the Boolean function f(A, B, C) = (A + B)(A + C) can be represented in POS form as f(A, B, C) = A + B + A + C = A + B + C.

Both SOP and POS forms are equivalent and can be used to represent the same Boolean function. However, the choice of form depends on the specific requirements of the circuit design and the method of simplification being used.

The SOP and POS forms can be expanded to their standard forms, which are the canonical forms of Boolean functions. The standard form of a Boolean function in SOP form is the canonical SOP form, where each minterm is represented by a single literal and there are no repeated terms. The standard form of a Boolean function in POS form is the canonical POS form, where each maxterm is represented by a single literal and there are no repeated terms.

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

A Boolean expression is a mathematical expression that consists of variables and operators, where the variables can only have two values: “true” or “false.” The operators used in Boolean algebra are AND, OR, NOT, NAND, NOR, XOR, and XNOR.

A logic diagram is a graphical representation of a Boolean expression, where the variables are represented by boxes and the operators are represented by connecting lines and symbols.

Here’s how you can convert a Boolean expression to a logic diagram:

- Identify the variables in the Boolean expression and represent each one with a box.
- For each operator in the expression, draw a line between the boxes representing the operands and add the symbol for the operator at the end of the line.
- For the NOT operator, draw a circle around the operand and add the symbol “!” inside the circle.

And here’s how you can convert a logic diagram to a Boolean expression:

- Identify the boxes representing the variables in the diagram and write them as the corresponding letters in the expression.
- Identify the lines and symbols representing the operators and translate them into the corresponding operator in the expression.
- For the NOT operator, write the corresponding letter with a “!” in front of it.

It’s important to note that there can be multiple equivalent Boolean expressions for a single logic diagram, and vice versa.

**Explain the NAND and NOR Logic Implementation**

**Implementing NOT gate using NAND gate:**

(A.A)’=A’ (Idempotent Law)

**Implementing AND gate using NAND gate:**

((AB)’ (AB)’)’= ((AB)’)’ (By Idempotent Law)

= AB (Involution Law)

**Implementing OR gate using NAND gate:**

((AA)'(BB)’)’= (A’B’)’ (By Idempotent Law)

= A”+B” (By De Morgan’s Law)

= A+B ( By involution Law)

**Implementing NOT gate using NOR gate:**

(A+A)’=A’ (By Idempotent Law)