Mathematical logic is the foundational discipline that deals with the formal methods of reasoning. At an elementary level, logic provides the precise rules and techniques required to determine whether a given argument is valid. In computer science and software engineering, logical reasoning is used to verify the correctness of computer programs, prove theorems in algorithm design, analyze computational complexity, and design digital logic circuits. This comprehensive academic reference document provides an exhaustive study of Unit 2, synthesized directly from core university discrete mathematics literature (including Grimaldi, Rosen, and Kolman/Busby/Ross).
2.1 Propositions and Logical Operators
At the core of mathematical logic is the proposition (also called a statement). A proposition is a declarative sentence that evaluates to a definite truth value: it is either True (T or 1) or False (F or 0), but never both simultaneously. This fundamental property is known as the Principle of Bivalence.
- Simple (Primitive) Propositions: Atomic statements containing no logical connectives or sub-propositions. Example: "The integer 2 is a prime number." (True)
- Compound Propositions: Statements formed by combining one or more simple propositions using logical operators (connectives). Example: "The integer 2 is prime and 2 + 3 = 5." (True)
- Non-Propositions: Sentences that do not possess a fixed truth value. These include questions ("What time is it?"), commands ("Read this chapter carefully."), exclamations ("Wow!"), and open sentences containing unassigned variables ("x + 1 = 2"). Self-referential paradoxes such as "This statement is false" (the Epimenides paradox) are also excluded from propositional logic.
Fundamental Logical Connectives
We use lowercase propositional variables (typically p, q, r, s) to represent propositions. These variables are combined using standard logical operators. The table below defines the semantics, symbols, and truth conditions for each primary connective.
Operator Precedence and Bit Operations
When evaluating compound propositions without parentheses, the standard order of operator precedence is: (1) Parentheses, (2) Negation (¬), (3) Conjunction (∧), (4) Disjunction (∨), (5) Implication (→), and (6) Biconditional (↔).
In computer science, propositional logic directly maps to digital logic circuits and bitwise operations. A bit has two possible values: 1 (corresponding to True) and 0 (corresponding to False). Logical connectives correspond directly to hardware logic gates: AND gate (∧), OR gate (∨), XOR gate (⊕), and Inverter/NOT gate (¬).
2.2 Truth Tables and Expression Evaluation
A truth table is a systematic tabular representation that displays all possible combinations of truth values for the atomic propositional variables within a compound expression, along with the resulting truth value of the overall compound statement. If an expression contains n distinct propositional variables, its complete truth table will contain exactly 2n rows.
Master Truth Table of Basic Operators
Evaluating Complex Compound Propositions
To evaluate complex statements systematically, construct intermediate helper columns for component sub-expressions. Below is a fully worked 4-row truth table evaluation for the expression: (p → q) ↔ (¬q → ¬p).
2.3 Tautologies, Contradictions, and Contingencies
Compound propositions are categorized into three distinct classifications based on the truth values appearing in the final column of their truth table:
- Tautology: A compound proposition that is always True (T) for every possible assignment of truth values to its atomic variables. Denoted by T0 or 1. Example: The Law of Excluded Middle, p ∨ ¬p, or the expression evaluated in Section 2.2 above.
- Contradiction (Absurdity): A compound proposition that is always False (F) for all possible truth value assignments. Denoted by F0 or 0. Example: The Law of Non-Contradiction, p ∧ ¬p.
- Contingency: A proposition that is neither a tautology nor a contradiction; its truth value depends on the specific truth values assigned to its variables (its final column contains a mix of T's and F's). Example: p → (q ∧ p).
2.4 Logical Equivalence and Implications
Two compound propositions p and q are said to be logically equivalent, denoted by p ≡ q (or p ↔ q is a tautology), if they have identical truth values for every possible valuation of their propositional variables.
Related Conditional Statements
Starting with a conditional statement p → q, we define three critical related conditional forms:
- Converse: q → p (Reversing hypothesis and conclusion).
- Inverse: ¬p → ¬q (Negating both hypothesis and conclusion).
- Contrapositive: ¬q → ¬p (Reversing and negating both).
Crucial Principle: An implication is always logically equivalent to its contrapositive (p → q ≡ ¬q → ¬p). The converse and inverse are logically equivalent to each other, but never equivalent to the original implication unless the statement is a biconditional.
Master Table of Logical Equivalences (The Laws of Logic)
Verifying Equivalences Algebraically
Instead of constructing cumbersome truth tables (which grow exponentially with more variables), we can establish logical equivalences by applying a step-by-step chain of established laws of logic.
Worked Algebraic Proof 1: Prove that ¬(p → ¬q) ≡ p ∧ q.
Step 1: ¬(p → ¬q)
≡ ¬(¬p ∨ ¬q) [By Implication Equivalence: X → Y ≡ ¬X ∨ Y]
Step 2: ≡ ¬(¬p) ∧ ¬(¬q) [By De Morgan's Law: ¬(X ∨ Y) ≡ ¬X ∧ ¬Y]
Step 3: ≡ p ∧ q [By Double Negation Law: ¬(¬X) ≡ X]
∎ (Hence proved)
Worked Algebraic Proof 2: Prove that (p ∧ q) ∨ (p ∧ ¬q) ≡ p.
Step 1: (p ∧ q) ∨ (p ∧ ¬q)
≡ p ∧ (q ∨ ¬q) [By Distributive Law (factoring out p)]
Step 2: ≡ p ∧ T [By Negation / Inverse Law: q ∨ ¬q ≡ T]
Step 3: ≡ p [By Identity Law: p ∧ T ≡ p]
∎ (Hence proved)
2.5 Predicate Logic and Quantifiers
Propositional logic is limited because it cannot analyze the internal structure of general statements such as "Every computer connected to the university network is secure." To analyze assertions about objects and their properties, we introduce Predicate Logic.
- Predicate (Propositional Function): A statement containing variables, denoted as P(x), where P is the predicate representing a property or relation, and x is the subject variable. Once a specific value is assigned to x from a designated domain, P(x) becomes a proposition with a definite truth value.
- Universe of Discourse (Domain D): The set of all allowable values that can be substituted for the variable x in a propositional function.
- Truth Set: The set of all elements x in the domain D for which P(x) is True, denoted as {x ∈ D | P(x)}.
Universal and Existential Quantifiers
De Morgan's Laws for Quantifiers
When negating quantified expressions, the quantifiers flip across the negation symbol (∀ becomes ∃, and ∃ becomes ∀), and the negation applies directly to the internal predicate:
- ¬(∀x P(x)) ≡ ∃x ¬P(x) — "It is not true that everything has property P" is logically equivalent to "There is something that does not have property P."
- ¬(∃x P(x)) ≡ ∀x ¬P(x) — "It is not true that there exists an object with property P" is logically equivalent to "Every object fails to have property P."
Nested Quantifiers and Order of Quantification
When predicates involve multiple variables, quantifiers are nested. The order of quantification is critically important when different quantifiers are mixed:
- ∀x ∀y P(x, y) ≡ ∀y ∀x P(x, y): Order does not matter for identical universal quantifiers.
- ∃x ∃y P(x, y) ≡ ∃y ∃x P(x, y): Order does not matter for identical existential quantifiers.
- ∀x ∃y P(x, y): For every x, there is some y (where the choice of y can depend on x) such that P(x, y) holds. Example: In real numbers, ∀x ∃y (x + y = 0) is True (choose y = −x).
- ∃y ∀x P(x, y): There is a single, universal y that works simultaneously for every possible x. Example: In real numbers, ∃y ∀x (x + y = 0) is False (no single real number is the additive inverse of all real numbers).
2.6 Rules of Inference and Valid Arguments
An argument is a sequence of propositions called premises (p1, p2, ..., pn) ending with a proposition called the conclusion (q). An argument is valid if the truth of all its premises guarantees the truth of its conclusion; formally, the implication (p1 ∧ p2 ∧ ... ∧ pn) → q must be a tautology. Rules of inference are universally valid argument forms used as elementary building blocks in rigorous mathematical proofs.
Classical Rules of Inference for Propositional Logic
Rules of Inference for Quantified Statements
- Universal Instantiation: If ∀x P(x) is True, then P(c) is True for any specific element c in the domain.
- Universal Generalization: If P(c) is proven True for an arbitrary, non-specific element c in the domain, then ∀x P(x) is True.
- Existential Instantiation: If ∃x P(x) is True, we can conclude that there is some specific element a in the domain such that P(a) is True (where a is a new symbol not previously used in the proof).
- Existential Generalization: If P(c) is known to be True for some specific element c, then ∃x P(x) is True.
Common Logical Fallacies (Errors in Reasoning)
- Fallacy of Affirming the Conclusion: Assuming that [(p → q) ∧ q] → p is a valid argument. (e.g., "If you study hard, you pass. You passed. Therefore, you studied hard." — Invalid, as you might have passed by guessing).
- Fallacy of Denying the Hypothesis: Assuming that [(p → q) ∧ ¬p] → ¬q is a valid argument. (e.g., "If it rains, the grass is wet. It is not raining. Therefore, the grass is not wet." — Invalid, as a sprinkler might be running).
- Begging the Question (Circular Reasoning): A fallacy where one or more steps of a proof are based on the truth of the very statement being proved.
2.7 Mathematical Reasoning and Proof Techniques
A theorem is a mathematical statement that has been proven true. To prove theorems of the universal conditional form ∀x (P(x) → Q(x)), we employ several standard proof methods.
1. Direct Proof
Assume the hypothesis P(x) is True for an arbitrary element x. Use axioms, definitions, and previously proven theorems to construct a logical chain of implications showing that the conclusion Q(x) must also be True.
Theorem: If n is an odd integer, then n2 is an odd integer.
Proof:
1. Assume n is an arbitrary odd integer.
2. By definition of odd integers, there exists an integer k such that n = 2k + 1.
3. Squaring both sides gives:
n2 = (2k + 1)2
= 4k2 + 4k + 1
= 2(2k2 + 2k) + 1.
4. Let m = 2k2 + 2k. Since k is an integer, m is an integer (by closure of integers under addition and multiplication).
5. Thus, n2 = 2m + 1, which satisfies the definition of an odd integer.
∎ Therefore, n2 is odd.
2. Indirect Proof (Proof by Contraposition)
Based on the logical equivalence P → Q ≡ ¬Q → ¬P. Assume the conclusion Q(x) is False (¬Q(x) is True), and prove that the hypothesis P(x) must also be False (¬P(x) is True).
Theorem: If 3n + 2 is an odd integer, then n is an odd integer.
Proof (by Contraposition):
1. State the contrapositive: "If n is NOT odd (i.e., n is even), then 3n + 2 is NOT odd (i.e., 3n + 2 is even)."
2. Assume n is an even integer. By definition, n = 2k for some integer k.
3. Substitute n = 2k into the expression:
3n + 2 = 3(2k) + 2
= 6k + 2
= 2(3k + 1).
4. Let m = 3k + 1. Since k is an integer, m is an integer.
5. Thus, 3n + 2 = 2m, which means 3n + 2 is an even integer.
∎ Since the contrapositive is proven true, the original implication holds.
3. Proof by Contradiction (Reductio ad Absurdum)
To prove a proposition P is True, assume that P is False (¬P is True). Use rigorous logical reasoning to deduce an absurdity or logical contradiction of the form R ∧ ¬R ≡ False. Since assuming ¬P leads to a contradiction, ¬P must be False, proving that P is True.
Theorem: The square root of 2 (√2) is an irrational number.
Proof (by Contradiction):
1. Assume the negation: Assume √2 is a rational number.
2. By definition of rationality, there exist integers a and b (with b ≠ 0) such that √2 = a / b, where the fraction is in lowest terms (i.e., gcd(a, b) = 1; a and b share no common prime factors).
3. Squaring both sides gives: 2 = a2 / b2 &implies; a2 = 2b2.
4. This implies that a2 is an even integer. By a known theorem, if a2 is even, then a must be even.
5. Since a is even, let a = 2c for some integer c.
6. Substitute a = 2c into our equation from step 3:
(2c)2 = 2b2 &implies; 4c2 = 2b2 &implies; b2 = 2c2.
7. This implies that b2 is even, which forces b to also be an even integer.
8. Contradiction: We have deduced that both a and b are even integers (meaning they share a common factor of 2). This directly contradicts our initial assumption in step 2 that gcd(a, b) = 1.
∎ Therefore, the assumption that √2 is rational must be false. Hence, √2 is irrational.
4. Proof by Cases (Exhaustion)
When a theorem covers several distinct possibilities, break the domain into a finite number of exhaustive cases (p1 ∨ p2 ∨ ... ∨ pk) and prove that the conclusion holds for each case independently.
Theorem: For every real number x, |x| ≥ x.
Proof (by Cases):
We split the real numbers into two exhaustive cases based on the definition of absolute value:
Case 1: Assume x ≥ 0.
By definition of absolute value, when x ≥ 0, |x| = x.
The inequality |x| ≥ x becomes x ≥ x, which is trivially true.
Case 2: Assume x < 0.
By definition of absolute value, when x < 0, |x| = -x. Since x < 0, its negation -x is strictly positive (-x > 0).
Therefore, |x| > 0. Since x < 0 and |x| > 0, by transitivity we have |x| > x, which satisfies |x| ≥ x.
∎ Since the inequality holds in all possible cases, |x| ≥ x for all real numbers.
5. Existence and Uniqueness Proofs
- Constructive Existence Proof: To prove ∃x P(x), explicitly find or construct a witness element c such that P(c) is True. (Example: Prove there exists an even prime number → witness is c = 2).
- Non-constructive Existence Proof: Prove ∃x P(x) is True using proof by contradiction or counting arguments (such as the Pigeonhole Principle) without explicitly producing the specific witness element.
- Uniqueness Proof: To prove ∃!x P(x) (there exists a unique x such that P(x)), two distinct steps are required:
- Existence: Show that some element c exists where P(c) is True.
- Uniqueness: Assume that two elements y and z both satisfy P(y) and P(z), and algebraically prove that y = z.