Mathematics for Computer Scientists - Lecture 2 Study Notes
Mathematics for Computer Scientists - COMP1001: Lecture 2
Overview of Lecture Topics
Reminder on truth tables
Discussion of more complex formulas
Tautologies, contradictions, satisfiability
Equivalencies
De Morgan’s Laws
Truth Table Reminder
Conjunction (AND, ∧)
Truth Table:
| A | B | A ∧ B |
|----|----|--------|
| F | F | F |
| F | T | F |
| T | F | F |
| T | T | T |
Binary Ordering: The input values are represented as 0 (False) and 1 (True). The combinations yield results as follows:
| A | B | A ∧ B |
|---|---|--------|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Disjunction (OR, ∨)
Truth Table:
| A | B | A ∨ B |
|---|---|--------|
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | T |
Binary Ordering Representation:
| A | B | A ∨ B |
|---|---|--------|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Implication (Implies, ⇒)
Definition: A being true implies B being true. If A is true, then B must also be true.
Important aspects of the implication:
If A is false, the implication does not restrict B. Thus, A ⇒ B is true unless A is true and B is false.
Truth Table:
A
B
A ⇒ B
F
F
?
F
T
?
T
F
F
T
T
T
Truth Table for “Only If” (⇐)
Definition: A ⇐ B indicates that B can only be true if A is also true. This is effectively B ⇒ A.
Truth Table:
| A | B | A ⇐ B |
|---|---|--------|
| F | F | T |
| F | T | T |
| T | F | F |
| T | T | T |
Biconditional (If and Only If, ↔)
Definition: A ↔ B indicates that B is true if and only if A is true. A and B must either both be true or both be false.
Truth Table:
| A | B | A ↔ B |
|---|---|--------|
| F | F | T |
| F | T | F |
| T | F | F |
| T | T | T |
Propositions and Logical Statements
Importance of Propositions
Propositions can simplify logical problems, e.g., determining whether a certain condition (like code functionality) is true. Propositions enable use of propositional logic, which is simpler than complex calculations.
Example: “Jason is teaching COMP1001 this week” and “If Jason is teaching COMP1001, he will be in B52 at noon on Monday.”
Question: Will Jason be in B52?
December 3, 2022: If proposition structure is unclear, assess whether they are self-contained True/False statements.
Formulation of Propositions
Rephrasing scenario:
If Jason is teaching COMP1001 this week, then Jason will be in B52 at noon on Monday.
Then formalizing as:
Let P be: "Jason is teaching COMP1001 this week"
Let Q be: "Jason will be in B52 at noon on Monday"
This leads to the mathematical statement: $P ⇒ Q$.
Complex Formulas
Explanation of Larger Formulas
Consider the formula: ¬P ∨ Q ↔ (P ⇒ Q)
Brackets are often necessary to define evaluation order, but may not always be required in simple cases.
Precedence order of logical operators, based on most common evaluation sequence:
Negation (¬)
Conjunction (∧)
Disjunction (∨)
Implication (⇒)
Biconditional (↔) is sometimes considered of lower priority than implications.
Analyzing ¬P ∨ Q ↔ (P ⇒ Q)
Using truth tables:
Given: ¬P ∨ Q ↔ (P ⇒ Q)
Analyze rows for each possible combination of P and Q to check equivalence.
Tautologies and Contradictions
Definition and Examples
Tautology: A formula is a tautology if it is always true regardless of the truth values of its atomic propositions. Example: ¬P ∨ Q ↔ (P ⇒ Q).
Contradiction: A formula that is always false, e.g. P ∧ ¬P.
Law of Excluded Middle: This principle states that for any proposition P, either P is true or ¬P is true.
Additional Formulations
More Complex Examples
Example: (P ∧ Q) ∨ ¬P ⇒ (Q ↔ True)
Formulated as: ((P ∧ Q) ∨ ¬P) ⇒ (Q ↔ True)
Example Analysis (P ∧ Q) ⇒ R ↔ P ⇒ (Q ⇒ R)
Use truth tables to verify equivalence and tautologies.
Conclusion on Logical Frameworks
We have covered the essential principles and structure of logical propositions, including their operations and implications in both propositional and Boolean logic.
Next Lecture
Focusing on practical reasoning using truth tables.
Discussion of Modus Ponens (MP) and Modus Tollens (MT).