EX1
If P is false and Q is true, evaluate P ∧ Q, P ∨ Q, and P → Q.
Answer: P ∧ Q is false; P ∨ Q is true; P → Q is true because a false antecedent makes the implication true in classical logic.
LESSON 02 · FOUNDATIONS
Discrete Mathematics and Logic
Build precise reasoning with propositions, sets, and relations.
Discrete mathematics studies structures made of distinct objects. Logic helps express and test claims; sets organize collections; relations describe connections between objects. These ideas underpin algorithms, databases, digital circuits, and formal verification.
Learning objectives
- Distinguish propositions from questions or commands.
- Evaluate NOT, AND, OR, and implication.
- Use truth tables to test logical statements.
- Apply basic set notation and understand relations.
1. Propositions and truth values
A proposition is a declarative statement that is either true or false in a given interpretation. “7 is prime” is true; “10 < 3” is false. “Close the door” is a command, not a proposition. A variable such as P can stand for a proposition.
Negation NOT P reverses the truth value of P. If P is true, ¬P is false; if P is false, ¬P is true.
2. Logical connectives
Conjunction P ∧ Q (AND) is true only when both P and Q are true. Disjunction P ∨ Q (OR) is true when at least one is true, including when both are true. Negation ¬P reverses P.
Implication P → Q is false only when P is true and Q is false. Read it as “if P, then Q.” If P is false, the implication is true in classical logic, regardless of Q.
3. Truth tables
A truth table lists every possible truth-value combination. For two propositions P and Q, there are 2² = 4 rows.
P | Q | P ∧ Q | P ∨ Q | P → Q\nT | T | T | T | T\nT | F | F | T | F\nF | T | F | T | T\nF | F | F | F | T
To compare two expressions, evaluate both columns row by row. If they match on every row, the expressions are logically equivalent.
4. Sets and set operations
A set is a collection of distinct elements. If A = {1, 2, 3} and B = {3, 4}, then A ∪ B = {1, 2, 3, 4} (union), A ∩ B = {3} (intersection), and A \\ B = {1, 2} (difference). The order of elements does not matter, and repeated elements do not create new members.
Use x ∈ A to mean “x is an element of A” and A ⊆ B to mean every element of A is also in B. The empty set ∅ contains no elements.
5. Relations and applications
A relation from A to B is a set of ordered pairs drawn from A × B. For example, “is less than” relates some numbers to others. Relations can be represented as tables, pairs, or graphs. In databases, a relation-like table organizes records by fields.
A relation on one set may be reflexive (each element relates to itself), symmetric (aRb implies bRa), or transitive (aRb and bRc imply aRc). Check the definition carefully before assigning a property.
6. Common mistakes
• Treating logical OR as exclusive OR when the context uses inclusive OR.\n• Assuming P → Q is the same as Q → P.\n• Confusing an element x ∈ A with a subset A ⊆ B.\n• Counting duplicate set elements more than once.\n• Declaring a relation symmetric or transitive from only one example.
7. Practice exercises
Try each question before revealing the worked answer.
EX2
Let A = {a, b, c} and B = {b, c, d}. Find A ∩ B and A ∪ B.
Answer: A ∩ B = {b, c}; A ∪ B = {a, b, c, d}.
EX3
Is the implication P → Q always equivalent to Q → P?
Answer: No. For P true and Q false, P → Q is false while Q → P is true.
8. Quick knowledge check
When P is false, what is the truth value of P → Q in classical logic?
What would you like to learn next?
Choose a topic to help prioritize future learning materials.