Unit 1: Mathematical Logic
1.1 Statements (Propositions) and Notations
A statement or proposition is a declarative sentence that is either true (T) or false (F), but not both.
- Examples of statements:
- "Silchar is in Assam." (True)
- "2 + 2 = 5." (False)
- Examples of non-statements:
- "What time is it?" (Question)
- "Close the door." (Command)
- "x + 1 = 3." (This is a predicate, not a statement, as its truth value depends on x.)
Notations: We use lowercase letters like p, q, r, ... to represent propositions.
1.2 Connectives (Logical Operators)
Connectives are used to combine simple propositions into compound propositions.
| Operator | Name | Symbol | Meaning |
|---|
| Negation | NOT | ¬ p (or p') | "It is not the case that p." |
| Conjunction | AND | p \land q | "p and q" |
| Disjunction | OR | p \lor q | "p or q" (inclusive) |
| Implication | IF...THEN | p \to q | "If p, then q." (p is hypothesis, q is conclusion) |
| Biconditional | IF AND ONLY IF | p ≤ftrightarrow q | "p if and only if q" |
Truth Tables for Connectives
| p | q | ¬ p | p \land q | p \lor q | p \to q | p ≤ftrightarrow q |
|---|
| T | T | F | T | T | T | T |
| T | F | F | F | T | F | F |
| F | T | T | F | T | T | F |
| F | F | T | F | F | T | T |
Common Mistake: The implication p \to q is only false when the hypothesis (p) is true and the conclusion (q) is false. If the hypothesis is false, the implication is always true ("false implies anything").
A normal form is a standard way of writing a logical expression. This is crucial for simplifying and comparing propositions.
- Tautology: A compound proposition that is always true, regardless of the truth values of its variables. (e.g., p \lor ¬ p)
- Contradiction: A compound proposition that is always false. (e.g., p \land ¬ p)
- Contingency: A proposition that is neither a tautology nor a contradiction.
Disjunctive Normal Form (DNF)
A formula is in DNF if it is a sum of minterms (a disjunction of conjunctions). A Principal DNF (PDNF) is a DNF where each conjunction (minterm) contains every variable or its negation exactly once.
Example: (p \land q \land ¬ r) \lor (¬ p \land q \land r) is in PDNF.
Conjunctive Normal Form (CNF)
A formula is in CNF if it is a product of maxterms (a conjunction of disjunctions). A Principal CNF (PCNF) is a CNF where each disjunction (maxterm) contains every variable or its negation exactly once.
Example: (p \lor q \lor ¬ r) \land (¬ p \lor q \lor r) is in PCNF.
1.4 Logical Equivalences
Two propositions P and Q are logically equivalent (written P ≡ Q or P ⇔ Q) if they have the same truth table. That is, P ≤ftrightarrow Q is a tautology.
Important Equivalences (Laws)
- De Morgan's Laws:
- ¬ (p \land q) ≡ ¬ p \lor ¬ q
- ¬ (p \lor q) ≡ ¬ p \land ¬ q
- Commutative Laws: p \land q ≡ q \land p; p \lor q ≡ q \lor p
- Associative Laws: (p \land q) \land r ≡ p \land (q \land r); (p \lor q) \lor r ≡ p \lor (q \lor r)
- Distributive Laws: p \land (q \lor r) ≡ (p \land q) \lor (p \land r); p \lor (q \land r) ≡ (p \lor q) \land (p \lor r)
- Implication Equivalence: p \to q ≡ ¬ p \lor q
- Contrapositive: p \to q ≡ ¬ q \to ¬ p
1.5 Predicate Calculus
Propositional logic is limited. We cannot, for example, express "All men are mortal." We need predicates and quantifiers.
A predicate is a property or relation that a variable or set of variables can have. It becomes a proposition when the variables are assigned specific values from a domain of discourse.
Example: Let P(x) be the predicate "x > 3." The domain is the set of integers.
- P(4) is the proposition "4 > 3" (True).
- P(2) is the proposition "2 > 3" (False).
1.6 Quantifiers
Quantifiers turn predicates into propositions by specifying "how many" variables satisfy the predicate.
Universal Quantifier (∀)
- Symbol: ∀ (read "for all" or "for every")
- Usage: ∀ x P(x) is the proposition "For all x in the domain, P(x) is true."
- Example: ∀ x (x2 ≥ 0) (assuming the domain is real numbers).
Existential Quantifier (∃)
- Symbol: ∃ (read "there exists" or "for some")
- Usage: ∃ x P(x) is the proposition "There exists at least one x in the domain such that P(x) is true."
- Example: ∃ x (x2 = 4) (domain of real numbers).
Negating Quantifiers (De Morgan's Laws for Quantifiers)
- ¬ (∀ x P(x)) ≡ ∃ x ¬ P(x) ("Not all x are P" is the same as "There exists an x that is not P.")
- ¬ (∃ x P(x)) ≡ ∀ x ¬ P(x) ("There does not exist an x that is P" is the same as "All x are not P.")
1.7 Inference Theory of the Predicate Calculus
Inference theory deals with determining the validity of an argument. An argument is a sequence of propositions (premises) that lead to another proposition (conclusion). An argument is valid if the conclusion is true whenever all the premises are true.
Rules of Inference for Propositional Logic
| Rule Name | Premises | Conclusion |
|---|
| Modus Ponens | p
p \to q | ∴ q |
| Modus Tollens | ¬ q
p \to q | ∴ ¬ p |
| Hypothetical Syllogism | p \to q
q \to r | ∴ p \to r |
| Disjunctive Syllogism | p \lor q
¬ p | ∴ q |
| Addition | p | ∴ p \lor q |
| Simplification | p \land q | ∴ p |
Inference Rules for Quantified Statements
- Universal Instantiation (UI): From ∀ x P(x), we can conclude P(c) for any specific c in the domain.
- Universal Generalization (UG): If P(c) is true for an arbitrary c from the domain, we can conclude ∀ x P(x).
- Existential Instantiation (EI): From ∃ x P(x), we can conclude P(c) for some new constant c (we give it a name).
- Existential Generalization (EG): If P(c) is true for some specific c, we can conclude ∃ x P(x).
How to prove an argument is valid: Start with the premises. Use the rules of inference and logical equivalences to derive new propositions. If you can derive the conclusion, the argument is valid.