The Central Idea
A Boolean value has one of two states:
\[ \boxed{T\text{ or }F} \]or, in many computational settings,
\[ \boxed{1\text{ or }0}. \]A Boolean operation takes one or more Boolean values as inputs and produces another Boolean value as output.
For example,
\[ T\land F=F. \]The inputs are \(T\) and \(F\), the operation is AND, and the output is \(F\).
Boolean Values and Propositions
In propositional logic, propositions have truth values.
In Boolean computation, those truth values can be treated as data:
\[ T,\qquad F. \]Boolean operations then manipulate those values according to fixed rules.
This creates a direct bridge between symbolic logic and computation.
Using \(1\) and \(0\)
A common convention is
\[ 1\leftrightarrow T \]and
\[ 0\leftrightarrow F. \]Under this convention,
\[ 1\land0=0 \]represents the same Boolean behavior as
\[ T\land F=F. \]The symbols change, but the two-valued structure does not.
Unary and Binary Operations
A unary operation acts on one input.
Negation is unary:
\[ \neg p. \]A binary operation acts on two inputs.
AND and OR are binary:
\[ p\land q \]and
\[ p\lor q. \]The NOT Operation
NOT reverses a Boolean value.
\[ \neg T=F \]and
\[ \neg F=T. \]| \(p\) | \(\neg p\) |
|---|---|
| T | F |
| F | T |
NOT with Binary Values
Using \(1\) and \(0\),
\[ \neg1=0 \]and
\[ \neg0=1. \]NOT behaves like a switch that flips one Boolean state to the other.
The AND Operation
AND produces true only when both inputs are true.
| \(p\) | \(q\) | \(p\land q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
AND therefore represents simultaneous requirements.
AND as a Requirement
Suppose
\(p\): A user entered the correct password.
\(q\): A user supplied a valid security code.
Then
\[ p\land q \]requires both conditions to hold.
If either requirement fails, the result is false.
AND with \(1\) and \(0\)
| \(a\) | \(b\) | \(a\land b\) |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
For Boolean inputs \(0\) and \(1\), AND behaves numerically like multiplication:
\[ a\land b=ab. \]This is a useful analogy, although Boolean operations are logical operations rather than ordinary arithmetic in general.
The OR Operation
OR produces true when at least one input is true.
| \(p\) | \(q\) | \(p\lor q\) |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
OR Means At Least One
The Boolean expression
\[ p\lor q \]is true if:
- \(p\) is true and \(q\) is false;
- \(p\) is false and \(q\) is true;
- both \(p\) and \(q\) are true.
It is false only when both inputs are false.
OR with \(1\) and \(0\)
| \(a\) | \(b\) | \(a\lor b\) |
|---|---|---|
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
For two Boolean values, OR can be viewed as selecting whether at least one input contains a \(1\).
The XOR Operation
XOR means exclusive or.
It is true exactly when the two inputs are different.
| \(p\) | \(q\) | \(p\oplus q\) |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
XOR as Difference Detection
Because XOR is true exactly when its inputs differ,
\[ p\oplus q \]can be understood as a Boolean test for inequality between two truth values.
In binary notation:
\[ 0\oplus0=0, \] \[ 0\oplus1=1, \] \[ 1\oplus0=1, \] \[ 1\oplus1=0. \]XOR and Binary Addition
XOR behaves like addition modulo \(2\) for individual bits:
\[ \boxed{a\oplus b\equiv a+b\pmod 2}. \]For example,
\[ 1\oplus1=0 \]because
\[ 1+1=2\equiv0\pmod2. \]This connection becomes important in digital arithmetic and error detection.
The NAND Operation
NAND means NOT AND.
It is the negation of conjunction:
\[ p\uparrow q=\neg(p\land q). \]| \(p\) | \(q\) | \(p\land q\) | \(p\uparrow q\) |
|---|---|---|---|
| T | T | T | F |
| T | F | F | T |
| F | T | F | T |
| F | F | F | T |
The NOR Operation
NOR means NOT OR.
It is the negation of disjunction:
\[ p\downarrow q=\neg(p\lor q). \]| \(p\) | \(q\) | \(p\lor q\) | \(p\downarrow q\) |
|---|---|---|---|
| T | T | T | F |
| T | F | T | F |
| F | T | T | F |
| F | F | F | T |
NAND and NOR Are Derived Operations
NAND and NOR are built by combining NOT with another operation:
\[ \text{NAND}=\text{NOT}(\text{AND}), \] \[ \text{NOR}=\text{NOT}(\text{OR}). \]They are especially important in digital logic because complete Boolean systems can be constructed using NAND alone or NOR alone.
The circuit interpretation will be developed later in this unit.
Implication as a Boolean Operation
Implication also defines a two-input Boolean operation:
\[ p\to q. \]| \(p\) | \(q\) | \(p\to q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
It can also be represented by
\[ \neg p\lor q. \]Biconditional as a Boolean Operation
The biconditional
\[ p\leftrightarrow q \]returns true when its inputs agree.
It behaves like a Boolean equality test.
| \(p\) | \(q\) | \(p\leftrightarrow q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
XOR and Biconditional Are Opposites
XOR is true when two inputs differ.
Biconditional is true when two inputs agree.
Therefore,
\[ p\leftrightarrow q \]has the opposite truth value from
\[ p\oplus q. \]In symbolic form,
\[ p\leftrightarrow q\equiv\neg(p\oplus q). \]Boolean Expressions
A Boolean expression combines Boolean variables, constants, and operations.
Examples include
\[ p\land q, \] \[ \neg p\lor q, \] \[ (p\land q)\lor r, \]and
\[ (p\oplus q)\land\neg r. \]Every complete Boolean expression evaluates to either true or false.
Boolean Constants
The values
\[ T,\qquad F \]or
\[ 1,\qquad0 \]can appear directly as constants in Boolean expressions.
For example,
\[ p\land T \]has the same value as \(p\).
Evaluating Boolean Expressions
Suppose
\[ p=T,\qquad q=F,\qquad r=T. \]Evaluate
\[ (p\lor q)\land r. \]First,
\[ p\lor q=T\lor F=T. \]Then,
\[ T\land r=T\land T=T. \]Therefore,
\[ \boxed{(p\lor q)\land r=T}. \]Evaluate from the Inside Out
Consider
\[ \neg(p\land q)\lor r. \]A reliable sequence is:
- evaluate \(p\land q\);
- negate that result;
- combine the result with \(r\) using OR.
Boolean expressions should be evaluated structurally rather than all at once.
Operator Precedence
Boolean notation often uses a precedence convention similar to the one used in propositional logic.
A common order is:
- NOT;
- AND;
- XOR;
- OR;
- implication and biconditional.
Conventions can vary by programming language or technical system, so parentheses should be used whenever ambiguity is possible.
Parentheses Control Grouping
Compare
\[ (p\lor q)\land r \]with
\[ p\lor(q\land r). \]These expressions group the operations differently and may produce different outputs.
Boolean operations, like arithmetic operations, depend on structure.
Example: Different Groupings
Let
\[ p=T,\qquad q=F,\qquad r=F. \]Then
\[ (p\lor q)\land r=(T\lor F)\land F=T\land F=F. \]But
\[ p\lor(q\land r)=T\lor(F\land F)=T\lor F=T. \]Therefore, the two grouped expressions do not always have the same value.
Repeated NOT Operations
Applying NOT twice returns the original value:
\[ \neg(\neg p)=p. \]If \(p=T\),
\[ \neg p=F \]and then
\[ \neg(\neg p)=T. \]Double negation will later appear as a standard Boolean identity.
Combining a Variable with Itself
If the same Boolean value is ANDed with itself,
\[ p\land p=p. \]Likewise,
\[ p\lor p=p. \]Repeating the same condition does not change its truth value.
Combining with True
Consider
\[ p\land T. \]Since AND requires both inputs to be true, the result depends entirely on \(p\):
\[ p\land T=p. \]Also,
\[ p\lor T=T, \]because OR needs only one true input.
Combining with False
For AND,
\[ p\land F=F. \]One false requirement is enough to make the entire conjunction false.
For OR,
\[ p\lor F=p. \]A false alternative contributes no new true case.
Complementary Inputs
A Boolean variable and its negation cannot both be true:
\[ p\land\neg p=F. \]They also cannot both be false:
\[ p\lor\neg p=T. \]These relationships are previews of complement laws in Boolean algebra.
Boolean Expressions as Functions
A Boolean expression can be viewed as a function.
For example,
\[ f(p,q)=p\land q \]maps each ordered pair of Boolean inputs to one Boolean output.
The truth table of the operation is the complete input-output table for that function.
A Two-Input Boolean Function
Consider
\[ f(p,q)=\neg p\lor q. \]There are four possible inputs:
\[ (T,T),\quad(T,F),\quad(F,T),\quad(F,F). \]Evaluating \(f\) at all four inputs completely specifies the function.
Boolean Functions Are Finite
A Boolean function with \(n\) inputs has only
\[ 2^n \]possible input assignments.
This means the behavior of the function can always be fully listed in a finite truth table.
How Many Two-Input Boolean Functions Exist?
Two Boolean inputs create
\[ 2^2=4 \]possible input rows.
Each row can independently produce either \(T\) or \(F\).
Therefore, the total number of distinct two-input Boolean functions is
\[ 2^4=16. \]AND, OR, XOR, NAND, NOR, implication, and biconditional are several important members of this finite collection.
General Number of Boolean Functions
A Boolean function of \(n\) variables has
\[ 2^n \]input rows.
Each row can receive one of two outputs.
Therefore, the number of distinct Boolean functions of \(n\) variables is
\[ \boxed{2^{2^n}}. \]This count grows extremely rapidly.
Boolean Conditions in Programs
Programming languages frequently evaluate Boolean expressions to decide whether instructions should run.
A condition conceptually similar to
\[ p\land q \]might require both:
- a user to be authenticated;
- a requested resource to be available.
The program proceeds only if the Boolean expression evaluates to true.
Boolean Conditions in Search and Filtering
Boolean operations also combine search conditions.
For example,
\[ p\land q \]can mean records satisfying both conditions,
while
\[ p\lor q \]can mean records satisfying at least one condition.
Boolean Conditions in Access Control
Suppose access requires
\[ \text{employee}\land\text{authorized}. \]The Boolean expression is true only when both access conditions are true.
More complicated policies can combine many Boolean operations.
Boolean Operations in Digital Systems
Digital circuits physically implement Boolean operations.
Common examples include:
- NOT gates;
- AND gates;
- OR gates;
- XOR gates;
- NAND gates;
- NOR gates.
Later lessons will connect symbolic expressions directly to circuit diagrams.
Boolean Operations and State
Boolean values can represent whether a finite condition is active or inactive.
Examples include:
- door open or closed;
- signal high or low;
- permission granted or denied;
- feature enabled or disabled;
- machine running or stopped.
Boolean operations combine these state conditions into decision rules.
Common Error: Treating Boolean Values as Ordinary Numbers
Although \(T\) and \(F\) are often represented by \(1\) and \(0\), Boolean operations are not identical to ordinary arithmetic.
For example,
\[ 1\lor1=1, \]not \(2\).
Boolean OR asks whether at least one input is true; it does not perform ordinary addition.
Common Error: Confusing OR and XOR
For ordinary OR,
\[ T\lor T=T. \]For XOR,
\[ T\oplus T=F. \]The operations differ precisely when both inputs are true.
Common Error: Forgetting the Final NOT in NAND
NAND means
\[ \neg(p\land q). \]First compute the conjunction, then reverse its value.
NAND is not the same operation as AND.
Common Error: Forgetting the Final NOT in NOR
NOR means
\[ \neg(p\lor q). \]It is true only when both inputs are false.
Common Error: Ignoring Grouping
Compare
\[ \neg(p\land q) \]with
\[ (\neg p)\land q. \]The first expression is NAND-like. The second negates only \(p\) before applying AND.
The two expressions do not have the same output pattern.
Common Error: Evaluating Too Much at Once
For
\[ \neg(p\lor q)\oplus r, \]work in stages:
- evaluate \(p\lor q\);
- apply NOT;
- apply XOR with \(r\).
Layered evaluation reduces errors.
A Reliable Procedure for Evaluating Boolean Expressions
- Identify the Boolean variables and their values.
- Locate parentheses and innermost subexpressions.
- Apply NOT to the correct inputs.
- Evaluate grouped binary operations.
- Continue outward one layer at a time.
- Record the final Boolean value.
- Check the result against the operation definitions when needed.
A Reliable Procedure for Building an Operation from Others
- Write the desired output pattern.
- Identify familiar operations with similar behavior.
- Combine operations using parentheses.
- Evaluate the resulting expression for every input row.
- Compare the output with the desired pattern.
- Revise the expression if any row differs.
Example: Construct XOR from Basic Operations
XOR should be true when exactly one input is true.
One expression with this behavior is
\[ (p\lor q)\land\neg(p\land q). \]The first part,
\[ p\lor q, \]requires at least one true input.
The second part,
\[ \neg(p\land q), \]excludes the case where both are true.
Therefore,
\[ \boxed{p\oplus q\equiv(p\lor q)\land\neg(p\land q)}. \]Example: Construct NAND
Start with AND:
\[ p\land q. \]Then negate the entire result:
\[ \boxed{\neg(p\land q)}. \]This creates NAND.
Example: Construct NOR
Start with OR:
\[ p\lor q. \]Negate the entire result:
\[ \boxed{\neg(p\lor q)}. \]This creates NOR.
Example: Full Evaluation
Suppose
\[ p=T,\qquad q=F,\qquad r=T. \]Evaluate
\[ \neg(p\land q)\land(q\oplus r). \]First,
\[ p\land q=T\land F=F. \]Therefore,
\[ \neg(p\land q)=T. \]Next,
\[ q\oplus r=F\oplus T=T. \]Finally,
\[ T\land T=T. \]Thus,
\[ \boxed{\neg(p\land q)\land(q\oplus r)=T}. \]Practice 1: NOT
Evaluate
\[ \neg T. \]Practice 2: AND
Evaluate
\[ T\land F. \]Practice 3: OR
Evaluate
\[ F\lor T. \]Practice 4: XOR
Evaluate
\[ T\oplus T. \]Practice 5: NAND
Evaluate
\[ \neg(T\land F). \]Practice 6: NOR
Evaluate
\[ \neg(F\lor F). \]Practice 7: Compound Expression
Suppose
\[ p=T,\qquad q=F. \]Evaluate
\[ \neg p\lor q. \]Practice 8: Grouping
Suppose
\[ p=T,\qquad q=F,\qquad r=F. \]Evaluate
\[ p\lor(q\land r). \]Practice 9: Boolean Identity Preview
Evaluate
\[ p\land T \]for \(p=T\) and for \(p=F\). What pattern do you observe?
Practice 10: XOR from Basic Operations
Evaluate
\[ (p\lor q)\land\neg(p\land q) \]when
\[ p=T,\qquad q=F. \]Compare the result with \(p\oplus q\).
Practice Answers
Practice 1
\[ \boxed{\neg T=F}. \]Practice 2
\[ \boxed{T\land F=F}. \]Practice 3
\[ \boxed{F\lor T=T}. \]Practice 4
XOR is false when the two inputs agree.
\[ \boxed{T\oplus T=F}. \]Practice 5
First,
\[ T\land F=F. \]Then negate:
\[ \boxed{\neg(T\land F)=T}. \]Practice 6
First,
\[ F\lor F=F. \]Then negate:
\[ \boxed{\neg(F\lor F)=T}. \]Practice 7
Since \(p=T\),
\[ \neg p=F. \]Therefore,
\[ F\lor F=F. \]Thus,
\[ \boxed{\neg p\lor q=F}. \]Practice 8
First,
\[ q\land r=F\land F=F. \]Then,
\[ p\lor(q\land r)=T\lor F=T. \]Therefore,
\[ \boxed{T}. \]Practice 9
If \(p=T\),
\[ T\land T=T. \]If \(p=F\),
\[ F\land T=F. \]Therefore,
\[ \boxed{p\land T=p}. \]Practice 10
First,
\[ p\lor q=T\lor F=T. \]Next,
\[ p\land q=T\land F=F, \]so
\[ \neg(p\land q)=T. \]Thus,
\[ (p\lor q)\land\neg(p\land q)=T\land T=T. \]Also,
\[ p\oplus q=T. \]The outputs agree.
What to Remember
- Boolean values have two states, commonly written \(T/F\) or \(1/0\).
- NOT reverses a Boolean value.
- AND is true only when all required inputs are true.
- OR is true when at least one input is true.
- XOR is true when exactly one of two inputs is true.
- NAND is the negation of AND.
- NOR is the negation of OR.
- Boolean expressions should be evaluated from the inside outward.
- Parentheses control the grouping of Boolean operations.
- Boolean expressions can be treated as finite input-output functions.
The central operational habit is to identify each Boolean operation, evaluate its inputs correctly, and combine results one structural layer at a time.
Where We Go Next
Boolean operations give us the basic mechanisms for transforming two-valued information. Different expressions can sometimes produce exactly the same output for every possible input.
The next lesson, Logical Equivalence, develops systematic methods for recognizing when two logical expressions have identical truth behavior.