MATH1081 Discrete Mathematics Study Notes
Introduction to Logic and Truth Tables
- Logic: Study of how the truth or falsity of statements follows from other statements.
- Example: If "G is an Eulerian graph" (true), then "no vertex of G has odd degree" (true).
- Importance of truth values in logic; evaluating implications without assuming statements are true.
Propositions
- Proposition: Statement clearly true or false.
- Examples:
- "1 + 1 = 2" (true)
- "2 + 2 = 3" (false)
- "My birthday is on February 29" (true or false, depending on the year).
- Non-examples:
- "2 + 2"
- "x² + x - 12 = 0"
- Subjective statements (like opinion based) are not propositions.
Operators in Logic
- Logical Operators: Combine propositions to form complex expressions.
- Notation and meanings:
- Not ($
eg$) : negation - And ($igwedge$) : conjunction (true if both are true)
- Or ($igvee$) : disjunction (true if at least one is true)
- Exclusive Or ($igoplus$): true if exactly one is true
- If… then ($
ightarrow$): implication - If and only if ($
ightarrow
ightarrow$): biconditional
- Use examples to simplify understanding:
- If p and q are propositions, expressions with these operators create compound propositions.
Translating Statements
- Example Translations: Assign values to p, q, r to structure different statements in logical notation:
- (i) “I will go to the pub tonight, but I will submit my assignment on time tomorrow.” → $q igwedge r$
- (ii) “I will not both study and go to the pub tonight.” → $
eg (p igwedge q)$ - (iii) “I will submit my assignment late tomorrow unless I avoid the pub and study instead tonight.” → $
eg(
eg q igwedge p)
ightarrow
eg r$
Truth Values and Compound Propositions
- Truth of propositions determines the truth of compound propositions ($p igvee q$).
- Task: Determine truth value of expressions step-by-step using known single truths.
- Negation: Opposite of the truth value.
- Example: Truth table for $
eg p$ - | p | $
eg p$ |
|---|---|
| T | F |
| F | T |
- Example: Truth table for $
And, Or, Exclusive Or Truth Tables
Conjunction (And) ($p igwedge q$):
- True only when both p and q are true.
- Truth Table:
| p | q | $p igwedge q$ | |
|---|---|---|---|
| T | T | T | |
| T | F | F | |
| F | T | F | |
| F | F | F | |
Disjunction (Or) ($p igvee q$): True when at least one of p or q is true. | |||
| p | q | $p igvee q$ | |
| --- | --- | --- | |
| T | T | T | |
| T | F | T | |
| F | T | T | |
| F | F | F | |
Exclusive Or ($p igoplus q$): True if exactly one of p or q is true. | |||
| p | q | $p igoplus q$ | |
| --- | --- | --- | |
| T | T | F | |
| T | F | T | |
| F | T | T | |
| F | F | F | |
Logical Equivalence and Laws |
- Two propositional forms are logically equivalent if they yield identical truth values under all valuations.
- Example: $
eg(p igvee q) ext{ is equivalent to }
eg p igwedge
eg q$ (De Morgan’s Law).
- Example: $
- Notable logical laws include:
- Commutative Laws: $p igwedge q ext{ and } q igwedge p$.
- Associative Laws: $(p igwedge q) igwedge r ext{ is equivalent to } p igwedge(q igwedge r)$.
- Distributive Laws: $p igwedge(q igvee r) ext{ is equivalent to } (p igwedge q) igvee(p igwedge r)$.
- Identity Laws: $p igwedge T ext{ is equivalent to } p$.
Valid Argument Forms
- Common rules of inference include:
- Modus Ponens: $p
ightarrow q, p
ightarrow q$. - Modus Tollens: $p
ightarrow q,
eg q
ightarrow
eg p.$ - Hypothetical Syllogism: $p
ightarrow q, q
ightarrow r
ightarrow p
ightarrow r.$ - Validity verified through truth tables showing all true hypotheses yield true conclusions.
- Modus Ponens: $p
Tautologies and Contradictions
- Tautology: Always true (
$ p igvee
eg p$). - Contradiction: Always false (
$p igwedge
eg p$). - Contingency: Neither a tautology nor a contradiction.
Implications and Biconditionals
- Implication ($p
ightarrow q$): Truth table shows it's only false when p is true and q is false. - Biconditional ($p
ightarrow q$): True only when both p and q share truth values. - Logical equivalence to tautology with biconditionals indicates relationships between propositions.