Compound Expressions

Full Operator Precedence

When all three operators appear in an expression, the precedence order is:

1. NOT ($\neg$) — highest precedence, binds tightest
2. AND ($\land$) — medium precedence
3. OR ($\lor$) — lowest precedence, binds loosest

So P $\lor$ Q $\land$ R is read as P $\lor$ (Q $\land$ R), not (P $\lor$ Q) $\land$ R.

This is similar to arithmetic where multiplication binds tighter than addition: a + b $\times$ c = a + (b $\times$ c).

AND and OR Without Parentheses

When AND and OR appear without parentheses, AND is evaluated first:

P $\lor$ Q $\land$ R = P $\lor$ (Q $\land$ R)

Think of it like arithmetic: just as 2 + 3 $\times$ 4 = 2 + 12 = 14 (not 20), we do AND before OR.

Parentheses Change Meaning

Parentheses override the default precedence:

• P $\lor$ Q $\land$ R = P $\lor$ (Q $\land$ R) — default, AND first
• (P $\lor$ Q) $\land$ R — OR first due to parentheses

These can give different results! With P = T, Q = F, R = F:

• P $\lor$ (Q $\land$ R) = T $\lor$ F = T
• (P $\lor$ Q) $\land$ R = T $\land$ F = F

Three-Operator Evaluation

When an expression contains NOT, AND, and OR, follow the precedence order:

1. Evaluate all NOTs first
2. Evaluate all ANDs
3. Evaluate all ORs

For $\neg$P $\land$ Q $\lor$ R: first $\neg$P, then ($\neg$P) $\land$ Q, then the result $\lor$ R.

Nested Parentheses

When parentheses are nested, evaluate from the inside out:

For $\neg$(P $\land$ (Q $\lor$ R)):

1. First: Q $\lor$ R (innermost)
2. Then: P $\land$ (result)
3. Finally: $\neg$(result)

Truth Tables for Three Variables

With two variables (P, Q), a truth table has 4 rows (2² = 4).

With three variables (P, Q, R), a truth table has 8 rows (2³ = 8):

Each additional variable doubles the number of rows.

Compound English to Logic

Complex English sentences can combine multiple logical operations:

• "If it's raining and cold, or snowing" $\to$ (R $\land$ C) $\lor$ S
• "It's not both raining and cold" $\to$ $\neg$(R $\land$ C)
• "It's sunny or warm, but not both" $\to$ (S $\lor$ W) $\land$ $\neg$(S $\land$ W)

Pay attention to grouping words and commas that suggest parentheses.

Complex Expression Evaluation

Complex expressions combine parentheses with NOT, AND, and OR:

1. Parentheses (innermost first)
2. NOT ($\neg$) - highest among operators
3. AND ($\land$) - binds tighter than OR
4. OR ($\lor$) - lowest precedence

For example: $\neg$(P $\lor$ Q) $\land$ R means ($\neg$(P $\lor$ Q)) $\land$ R

More Expression Forms

Boolean expressions come in many forms. Some common patterns:

• Double negation: $\neg$$\neg$P
• Mixed operations: P $\land$ Q $\lor$ R, P $\lor$ Q $\land$ R
• Negated compounds: $\neg$(P $\land$ Q), $\neg$(P $\lor$ Q)
• Nested structures: (P $\land$ Q) $\lor$ (R $\land$ S)

Recognizing these patterns helps you evaluate expressions faster.

Evaluation Walkthrough

To evaluate a compound expression systematically:

1. Identify all subexpressions
2. Order them by precedence (NOT > AND > OR, parentheses first)
3. Substitute known values
4. Evaluate one operation at a time
5. Track intermediate results

This methodical approach prevents errors in complex expressions.

Which Step Next?

Knowing which operation to evaluate next is crucial:

Priority order:

1. Parentheses - innermost first
2. NOT - applies to immediately adjacent term
3. AND - binds tighter than OR
4. OR - lowest precedence

When in doubt, add mental parentheses following precedence rules.

Expression Equivalence

Two Boolean expressions are equivalent if they produce the same output for all possible input combinations.

Examples of equivalent pairs:

• $\neg$$\neg$P $\equiv$ P (double negation)
• P $\land$ P $\equiv$ P (idempotence)
• P $\lor$ P $\equiv$ P (idempotence)
• $\neg$(P $\land$ Q) $\equiv$ $\neg$P $\lor$ $\neg$Q (De Morgan's Law)

Testing equivalence: check all input combinations!

Build From Requirements

Building expressions from requirements:

1. Identify variables - what conditions are involved?
2. Identify connectives - AND (all must be true), OR (at least one), NOT (negation)
3. Add parentheses - clarify grouping where needed

Keywords to operations:

• "both", "and", "all of" $\to$ AND
• "either", "or", "at least one" $\to$ OR
• "not", "unless", "except" $\to$ NOT

Multi-Variable Challenge

Real-world Boolean expressions often involve many variables.

Strategy for complex expressions:

1. Identify the main structure (top-level operation)
2. Break into sub-expressions
3. Evaluate each sub-expression independently
4. Combine results

With 4+ variables, systematic evaluation prevents mistakes.

Quick Boolean Drill

Fluency with boolean operations comes from practice. These quick drills help build automatic recognition of common patterns.

Mixed Law Evaluation

Real boolean expressions often involve multiple operations and concepts working together. Being able to evaluate these systematically is an important skill for both theory and practical applications.