Proposition: A statement that is either true or false (but not both)
The Five Basic Connectives
Symbol
Name
Meaning
When is it TRUE?
¬
NOT
negation
When p is false
∧
AND
conjunction
When BOTH are true
∨
OR
disjunction
When AT LEAST ONE is true
→
IF...THEN
implication
When p is false OR q is true
↔
IF AND ONLY IF
biconditional
When BOTH have the SAME truth value
Week 1 Recap: Truth Tables
Truth tables give us a systematic way to determine truth values.
Example: Truth Table for p → q
p
q
p → q
T
T
T
T
F
F
F
T
T
F
F
T
Key Insight: p → q is only false when p is true but q is false (broken promise!)
Recall: Why Is p → q True When p Is False?
Example: "If it's Friday, then I wear a fun shirt"
This statement makes a promise about what happens on Fridays.
Friday + fun shirt → Promise kept ✓ (TRUE)
Friday + boring shirt → Promise broken ✗ (FALSE)
Not Friday + any shirt → No promise was made! (TRUE)
When p is false, the implication makes no claim, so it can't be false!
Memorize this pattern:
p → q is FALSE only in one case: T → F
All other cases are TRUE
Self-Check: Are You Ready for Week 2?
Quick Quiz
1. What is the truth value of (T ∧ F) ∨ T?
2. When is p ∨ q false?
3. Fill in the blank: (F → T) = ___
4. If p ↔ q is true, what can you say about p and q?
If you struggled with any of these, review Week 1 slides before continuing!
The Bridge: From Week 1 to Week 2
Week 1: Specific Propositions
When we wrote p: "I will cook dinner", the symbol p had a specific meaning.
→ p was a proposition with a definite truth value (T or F)
Week 2: Variables and Expressions
Sometimes we want to talk about patterns that work for any propositions.
→ p becomes a variable (like x in algebra)
→ p ∧ ¬q becomes an expression (like x + 5 in algebra)
Key Difference:
An expression doesn't have a truth value until we substitute specific propositions for the variables!
Why Learn Laws of Logic?
Week 1 Method: Truth Tables
To check if p ∨ ¬(¬p ∧ q) simplifies to something simpler:
Build an 8-column truth table
Fill in 4 rows for all combinations of p and q
Calculate each sub-expression step by step
Takes 5+ minutes ⏱️
Week 2 Method: Laws of Logic
Using algebraic rules:
p ∨ ¬(¬p ∧ q) ≡ p ∨ (p ∨ ¬q)
≡ p ∨ ¬q
2 steps, 30 seconds ⚡
Laws of logic let us manipulate expressions like algebra—faster and more powerful!
2.1 Logical Expressions
Propositional Variable: A symbol (p, q, r, ...) that can stand for any proposition
Logical Expression: A combination of propositional variables and logical connectives
Examples of Logical Expressions
p ∧ q
¬p ∨ (q → r)
(p ∧ ¬q) ∨ q
p → (q ∨ p)
Note: These don't have truth values until we assign specific propositions to p, q, r!
Evaluating Logical Expressions
Example: Evaluate (p ∧ ¬q) ∨ q for all possible values
p
q
¬q
p ∧ ¬q
(p ∧ ¬q) ∨ q
T
T
F
F
T
T
F
T
T
T
F
T
F
F
T
F
F
T
F
F
Observation: The final column shows the expression is sometimes true, sometimes false depending on p and q.
Tautologies: Always True
Example: Is (p ∧ q) → q always true?
p
q
p ∧ q
(p ∧ q) → q
T
T
T
T
T
F
F
T
F
T
F
T
F
F
F
T
Observation: ALL TRUE! This expression is true no matter what p and q are.
Tautology: An expression that is always true, regardless of the truth values of its variables
Contradictions: Always False
Example: Is p ∧ ¬p ever true?
p
¬p
p ∧ ¬p
T
F
F
F
T
F
Observation: ALWAYS FALSE! A proposition can't be both true and false.
Contradiction: An expression that is always false, regardless of the truth values of its variables
Relationship: If A is a tautology, then ¬A is a contradiction (and vice versa)
Examples: Tautologies and Contradictions
Common Tautologies
p ∨ ¬p — "It's either true or not true" (Law of Excluded Middle)
p → p — "If p, then p" (trivially true)
(p ∧ q) → p — "If both are true, then p is true"
p → (p ∨ q) — "If p is true, then at least one is true"
Common Contradictions
p ∧ ¬p — "It's both true and false" (impossible!)
¬(p ∨ ¬p) — "Neither p nor ¬p is true" (impossible!)
(p → q) ∧ (p ∧ ¬q) — "p implies q, but p is true and q is false"
Counterexamples
Not all expressions are tautologies or contradictions!
Counterexample: An assignment of truth values that makes an expression FALSE
Example: Is (p ∨ q) → p a tautology?
Let's try p = F, q = T:
p ∨ q = F ∨ T = T
(p ∨ q) → p = T → F = F ✗
Conclusion: No! The assignment p = F, q = T is a counterexample.
Key Insight: To show an expression is NOT a tautology, we only need to find ONE counterexample!
Quiz: Identify Tautologies and Contradictions
1. Is p → (q → p) a tautology, contradiction, or neither?
Hint: Try building a truth table
2. Is (p ∧ q) ∧ ¬p a tautology, contradiction, or neither?
3. Is p ∨ q a tautology, contradiction, or neither?
4. Find a counterexample to (p → q) → (q → p)
Logical Equivalence
Motivating Example
Are these two expressions the same?
Expression A: ¬(p ∨ q)
Expression B: ¬p ∧ ¬q
p
q
p ∨ q
¬(p ∨ q)
¬p
¬q
¬p ∧ ¬q
T
T
T
F
F
F
F
T
F
T
F
F
T
F
F
T
T
F
T
F
F
F
F
F
T
T
T
T
Observation: The truth tables for A and B are IDENTICAL!
Definition of Logical Equivalence
Logical Equivalence:
Two expressions A and B are logically equivalent if they have the same truth table.
We write: A ≡ B
Alternative Definition
A ≡ B if and only if A ↔ B is a tautology
From previous slide:
¬(p ∨ q) ≡ ¬p ∧ ¬q
This means: (¬(p ∨ q)) ↔ (¬p ∧ ¬q) is a tautology
Important: ≡ means the expressions are interchangeable—we can replace one with the other!
Logical Equivalence vs. Biconditional
≡ (Equivalence)
A relationship between expressions
NOT part of an expression
Meta-level statement
Example: "p ∨ q ≡ q ∨ p"
Means: "These two things are the same"
↔ (Biconditional)
A connective (operator)
INSIDE an expression
Object-level operator
Example: "p ↔ q"
Means: "p if and only if q"
Connection:
A ≡ B means that (A ↔ B) is a tautology
Example: p ∨ q ≡ q ∨ p
This is true because (p ∨ q) ↔ (q ∨ p) is always true
Important Equivalence: p → q
Theorem: p → q ≡ ¬p ∨ q
Let's verify with a truth table:
p
q
p → q
¬p
¬p ∨ q
T
T
T
F
T
T
F
F
F
F
F
T
T
T
T
F
F
T
T
T
Why this makes intuitive sense:
"If it's Friday, I wear a fun shirt" is true when:
→ Either it's NOT Friday (¬p) OR I'm wearing a fun shirt (q)
Converse, Inverse, and Contrapositive
Given an implication p → q, we can form three related statements:
Name
Form
Example (p: Friday, q: fun shirt)
Original
p → q
"If Friday, then fun shirt"
Converse
q → p
"If fun shirt, then Friday"
Inverse
¬p → ¬q
"If not Friday, then not fun shirt"
Contrapositive
¬q → ¬p
"If not fun shirt, then not Friday"
Key Facts:
• An implication and its contrapositive are ALWAYS equivalent: p → q ≡ ¬q → ¬p
• The converse and inverse are equivalent to each other: q → p ≡ ¬p → ¬q
• But the original and converse are NOT necessarily equivalent!
Verifying Contrapositive Equivalence
Proof that p → q ≡ ¬q → ¬p
p
q
p → q
¬q
¬p
¬q → ¬p
T
T
T
F
F
T
T
F
F
T
F
F
F
T
T
F
T
T
F
F
T
T
T
T
Why this matters in mathematics:
Sometimes proving the contrapositive is easier than proving the original statement!
To prove: "If n² is even, then n is even"
Contrapositive: "If n is odd, then n² is odd" ← Much easier to prove!
2.2 Laws of Logic
Just like algebra has rules (commutative, distributive, etc.), logic has laws!
Law of Logic: A statement of the form A ≡ B that is always true
Why Learn These Laws?
Simplify complex logical expressions
Prove that two expressions are equivalent (without truth tables!)
Optimize code and circuits
Validate arguments systematically
We'll learn the fundamental laws and how to apply them algebraically.
Fundamental Laws: Implication and Equivalence
Implication Law:
p → q ≡ ¬p ∨ q
Equivalence Law:
p ↔ q ≡ (p → q) ∧ (q → p)
Using Implication Law:
Simplify: (p → q) ∧ p
≡ (¬p ∨ q) ∧ p (implication law)
Using Equivalence Law:
To prove A ≡ B, we can prove:
(1) A → B is a tautology, AND
(2) B → A is a tautology
De Morgan's Laws
These laws tell us how to negate AND and OR:
De Morgan's Law 1:
¬(p ∧ q) ≡ ¬p ∨ ¬q
"NOT both" = "Either NOT p OR NOT q"
De Morgan's Law 2:
¬(p ∨ q) ≡ ¬p ∧ ¬q
"NOT either" = "Both NOT p AND NOT q"
English Example:
"I don't like apples or pears" can mean:
→ ¬(a ∨ p) ≡ ¬a ∧ ¬p = "I don't like apples AND I don't like pears"
Commutative and Associative Laws
Commutative Laws (Order doesn't matter)
p ∧ q ≡ q ∧ p
p ∨ q ≡ q ∨ p
Associative Laws (Grouping doesn't matter)
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
Example:
"I like cats and dogs" ≡ "I like dogs and cats" (commutative)
"(I like cats and dogs) and birds" ≡ "I like cats and (dogs and birds)" (associative)
Because of associativity, we can write: p ∧ q ∧ r (no parentheses needed!)
Distributive Laws
In arithmetic: a × (b + c) = (a × b) + (a × c)
In logic, we have TWO distributive laws:
Distributive Law 1:
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
"AND distributes over OR"
Distributive Law 2:
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
"OR distributes over AND" (doesn't work in arithmetic!)
Example:
"I'm happy if it's sunny and (warm or I have coffee)"
≡ "I'm happy if (it's sunny and warm) or (it's sunny and I have coffee)"
Identity and Annihilation Laws
We need two special propositions:
T = a tautology (always true)
F = a contradiction (always false)
Identity Laws (neutral elements)
p ∧ T ≡ p
p ∨ F ≡ p
Annihilation Laws (absorbing elements)
p ∧ F ≡ F
p ∨ T ≡ T
Inverse Laws
p ∧ ¬p ≡ F
p ∨ ¬p ≡ T
Complete List of Laws
Law Name
Equivalence
Implication
p → q ≡ ¬p ∨ q
Equivalence
p ↔ q ≡ (p → q) ∧ (q → p)
De Morgan
¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q
Commutative
p ∧ q ≡ q ∧ p p ∨ q ≡ q ∨ p
Associative
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)