11.1 Boolean Algebra

COS2621 - Computer Organisation · 11. Digital Logic

Boolean Algebra

Introduction to Boolean Algebra

Boolean algebra is a mathematical structure that deals with binary variables (0 and 1) and logical operations. It is essential in digital logic design and computer architecture. The primary operations in Boolean algebra are AND, OR, and NOT.

Basic Operations

AND Operation

The AND operation results in true (1) if both operands are true (1). The truth table for the AND operation is as follows:

ABA AND B
111
100
010
000

OR Operation

The OR operation results in true (1) if at least one operand is true (1). The truth table is:

ABA OR B
111
101
011
000

NOT Operation

The NOT operation inverts the value of the operand. The truth table is as follows:

ANOT A
10
01

Boolean Identities

Boolean algebra has several identities that simplify expressions:

  • Identity Law: A AND 1 = A, A OR 0 = A
  • Null Law: A AND 0 = 0, A OR 1 = 1
  • Idempotent Law: A AND A = A, A OR A = A
  • Complement Law: A AND NOT A = 0, A OR NOT A = 1

Example of Simplifying a Boolean Expression

Consider the expression: [(AB)' + C]'. We will simplify it step by step:

  1. Apply De Morgan's Theorem: (AB)' = A' + B'
  2. Substitute into the expression: [(A' + B') + C]' = (A' + B' + C)'
  3. Apply De Morgan's Theorem again: A''B''C' = A'B'C'

The final result is A'B'C'.

Watch out: Do not confuse the AND and OR operations. Remember their truth tables.

Postfix Notation

Postfix notation, also known as Reverse Polish Notation (RPN), is a way to write expressions without parentheses. For example, the infix expression (A * B + C) / (E - F) can be converted to postfix as follows:

  • Convert A * B to AB*
  • Add C: AB*C+
  • Convert E - F to EF-
  • Combine: AB*C+EF-/

Applications of Boolean Algebra

Boolean algebra is crucial for designing digital circuits. For instance, to design a binary gate that outputs 1 when both inputs are equal (either both 0 or both 1), the Boolean function would be x'y' + xy.

Check your understanding

  • What is the result of A AND 1 if A = 0?
  • How does the NOT operation affect the value of a variable?
  • Simplify the expression A AND (B OR C).
  • State the Complement Law in Boolean algebra.

Test yourself

5 quick questions on this lesson. Pick an answer to see if you're right.

  1. 1. Given A and B as input and F as out function, the algebraic expression for XOR is

  2. 2. Give the postfix representation of the following expression where infix notation is used. (A + B * C) - (E / F)

  3. 3. Which law states that A AND NOT A = 0?

  4. 4. Give the result of the following binary operation: A AND B, where A = 1010 1101 and B = 0011 1001

  5. 5. What is the function of the REP instruction?