Truth Table Construction

Truth Table Basics

A truth table lists all possible input combinations and their outputs:

Structure:

• One column per input variable
• One column per output (can have multiple outputs)
• One row per input combination
• n variables $\to$ 2ⁿ rows

Example (2 variables):

Truth tables completely specify a Boolean function.

Enumeration Order

Standard enumeration order (binary counting):

For variables A, B, C (A is MSB, C is LSB):

Row | A B C | Decimal
----|-------|--------
 0  | 0 0 0 |   0
 1  | 0 0 1 |   1
 2  | 0 1 0 |   2
 3  | 0 1 1 |   3
 4  | 1 0 0 |   4
 5  | 1 0 1 |   5
 6  | 1 1 0 |   6
 7  | 1 1 1 |   7

Key insight: Row number = binary value of inputs.

This makes it easy to find any row: row 5 = 101 = A=1, B=0, C=1.

Evaluating Expressions

To fill in a truth table:

For each row:

1. Substitute the input values into the expression
2. Evaluate from innermost parentheses outward
3. Follow operator precedence: NOT, then AND, then OR
4. Record the result

Example: Evaluate A $\land$ (B $\lor$ $\neg$C) for A=1, B=0, C=1

1. $\neg$C = $\neg$1 = 0
2. B $\lor$ $\neg$C = 0 $\lor$ 0 = 0
3. A $\land$ (B $\lor$ $\neg$C) = 1 $\land$ 0 = 0

Using Intermediate Columns

For complex expressions, add intermediate columns:

Example: Build table for (A $\land$ B) $\lor$ ($\neg$A $\land$ C)

Benefits:

• Reduces errors
• Makes evaluation traceable
• Helps verify work
• Shows how subexpressions combine

Multi-Output Truth Tables

Multiple outputs can share one truth table:

Example: Half adder with inputs A, B and outputs Sum, Carry

Sum = A $\oplus$ B (XOR) Carry = A $\land$ B (AND)

Each output column is a separate function of the same inputs.

Truth Table Practice

Truth table construction checklist:

1. List all input variables
2. Calculate number of rows: 2^(number of variables)
3. Fill in input columns in binary counting order
4. Add intermediate columns if helpful
5. Evaluate expression for each row
6. Verify a few rows by substitution

Systematic Table Construction

Systematic truth table construction:

1. List variables in alphabetical order (A, B, C...)
2. Count rows: 2^n for n variables
3. Fill input columns: binary counting (000, 001, 010...)
   • Rightmost column alternates fastest
   • Each column to left alternates half as fast
4. Add output column(s)
5. Evaluate each row - substitute values

This systematic approach ensures no combinations are missed!

Intermediate Column Strategy

Intermediate column strategy:

For complex expressions like (A $\land$ B) $\lor$ ($\neg$A $\land$ C):

1. Add columns for sub-expressions:
   • Column for $\neg$A
   • Column for A $\land$ B
   • Column for $\neg$A $\land$ C
   • Final column for result
2. Evaluate left-to-right, using previous columns

Benefits:

• Reduces errors
• Shows step-by-step work
• Easier to debug if result seems wrong

Truth Table Size Growth

Truth table size grows exponentially:

Implication: For many variables, use algebraic methods or K-maps instead!

Complex Truth Table Challenge

Complex expression evaluation:

For expressions like (A $\oplus$ B) $\land$ (B $\lor$ C):

1. Identify sub-expressions
2. Evaluate innermost first
3. Use intermediate columns
4. Verify by spot-checking

Tip: Always double-check rows that seem unusual!

Boolean Logic in Programming

Boolean logic maps directly to programming:

• AND ($\land$) $\to$ && in most languages
• OR ($\lor$) $\to$ || in most languages
• NOT ($\neg$) $\to$ ! in most languages

De Morgan in code: !(a && b) is equivalent to !a || !b

Short-circuit evaluation: Most languages stop evaluating early. If the first operand of && is false, the result is false regardless—so the second operand is never checked. Same idea as annihilation: false AND anything = false.

Distribution in code: (a || b) && (a || c) simplifies to a || (b && c). OR distributes over AND, just as in Boolean algebra.

Boolean Search Queries

Boolean search operators:

• AND narrows results: "python AND tutorial" = must contain both
• OR broadens results: "python OR javascript" = contain either
• NOT excludes: "python NOT snake" = python but not snake
• Parentheses group: "(python OR java) AND tutorial"

Defaults: Most search engines AND words together implicitly—typing "python tutorial" means "python AND tutorial."

SQL WHERE clauses use the same operators: WHERE status = 'active' AND (role = 'admin' OR role = 'editor').

De Morgan applies here too: The complement of "active AND admin" is "NOT active OR NOT admin"—records that fail to match the original query.