Boolean Logic

Boolean logic is a way to compute with truth values.

Instead of numbers like 7 or 3.14, the “data type” here is:

• •TRUE
• •FALSE

A Boolean expression is anything that evaluates to TRUE or FALSE.

Why care? Because many real questions are naturally yes/no:

• •“Is the user logged in?”
• •“Is the temperature above a threshold?”
• •“Is this number divisible by 2?”

In computing, these yes/no questions drive control flow:

• •if statements
• •while loops
• •filtering (keep items that satisfy a condition)

In math, the same ideas show up in proofs:

• •You assume something is TRUE and derive consequences.
• •You show something cannot be TRUE (so it must be FALSE).

Propositions: the things that can be TRUE/FALSE

A proposition is a statement that is definitively TRUE or FALSE.

Examples:

• •“2 is even.” (TRUE)
• •“5 < 3.” (FALSE)
• •“This program will terminate.” (depends, but still intended to be either TRUE or FALSE)

Non-examples (not propositions):

• •“Close the door.” (command)
• •“x is greater than 3.” (depends on x; becomes a proposition only after x is fixed)

From everyday language to logic

Natural language has words like “and”, “or”, “not”, “if”, “only if”, “unless”. Boolean logic begins with the simplest three:

• •NOT
• •AND
• •OR

We’ll use the programming-style symbols specified in this node:

• •! for NOT
• •&& for AND
• •|| for OR

You should read them as:

• •!P : “not P”
• •P && Q : “P and Q”
• •P || Q : “P or Q”

The key idea: an operator is a function on truth values

Each operator takes input truth values and produces an output truth value.

• •NOT takes 1 input (unary operator)
• •AND takes 2 inputs (binary operator)
• •OR takes 2 inputs (binary operator)

A truth table is how we define these operators precisely: list all possible inputs, and specify the output for each case.

That’s the foundation: Boolean logic is “functions on {TRUE, FALSE}”.

Truth tables matter because they remove ambiguity.

In everyday speech, “or” can be confusing:

• •“You can have soup or salad.” (sometimes means one but not both)
• •“It’s raining or snowing.” (could be one or both)

In Boolean logic, || is the inclusive OR: it is TRUE when at least one input is TRUE.

We’ll use these conventions:

• •T = TRUE
• •F = FALSE

NOT (!)

NOT flips the truth value.

Interpretation: if P is TRUE, then “not P” is FALSE, and vice versa.

AND (&&)

AND is TRUE only when both inputs are TRUE.

Interpretation: P && Q means “P and Q are both the case.”

OR (||)

OR is TRUE when at least one input is TRUE.

Interpretation: P || Q means “P is the case, or Q is the case, or both.”

Building larger truth tables (slowly and mechanically)

Real conditions are usually built from smaller ones:

• •(!P) && Q
• •P && (Q || R)

A good habit: compute intermediate columns.

For example, to evaluate (!P) && Q, make a column for !P, then a column for (!P) && Q.

This is “showing your work” in logic.

Precedence and parentheses (so we don’t accidentally mean something else)

In most programming languages, ! binds tighter than &&, which binds tighter than ||.

So typically:

• •!P && Q || R is read as ((!P) && Q) || R

But relying on precedence can be risky for learners and teammates.

Use parentheses when learning:

• •Write ((!P) && Q) || R if that’s what you mean.

Quick comparison table

Here’s a compact way to remember behavior:

Truth tables are the “ground truth” for all later topics: proofs, algebraic simplification, satisfiability, and circuit design.

Once you know what an expression means (via truth tables), the next power is to recognize when two different-looking expressions always give the same result.

That idea is called logical equivalence.

Definition: logical equivalence

Two Boolean expressions A and B are logically equivalent if they evaluate to the same truth value for every assignment of truth values to their variables.

We write:

• •A ≡ B

Why this matters:

• •Simplification: make conditions shorter and clearer.
• •Optimization: fewer checks in code or fewer gates in circuits.
• •Proof: replace an expression with an equivalent one to make reasoning easier.

How to prove equivalence (at this level)

At Difficulty 1, the main tool is: compare truth tables.

Process:

1. 1)List all combinations of input variables.
2. 2)Compute A and B for each row.
3. 3)If the output columns match exactly, then A ≡ B.

The most important equivalences to know early

These are the “algebra rules” of Boolean logic. You don’t need to memorize all of them immediately, but you should get comfortable using them.

1) Double negation

Negating twice returns the original:

• •!!P ≡ P

Truth table check:

The last column equals P.

2) De Morgan’s Laws

These explain how NOT interacts with AND/OR.

• •!(P && Q) ≡ (!P) || (!Q)
• •!(P || Q) ≡ (!P) && (!Q)

Intuition:

• •“Not (P and Q)” means “at least one of them is not true.”
• •“Not (P or Q)” means “neither is true.”

Truth table for the first law:

The columns !(P && Q) and (!P) || (!Q) match row-by-row, so they’re equivalent.

3) Identity and domination (helpful for simplification)

Think of TRUE and FALSE as special “absorbing” values.

• •P && TRUE ≡ P
• •P || FALSE ≡ P
• •P && FALSE ≡ FALSE
• •P || TRUE ≡ TRUE

You can confirm each via a 2-row truth table.

4) Idempotence (repeating doesn’t change anything)

• •P && P ≡ P
• •P || P ≡ P

5) Commutativity and associativity (reordering and regrouping)

• •P && Q ≡ Q && P
• •P || Q ≡ Q || P
• •(P && Q) && R ≡ P && (Q && R)
• •(P || Q) || R ≡ P || (Q || R)

These are why we can write P && Q && R without worrying about parentheses (conceptually), though you should still be careful in code with mixed operators.

A note on “exclusive or”

People sometimes mean “one or the other but not both.” That operator is XOR.

This node does not include XOR, but it’s worth knowing that plain || is inclusive.

If you ever need XOR using only !, &&, ||, one common form is:

• •(P || Q) && !(P && Q)

You can verify it with a truth table when you’re ready.

Showing work: rewriting with laws

Equivalence laws let you rewrite step-by-step.

Example goal: simplify !(P || Q) || Q.

We can rewrite using De Morgan:

• •!(P || Q) || Q
• •≡ ((!P) && (!Q)) || Q

From here, a full simplification would use additional distributive/absorption laws (often taught next). For now, the key skill is: you can legally replace !(P || Q) with (!P) && (!Q) because they are equivalent.

At this stage, truth tables are your safety net: if you’re unsure, compute and compare.

Boolean logic is a shared language between programming, math proofs, and hardware.

1) Programming: conditions in if and while

A program constantly evaluates Boolean expressions:

• •if (isAdmin && !isBanned) { ... }
• •while (hasWork || retryCount < 3) { ... }

Truth tables help you reason about edge cases.

Example: Suppose

• •P = “user is logged in”
• •Q = “user has premium access”

Then:

• •P && Q means “logged in AND premium”
• •P || Q means “logged in OR premium (or both)”

A common design question is: do you want to allow premium users who are not logged in? If not, P || Q is wrong.

2) Proof techniques (what this node unlocks)

In proofs, you often transform statements using logic.

• •In a direct proof, you start from assumptions (TRUE statements) and chain implications.
• •In proof by contradiction, you assume the opposite of what you want, then derive FALSE.

Even though implication (→) isn’t covered in this node, the mindset is already here:

• •Build complex statements from simpler ones.
• •Use equivalences to rewrite.
• •Use contradictions like “P && !P” (can never be TRUE).

3) Circuits: logic gates

Digital circuits represent TRUE/FALSE as voltage levels. Gates compute the same operations:

This is why truth tables are also used in hardware design: they specify exactly what a gate or circuit should do.

4) Why equivalence matters in applications

If two expressions are equivalent, you can swap them without changing behavior.

• •In code: rewrite to something clearer.
• •In circuits: reduce gate count.
• •In proofs: rewrite a statement into a form that matches a theorem you can apply.

Example: !(P && Q) is sometimes easier to implement or reason about as (!P) || (!Q) (De Morgan), depending on what signals are available.

A practical “debugging” strategy

When a Boolean condition seems wrong:

1. 1)Name subconditions (P, Q, R).
2. 2)Write the intended behavior in words.
3. 3)Create a truth table for the expression.
4. 4)Compare the table to what you intended.

This is slow at first, but it’s extremely reliable—and it scales to more advanced logic later.