Produce truth tables for logic circuits including half adders and full adders

Resources | Subject Notes | Computer Science

Boolean Algebra and Logic Circuits - A-Level Computer Science

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: \( A \cdot B \)
  • OR (Suggested diagram: OR gate): Output is 1 if at least one input is 1. Symbol: \( A + B \)
  • NOT (Suggested diagram: NOT gate): Inverts the input. If the input is 1, the output is 0, and vice versa. Symbol: \( \overline{A} \)
  • XOR (Exclusive OR) (Suggested diagram: XOR gate): Output is 1 if the inputs are different. Symbol: \( A \oplus B \)
  • XNOR (Exclusive NOR) (Suggested diagram: XNOR gate): Output is 1 if the inputs are the same. Symbol: \( A \odot B \)

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 Laws: \( A + B = B + A \), \( A \cdot B = B \cdot A \)
  • Associative Laws: \( A + (B + C) = (A + B) + C \), \( A \cdot (B \cdot C) = (A \cdot B) \cdot C \)
  • Distributive Laws: \( A \cdot (B + C) = (A \cdot B) + (A \cdot C) \), \( A + (B \cdot C) = (A + B) \cdot (A + C) \)
  • Identity Laws: \( A \cdot 1 = A \), \( A + 0 = A \)
  • Null Laws: \( A \cdot 0 = 0 \), \( A + 1 = 1 \)
  • Inverse Laws: \( A \cdot \overline{A} = 0 \), \( A + \overline{A} = 1 \)
  • Idempotent Laws: \( A \cdot A = A \), \( A + A = A \)
  • Absorption Laws: \( A \cdot (A + B) = A \), \( A + (A \cdot B) = A \)
  • De Morgan’s Laws: \( \overline{A \cdot B} = \overline{A} + \overline{B} \), \( \overline{A + B} = \overline{A} \cdot \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 + B \)

A B \( A + B \)
000
011
101
111

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)
0000
0110
1010
1101

Boolean Expression for a Half Adder:

\( S = A \oplus B \)
\( C = A \cdot B \)

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
00000
00110
01010
01101
10010
10101
11001
11111

Boolean Expressions for a Full Adder:

\( S = A \oplus B \oplus C_{in} \)
\( C_{out} = (A \cdot B) + (A \cdot C_{in}) + (B \cdot C_{in}) \)