Boolean Logic
Will Leeson
What comes to mind
when you think of
“Logic”?
Boolean Logic
● Developed by George Boole in 1854 X Y XΦY
● A systematic approach to logic
T T T
● Two Values
○ True (1) T F F
○ False (0)
● Variables F T F
● Three “Basic” operators F F T
● Several “Secondary” Operators
Some Terminology
● Constant
○ A value that does not change
○ In algebra: 1, -30, 2.541, π
○ In boolean logic: True, False
● Variable
○ A value that can span many values
○ Usually represented by a single letter (x, y, z, etc.)
○ Same for both algebra and boolean logic
Some Terminology
● Operator
○ A symbol representing a set function
○ Unary and Binary operators
○ In algebra: +, -, /, ^, etc.
○ In boolean logic: ∧, ∨, ↔, ¬
● Operand
○ The values an operator acts on
○ Algebra: 1 + 3, 27 / x, -3, etc.
○ Boolean logic: True ∧ False, X ↔ Y, ¬X
● Expression
○ A combination of operators and operands
○ Follows rules according to the mathematical language
Conjunction
● Binary Operator X Y XΛY
● In words - and
T T T
● In symbols - Λ
● Only true is both expressions are T F F
true
F T F
○ “Did you go to dinner and a movie.”
○ “If you are happy and you know it, clap F F F
your hands”
Disjunction
● Binary Operator X Y X∨Y
● In words - or
T T T
● In symbols - ∨
● True when either expression is true T F T
○ “My friends must enjoy listening to Folk
or R&B music” F T T
○ “Are there shellfish or cheese in this
F F F
dish? I’m deathly allergic.”
Negation
● Unary Operator
● In words - not
X ¬X
● In symbols - ¬
● True when the expression is False T F
○ “I am not 30 years old.”
○ “They are not a fan of the New York F T
Jets.”
Conditional
● Binary Operator X Y X→Y
● In words - If X then Y
T T T
● In symbols - →
● True unless X is true and Y is false T F F
○ “If I’ve been to Pluto, then I’ve been to
Mars.” F T T
○ “If I’ve seen a cute dog, then I’ve said
F F T
out loud ‘Ooo, cute dog’”
Biconditional
● Binary Operator X Y X↔Y
● In words - X if and only if Y
T T T
● In symbols - ↔
● True if X equals Y T F F
○ “Johnny can have dessert if and only if I
did all of my homework” F T F
○ “I will go to the concert if and only if I
F F T
know the band that is playing.”
Exclusive Disjunction
● Binary Operator X Y X⊕Y
● In words - (exclusive) or
T T F
● In symbols - ⊕
● True if either X or Y is true, not both T F T
○ “Would you like the chicken or the fish?”
○ “I need to take my pill or the lactose in F T T
the pizza will be a problem.”
F F F
Order of operation
● In algebra, PEMDAS
○ Parentheses
○ Exponent
○ Multiplication/Division
○ Addition/Subtraction
● In boolean logic, IPAOEBC
○ Inverse (Not)/Parentheses
○ And
○ Or/EXOR
○ Biconditional/Conditional
Truth Tables
● A way to structure Boolean Formula X Y X→Y
○ Break down the formula into “atoms”
○ Define the atoms using True and False T T T
○ Combine atoms using order of operations
○ Repeat until none are left T F F
F T T
F F T
Truth Tables
(X ∨ Y) ∧ ¬X
X Y (X ∨ Y) ¬X (X∨Y) ∧ ¬X
T T T F F
T F T F F
F T T T T
F F F T F
Truth Tables
(A → B) ∨ (B → A)
A B (A → B) (B → A) (A → B) ∨ (B → A)
T T T T T
T F F T T
F T T F T
F F T T T
Tautology!
Truth Tables
(X ∨ Y) ∧ ¬(X ∨ Y)
X Y (X ∨ Y) ¬(X ∨ Y) (X∨Y) ∧ ¬(X∨Y)
T T T F F
T F T F F
F T T F F
F F F T F
Contradiction!
Truth Tables
X∧Y↔Z∨Y
X Y Z X∧Y Z∨Y X∧Y↔Z∨Y
T T T T T T
T T F T T T
T F T F T F
T F F F F T
F T T F T F
F T F F T F
F F T F T F
F F F F F T
Logical Equivalence
X Y X→Y X Y ¬X ¬X ∨ Y
T T T T T F T
T F F ≡ T F F F
F T T F T T T
F F T F F T T
Logical Equivalence
X Y X↔Y X Y (X ∧ Y) ∨ (¬X ∧
¬Y)
T T T
T T T
T F F ≡ T F F
F T F
F T F
F F T
F F T
Logical Equivalence
X Y X⊕Y X Y (X ∨ Y) ∧ ¬(X ∧ Y)
T T F T T T
T F T ≡ T F F
F T T F T F
F F F F F T
So what does this
have to do with
Computers?
Computers are machines
● They do not think for themselves
● They follow a set of instructions
○ Can be informed by external stimulus
○ Can be informed by “randomness”
● Programs rarely don’t make “decisions”
○ If they clicked button X, do Y
○ If X and Y or Z, do A
● When writing programs, you will use boolean logic
Computers are machines
● Computers are wires with electricity
running through them
● They don’t know what X+Y means
○ We must translate X+Y to electricity
○ This is where Boolean Algebra comes in
● Different “gates” enact boolean
operations
● Circuits are combinations of gates
serving different purposes
Gate diagrams
AND Gate OR Gate NOT Gate
NAND Gate NOR Gate XOR Gate
Addition Circuit
1 1 1 1
1 0
0 0 1 1
1 1
0 1
0 1
In decimal: 1 + 0 = 1 In decimal: 1 + 1 = 2
In binary: 1 + 0 = 1 In binary: 1 + 1 = 10
In logic: S = 1 ⊕ 0 = 1 In logic: S = 1 ⊕ 1 = 0
C=1∧0=0 C=1∧1=1
And we can go on from there…
