MA2211/MA2011
Discrete Mathematics
Week 1: Introduction to Logic and Propositions
James Cook University
Semester 1, 2025
Your Instructor
Stephen Vu
- 🎓 Education: PhD in Recommender Systems, Queensland University of Technology (QUT)
- 💼 Industry Experience: AI Specialist at Telstra
- 👨🏫 Teaching Experience: 4 years of university teaching across:
- Queensland University of Technology (QUT)
- Kaplan Business School
- Central Queensland University (CQU)
- 📧 Contact: Available during consultation hours and via email
What is Discrete Mathematics?
Discrete (adjective): Individually separate and distinct.
"Speech sounds are produced as a continuous sound signal rather than discrete units"
Discrete Mathematics is:
- The mathematics of discrete objects (countable, separated items)
- The mathematical foundation of computer science
- A collection of techniques used throughout mathematics and engineering
- A way of rigorous, logical thinking
Why Study Discrete Mathematics?
Build Understanding
- Fundamental principles of computing
- How computers process information
- Algorithm design foundations
- Database structures
Develop Skills
- Rigorous logical thinking
- Creative problem-solving
- Abstract reasoning
- Precise communication
Bottom line: Discrete math teaches you to think like a computer scientist!
What We'll Learn This Semester
- Propositional Logic (Weeks 1-2)
- Predicate Logic (Week 3)
- Proof Methods (Weeks 4-5)
- Sets and Relations (Weeks 6-7)
- Functions (Week 8)
- Induction and Recursion (Weeks 9-10)
- Combinatorics (Week 11)
- Graph Theory (Week 12)
Assessment Structure
| Online Quizzes (Weekly) |
10% - Check your understanding |
| Written Problem Task |
30% - Deep investigation project |
| Problem Sheets (4 total) |
60% - Tutorial exercises (15% each) |
To Pass: You need 50% overall AND demonstrate reasonable attempts on all assessments (including 8/10 quizzes)
What is Logic?
Logic is:
- Correct reasoning according to a system of rules
- A framework of rigorous argument
- The foundation of mathematical proof
Why is Logic Important?
- Computer Science: Ensures programs reach correct conclusions
- Mathematics: Enables rigorous proofs
- Engineering: Designs reliable systems
- Everyday Life: Helps evaluate arguments and make decisions
What is a Proposition?
Definition: A proposition is a statement that is either true or false (but not both).
Examples of Propositions:
✓ "Townsville is south of Cairns." (TRUE)
✓ "1 + 1 = 2" (TRUE)
✓ "1 + 1 = 3" (FALSE)
✓ "Sharks are mammals." (FALSE)
✓ "There exists life outside our solar system." (unknown, but still true or false)
What is NOT a Proposition?
NOT Propositions:
- Questions:
"Is it raining?"
- Commands:
"Close the door!"
- Exclamations:
"Wow!"
Also NOT Propositions:
- Variables:
"x + 1 = 3"
(depends on x)
- Paradoxes:
"This statement is false"
(can't be T or F)
Key Point: A proposition must have a definite truth value!
Truth Values
The truth value of a proposition is whether it is true (T) or false (F).
Examples:
| Proposition |
Truth Value |
| The sun rises in the east. |
T |
| 2 + 2 = 5 |
F |
| Python is a programming language. |
T |
| All computers use Windows. |
F |
Building New Propositions from Old
We can combine simple propositions using logical connectives:
| NOT |
¬ |
Negation |
| AND |
∧ |
Conjunction |
| OR |
∨ |
Disjunction |
| IF...THEN |
→ |
Implication |
| IF AND ONLY IF |
↔ |
Biconditional |
Negation (NOT): ¬
¬p is true when p is false, and false when p is true.
Example:
p: "It is raining."
¬p: "It is NOT raining."
If p is true, then ¬p is false.
If p is false, then ¬p is true.
Conjunction (AND): ∧
p ∧ q is true when both p and q are true, and false otherwise.
Truth Table:
| p |
q |
p ∧ q |
| T |
T |
T |
| T |
F |
F |
| F |
T |
F |
| F |
F |
F |
Example:
p: "I will study."
q: "I will pass."
p ∧ q: "I will study AND I will pass."
This is only true if BOTH things happen!
Conjunction (AND): More Examples
English Variations:
p ∧ q can be expressed as:
- "p and q"
- "p but q"
- "p although q"
- "p while q"
- "not only p but also q"
Real Examples:
✓ "The code compiles AND runs without errors."
✓ "She studied hard BUT still found the exam difficult."
✓ "The algorithm is efficient WHILE using minimal memory."
Disjunction (OR): ∨
p ∨ q is true when p is true, or q is true, or both are true, and false otherwise.
Truth Table:
| p |
q |
p ∨ q |
| T |
T |
T |
| T |
F |
T |
| F |
T |
T |
| F |
F |
F |
Example:
p: "It's a weekend."
q: "It's a holiday."
p ∨ q: "It's a weekend OR it's a holiday."
True if at least one is true (or both!)
Important: Inclusive OR
In logic, OR (∨) is inclusive: it includes the case where both are true!
Comparison:
| Inclusive OR (∨) |
Exclusive OR (⊕) |
| "Coffee or tea?" (can have both!) |
"Chicken or fish?" (pick only one) |
| True when: p OR q OR both |
True when: p OR q BUT NOT both |
In this course, we always use inclusive OR (∨) unless stated otherwise.
Quiz 1: Test Your Understanding
Let p = "I have a laptop" and q = "I have internet"
Question: When is the statement "p ∧ q" TRUE?
A) When I have a laptop but no internet
B) When I have internet but no laptop
C) When I have both a laptop and internet
D) When I have either a laptop or internet
Implication (IF...THEN): →
p → q means "if p, then q"
This is false only when p is true and q is false.
Think of it as a Promise:
Promise: "If it rains (p), then I will bring an umbrella (q)."
When is this promise broken?
→ Only when it DOES rain but I DON'T bring an umbrella!
In all other cases, I kept my promise:
- It rains and I bring umbrella ✓
- It doesn't rain (promise doesn't apply) ✓
Implication: Truth Table
Truth Table:
| p |
q |
p → q |
| T |
T |
T |
| T |
F |
F |
| F |
T |
T |
| F |
F |
T |
Remember:
"A false promise is a lie"
False only when:
T → F
Implication: Real Examples
Let p = "It's Friday" and q = "I wear casual clothes"
Statement: "If it's Friday, then I wear casual clothes." (p → q)
| Scenario |
p |
q |
p → q |
Explanation |
| It's Friday and I wear casual clothes |
T |
T |
T |
Promise kept! |
| It's Friday but I wear formal clothes |
T |
F |
F |
Promise broken! |
| It's Monday and I wear casual clothes |
F |
T |
T |
No promise made |
| It's Monday and I wear formal clothes |
F |
F |
T |
No promise made |
Implication: Mathematical Examples
Evaluate the truth value of these implications:
1. "If 2+2=4, then Python is a programming language."
T → T = TRUE
2. "If 1+1=3, then the earth is flat."
F → F = TRUE (no false promise!)
3. "If 2+2=4, then 1+1=3."
T → F = FALSE (broken promise!)
4. "If unicorns exist, then I am a millionaire."
F → ? = TRUE (premise is false!)
Implication: Different Ways to Say It
All of these mean p → q:
✓ "If p, then q"
✓ "p implies q"
✓ "q if p"
✓ "q when p"
✓ "q whenever p"
✓ "p only if q"
✓ "p is sufficient for q"
✓ "q is necessary for p"
✓ "q follows from p"
Caution: "p only if q" means p → q (NOT q → p!)
Quiz 2: Implication
Let p = "x > 5" and q = "x > 3"
Question: Is the statement "p → q" TRUE?
(Think: If x is greater than 5, is it necessarily greater than 3?)
A) Yes, always TRUE - if x > 5, then x must be > 3
B) No, always FALSE - these are different conditions
C) Depends on the value of x
D) Cannot determine without knowing x
Biconditional (IF AND ONLY IF): ↔
p ↔ q means "p if and only if q"
This is true when p and q have the same truth value.
Think of it as a Two-Way Promise:
p ↔ q means BOTH:
- "If p, then q" (p → q)
- AND "If q, then p" (q → p)
Example: "I will go to the beach if and only if it's sunny."
→ If sunny, I go to beach
→ If I go to beach, it must be sunny
Biconditional: Truth Table
Truth Table:
| p |
q |
p ↔ q |
| T |
T |
T |
| T |
F |
F |
| F |
T |
F |
| F |
F |
T |
Remember:
"Same truth value"
True when:
Both T or Both F
Biconditional: Examples
1. "2+2=4 if and only if 1+1=2"
Both are true → TRUE
2. "A number is even if and only if it's divisible by 2"
Both have same truth value for any number → TRUE
3. "I study if and only if it's exam week"
Might study other times too → FALSE
4. "It's raining if and only if the ground is wet"
Ground can be wet for other reasons → FALSE
Biconditional: Different Ways to Say It
All of these mean p ↔ q:
✓ "p if and only if q"
✓ "p is necessary and sufficient for q"
✓ "p precisely when q"
✓ "p iff q" (mathematical abbreviation)
Remember: Biconditional is the strongest logical connection - it means both directions!
Quiz 3: Biconditional
Let p = "x = 2" and q = "x² = 4"
Question: Is the statement "p ↔ q" TRUE?
A) Yes, because if x=2, then x²=4
B) No, because x could be -2 (x²=4 but x≠2)
C) Yes, because both statements involve the same variable
D) Cannot determine without more information
Summary: All Logical Connectives
| Name |
Symbol |
Read as |
True when... |
| Negation |
¬p |
"not p" |
p is false |
| Conjunction |
p ∧ q |
"p and q" |
both p and q are true |
| Disjunction |
p ∨ q |
"p or q" |
at least one is true |
| Implication |
p → q |
"if p, then q" |
p is false OR q is true |
| Biconditional |
p ↔ q |
"p iff q" |
p and q have same value |
Operator Precedence (Order of Operations)
Just like arithmetic (×, ÷ before +, −), logical operators have an order:
| Priority |
Operator |
Symbol |
| 1 (Highest) |
Parentheses |
( ) |
| 2 |
Negation |
¬ |
| 3 |
Conjunction |
∧ |
| 4 |
Disjunction |
∨ |
| 5 |
Implication |
→ |
| 6 (Lowest) |
Biconditional |
↔ |
Precedence: Example 1
¬p ∨ q
How do we read this?
Step-by-step:
1. ¬ has higher precedence than ∨
2. So we evaluate ¬p first
3. Then apply ∨
Result: (¬p) ∨ q
NOT the same as ¬(p ∨ q) !
Precedence: Example 2
Step-by-step:
1. ∧ has higher precedence than →
2. Evaluate p ∧ q first
3. Then apply → with result and r
Result: (p ∧ q) → r
English: "If (p and q), then r"
Example: "If (I study AND I sleep well), then I will pass"
Truth Tables for Complex Propositions
Example: (p ∨ q) → ¬r
| p |
q |
r |
p ∨ q |
¬r |
(p ∨ q) → ¬r |
| T |
T |
T |
T |
F |
F |
| T |
T |
F |
T |
T |
T |
| T |
F |
T |
T |
F |
F |
| T |
F |
F |
T |
T |
T |
| F |
T |
T |
T |
F |
F |
| F |
T |
F |
T |
T |
T |
| F |
F |
T |
F |
F |
T |
| F |
F |
F |
F |
T |
T |
Quiz 4: Putting It All Together
Let p = T, q = F, r = T
Question: What is the truth value of: (p → q) ∨ r
A) TRUE, because p is true
B) TRUE, because r is true (making the disjunction true)
C) FALSE, because q is false
D) FALSE, because p → q is false
Hint: Evaluate (p → q) first (T → F = F), then F ∨ T = ?
Week 1 Summary
What We've Learned:
- ✓ What discrete mathematics is and why it matters
- ✓ Propositions and truth values
- ✓ Five logical connectives: ¬, ∧, ∨, →, ↔
- ✓ Truth tables for evaluating propositions
- ✓ Operator precedence rules
- ✓ Building and evaluating complex logical expressions
Next Steps:
→ Complete Tutorial Worksheet 1
→ Take Online Quiz 1 (due this week)
→ Review the textbook: Rosen Chapter 1.1
→ Next week: More logical equivalences and applications!