Boolean algebra

Learn the fundamentals of Digital Systems and Logic Design, including Boolean algebra, logic gates, truth tables, Karnaugh maps, and circuit design. Explore key concepts, applications, and simplified Boolean expressions for students and professionals.

MCQs

---

1. Which of the following Boolean expressions represents the OR operation?

Options:
(a) A · B
(b) A + B
(c) A
(d) A⊕B

Answer: (b) A + B

Explanation:
In Boolean algebra, the OR operation is represented by the + symbol. The OR gate outputs 1 if at least one of its inputs is 1.

Tip:

• + means OR operation
• · (dot) means AND operation
• ⊕ means XOR operation

---

2. What is the dual of the Boolean expression A . 0 = 0?

Options:
(a) A + 1 = 1
(b) A + 0 = A
(c) A . 1 = A
(d) A . 0 = 0

Answer: (a) A + 1 = 1

Explanation:
The dual of a Boolean expression is obtained by:

1. Replacing AND (·) with OR (+).
2. Replacing OR (+) with AND (·).
3. Swapping 0s and 1s.

The given expression is A . 0 = 0, applying duality:

• Replace · with +, and 0 with 1, so it becomes A + 1 = 1.

Tip:

• AND (·) and OR (+) are interchanged in duality.
• 0 and 1 are swapped.

---

3. Which logic gate outputs true only if both inputs are true?

Options:
(a) OR gate
(b) AND gate
(c) XOR gate
(d) NOT gate

Answer: (b) AND gate

Explanation:
The AND gate outputs 1 (true) only when both inputs are 1. Otherwise, it outputs 0.

Truth Table:

A	B	A · B
0	0	0
0	1	0
1	0	0
1	1	1

Tip:

• A · B (AND) gives 1 only when both A and B are 1.

---

4. In a half-adder circuit, the carry is generated by which operation?

Options:
(a) XOR operation
(b) AND operation
(c) OR operation
(d) NOT operation

Answer: (b) AND operation

Explanation:
In a half-adder, the sum (S) and carry (C) are calculated as follows:

• Sum: S = A ⊕ B (XOR operation)
• Carry: C = A · B (AND operation)

The carry is 1 only when both inputs are 1, which is why the AND gate is used.

Tip:

• Sum in half-adder = XOR
• Carry in half-adder = AND

---

5. What is the decimal equivalent of the binary number 1101?

Options:
(a) 11
(b) 12
(c) 13
(d) 14

Answer: (c) 13

Explanation:
To convert 1101 (binary) to decimal: (1×2³)+(1×2²)+(0×2¹)+(1×2⁰) (1×8)+(1×4)+(0×2)+(1×1)=8+4+0+1=13

Tip:

• Multiply each digit by 2 raised to its position (rightmost is position 0).
• Add the results to get the decimal value.

---

Short questions

---

1. Define a Boolean function and give an example.

A Boolean function is a mathematical expression that uses Boolean algebra to produce an output based on logical operations like AND, OR, and NOT. It takes binary inputs (0s and 1s) and gives a binary output (0 or 1).

Example:
A Boolean function can be: F=A+B

Here, A and B are inputs, and + represents the OR operation. The function will output 1 if at least one input is 1.

---

2. What is the significance of the truth table in digital logic?

A truth table is a table that shows all possible input values and their corresponding outputs for a logic circuit or Boolean function. It helps in:

• Understanding how a logic gate or circuit works.
• Checking if a Boolean expression is correct.
• Designing digital circuits efficiently.

Example:
For an AND gate, the truth table is:

A	B	A · B
0	0	0
0	1	0
1	0	0
1	1	1

It shows that the output is 1 only when both inputs are 1.

---

3. Explain the difference between analog and digital signals.

Analog and digital signals are two types of signals used in electronics.

• Analog signals are continuous and can have any value within a range. They are used in natural sounds, temperature, and radio waves.
  Example: The human voice in a telephone or music from a speaker.
• Digital signals are discrete and have only two values (0 and 1). They are used in computers and digital devices.
  Example: Data stored in a computer or images on a mobile screen.

Key Difference:

• Analog signals vary smoothly, while digital signals change in steps (0 or 1).

---

4. Describe the function of a NOT gate with its truth table.

A NOT gate is a logic gate that inverts the input. If the input is 1, it outputs 0, and if the input is 0, it outputs 1.

Truth Table for NOT Gate:

Input (A)	Output (A’)
0	1
1	0

Example: If you enter 0, the NOT gate flips it to 1, and vice versa.

---

5. What is the purpose of a Karnaugh map in simplifying Boolean expressions?

A Karnaugh map (K-map) is a simple way to reduce Boolean expressions and design logic circuits more efficiently. It helps in:

• Making Boolean expressions simpler.
• Reducing the number of logic gates needed.
• Improving the speed of digital circuits.

Example:
If a Boolean function is: F=AB+AB′

Using a K-map, we can simplify it to: F=A

This means we need only one variable instead of two.

---

Long Questions

---

1. Explain the usage of Boolean functions in computers.

Answer:
Boolean functions are used in computers to perform logical operations. Computers work with binary numbers (0s and 1s), and Boolean functions help process these numbers in circuits.

Uses in Computers:

1. Logic Gates: Boolean functions control AND, OR, NOT, NAND, NOR, and XOR gates in a computer.
2. Decision Making: If-else conditions in programming use Boolean logic.
3. Arithmetic Operations: Computers perform addition, subtraction, and multiplication using Boolean logic.
4. Memory Storage: RAM and storage devices use Boolean logic to store and retrieve data.
5. Search Engines: Google and other search engines use Boolean logic to filter and display results.

Example:

• If a login system checks whether a password is correct, it uses Boolean logic: Is Password Correct?=Yes (1) or No (0)

---

2. Describe how to construct a truth table for a Boolean expression with an example.

Answer:
A truth table is a table that shows all possible values of a Boolean expression.

Steps to Construct a Truth Table:

1. Identify the number of input variables (e.g., A and B).
2. List all possible combinations of inputs (0 and 1).
3. Apply the Boolean expression to find the output.

Example:
Consider the Boolean function: F=A+B

This represents an OR gate.

A	B	F = A + B
0	0	0
0	1	1
1	0	1
1	1	1

Explanation:

• The output is 1 if at least one input is 1.
• The output is 0 only if both inputs are 0.

---

3. Describe the concept of duality in Boolean algebra and provide an example.

Answer:
Duality in Boolean algebra means that every Boolean expression has another form where:

• AND (·) is replaced by OR (+)
• OR (+) is replaced by AND (·)
• 0 is replaced by 1 and vice versa

Example:
Given the Boolean equation: A+0=A

Its dual is: A⋅1=A

Importance:

• Helps in simplifying Boolean expressions.
• Used in digital circuit design.

---

4. Compare and contrast half-adders and full-adders, including their truth tables, Boolean expressions, and circuit diagrams.

Answer:
Half-Adder:
A half-adder adds two binary numbers but does not consider carry from the previous addition.

Boolean Equations:

• Sum (S): S=A⊕B (XOR operation)
• Carry (C): C=A⋅B (AND operation)

Truth Table:

A	B	Sum (S)	Carry (C)
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

---

Full-Adder:
A full-adder adds three binary numbers: two inputs and a carry from the previous addition.

Boolean Equations:

• Sum (S): S=A⊕B⊕Cin
• Carry (C): C=(A⋅B)+(B⋅Cin)+(A⋅Cin)

Truth Table:

A	B	C_in	Sum (S)	Carry (C)
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

Comparison:

Feature	Half-Adder	Full-Adder
Inputs	2	3
Carry-In	No	Yes
Used In	Basic addition	Complex addition

---

5. How do Karnaugh maps simplify Boolean expressions? Provide a detailed example with steps.

Answer:
A Karnaugh Map (K-map) is a graphical method used to simplify Boolean expressions. It helps in:

• Reducing logic gates.
• Minimizing circuit complexity.

Example:
Given Boolean expression: F(A,B,C)=AB+AB′C+A′BC

Steps:

1. Draw a 3-variable K-map (since A, B, C are used).
2. Place 1s in the K-map for each term.
3. Group the adjacent 1s into pairs or quads.
4. Write the simplified expression.

Using K-map simplification, we get: F=AB+BC

---

6. Design a 4-bit binary adder using both half-adders and full-adders.

A 4-bit binary adder adds two 4-bit numbers and consists of:

• 1 Half-Adder for the first bit.
• 3 Full-Adders for the remaining bits.

Each stage carries the result to the next stage.

---

7. Simplify the Boolean function using Boolean algebra:

F(A,B)=A.B+A.B′

Solution: F=A(B+B′)

Since B+B′=1B + B’ = 1, we get: F=A.1=A

---

8. Use De Morgan’s Theorem to simplify:

F(A,B,C)=A+B+AC

Applying De Morgan’s Theorem: F=(A+B)+AC

Since A+AC=A+C, we get: F=A+B+C

---

9. Solve the Boolean expressions:

(a) A+B⋅(A+B)

Using distribution: (A+B)⋅(A+B)=A+B

So, F=A+B

(b) (A+B)⋅(A‾+B)

Using distribution and simplification: (A+B)⋅(A‾+B)=B

---