Test: Minimization of Boolean Functions - 1 - Computer Science Engineering (CSE) MCQ

Concept:
The given data,
F = AB'CD' +A'BCD' +AB'C'D+A'BC'D 
F = CD' [ AB' + A'B ] +C'D [AB' + A'B]
F =CD' [A⊕B] + C'D [A⊕B]
F = [A⊕B] [CD' + C'D ]
F = [A⊕B] [C⊕D]
Hence the given function has 2 EX-OR gates and one And gate are required.
Hence the correct answer is 2,1.

Concept:

• NOR, 
• NAND,
• {OR and NOT i.e It behaves like NOR Gate } and
• {AND, NOT, It behaves like NAND Gate}

are the universal gates because they may be used to create any logic gate.  
The given option 1, option 2 and option 3 are not sufficient to represent any boolean operation.
Option 1: {OR , OR} behaves like an OR gate. It can not sufficient for the universal gate.
Option 2: {XOR} is a simple XOR gate. It can not sufficient for the universal gate.
Option 3: {AND, AND} behaves like an AND gate. It can not sufficient for the universal gate.
Option 4:   2×1 MUX or 2X1 multiplexer is functionally complete provided we have external 1 and 0 available.
For NOT gate, use x  as a select line and use 0 and 1 as inputs.
For AND gate, use y and 0 as inputs and x as select. With {AND, NOT} any other gate can be made.
Hence the correct answer is 2×1 MUX.

(A.A̅) + A
= 0 + A = A
All Boolean algebra laws are shown below:

Concept:
Draw the K- map, convert the K-map into a SOP (sum of product) or POS (product of sum) form. While reducing the K-map in these forms, a don’t care will be needed only when with the use of don’t cares we can reduce the term size.

Diagram: K – Map

From the K-map simplification:
F(a, b, c, d) = a̅.c
Diagram:

Therefore, only one NOR gate is needed to implement the minimized function

Concept:
Implicants:  Every min-term in SOP form or max-term in POS form in a Boolean function is termed as an implicant. 
For example,
F = AB + AC 
AB and AC are called implicants.
Prime Implicants:  All pairs that cannot be a part of any quad or all quads that cannot be a part of any octet in a K-map are termed as prime implicants.
Essential Prime Implicants:  Those prime implicants that cover at least one min-term that can’t be covered by any other prime implicant are called essential prime implicants.

Calculation:
Given the Boolean function,
F (A, B, C, D) = A'B'C'D + A'BCD' + ABC'D'
For the above Boolean function, the K – map representation is:

Hence we can see there three minterms in the given function.
Essential prime implicants are also three as they are not covered by any other prime implicant.
Hence option (3) is the correct answer.

In a n variable Boolean function, the maximum number of prime implicant is given by:

n = 4:

Maximum number of prime applicants = 2^n-1 = 2^{4 -}1 = 8

Concept:
The K-map is a graphical method that provides a systematic method for simplifying and manipulating the Boolean expressions or to convert a truth table to its corresponding logic circuit in a simple, orderly process.
In an 'n' variable K map, there are 2n cells
For 4 variables there will be 24 = 16 cells as shown:

Calculations:
F(a, b, c) = ∑(0, 2, 4, 5, 6)

F = c' + ab'

Given Y = A (A̅ + C) (A̅B + C) (A̅BC + C̅)
This can be written as:
Y = (A.A̅ + AC) (A̅B + C) (A̅BC + C̅)
Since A.A̅ = 0, the above expression can be written as:
Y = (AC) (A̅B + C) (A̅BC + C̅)
Y = (AC.A̅B + AC.C) (A̅BC + C̅)
With C.C = C, we can write:
Y = (AC) (A̅BC + C̅)
Y = AC.A̅BC + AC.C̅ 
Y = 0 + 0
Y = 0

Concept:

All Boolean algebra laws are shown below

Calculation:
F = X̅ Z̅ + Y̅ Z̅ + Y Z̅ + XYZ
= X̅ Z̅ + Z̅ (Y̅ + Y) + XYZ
= X̅ Z̅ + Z̅ + XYZ
= Z̅ (1 + X̅) + XYZ
= Z̅ + XYZ 
Now using Distributive Law
= (Z̅ + Z)(Z̅ + XY)
= Z̅ + XY