15.2 Boolean Algebra and Logic Circuits

This section covers the fundamental principles of Boolean algebra and their application to the design and analysis of logic circuits. We will explore truth tables, Boolean expressions, and how these are used to construct basic logic gates and combinational circuits like half and full adders.

Boolean Algebra

Boolean algebra is a system of logic that deals with binary values (true or false, represented as 1 or 0). It provides a set of rules for manipulating these values using logical operators.

The basic logical operators are:

• AND (Suggested diagram: AND gate): Output is 1 only if both inputs are 1. Symbol: $\land$ or $\cdot$
• OR (Suggested diagram: OR gate): Output is 1 if at least one input is 1. Symbol: $\lor$ or $+$
• NOT (Suggested diagram: NOT gate): Inverts the input. If the input is 1, the output is 0, and vice versa. Symbol: $\neg$ or $\overline{x}$
• XOR (Exclusive OR) (Suggested diagram: XOR gate): Output is 1 if the inputs are different. Symbol: $\oplus$
• XNOR (Exclusive NOR) (Suggested diagram: XNOR gate): Output is 1 if the inputs are the same. Symbol: $\equiv$

Boolean Expressions are formed by combining these operators with binary variables (e.g., A, B, C). These expressions can be simplified using algebraic rules.

Boolean Algebra Laws:

• Commutative Law: $A \land B = B \land A$, $A \lor B = B \lor A$
• Associative Law: $(A \land B) \land C = A \land (B \land C)$, $(A \lor B) \lor C = A \lor (B \lor C)$
• Distributive Law: $A \land (B \lor C) = (A \land B) \lor (A \land C)$, $A \lor (B \land C) = (A \lor B) \land (A \lor C)$
• Identity Law: $A \land 1 = A$, $A \lor 0 = A$
• Complement Law: $A \land \overline{A} = 0$, $A \lor \overline{A} = 1$
• Absorption Law: $A \land (A \lor B) = A$, $A \lor (A \land B) = A$
• De Morgan's Laws: $\overline{A \land B} = \overline{A} \lor \overline{B}$, $\overline{A \lor B} = \overline{A} \land \overline{B}$

Truth Tables

A truth table is a way to represent all possible combinations of input values and their corresponding output values for a logical expression or circuit.

Example: Truth table for $A \lor B$

A	B	A $\lor$ B
0	0	0
0	1	1
1	0	1
1	1	1

Logic Circuits

Logic circuits are physical implementations of Boolean functions using logic gates. The most common logic gates are AND, OR, NOT, XOR, and XNOR.

Half Adder

A half adder is a combinational circuit that adds two single-bit binary numbers (A and B) and produces a sum (S) and a carry (C) bit.

Truth Table for a Half Adder:

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

Boolean Expression for a Half Adder:

$$ \begin{aligned} S &= A \oplus B \\ C &= A \land B \end{aligned} $$

Full Adder

A full adder is a combinational circuit that adds three single-bit binary numbers: two input bits (A and B) and a carry-in bit (Cin). It produces a sum (S) and a carry-out bit (Cout).

Truth Table for a Full Adder:

A	B	Cin	Sum (S)	Cout
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

Boolean Expressions for a Full Adder:

$$ \begin{aligned} S &= A \oplus B \oplus Cin \\ Cout &= (A \land B) \lor (A \land Cin) \lor (B \land Cin) \end{aligned} $$