Unit I: Mathematical Logic
Course: Discrete Mathematics
Code: CADSC102
Statements and Notations
Mathematical logic begins with the concept of a statement (or proposition). A statement is a declarative sentence that is either true or false, but not both.
Notations
- Propositions are usually denoted by lowercase letters such as p, q, r, s.
- The truth value of a statement is denoted by T (True) or F (False).
Connectives
Connectives are used to combine simple statements into compound statements.
| Connective | Symbol | Name | Condition for Truth |
|---|---|---|---|
| NOT | ~ or ¬ | Negation | True if the original statement is false. |
| AND | ^ | Conjunction | True only if both statements are true. |
| OR | v | Disjunction | True if at least one statement is true. |
| If...then | → | Conditional | False only if the first is true and the second is false. | ↔ | Bi-conditional | True if both statements have the same truth value. |
Equivalences and Normal Forms
Logical Equivalences
Two statements are logically equivalent if they have the same truth value in every possible scenario. This is denoted by the symbol ≡.
Normal Forms
Normal forms are standardized ways of representing logical expressions.
- Disjunctive Normal Form (DNF): A sum of products (e.g., (p ^ q) v (~p ^ r)).
- Conjunctive Normal Form (CNF): A product of sums (e.g., (p v q) ^ (~p v r)).
Predicate Calculus and Quantifiers
Predicate calculus extends propositional logic to include variables and quantifiers.
Predicate: A property or relation assigned to objects in a domain (e.g., P(x) where x is an integer).
Quantifiers
- Universal Quantifier (∀): Read as "For all x". It means the property is true for every element in the domain.
- Existential Quantifier (∃): Read as "There exists an x". It means the property is true for at least one element in the domain.
Inference Theory
Inference theory provides the rules for mathematical reasoning and for arriving at logical conclusions from given premises.
- Modus Ponens: If p and (p → q) are true, then q is true.
- Modus Tollens: If ~q and (p → q) are true, then ~p is true.
Exam Focus & Tips
- Exam Tip: Practice constructing truth tables for complex expressions like (p ^ q) → (r v ~p).
- Common Mistake: Confusing "Inclusive OR" (standard v) with "Exclusive OR". In logic, "p v q" is true if both are true.
- Mnemonic: ∀ looks like an upside-down "A" for All. ∃ looks like a backward "E" for Exists.
Frequently Asked Questions
Q: What is a Tautology?
A: A compound statement that is always true, regardless of the truth values of its individual parts.
Q: What is a Contradiction?
A: A statement that is always false.