Mathematical Reasoning

A mathematical statement (or proposition) is a declarative sentence that is either definitively true or definitively false, but not both simultaneously. The truth or falsity of a statement is called its truth value, denoted by $T$ (true) or $F$ (false).

• "The sum of two odd integers is even." (True statement)
• "$\sqrt{2}$ is a rational number." (False statement)
• "$7 > 5$." (True statement)

• "Close the door." (command, not declarative)
• "What time is it?" (question)
• "$x + 5 = 8$." (open sentence — truth value depends on $x$)
• "May you have a great day." (wish/exclamation)

Open Sentences: A declarative sentence containing one or more variables whose truth value depends on the value(s) assigned to the variable(s). For example, "$x$ is a prime number" is an open sentence — it becomes a statement once $x$ is specified.

• Simple Statement: Cannot be broken down further into simpler component statements. (e.g., "It is raining.")
• Compound Statement: Formed by combining two or more simple statements using logical connectives (e.g., "It is raining AND the road is wet.").

Component Statements: The simple statements making up a compound statement. To analyze a compound statement, identify its component statements and the connectives used.

Notation: Statements are typically denoted by lowercase letters $p, q, r, s, \ldots$

Compound statements are formed using logical connectives (also called logical operators). The five fundamental connectives in propositional logic are:

1. Negation ($\sim p$ or $\neg p$): The opposite truth value of $p$.
$\sim p$ is read as "not $p$" or "it is not the case that $p$". \[ \begin{array}{|c|c|} p & \sim p \\ T & F \\ F & T \\ \end{array} \]

2. Conjunction ($p \wedge q$): "$p$ AND $q$". True only when both $p$ and $q$ are true. \[ \begin{array}{|c|c|c|} p & q & p \wedge q \\ T & T & T \\ T & F & F \\ F & T & F \\ F & F & F \\ \end{array} \]

3. Disjunction ($p \vee q$): "$p$ OR $q$" (inclusive or). False only when both $p$ and $q$ are false. \[ \begin{array}{|c|c|c|} p & q & p \vee q \\ T & T & T \\ T & F & T \\ F & T & T \\ F & F & F \\ \end{array} \]

4. Conditional / Implication ($p \Rightarrow q$): "If $p$ then $q$". False only when $p$ is true and $q$ is false. \[ \begin{array}{|c|c|c|} p & q & p \Rightarrow q \\ T & T & T \\ T & F & F \\ F & T & T \\ F & F & T \\ \end{array} \] $p$ is called the antecedent (or hypothesis); $q$ is the consequent (or conclusion). The rows with $p$ false are called vacuously true.

5. Biconditional ($p \Leftrightarrow q$): "$p$ if and only if $q$" (often abbreviated "$p$ iff $q$"). True when $p$ and $q$ have the same truth value. \[ \begin{array}{|c|c|c|} p & q & p \Leftrightarrow q \\ T & T & T \\ T & F & F \\ F & T & F \\ F & F & T \\ \end{array} \]

• $p \Leftrightarrow q \equiv (p \Rightarrow q) \wedge (q \Rightarrow p)$
• $p \Rightarrow q \equiv \sim p \vee q$ (Material implication)
• Double negation: $\sim(\sim p) \equiv p$

• Tautology: A compound statement that is always true regardless of truth values of components. E.g., $p \vee \sim p$.
• Contradiction (Fallacy): Always false. E.g., $p \wedge \sim p$.
• Contingency: Sometimes true and sometimes false. Most compound statements are contingencies.

Two compound statements $P$ and $Q$ are logically equivalent, written $P \equiv Q$, if they have the same truth value for every assignment of truth values to their atomic components. Equivalently, $P \Leftrightarrow Q$ is a tautology.

Important Logical Equivalences (Laws of Logic):

Idempotent Laws: \[ p \vee p \equiv p, \quad p \wedge p \equiv p \]

Commutative Laws: \[ p \vee q \equiv q \vee p, \quad p \wedge q \equiv q \wedge p \]

Associative Laws: \[ (p \vee q) \vee r \equiv p \vee (q \vee r), \quad (p \wedge q) \wedge r \equiv p \wedge (q \wedge r) \]

Distributive Laws: \[ p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r) \] \[ p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r) \]

Identity Laws (where $\mathbf{T}$ is any tautology and $\mathbf{F}$ is any contradiction): \[ p \vee \mathbf{F} \equiv p, \quad p \wedge \mathbf{T} \equiv p \] \[ p \vee \mathbf{T} \equiv \mathbf{T}, \quad p \wedge \mathbf{F} \equiv \mathbf{F} \]

Complement (Negation) Laws: \[ p \vee \sim p \equiv \mathbf{T}, \quad p \wedge \sim p \equiv \mathbf{F} \] \[ \sim(\sim p) \equiv p \quad \text{(Double negation)} \]

De Morgan's Laws (Critical for JEE): \[ \sim(p \wedge q) \equiv \sim p \vee \sim q \] \[ \sim(p \vee q) \equiv \sim p \wedge \sim q \]

Negation of Conditional: \[ \sim(p \Rightarrow q) \equiv p \wedge \sim q \] This is derived because $p \Rightarrow q \equiv \sim p \vee q$, and by De Morgan's: $\sim(\sim p \vee q) \equiv p \wedge \sim q$.

Negation of Biconditional: \[ \sim(p \Leftrightarrow q) \equiv (p \wedge \sim q) \vee (\sim p \wedge q) \] (Which means "exactly one of $p, q$ is true" — the XOR operation.)

Absorption Laws: \[ p \vee (p \wedge q) \equiv p, \quad p \wedge (p \vee q) \equiv p \]

Given a conditional statement $p \Rightarrow q$, we can form three related conditional statements:

Converse: $q \Rightarrow p$
(Switches the antecedent and consequent.)

Inverse: $\sim p \Rightarrow \sim q$
(Negates both the antecedent and consequent, keeping the order.)

Contrapositive: $\sim q \Rightarrow \sim p$
(Negates both AND switches them.)

Crucial Logical Equivalences: \[ p \Rightarrow q \equiv \sim q \Rightarrow \sim p \quad \text{(Original is equivalent to its contrapositive)} \] \[ q \Rightarrow p \equiv \sim p \Rightarrow \sim q \quad \text{(Converse is equivalent to inverse)} \]

However: \[ p \Rightarrow q \not\equiv q \Rightarrow p \quad \text{(Original NOT equivalent to converse, in general)} \] \[ p \Rightarrow q \not\equiv \sim p \Rightarrow \sim q \quad \text{(Original NOT equivalent to inverse, in general)} \]

Verification table: \[ \begin{array}{|c|c|c|c|c|c|c|c|} p & q & \sim p & \sim q & p \Rightarrow q & q \Rightarrow p & \sim p \Rightarrow \sim q & \sim q \Rightarrow \sim p \\ T & T & F & F & T & T & T & T \\ T & F & F & T & F & T & T & F \\ F & T & T & F & T & F & F & T \\ F & F & T & T & T & T & T & T \\ \end{array} \] Columns 5 and 8 match (original $\equiv$ contrapositive). Columns 6 and 7 match (converse $\equiv$ inverse).

• $p$ is a sufficient condition for $q$. (If you have $p$, you're guaranteed $q$.)
• $q$ is a necessary condition for $p$. (You can't have $p$ without $q$.)

Importance in Theorems: Many mathematical theorems are biconditionals. To prove $p \Leftrightarrow q$, one must prove both $p \Rightarrow q$ and $q \Rightarrow p$.
An alternative to proving $p \Rightarrow q$ directly is to prove its contrapositive $\sim q \Rightarrow \sim p$. This is the basis of proof by contrapositive.

A quantifier is a word or phrase that indicates the quantity or range of objects to which a statement applies. In mathematical logic, there are two fundamental quantifiers.

Universal Quantifier ($\forall$): "for all", "for every", "for each".
$\forall x \in S, P(x)$ means "for every element $x$ in $S$, the property $P(x)$ holds."
Example: $\forall n \in \mathbb{N}, n + 1 > n$.

Existential Quantifier ($\exists$): "there exists", "for some", "for at least one".
$\exists x \in S, P(x)$ means "there exists at least one $x$ in $S$ such that $P(x)$ holds."
Example: $\exists n \in \mathbb{N}, n^2 = 25$ (namely $n = 5$).

Negation of Quantified Statements (Critical Rules): \[ \sim(\forall x, P(x)) \equiv \exists x, \sim P(x) \] \[ \sim(\exists x, P(x)) \equiv \forall x, \sim P(x) \]

• The negation of "All $x$ satisfy $P$" is "There exists an $x$ that does not satisfy $P$".
• The negation of "Some $x$ satisfies $P$" is "Every $x$ fails to satisfy $P$".

Combining Quantifiers: A statement may have multiple quantifiers, and the order matters!
$\forall x \exists y P(x, y)$ is generally NOT equivalent to $\exists y \forall x P(x, y)$.

Example: "For every real number $x$, there exists a real number $y$ such that $y > x$." (True)
But: "There exists a real number $y$ such that for every real number $x$, $y > x$." (False — no universal upper bound exists.)

Negation of Multiple Quantifiers:
To negate, flip each quantifier and negate the innermost statement: \[ \sim(\forall x \exists y P(x, y)) \equiv \exists x \forall y \sim P(x, y) \] \[ \sim(\exists x \forall y P(x, y)) \equiv \forall x \exists y \sim P(x, y) \]

• "All triangles have three sides" $= \forall t \in T, \text{sides}(t) = 3$.
• "Some real numbers are negative" $= \exists r \in \mathbb{R}, r < 0$.
• "No prime is even except 2" $= \forall p \in \text{Primes}, (p = 2 \vee p \neq \text{even})$.

A proof is a logical argument that establishes the truth of a mathematical statement using axioms, definitions, and previously proven results. Several proof techniques are essential for JEE:

1. Direct Proof: To prove $p \Rightarrow q$, assume $p$ is true, then deduce $q$ through a chain of logical implications.
Example: "If $n$ is odd, then $n^2$ is odd."
Assume $n = 2k + 1$. Then $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$, which is odd. \checkmark

2. Proof by Contrapositive: To prove $p \Rightarrow q$, instead prove $\sim q \Rightarrow \sim p$, which is logically equivalent.
Useful when: The contrapositive is easier to manipulate. (E.g., when negating $q$ produces a more concrete algebraic condition.)

3. Proof by Contradiction (Reductio ad Absurdum): To prove $p$, assume $\sim p$ is true and derive a contradiction. Since $\sim p$ leads to a contradiction, $\sim p$ must be false, so $p$ is true.
Classic Example: Prove $\sqrt{2}$ is irrational. Assume $\sqrt{2} = p/q$ in lowest terms. Squaring: $2q^2 = p^2$, so $p^2$ is even, hence $p$ is even. Write $p = 2m$; then $2q^2 = 4m^2 \implies q^2 = 2m^2$, so $q$ is also even — contradicting the assumption that $p/q$ was in lowest terms. Therefore $\sqrt{2}$ is irrational.

• Case 1: $n$ is even. Then $n^2$ is even, and even + even = even.
• Case 2: $n$ is odd. Then $n^2$ is odd, and odd + odd = even.

• Base Case: Prove $P(n_0)$.
• Inductive Step: Assume $P(k)$ holds for some arbitrary $k \geq n_0$ (Inductive Hypothesis). Prove $P(k + 1)$.

6. Counterexample: To disprove a universal statement $\forall x, P(x)$, provide a single $x$ for which $P(x)$ fails.
Example: "Every prime is odd" is disproved by the counterexample $p = 2$.

• Modus Ponens: From $p \Rightarrow q$ and $p$, infer $q$.
• Modus Tollens: From $p \Rightarrow q$ and $\sim q$, infer $\sim p$.
• Hypothetical Syllogism: From $p \Rightarrow q$ and $q \Rightarrow r$, infer $p \Rightarrow r$.
• Disjunctive Syllogism: From $p \vee q$ and $\sim p$, infer $q$.

An argument is a sequence of statements (premises) followed by a statement (conclusion). The argument is valid if the truth of the premises guarantees the truth of the conclusion. Symbolically, if premises are $P_1, P_2, \ldots, P_n$ and conclusion is $C$, then validity requires: \[ (P_1 \wedge P_2 \wedge \cdots \wedge P_n) \Rightarrow C \quad \text{is a tautology} \]

Key Rules of Inference:

1. Modus Ponens (Affirming the Antecedent): \[ \frac{p \Rightarrow q, \; p}{\therefore q} \]

2. Modus Tollens (Denying the Consequent): \[ \frac{p \Rightarrow q, \; \sim q}{\therefore \sim p} \]

3. Hypothetical Syllogism (Chain Rule): \[ \frac{p \Rightarrow q, \; q \Rightarrow r}{\therefore p \Rightarrow r} \]

4. Disjunctive Syllogism: \[ \frac{p \vee q, \; \sim p}{\therefore q} \]

5. Constructive Dilemma: \[ \frac{(p \Rightarrow q) \wedge (r \Rightarrow s), \; p \vee r}{\therefore q \vee s} \]

6. Simplification: \[ \frac{p \wedge q}{\therefore p} \]

7. Conjunction: \[ \frac{p, \; q}{\therefore p \wedge q} \]

8. Addition: \[ \frac{p}{\therefore p \vee q} \]

Common Fallacies (Invalid Argument Forms):

Fallacy of Affirming the Consequent (Converse Fallacy): \[ \frac{p \Rightarrow q, \; q}{\therefore p} \quad \text{(INVALID)} \]

Fallacy of Denying the Antecedent (Inverse Fallacy): \[ \frac{p \Rightarrow q, \; \sim p}{\therefore \sim q} \quad \text{(INVALID)} \]

Checking Argument Validity Using Truth Tables: Construct a truth table for all premises and the conclusion. Look for rows where all premises are true. If the conclusion is also true in every such row, the argument is valid.

Validity vs. Soundness: An argument is valid if the conclusion logically follows from the premises (regardless of whether premises are true). It is sound if it is valid AND all premises are actually true.

Logic and Boolean algebra are equivalent algebraic systems. Each logical statement corresponds to a Boolean expression, where: \[ \text{TRUE} \longleftrightarrow 1, \quad \text{FALSE} \longleftrightarrow 0 \] \[ p \wedge q \longleftrightarrow p \cdot q \text{ (AND/multiplication)} \] \[ p \vee q \longleftrightarrow p + q \text{ (OR/addition with } 1 + 1 = 1\text{)} \] \[ \sim p \longleftrightarrow p' \text{ or } \bar{p} \text{ (NOT/complementation)} \]

• Idempotent: $p \cdot p = p$, $p + p = p$
• Absorption: $p + (p \cdot q) = p$, $p \cdot (p + q) = p$
• De Morgan: $(p \cdot q)' = p' + q'$, $(p + q)' = p' \cdot q'$
• Complement: $p \cdot p' = 0$, $p + p' = 1$

• Series Configuration (current flows iff BOTH switches are closed): Models AND ($p \wedge q$ or $p \cdot q$).
• Parallel Configuration (current flows iff AT LEAST ONE switch is closed): Models OR ($p \vee q$ or $p + q$).

A complex switching circuit is equivalent to a Boolean expression, and minimizing the circuit corresponds to simplifying the Boolean expression using algebraic identities (or methods like Karnaugh maps in computer engineering).

• Logic gates in computers (AND, OR, NOT, NAND, NOR, XOR).
• Truth tables for combinational circuits.
• Simplifying networks of relays.

Exclusive OR (XOR): The Boolean function $p \oplus q$ outputs 1 iff exactly one of $p, q$ is 1. \[ p \oplus q = (p \cdot q') + (p' \cdot q) = \sim(p \Leftrightarrow q) \]

NAND and NOR Gates: The functions NAND $= \sim(p \wedge q)$ and NOR $= \sim(p \vee q)$ are called functionally complete — any logical function can be expressed using only NAND gates or only NOR gates.