Boolean Logic — Study Notes

1. Introduction

Boolean logic, named after the English mathematician George Boole, is a branch of algebra in which every variable can take only one of two values: true (1) or false (0). In the 1850s, Boole showed that logical reasoning could be expressed through mathematical equations. Today, Boolean algebra is the mathematical foundation of all digital circuits. Every operation performed by a computer, from adding two numbers to displaying an image, is ultimately implemented with circuits built from logic gates that obey the rules of Boolean algebra.

Boolean variables and the operations that act on them are the building blocks of the hardware inside the CPU. A variable that can hold either 0 or 1 is called a Boolean variable, and the operations used are AND, OR and NOT. From these three basic operations, all other gates and all complex digital systems can be constructed. Boolean expressions are also used inside programming languages; for example, the condition in an "if" statement evaluates to a Boolean value.

This chapter introduces the basic logic gates and their truth tables, the laws and identities of Boolean algebra, De Morgan's theorems, the concept of minterms and maxterms, and simple combinational circuits such as adders. Understanding Boolean logic prepares students to design circuits and to reason precisely about the conditions used in programs.

2. Boolean Variables and Basic Operations

A Boolean variable is a symbol, such as A, B or C, that can represent either 0 (false) or 1 (true). Boolean operations combine one or more Boolean inputs to produce a Boolean output.

2.1 NOT Operation

The NOT operation is a unary operation (it acts on a single variable). It inverts the input: NOT 0 = 1 and NOT 1 = 0. It is also called complementation or negation, and is written as A' or A-bar.

2.2 AND Operation

The AND operation produces output 1 only when all its inputs are 1; otherwise the output is 0. It is written as A . B or AB. In everyday terms, "A AND B is true only when both A and B are true".

2.3 OR Operation

The OR operation produces output 1 when at least one of its inputs is 1; the output is 0 only when all inputs are 0. It is written as A + B. In everyday terms, "A OR B is true when either A or B (or both) is true".

3. Logic Gates and Truth Tables

A logic gate is an electronic circuit that implements a Boolean operation. The main gates are NOT, AND, OR, NAND, NOR, XOR and XNOR.

3.1 NOT Gate

The NOT gate has one input and one output. Its symbol is a triangle with a small bubble at the output.

3.2 AND Gate

The AND gate has two or more inputs and one output.

3.3 OR Gate

The OR gate has two or more inputs and one output.

3.4 NAND Gate

The NAND gate is the complement of AND. Its output is 0 only when all inputs are 1. It is a universal gate, meaning any logic circuit can be built using only NAND gates.

3.5 NOR Gate

The NOR gate is the complement of OR. Its output is 1 only when all inputs are 0. It is also a universal gate.

3.6 XOR Gate (Exclusive OR)

The XOR gate produces output 1 when the number of inputs equal to 1 is odd. For two inputs, output is 1 when exactly one input is 1. It is written as A XOR B.

3.7 XNOR Gate (Exclusive NOR)

The XNOR gate is the complement of XOR. Its output is 1 when both inputs are equal.

4. Boolean Laws and Identities

Boolean algebra follows several important laws that help simplify expressions.

4.1 Basic Identities

• A + 0 = A
• A + 1 = 1
• A . 0 = 0
• A . 1 = A
• A + A = A
• A . A = A
• A + A' = 1
• A . A' = 0

4.2 Commutative, Associative and Distributive Laws

• Commutative: A + B = B + A; A . B = B . A
• Associative: (A + B) + C = A + (B + C); (A . B) . C = A . (B . C)
• Distributive: A . (B + C) = (A . B) + (A . C); A + (B . C) = (A + B) . (A + C)

4.3 De Morgan's Theorems

De Morgan's theorems relate the complement of a combination to the combination of complements: - (A . B)' = A' + B' - (A + B)' = A' . B'

In words, the complement of a product is the sum of the complements, and the complement of a sum is the product of the complements. De Morgan's theorems are extremely useful for simplifying logic circuits and for converting between NAND/NOR designs.

4.4 Absorption Law

• A + (A . B) = A
• A . (A + B) = A

5. Boolean Expressions and Simplification

A Boolean expression is a combination of Boolean variables and operations, such as F = A . B + A'. A truth table for the expression lists the output for every combination of inputs. For an expression with n variables, the truth table has 2^n rows.

Expressions can be simplified using the laws above. For example, consider F = A . B + A . B'. Using the distributive law, F = A . (B + B'). Since B + B' = 1, we get F = A. So the expression A.B + A.B' simplifies to just A. Such simplification reduces the number of gates needed in a circuit, making it cheaper, faster and more reliable.

5.1 Minterms and Maxterms

For n variables, each combination of inputs is a minterm. A minterm is written as a product (AND) of all the variables, with each variable complemented if its value is 0 and uncomplemented if its value is 1. For example, for two variables A and B, the minterm for the combination A=1, B=0 is A . B'. A Boolean function written as a sum of its minterms (SOP, Sum of Products) lists the minterms for which the output is 1.

A maxterm is written as a sum (OR) of all variables, each complemented if its value is 1 and uncomplemented if its value is 0. A function written as a product of its maxterms (POS, Product of Sums) lists the maxterms for which the output is 0. Both SOP and POS forms are standard ways to express a Boolean function from its truth table.

6. Basic Combinational Circuits

Combinational circuits are circuits whose output depends only on the current inputs, with no memory of past inputs.

6.1 Half Adder

A half adder adds two single bits A and B, producing a sum (S) and a carry (C). Its logic: - S = A XOR B - C = A AND B When both inputs are 1, the sum is 0 and the carry is 1.

6.2 Full Adder

A full adder adds three bits: A, B and a carry-in (Cin) from a previous stage. It produces sum and carry-out using XOR, AND and OR gates. Full adders are chained together to build multi-bit adders inside the ALU.

7. Boolean Logic in Python

Boolean logic is not just for hardware; Python programs use it constantly. Python has the boolean type with values True and False, and operators and, or, not. A comparison expression evaluates to a Boolean value that can be used in conditions.

a = 5
b = 10
print(a < b and b < 20)   # True and True = True
print(a > b or b > 20)    # False or False = False
print(not (a == b))       # not False = True

Notice how the Python results match the truth tables: AND is True only when both operands are True, OR is True when at least one is True, and NOT inverts the value.

Quick Revision Tables

Table 1: Truth Table of All Basic Gates

Table 2: Boolean Laws Quick Reference

Mind Map

Important Diagrams (SVG)

Diagram 1: Logic Gate Symbols and Their Meaning

Diagram 2: Half Adder Circuit

Common Mistakes

1. Mixing up AND and OR truth tables: Remember AND needs all inputs 1 for output 1, while OR needs only one input 1.
2. Forgetting that XNOR is the complement of XOR: XNOR gives 1 when inputs are equal, while XOR gives 1 when they differ.
3. Applying De Morgan's theorem incorrectly: (A . B)' = A' + B' and (A + B)' = A' . B'. The OR/AND symbols swap and every variable is complemented. A common error is to forget the negation of individual variables.
4. Confusing minterms and maxterms: A minterm is a product of variables (AND) with output 1; a maxterm is a sum of variables (OR) with output 0.
5. Building the truth table with the wrong number of rows: For n variables the truth table has 2^n rows. Forgetting this leads to incomplete or extra rows.
6. Believing OR output is 0 for both 1s: OR output is 1 even when both inputs are 1; only NOR gives 0 in that case.
7. Mistaking the half adder carry logic: In a half adder, carry = A AND B, which is 1 only when both inputs are 1.

Exam Tips

1. Draw the truth table first for any Boolean expression question; it guarantees marks and reduces errors.
2. Memorise the standard truth table of all seven gates; many objective questions test just one row.
3. For simplification questions, apply De Morgan's theorems and the absorption law step by step, writing each step to avoid losing marks.
4. Remember NAND and NOR are universal gates and be ready to state why (any circuit can be built using only them).
5. For SOP/POS questions, carefully mark which rows have output 1 (for SOP) or output 0 (for POS).
6. In Python, remember that and, or, not are lowercase keywords, and comparisons return True/False values.
7. Practise 2-variable and 3-variable truth tables so that 2^n rows become second nature.

Conclusion

Boolean logic provides the simple but powerful mathematics behind all digital electronics and every conditional statement in programming. Starting from just three operations, AND, OR and NOT, we can build every logic gate, simplify complex expressions with Boolean laws and De Morgan's theorems, and design useful circuits such as adders. The same ideas appear again in Python, where boolean values and the and, or, not operators control the flow of programs. With this foundation, we now move from how machines think to how humans think about solving problems systematically, the subject of the next chapter on problem solving.