Go back to UGC NET COMUPTER SCIENCE

UGC NET Computer Science Application – Unit 1 – Boolean Algebra

(Boolean Functions, Representations, Simplification)

---

1. BOOLEAN ALGEBRA

Definition

A Boolean Algebra is an algebraic structure

$$(B,+,\cdot {,}^{\mathrm{\prime }})$$

with elements 0 and 1, and three operations:

• OR → $+$

• AND → $\cdot$

• NOT → $x^{\mathrm{\prime }}$

It satisfies the following axioms for all $x,y,z\in B$:

1. Commutative laws

   • $x+y=y+x$

   • $x\cdot y=y\cdot x$

2. Associative laws

   • $(x+y)+z=x+(y+z)$

   • $(x\cdot y)\cdot z=x\cdot (y\cdot z)$

3. Distributive laws

   • $x\cdot (y+z)=(x\cdot y)+(x\cdot z)$

   • $x+(y\cdot z)=(x+y)(x+z)$

4. Identity elements

   • $x+0=x$

   • $x\cdot 1=x$

5. Complement

   • $x+x^{\mathrm{\prime }}=1$

   • $x\cdot x^{\mathrm{\prime }}=0$

---

2. BOOLEAN FUNCTIONS

Definition

A Boolean function of n variables is a mapping:

$$f:\{0,1{\}}^n\to \{0,1\}$$

Example:

$$f(x,y)=x{y}^{\mathrm{\prime }}+x^{\mathrm{\prime }}y$$

(This is XOR.)

---

Truth Tables

A Boolean function can be represented by a truth table listing all input combinations and outputs.

Example

Function $f(x,y)=x+y^{\mathrm{\prime }}$:

---

3. REPRESENTATION OF BOOLEAN FUNCTIONS

Boolean functions can be represented in canonical forms:

---

A. Sum of Products (SOP)

A function written as OR of AND terms.

Definition

SOP form consists of minterms (product terms in which every variable appears in complemented or uncomplemented form).

Example

$$f(x,y,z)=x^{\mathrm{\prime }}yz+x{y}^{\mathrm{\prime }}+xz$$

Canonical SOP (Minterm Form)

$$f=\sum m(i)$$

where $m(i)$ are minterms where output = 1.

Example

Given truth table output = 1 for minterms 1, 3, 4 →

$$f=\sum m(1,3,4)$$

---

B. Product of Sums (POS)

Function written as AND of OR terms.

Definition

POS form consists of maxterms (sum terms where each variable appears).

Canonical POS

$$f=\prod M(i)$$

Where $M(i)$ are maxterms for output = 0.

Example

Output is 0 for rows 2 and 5 →

$$f=\prod M(2,5)$$

---

⭐ C. Other Representations

• Boolean Expression (normal algebraic form)

• K-map Representation

• Logic Circuit representation (using AND/OR/NOT gates)

---

4. MINTERMS & MAXTERMS

Minterm

A minterm is a product term containing all variables exactly once (either complemented or not).

Example (3 variables):

$$m_3=x^{\mathrm{\prime }}yz$$

Maxterm

A maxterm is a sum term containing all variables.

Example:

$$M_5=(x+y^{\mathrm{\prime }}+z)$$

---

5. SIMPLIFICATION OF BOOLEAN FUNCTIONS

Simplification reduces Boolean expressions to minimum number of literals and gates.

Methods:

1. Boolean Algebra Laws

2. Karnaugh Maps (K-Maps)

3. Quine–McCluskey method (tabular, for large expressions)

---

6. SIMPLIFICATION USING BOOLEAN LAWS

Example

Simplify

$$f=xy+x^{\mathrm{\prime }}y$$

Solution:

$$f=y(x+x^{\mathrm{\prime }})=y(1)=y$$

---

Example

$$f=x+xy$$

Solution (Absorption law):

$$x+xy=x$$

---

Example

$$f=(x+y)(x+y^{\mathrm{\prime }})$$

Solution (Using algebra):

$$=x+y{y}^{\mathrm{\prime }}=x+0=x$$

---

7. KARNAUGH MAP (K-MAP) SIMPLIFICATION

K-maps group adjacent 1s to simplify expressions.

Rules

• Groups must be of size 1, 2, 4, 8, …

• Groups must be powers of 2

• Wrap-around grouping is allowed

• Larger groups → simpler answer

---

Example (2-variable K-map)

Minterms: $m_0,m_1,m_3$

Group m0 & m1 → gives A′
Group m1 & m3 → gives B

So simplified form:

$$f=A^{\mathrm{\prime }}+B$$

---

8. QUINE–McCLUSKEY METHOD

Used for systematic algebraic simplification when variables > 4.

Steps:

1. List minterms in binary.

2. Group by number of 1s.

3. Combine terms that differ in only one bit.

4. Find prime implicants.

5. Identify essential prime implicants.

6. Construct minimal expression.

---

9. PRIME IMPLICANTS

Definition

A prime implicant is a product term obtained by grouping 1s that cannot be combined further.

---

10. ESSENTIAL PRIME IMPLICANTS

Definition

A prime implicant that contains at least one minterm not covered by any other implicant.

These must appear in the simplified expression.

---

11. LOGIC GATE REPRESENTATION

Boolean expressions can be drawn using:

• AND gates

• OR gates

• NOT gates

• NAND / NOR universal gates

Example

Expression:

$$f=xy+z$$

Circuit:

• AND gate for $xy$

• OR gate to add $z$

---

Quick Summary for Exam