Back to: Mathematics – Freshman Courses
0
Chapter 1: Propositional Logic and Set Theory
1.1 Propositional Logic
Mathematical (or symbolic) logic is an analytical theory of reasoning. Its goal is to systematize principles of valid reasoning. Unlike natural language, symbolic logic ignores meaning and focuses only on the form of arguments—making it ideal for verifying mathematical proofs.
In this section, we explore:
- What constitutes a proposition,
- The five logical connectives,
- How to construct and evaluate compound propositions,
- Special types like tautologies and contradictions.
1.1.1 Definition and Examples of Propositions
Definition 1.1: A proposition (or statement) is a declarative sentence that is either True (T) or False (F)—but not both.
Key Points:
- Questions, commands, and exclamations are not propositions.
- A sentence may be a proposition even if we don’t know its truth value—as long as it has one.
Examples:
- “2 is an even number.” → True ✅
- “A triangle has four sides.” → False ❌
- “Emperor Menelik ate chicken soup the night after the Battle of Adwa.” → Either T or F, though historically uncertain. Still a proposition because it has a truth value.
- “May God bless you!” → Not a proposition (exclamation).
- “Give me that book.” → Not a proposition (command).
- “What is your name?” → Not a proposition (question).
Remark: Every proposition has exactly one truth value: T or F.
1.1.2 Logical Connectives
We combine propositions using logical connectives. The five primary ones are:
- Conjunction (AND): \( \land \)
- Disjunction (OR): \( \lor \)
- Implication (IF…THEN): \( \Rightarrow \)
- Biconditional (IF AND ONLY IF): \( \Leftrightarrow \)
- Negation (NOT): \( \neg \)
1. Conjunction (\( \land \))
The conjunction \( p \land q \) is true only when both \( p \) and \( q \) are true.
| \( p \) | \( q \) | \( p \land q \) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Let:
- \( p \): “3 is an odd number.” (T)
- \( q \): “27 is a prime number.” (F)
- \( r \): “Addis Ababa is the capital of Ethiopia.” (T)
- \( p \land q \): “3 is odd AND 27 is prime.” → False
- \( p \land r \): “3 is odd AND Addis Ababa is the capital.” → True
2. Disjunction (\( \lor \))
The disjunction \( p \lor q \) is false only when both \( p \) and \( q \) are false.
⚠️ Note: In logic, “or” is inclusive—meaning “\( p \), \( q \), or both.”
| \( p \) | \( q \) | \( p \lor q \) |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Using the same \( p, q, r \) as above:
- \( p \lor q \): “3 is odd OR 27 is prime.” → True
- \( q \lor s \) where \( s \): “Nairobi is Ethiopia’s capital.” (F) → False
3. Implication (\( \Rightarrow \))
The implication \( p \Rightarrow q \) (read: “if \( p \), then \( q \)”) is false only when \( p \) is true and \( q \) is false.
Equivalent phrasings:
- \( q \) if \( p \)
- \( p \) implies \( q \)
- \( p \) only if \( q \)
- \( p \) is sufficient for \( q \)
- \( q \) is necessary for \( p \)
| \( p \) | \( q \) | \( p \Rightarrow q \) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
- \( p \Rightarrow q \): “If 3 is odd, then 27 is prime.” → False
- \( p \Rightarrow r \): “If 3 is odd, then Addis Ababa is the capital.” → True
4. Biconditional (\( \Leftrightarrow \))
\( p \Leftrightarrow q \) means “\( p \) if and only if \( q \)”. It is true when \( p \) and \( q \) have the same truth value.
| \( p \) | \( q \) | \( p \Leftrightarrow q \) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
Let:
- \( p \): “2 > 3” (F)
- \( q \): “5 > 4” (T)
- \( p \Leftrightarrow q \): “2 > 3 iff 5 > 4” → False
5. Negation (\( \neg \))
The negation \( \neg p \) flips the truth value of \( p \).
| \( p \) | \( \neg p \) |
|---|---|
| T | F |
| F | T |
\( p \): “Addis Ababa is the capital.” (T)
\( \neg p \): “Addis Ababa is not the capital.” (F)
1.1.3 Compound Propositions
Definition 1.2: A compound proposition is formed by joining two or more propositions with logical connectives.
Parentheses are crucial! For example:
- \( (p \Rightarrow q) \land r \)
- \( p \Rightarrow (q \land r) \)
Convention: \( \land \) and \( \lor \) bind tighter than \( \Rightarrow \) and \( \Leftrightarrow \). So:
- \( p \land q \Rightarrow r \) means \( (p \land q) \Rightarrow r \)
- \( \neg q \Rightarrow \neg p \) means \( (\neg q) \Rightarrow (\neg p) \)
Definition 1.3: Two compound propositions \( P \) and \( Q \) are logically equivalent (written \( P \equiv Q \)) if they have identical truth values for all combinations of their components.
\( p \Rightarrow q \equiv \neg q \Rightarrow \neg p \) (this is the contrapositive, always equivalent!)
Related Conditional Propositions
Given \( p \Rightarrow q \):- Converse: \( q \Rightarrow p \)
- Inverse: \( \neg p \Rightarrow \neg q \)
- Contrapositive: \( \neg q \Rightarrow \neg p \) ✅ (equivalent to original)
Original: “If Kidist lives in Addis Ababa, then she lives in Ethiopia.”
- Converse: “If she lives in Ethiopia, then she lives in Addis Ababa.” ❌
- Contrapositive: “If she does not live in Ethiopia, then she does not live in Addis Ababa.” ✅
Important Logical Laws
- Idempotent: \( p \equiv p \lor p \), \( p \equiv p \land p \)
- Commutative: \( p \land q \equiv q \land p \)
- Associative: \( p \land (q \land r) \equiv (p \land q) \land r \)
- Distributive: \( p \lor (q \land r) \equiv (p \lor q) \land (p \lor r) \)
- De Morgan’s: \( \neg(p \land q) \equiv \neg p \lor \neg q \)
- Law of Contrapositive: \( p \Rightarrow q \equiv \neg q \Rightarrow \neg p \)
- Double Negation: \( \neg(\neg p) \equiv p \)
1.1.4 Tautology and Contradiction
- A tautology is always true (e.g., \( p \lor \neg p \)).
- A contradiction is always false (e.g., \( p \land \neg p \)).
- \( p \lor \neg p \): Law of excluded middle → tautology
- \( p \land \neg p \): Logical impossibility → contradiction
- \( p \Rightarrow (q \Rightarrow p) \): Always true → tautology
Remark:
- A proposition is a tautology iff every row in its truth table is T.
- \( P \equiv Q \) iff \( P \Leftrightarrow Q \) is a tautology.
End of Section 1.1 – Propositional Logic
Section 1.1: Propositional Logic – Exercises with Full Solutions
Exercise 1. Which of the following sentences are propositions? For those that are, indicate the truth value.
a. 123 is a prime number.
b. 0 is an even number.
c. \(x^2 – 4 = 0\).
d. Multiply \(5x + 2\) by 3.
e. What an impossible question!
a. 123 is a prime number.
b. 0 is an even number.
c. \(x^2 – 4 = 0\).
d. Multiply \(5x + 2\) by 3.
e. What an impossible question!
Solution:
a. Yes – False. (123 = 3 × 41)
b. Yes – True. (0 is divisible by 2)
c. No – It contains a variable and has no fixed truth value.
d. No – It is a command.
e. No – It is an exclamation.
a. Yes – False. (123 = 3 × 41)
b. Yes – True. (0 is divisible by 2)
c. No – It contains a variable and has no fixed truth value.
d. No – It is a command.
e. No – It is an exclamation.
Exercise 2. State the negation of each of the following statements.
a. \(\sqrt{2}\) is a rational number.
b. 0 is not a negative integer.
c. 111 is a prime number.
a. \(\sqrt{2}\) is a rational number.
b. 0 is not a negative integer.
c. 111 is a prime number.
Solution:
a. \(\sqrt{2}\) is not a rational number.
b. 0 is a negative integer. (Note: This is false, but it is the correct logical negation.)
c. 111 is not a prime number. (111 = 3 × 37)
a. \(\sqrt{2}\) is not a rational number.
b. 0 is a negative integer. (Note: This is false, but it is the correct logical negation.)
c. 111 is not a prime number. (111 = 3 × 37)
Exercise 3. Let \(p\): 15 is an odd number (True).
\(q\): 21 is a prime number (False).
State each of the following in words, and determine the truth value.
a. \(p \lor q\)
b. \(p \land q\)
c. \(\lnot p \lor q\)
d. \(p \land \lnot q\)
e. \(p \Rightarrow q\)
f. \(q \Rightarrow p\)
g. \(\lnot p \Rightarrow \lnot q\)
h. \(\lnot q \Rightarrow \lnot p\)
\(q\): 21 is a prime number (False).
State each of the following in words, and determine the truth value.
a. \(p \lor q\)
b. \(p \land q\)
c. \(\lnot p \lor q\)
d. \(p \land \lnot q\)
e. \(p \Rightarrow q\)
f. \(q \Rightarrow p\)
g. \(\lnot p \Rightarrow \lnot q\)
h. \(\lnot q \Rightarrow \lnot p\)
Solution:
a. “15 is odd or 21 is prime.” → T ∨ F = True
b. “15 is odd and 21 is prime.” → T ∧ F = False
c. “15 is even or 21 is prime.” → F ∨ F = False
d. “15 is odd and 21 is not prime.” → T ∧ T = True
e. “If 15 is odd, then 21 is prime.” → T ⇒ F = False
f. “If 21 is prime, then 15 is odd.” → F ⇒ T = True
g. “If 15 is even, then 21 is not prime.” → F ⇒ T = True
h. “If 21 is not prime, then 15 is even.” → T ⇒ F = False
a. “15 is odd or 21 is prime.” → T ∨ F = True
b. “15 is odd and 21 is prime.” → T ∧ F = False
c. “15 is even or 21 is prime.” → F ∨ F = False
d. “15 is odd and 21 is not prime.” → T ∧ T = True
e. “If 15 is odd, then 21 is prime.” → T ⇒ F = False
f. “If 21 is prime, then 15 is odd.” → F ⇒ T = True
g. “If 15 is even, then 21 is not prime.” → F ⇒ T = True
h. “If 21 is not prime, then 15 is even.” → T ⇒ F = False
Exercise 4. Complete the following truth table.
| \(p\) | \(q\) | \(\lnot q\) | \(p \land \lnot q\) |
|---|---|---|---|
| T | T | ||
| T | F | ||
| F | T | ||
| F | F |
Solution:
| \(p\) | \(q\) | \(\lnot q\) | \(p \land \lnot q\) |
|---|---|---|---|
| T | T | F | F |
| T | F | T | T |
| F | T | F | F |
| F | F | T | F |
Exercise (End of Section 1.1.4):
For statements \(p, q\), show that \((p \land \lnot q) \land (p \land q)\) is a contradiction.
For statements \(p, q\), show that \((p \land \lnot q) \land (p \land q)\) is a contradiction.
Solution:
Consider the expression: \((p \land \lnot q) \land (p \land q)\).
This simplifies to: \(p \land \lnot q \land p \land q = p \land (\lnot q \land q) = p \land \text{F} = \text{F}\).
Since \(\lnot q \land q\) is always false, the whole expression is always false — a contradiction.
Consider the expression: \((p \land \lnot q) \land (p \land q)\).
This simplifies to: \(p \land \lnot q \land p \land q = p \land (\lnot q \land q) = p \land \text{F} = \text{F}\).
Since \(\lnot q \land q\) is always false, the whole expression is always false — a contradiction.
Exercise: Write the contrapositive and the converse of:
“If it is cold, then the lake is frozen.”
“If it is cold, then the lake is frozen.”
Solution:
Original: \(p \Rightarrow q\), where
\(p\): It is cold.
\(q\): The lake is frozen.
Converse: If the lake is frozen, then it is cold. (\(q \Rightarrow p\))
Contrapositive: If the lake is not frozen, then it is not cold. (\(\lnot q \Rightarrow \lnot p\))
Original: \(p \Rightarrow q\), where
\(p\): It is cold.
\(q\): The lake is frozen.
Converse: If the lake is frozen, then it is cold. (\(q \Rightarrow p\))
Contrapositive: If the lake is not frozen, then it is not cold. (\(\lnot q \Rightarrow \lnot p\))
Exercise: Let \(p\) and \(q\) be statements. Which of the following implies that \(p \lor q\) is false?
a. \(\lnot p \lor \lnot q\) is false.
b. \(\lnot p \lor q\) is true.
c. \(\lnot p \land \lnot q\) is true.
d. \(p \Rightarrow q\) is true.
e. \(p \land q\) is false.
a. \(\lnot p \lor \lnot q\) is false.
b. \(\lnot p \lor q\) is true.
c. \(\lnot p \land \lnot q\) is true.
d. \(p \Rightarrow q\) is true.
e. \(p \land q\) is false.
Solution:
\(p \lor q\) is false **only when both \(p = F\) and \(q = F\)**.
This is exactly what \(\lnot p \land \lnot q = T\) means.
So, the correct choice is c.
\(p \lor q\) is false **only when both \(p = F\) and \(q = F\)**.
This is exactly what \(\lnot p \land \lnot q = T\) means.
So, the correct choice is c.
Exercise: Suppose \(p = T, q = F, r = F, s = T\). Find the truth value of:
\((p \lor \lnot q) \lor r \Rightarrow (s \land \lnot s)\)
\((p \lor \lnot q) \lor r \Rightarrow (s \land \lnot s)\)
Solution:
– \(\lnot q = T\) → \(p \lor \lnot q = T \lor T = T\)
– \((p \lor \lnot q) \lor r = T \lor F = T\)
– \(s \land \lnot s = T \land F = F\)
So the implication is: \(T \Rightarrow F = \textbf{False}\).
– \(\lnot q = T\) → \(p \lor \lnot q = T \lor T = T\)
– \((p \lor \lnot q) \lor r = T \lor F = T\)
– \(s \land \lnot s = T \land F = F\)
So the implication is: \(T \Rightarrow F = \textbf{False}\).
All exercises from Section 1.1: Propositional Logic with full solutions.