# Boolean Algebra and Propositional Logic — Laws, Truth Tables, SOP and POS Forms, K-Maps and Valid Arguments

Source: https://skills101.in/learn/discrete-math/dm-boolean-algebra-propositional-logic — Skills101 free tutorial (Discrete Mathematics). Updated 2026-11-21.

The [logic lesson](https://skills101.in/learn/discrete-math/propositional-predicate-logic) used T and F and the symbols ∧, ∨, ¬. Engineers write the same ideas as **Boolean algebra**: 1 and 0, with **+** for OR, **·** for AND and **′** for NOT. This is the maths behind every `if` condition, every SQL `WHERE` clause and every logic circuit in a CPU. In this lesson we generate every truth table with Python, so no row is ever missed.

## 1. From logic to Boolean algebra

| Logic | Boolean algebra | Python | Meaning |
|---|---|---|---|
| p ∧ q | p·q (or pq) | `p and q` / `p & q` | AND |
| p ∨ q | p + q | `p or q` / `p \| q` | OR |
| ¬p | p′ | `not p` / `1 - p` | NOT |
| T, F | 1, 0 | `True`, `False` | values |

Careful: in Boolean algebra **1 + 1 = 1** (true OR true is true). It is not ordinary arithmetic.

## 2. The laws, checked by brute force

| Law | OR form | AND form (the dual) |
|---|---|---|
| Identity | x + 0 = x | x · 1 = x |
| Null (domination) | x + 1 = 1 | x · 0 = 0 |
| Idempotent | x + x = x | x · x = x |
| Complement | x + x′ = 1 | x · x′ = 0 |
| Involution | (x′)′ = x | |
| Absorption | x + xy = x | x(x + y) = x |
| Distributive | x(y + z) = xy + xz | **x + yz = (x + y)(x + z)** |
| De Morgan | (x + y)′ = x′y′ | (xy)′ = x′ + y′ |

The second distributive law, x + yz = (x + y)(x + z), is **false** for ordinary numbers but **true** in Boolean algebra.

**Duality principle:** swap + with ·, and 0 with 1, in any true law and you get another true law. That is why the table has two columns.

With only 0 and 1, a law with three variables has just 2³ = 8 cases, so a computer can check every one:

```python
from itertools import product

laws = {
    "x + yz = (x+y)(x+z)": lambda x, y, z: (x | (y & z)) == ((x | y) & (x | z)),
    "x(y + z) = xy + xz":  lambda x, y, z: (x & (y | z)) == ((x & y) | (x & z)),
    "x + xy = x":          lambda x, y, z: (x | (x & y)) == x,
    "(x + y)' = x'y'":     lambda x, y, z: (1 - (x | y)) == ((1 - x) & (1 - y)),
    "x + y = x + y + xy":  lambda x, y, z: (x | y) == (x | y | (x & y)),
    "x + y' = (x + y)'":   lambda x, y, z: (x | (1 - y)) == (1 - (x | y)),
}
for name, law in laws.items():
    bad = [c for c in product([0, 1], repeat=3) if not law(*c)]
    print(f"{name:22} {'holds' if not bad else 'FALSE, e.g. x,y,z = ' + str(bad[0])}")
```

```text
x + yz = (x+y)(x+z)    holds
x(y + z) = xy + xz     holds
x + xy = x             holds
(x + y)' = x'y'        holds
x + y = x + y + xy     holds
x + y' = (x + y)'      FALSE, e.g. x,y,z = (1, 0, 0)
```

The last line is a made-up "law". Brute force finds a counterexample at once — a habit worth keeping when you simplify expressions by hand.

## 3. Truth tables in Python

A small function prints the table for any expression with any number of variables:

```python
from itertools import product

def truth_table(f, names):
    print(" ".join(names), "| F")
    rows = []
    for values in product([0, 1], repeat=len(names)):
        out = int(f(*values))
        rows.append(out)
        print(" ".join(map(str, values)), "|", out)
    return rows

# majority of three: 1 when at least two inputs are 1
majority = lambda a, b, c: (a & b) | (b & c) | (a & c)
column = truth_table(majority, ["A", "B", "C"])
```

```text
A B C | F
0 0 0 | 0
0 0 1 | 0
0 1 0 | 0
0 1 1 | 1
1 0 0 | 0
1 0 1 | 1
1 1 0 | 1
1 1 1 | 1
```

## 4. Canonical forms: SOP and POS

Every Boolean function can be written straight from its truth table in two standard ways.

- A **minterm** is an AND of all variables (each plain or primed) that is 1 in **exactly one** row. Row 3 (A B C = 0 1 1) gives the minterm A′BC.
- **Sum of products (SOP):** OR together the minterms of the rows where F = 1. Written **Σm(…)** with the row numbers.
- A **maxterm** is an OR of all variables that is 0 in exactly one row. Row 0 (0 0 0) gives A + B + C.
- **Product of sums (POS):** AND together the maxterms of the rows where F = 0. Written **ΠM(…)**.

```python
from itertools import product

def canonical(f, names):
    rows = list(product([0, 1], repeat=len(names)))
    ones = [i for i, r in enumerate(rows) if f(*r)]
    zeros = [i for i, r in enumerate(rows) if not f(*r)]
    minterm = lambda r: "".join(n if v else n + "'" for n, v in zip(names, r))
    maxterm = lambda r: "(" + " + ".join(n + "'" if v else n for n, v in zip(names, r)) + ")"
    print("SOP: F = Σm" + str(tuple(ones)), "=", " + ".join(minterm(rows[i]) for i in ones))
    print("POS: F = ΠM" + str(tuple(zeros)), "=", "".join(maxterm(rows[i]) for i in zeros))

canonical(lambda a, b, c: (a & b) | (b & c) | (a & c), ["A", "B", "C"])
```

```text
SOP: F = Σm(3, 5, 6, 7) = A'BC + AB'C + ABC' + ABC
POS: F = ΠM(0, 1, 2, 4) = (A + B + C)(A + B + C')(A + B' + C)(A' + B + C)
```

The two lists of row numbers always **split the rows between them**: every row is either a 1 (a minterm) or a 0 (a maxterm). Canonical forms are correct but long. The next step is to simplify them.

## 5. Simplifying with a Karnaugh map

A **Karnaugh map (K-map)** arranges the truth table so that **neighbouring cells differ in exactly one variable**. For three variables the columns use the order 00, 01, 11, 10 (a Gray code), not 00, 01, 10, 11.

**Problem:** simplify F(A, B, C) = Σm(0, 2, 4, 5, 6).

![Three-variable K-map for F = sum of minterms 0, 2, 4, 5 and 6: rows are A = 0 and A = 1, columns are BC in Gray-code order 00, 01, 11, 10; a group of four cells in the C = 0 columns gives C prime and a group of two in row A = 1 gives A B prime, so F = C prime plus A B prime](https://skills101.in/learn-img/discrete-math/kmap-3var.svg)

1. Put a 1 in each listed cell.
2. Cover all the 1s with the **largest possible** rectangles of size 1, 2, 4 or 8. The left and right edges of the map **wrap around** and count as neighbours.
3. Each group keeps only the variables that stay **the same** across the whole group.

- The four cells with C = 0 (columns 00 and 10, both rows) form one group: **C′**.
- Cells 4 and 5 (A = 1, B = 0) form a pair: **AB′**.
- **F = C′ + AB′**: two terms instead of five three-letter minterms.

Always check the simplified form against the original:

```python
from itertools import product

minterms = {0, 2, 4, 5, 6}
original = lambda a, b, c: (a * 4 + b * 2 + c) in minterms
simplified = lambda a, b, c: (1 - c) | (a & (1 - b))
print("same on all 8 rows:", all(original(*r) == bool(simplified(*r)) for r in product([0, 1], repeat=3)))
```

```text
same on all 8 rows: True
```

## 6. NAND can build everything

A set of operations is **functionally complete** if it can express every Boolean function. {AND, OR, NOT} is complete because SOP form uses only those. Remarkably, **NAND alone** (NOT-AND: (xy)′) is complete too, which is why chips are often built mostly from NAND gates.

![Building NOT, AND and OR from NAND gates only: NOT x is x NAND x; AND is NOT of x NAND y; OR is NOT x NAND NOT y by De Morgan's law](https://skills101.in/learn-img/discrete-math/nand-gates.svg)

```python
from itertools import product

nand = lambda x, y: 1 - (x & y)
NOT = lambda x: nand(x, x)
AND = lambda x, y: NOT(nand(x, y))
OR = lambda x, y: nand(NOT(x), NOT(y))          # De Morgan: (x'y')' = x + y

print("NOT ok:", all(NOT(x) == 1 - x for x in (0, 1)))
print("AND ok:", all(AND(x, y) == (x & y) for x, y in product((0, 1), repeat=2)))
print("OR  ok:", all(OR(x, y) == (x | y) for x, y in product((0, 1), repeat=2)))
```

```text
NOT ok: True
AND ok: True
OR  ok: True
```

NOR alone is also complete. AND and OR together, without NOT, are **not** complete: they can never turn all-0 inputs into a 1.

## 7. Valid arguments

An **argument** is a list of **premises** followed by a **conclusion**. It is **valid** if the conclusion is true in **every** row where all the premises are true. One row with true premises and a false conclusion — a **counterexample** — makes it invalid.

**Example:** "If the server is down, the site shows an error. The site does not show an error. So the server is not down." Let s = server down, e = error shown. Premises: s → e, ¬e. Conclusion: ¬s. Is it valid? A truth table answers it:

```python
from itertools import product

imp = lambda a, b: (not a) or b

def check(name, premises, conclusion):
    for p, q in product([True, False], repeat=2):
        if all(f(p, q) for f in premises) and not conclusion(p, q):
            return print(f"{name:26} INVALID, counterexample p={p}, q={q}")
    print(f"{name:26} valid")

check("modus ponens", [lambda p, q: imp(p, q), lambda p, q: p], lambda p, q: q)
check("modus tollens", [lambda p, q: imp(p, q), lambda p, q: not q], lambda p, q: not p)
check("disjunctive syllogism", [lambda p, q: p or q, lambda p, q: not p], lambda p, q: q)
check("affirming the consequent", [lambda p, q: imp(p, q), lambda p, q: q], lambda p, q: p)
check("denying the antecedent", [lambda p, q: imp(p, q), lambda p, q: not p], lambda p, q: not q)
```

```text
modus ponens               valid
modus tollens              valid
disjunctive syllogism      valid
affirming the consequent   INVALID, counterexample p=False, q=True
denying the antecedent     INVALID, counterexample p=False, q=True
```

The server argument is **modus tollens**, so it is valid. The last two are common **fallacies**. "If it rains the road is wet; the road is wet; so it rained" is affirming the consequent — the road may be wet because a tanker spilled water.

| Rule | Premises | Conclusion |
|---|---|---|
| Modus ponens | p → q, p | q |
| Modus tollens | p → q, ¬q | ¬p |
| Hypothetical syllogism | p → q, q → r | p → r |
| Disjunctive syllogism | p ∨ q, ¬p | q |
| Resolution | p ∨ q, ¬p ∨ r | q ∨ r |

**Resolution** is the rule SAT solvers and logic programming languages (like Prolog) are built on.

## Common mistakes

- Treating + as ordinary addition: in Boolean algebra 1 + 1 = 1.
- Using the binary column order 00, 01, 10, 11 in a K-map. It must be Gray code: 00, 01, 11, 10.
- Forgetting that K-map edges wrap around, and making two small groups where one big group fits.
- Writing maxterms with the wrong primes: in a maxterm, a variable is primed where its value is **1**.
- Calling an argument valid because the conclusion happens to be true. Validity is about **every** row where the premises hold.

## Quick recap

- Boolean algebra = logic with 1, 0, +, ·, ′; duality swaps + with · and 0 with 1.
- Laws include absorption, De Morgan and x + yz = (x + y)(x + z); check any law on all 2ⁿ rows.
- SOP = Σm of rows where F = 1; POS = ΠM of rows where F = 0.
- K-maps use Gray-code order; cover 1s with the largest groups of 1, 2, 4, 8 (edges wrap).
- NAND alone (or NOR alone) is functionally complete.
- An argument is valid if no row makes all premises true and the conclusion false; affirming the consequent and denying the antecedent are fallacies.


Practice quiz and free certificate: https://skills101.in/learn/discrete-math/dm-boolean-algebra-propositional-logic