Chapter 14 — Mathematical Reasoning

What is a statement (proposition)? A statement is a sentence that is either true (T) or false (F), but not both. Examples: "7 is prime" (T), "2+2=5" (F). Sentences that cannot be assigned a definite truth value (like questions, commands, or expressions with unspecified variables) are not statements.

Open statements vs closed statements: An open statement (or predicate) contains variables and becomes a statement only after the variables are given specific values or a domain and quantifier. Example: "x > 2" is open; with x = 5 it is true, with x = 1 it is false.

Truth values: Every statement has a truth value: True (T) or False (F). Truth values are the basic data used in constructing compound statements via logical connectives.

Logical connectives (building compound statements):

• Negation (NOT, ¬p): reverses the truth value — if p is T, ¬p is F, and vice versa.
• Conjunction (AND, p ∧ q): true only when both p and q are true; otherwise false.
• Disjunction (OR, p ∨ q): true when at least one of p or q is true (inclusive OR).
• Implication (IF...THEN, p → q): false only when p is true and q is false; otherwise true. (Interprets "if p then q".)
• Biconditional (IF AND ONLY IF, p ↔ q): true when p and q have the same truth value (both true or both false).

Truth tables: We use truth tables to list truth values of compound statements for all combinations of component truth values. Truth tables make it easy to check logical equivalences, find tautologies (always true), contradictions (always false), and contingent statements (sometimes true).

Important logical equivalences: De Morgan's laws, double negation, implication rewrite, and distributive/associative laws are used frequently:

• ¬(p ∧ q) ≡ ¬p ∨ ¬q
• ¬(p ∨ q) ≡ ¬p ∧ ¬q
• p → q ≡ ¬p ∨ q
• p ↔ q ≡ (p → q) ∧ (q → p)

Why this matters: Understanding statements and truth values is the foundation of mathematical reasoning, proofs, and precise expression of conditions in algebra, calculus, and problem solving. It also models everyday conditional thinking (if this, then that) and decision logic in computing.

Logical connectives are operators that join simple (atomic) statements to build compound statements. The basic connectives are negation, conjunction, disjunction, implication and biconditional. A compound statement's truth value is determined by the truth values of its components and the connectives used.

Symbols and meaning:

• Negation: ¬p (not p). True when p is false.
• Conjunction: p ∧ q (p and q). True when both p and q are true.
• Disjunction: p ∨ q (p or q). True when at least one of p, q is true. (Inclusive OR)
• Exclusive OR: p ⊕ q. True when exactly one of p, q is true.
• Implication: p → q (if p then q). False only when p is true and q is false.
• Biconditional: p ↔ q (p if and only if q). True when p and q have the same truth value.

Truth table for two propositions p and q:

Important ideas:

• Precedence (order) of connectives: ¬ (highest), ∧, ∨, →, ↔ (lowest). Use parentheses to avoid ambiguity.
• Tautology: a compound statement always true (e.g., p ∨ ¬p).
• Contradiction: always false (e.g., p ∧ ¬p).
• Contingent statement: sometimes true, sometimes false depending on component truth values.

Useful equivalences (used for simplification and proofs):

• De Morgan's laws: ¬(p ∧ q) ≡ ¬p ∨ ¬q, and ¬(p ∨ q) ≡ ¬p ∧ ¬q.
• Implication equivalence: p → q ≡ ¬p ∨ q.
• Contrapositive: p → q ≡ ¬q → ¬p.
• Biconditional: p ↔ q ≡ (p → q) ∧ (q → p) ≡ (p ∧ q) ∨ (¬p ∧ ¬q).
• Exclusive OR: p ⊕ q ≡ (p ∨ q) ∧ ¬(p ∧ q) ≡ (p ∧ ¬q) ∨ (¬p ∧ q).

How to evaluate compound statements:

1. Identify simple propositions and assign truth values.
2. Use parentheses and precedence to parse the compound statement.
3. Build a truth table (2^n rows for n distinct propositions) or evaluate step-by-step using known equivalences.

Applications: logical connectives underpin mathematical proofs, digital circuits (logic gates), programming conditionals, and everyday rules/permissions that combine conditions.

Implication (Conditional): A statement of the form p → q reads if p then q (p is antecedent, q is consequent). It is false only when p is true and q is false; otherwise it is true. This includes the case of vacuous truth when p is false.

Truth table (p → q):

p    q    p → q
T    T      T
T    F      F
F    T      T
F    F      T

Variants:

• Converse: q → p. Not generally equivalent to p → q.
• Inverse: ¬p → ¬q. Not generally equivalent to p → q.
• Contrapositive: ¬q → ¬p. Logically equivalent to p → q (always true together).
• Biconditional: p ↔ q means (p → q) ∧ (q → p). Read as p if and only if q (necessary and sufficient condition).

Necessary and sufficient conditions:

• p is sufficient for q means p → q.
• q is necessary for p means p → q (equivalently, if not q then not p).
• Both necessary and sufficient means p ↔ q.

Useful logical equivalences and forms:

• p → q is equivalent to ¬p ∨ q.
• p → q is equivalent to ¬(p ∧ ¬q).
• p → q is equivalent to its contrapositive ¬q → ¬p.
• p ↔ q is equivalent to (p → q) ∧ (q → p) and also to (p ∧ q) ∨ (¬p ∧ ¬q).

Proof strategies using variants: Direct proof tries to show p → q. Proof by contrapositive shows ¬q → ¬p (often easier). Demonstrating both directions establishes equivalence p ↔ q.

What is logical equivalence? Two compound statements A and B are logically equivalent (written A ≡ B or A <> B) if they have the same truth value for every possible truth assignment of their basic propositions. Equivalence means each implies the other: A <=> B iff (A → B) ∧ (B → A).

How to prove equivalence: (1) construct truth tables for A and B and check identical columns; (2) use standard logical laws and algebraic transformations to rewrite one into the other.

Important idea — implications and contrapositive: An implication p → q is equivalent to its contrapositive ¬q → ¬p. But it is not generally equivalent to its converse q → p.

Why this matters: Logical equivalences allow simplification of statements, proofs, and digital circuits (e.g., replacing expressions by simpler or more convenient equivalent forms). They also help negate complex statements correctly.

Standard laws (categories):

• Basic/identity laws: p ∨ F ≡ p, p ∧ T ≡ p.
• Domination (null) laws: p ∨ T ≡ T, p ∧ F ≡ F.
• Idempotent: p ∨ p ≡ p, p ∧ p ≡ p.
• Commutative: p ∨ q ≡ q ∨ p, p ∧ q ≡ q ∧ p.
• Associative: (p ∨ q) ∨ r ≡ p ∨ (q ∨ r), similarly for ∧.
• Distributive: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r), and p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r).
• De Morgan's laws: ¬(p ∧ q) ≡ (¬p) ∨ (¬q), ¬(p ∨ q) ≡ (¬p) ∧ (¬q).
• Double negation: ¬(¬p) ≡ p.
• Absorption: p ∨ (p ∧ q) ≡ p, p ∧ (p ∨ q) ≡ p.
• Complement: p ∨ ¬p ≡ T, p ∧ ¬p ≡ F.
• Implication equivalence: p → q ≡ (¬p) ∨ q; p → q ≡ ¬q → ¬p (contrapositive).
• Biconditional: p ↔ q ≡ (p → q) ∧ (q → p) ≡ (p ∧ q) ∨ (¬p ∧ ¬q).

Using equivalences in proofs and simplification: You replace parts of a formula by equivalent parts step by step (like algebra). For negating quantified statements the same laws apply: ¬(for all x, P(x)) ≡ there exists x, ¬P(x) and vice versa.

Note on truth tables vs algebraic laws: Truth tables are exhaustive and foolproof for a small number of variables; algebraic laws are convenient for symbolic simplification and reasoning for larger expressions.

Predicate: A predicate is a statement (property or relation) that contains one or more variables and becomes a proposition (true/false) only when specific values from a domain are substituted for the variables. We write a predicate on variable x as P(x). Example: P(x): "x is even". For x=4 the predicate is true; for x=5 it is false.

Predicates with two or more variables represent relations, e.g., R(x,y): "x is greater than y". For ordered pair (3,1) R(3,1) is true.

Domain (Universe of discourse): The set of all possible values that the variables can take. Always state the domain when using quantifiers (e.g., integers, natural numbers, students in a class).

Bound and free variables: A variable is bound if it appears within the scope of a quantifier (e.g., ∀x P(x)). A variable is free if it is not bound; a formula with free variables is not a proposition until the free variables are given values.

Quantifiers:

• Universal quantifier: ∀ ("for all" or "every"). ∀x P(x) means P(x) is true for every x in the domain.
• Existential quantifier: ∃ ("there exists" or "for some"). ∃x P(x) means there is at least one x in the domain for which P(x) is true.

Negation rules (De Morgan for quantifiers):

• ¬(∀x P(x)) ≡ ∃x ¬P(x) — "It is not true that P holds for all x" means "There exists an x for which P is false."
• ¬(∃x P(x)) ≡ ∀x ¬P(x) — "There does not exist an x such that P holds" means "P is false for every x."

Order of quantifiers matters. For two-variable predicates P(x,y): ∀x ∃y P(x,y) is generally not equivalent to ∃y ∀x P(x,y). Example: "For every person x there exists a person y whom x knows" vs "There exists a person y whom everyone knows."

Unique existence: ∃!x P(x) means there exists exactly one x such that P(x) is true. Formally: ∃x (P(x) ∧ ∀y (P(y) → y=x)).

Translating natural language: Practice turning statements into symbolic form and back. Always specify the domain and be careful about scope and connectives.

Overview. Mathematical reasoning turns statements into logically valid conclusions. A proof is a sequence of logically connected statements starting from accepted facts (axioms, definitions, previously proved results) and ending with the statement to be shown. CBSE Class 11 focuses on common proof methods: direct proof, proof by contrapositive, proof by contradiction, trivial and vacuous proofs, counterexamples (to disprove), and mathematical induction.

• Direct proof. Assume the hypothesis P is true and use definitions and known results to deduce the conclusion Q. Typical template: P ⇒ (logical steps) ⇒ Q.
• Proof by contrapositive. To prove P ⇒ Q, prove the logically equivalent statement ¬Q ⇒ ¬P. This often simplifies handling negations or divisibility/ parity properties.
• Proof by contradiction (reductio ad absurdum). Assume the statement to be proved is false (or assume the hypothesis plus the negation of the conclusion) and deduce a contradiction (a statement and its negation). Conclude the original statement must be true.
• Trivial and vacuous proofs. If Q is always true then P ⇒ Q is trivially true. If P is always false (e.g., P refers to an impossible condition), then P ⇒ Q is vacuously true.
• Counterexample. To disprove a universal claim “for all x, P(x)”, it suffices to find one x for which P(x) is false.
• Mathematical induction. Used to prove statements indexed by positive integers. Two steps: (i) Base case: prove true for n = 1 (or smallest n). (ii) Inductive step: assume true for n = k and prove for n = k+1. Conclude true for all n ≥ base.

When to use which method. Use direct proof when you can manipulate hypotheses straightforwardly. Use contrapositive when conclusion is a negation or when negating the conclusion leads to easier algebra/ divisibility/ parity reasoning. Use contradiction when an assumption leads to an obvious impossibility (e.g., parity conflicts, irrationality). Use induction for statements about all natural numbers.

Logical facts often used in proofs. p → q is equivalent to ¬p ∨ q; p → q is equivalent to ¬q → ¬p (contrapositive). De Morgan's laws and basic identities for connectives are frequently applied to rewrite statements.

Good proof practice. State assumptions clearly, write each inference with justification (definition, theorem, algebraic step), and conclude explicitly. For contradiction/contrapositive, clearly state what you assume in place of the original statement.

Overview. This topic shows how the ideas of mathematical reasoning (propositions, logical connectives, implication, equivalence, negation, quantifiers and inference rules) are used to model, analyse and solve statements from mathematics and real life. The goal is to translate natural-language claims into precise logical form, manipulate them using the laws of logic, and decide truth, validity or construct proofs.

Key ideas and workflow.

• Translate: convert an English sentence into a symbolic proposition or predicate with a clear domain.
• Classify: identify whether the statement is atomic, compound, universally quantified ("for all"), or existentially quantified ("there exists").
• Manipulate: use logical equivalences (De Morgan, implication equivalence, contrapositive) to simplify or negate the statement.
• Decide or prove: use truth tables, direct proof, contrapositive, or counterexample to establish truth or falsity.
• Use inference rules (Modus Ponens, Modus Tollens, etc.) to derive conclusions from premises.

Practical considerations. When modelling real-life sentences be explicit about domain and hidden assumptions. In everyday language "If A then B" often means "A is a cause of B" or is intended as a biconditional; logic treats it purely as implication (A → B). A true implication does not require biconditionality unless explicitly stated.

Common tasks in exercises.

• Write the symbolic form and its negation (pay attention to quantifiers).
• Construct truth tables or use known equivalences to check tautologies/contradictions.
• Prove implications by direct proof or by proving the contrapositive.
• Find counterexamples to disprove universal statements.
• Apply inference rules to a set of premises to obtain conclusions.

Example strategy (typical exercise): Given a universal statement like "All primes greater than 2 are odd", write P(x): "x is prime and x > 2 implies x is odd" as ∀x [(Prime(x) ∧ x > 2) → Odd(x)]. To negate it you write ∃x [(Prime(x) ∧ x > 2) ∧ ¬Odd(x)] and then look for a counterexample.

Note on proofs. Many number-theory implications are most easily proved by contrapositive (show ¬q → ¬p) or by direct algebraic argument. For propositional logic problems, mechanical tools are truth tables or application of equivalences.