| Classwise Concept with Examples | ||||||
|---|---|---|---|---|---|---|
| 6th | 7th | 8th | 9th | 10th | 11th | 12th |
Chapter 14 Mathematical Reasoning (Concepts)
Welcome to the fascinating realm of Mathematical Reasoning, a chapter dedicated to understanding the very foundations upon which rigorous mathematical arguments are built. Unlike other chapters that might focus on calculation or specific geometric properties, this section delves into the principles of logic that allow us to construct valid proofs, determine the truth or falsity of mathematical assertions, and communicate mathematical ideas with precision and clarity. Mastering these principles is essential for anyone seeking a deeper understanding of how mathematical knowledge is established and validated, moving beyond intuition to structured, deductive thought.
At the heart of mathematical reasoning lies the concept of a statement or proposition. A statement is defined as a declarative sentence that possesses a definite truth value: it must be unambiguously either true or false, but critically, not both simultaneously. Sentences that are questions ("Is it raining?"), commands ("Close the door."), exclamations ("What a beautiful day!"), or ambiguous declarations ("Mathematics is difficult.") are not considered logical statements in this context because their truth value cannot be definitively assigned. Examples of valid statements include "New Delhi is the capital of India" (True) or "$2 + 2 = 5$" (False).
We then explore how simple statements can be combined or modified using logical operations or connectives to form compound statements. The primary connectives are:
- Negation: Represented by $\neg p$ (or $\sim p$), read as "not $p$". The negation of a statement $p$ has the opposite truth value of $p$. If $p$ is true, $\neg p$ is false, and vice versa.
- Conjunction: Represented by $p \land q$, read as "$p$ and $q$". The conjunction $p \land q$ is true if and only if both statement $p$ and statement $q$ are true. Otherwise, it is false.
- Disjunction: Represented by $p \lor q$, read as "$p$ or $q$". The disjunction $p \lor q$ is true if at least one of the statements $p$ or $q$ is true (including the case where both are true). It is false only when both $p$ and $q$ are false. This is the inclusive 'or'.
A particularly crucial logical structure is the implication or conditional statement, typically expressed in the form "if $p$, then $q$", and symbolically written as $p \Rightarrow q$. Here, $p$ is called the hypothesis (or antecedent) and $q$ is the conclusion (or consequent). The implication $p \Rightarrow q$ is considered false only in the specific case where the hypothesis $p$ is true, but the conclusion $q$ is false. In all other cases, it is true. Associated with an implication $p \Rightarrow q$ are three other conditional statements:
- Converse: $q \Rightarrow p$
- Inverse: $\neg p \Rightarrow \neg q$
- Contrapositive: $\neg q \Rightarrow \neg p$
Statements often involve variables ranging over a set. To handle these, we introduce Quantifiers:
- The Universal Quantifier ($\forall$): Read as "for all", "for every", or "for any". A statement like $\forall x, P(x)$ asserts that the property $P(x)$ is true for every element $x$ in the considered domain.
- The Existential Quantifier ($\exists$): Read as "there exists", "for some", or "there is at least one". A statement like $\exists x, P(x)$ asserts that there is at least one element $x$ in the domain for which the property $P(x)$ is true.
Finally, the chapter outlines fundamental methods for validating statements, primarily focusing on proof techniques:
- Direct Proof: Assuming the hypothesis is true and logically deducing the conclusion.
- Proof by Contrapositive: Proving the equivalent contrapositive statement instead of the original implication.
- Proof by Contradiction: Assuming the statement to be proved is false and deriving a logical contradiction, thereby establishing the original statement must be true.
- Disproof by Counterexample: Demonstrating that a universally quantified statement ($\forall x, P(x)$) is false by finding just one specific example (a counterexample) for which $P(x)$ is false.
Propositions
Logic is fundamentally the science of reasoning. Historically, the study of logic was developed to identify fallacies (illogical patterns of reasoning) and to construct sound arguments. While Aristotle was a pioneer in this field, the English mathematician George Boole (1815–1864) was the first to apply mathematical methods to logic, leading to what is now known as Boolean Logic.
Classification of Verbal Expressions
To understand logic, we must first categorize how we communicate. Every sound we make is an utterance, but only specific types of sentences qualify as mathematical statements.
1. Utterance
An utterance is the broadest category. it includes any sound or verbal expression, even if it lacks meaning or structure. For example, sounds like "Bleep-blorp-zip" or "Abra-ca-dabra" are utterances.
2. Sentence
A sentence is an utterance that carries a specific meaning. However, not all sentences are useful in mathematical logic. Sentences include:
• Interrogative: "Is the Taj Mahal in Agra?" (A question)
• Imperative: "Please finish your homework." (A request or command)
• Exclamatory: "What a brilliant century by Virat Kohli!" (An expression of emotion)
• Optative: "May you have a prosperous Diwali." (A wish)
3. Proposition (Mathematical Statement)
A Proposition is a declarative sentence that is either definitely true or definitely false, but never both at once. This absolute nature is governed by the Law of the Excluded Middle, which states there is no middle ground between truth and falsehood.
Truth Values
Every proposition is assigned a truth value. By convention, we use the following notation:
• If a statement is true, its truth value is T (True).
• If a statement is false, its truth value is F (False).
Examples of Propositions:
1. $p:$ "The sum of $15$ and $25$ is $40$." (Truth Value: T)
2. $q:$ "A triangle has four sides." (Truth Value: F)
3. $r:$ "$\sqrt{2}$ is an irrational number." (Truth Value: T)
Sentences that are NOT Propositions
The most common trap is identifying sentences that seem like statements but are not. These are excluded from mathematical logic for specific reasons:
1. Subjective or Relative Sentences
Sentences that depend on personal opinion or varying standards are not propositions. What is "easy" for one student might be "hard" for another.
Example: "Mathematics is an interesting subject." (Non-proposition; interest is subjective).
Example: "Mumbai is a very crowded city." (Non-proposition; "crowded" is a relative term).
2. Time-Dependent Sentences
Sentences involving specific markers of time like today, yesterday, or tomorrow are excluded because their truth value changes with the passage of time.
Example: "It is a rainy day today." (The truth depends on the date the sentence is read).
3. Unspecified Referents (Pronouns and Places)
If a sentence uses pronouns without identifying the person, or vague locations, it cannot be a proposition.
Example: "He is the Prime Minister of India." (Who is 'He'? Without a name, we cannot determine the truth).
Example: "It is very cold there." (Where is 'there'?).
4. Open Sentences vs. Identities
An Open Sentence contains a variable and its truth value depends on the value assigned to that variable.
Example: $x + 10 = 15$ (If $x=5$ it is True, if $x=2$ it is False. Thus, it is not a proposition).
However, an Algebraic Identity is a proposition because it holds true for all possible values in its domain.
Example: $(a + b)^2 = a^2 + 2ab + b^2$ (This is a proposition with Truth Value: T).
Summary Table of Examples
| Sentence | Type/Reason | Is it a Proposition? |
|---|---|---|
| "Where do you live?" | Interrogative | No |
| "The Ganges flows into the Bay of Bengal." | Fact | Yes (T) |
| "Lucknow is the capital of Uttar Pradesh." | Fact | Yes (T) |
| "$\sin^2 \theta + \cos^2 \theta = 1$" | Trigonometric Identity | Yes (T) |
| "$x - 5 = 12$" | Open Sentence | No |
| "$\textsf{₹} 100$ is a lot of money." | Subjective | No |
Example 1. Identify which of the following sentences are propositions and state their truth values:
(i) All squares are rectangles.
(ii) $\pi$ is a rational number.
(iii) $x + 5 > 10$.
(iv) Indira Gandhi was the first woman President of India.
(v) The sum of any two odd integers is an even integer.
(vi) $x^2 + 1 = 0$ has no real roots.
(vii) $\textsf{₹} 500 + \textsf{₹} 200 = \textsf{₹} 800$.
(viii) Mathematics is the most interesting subject in school.
(ix) Every set is a finite set.
(x) Look at the blackboard.
(xi) $\sin^2 \theta + \cos^2 \theta = 1$ for all $\theta$.
(xii) Tomorrow is a national holiday in India.
(xiii) $2$ is the only even prime number.
(xiv) He is an expert in Vedic Mathematics.
Answer:
(i) Proposition: Yes. It is a mathematically proven fact. Truth Value: T.
(ii) Proposition: Yes. It is a sentence that can be proven false. Truth Value: F (since $\pi$ is irrational).
(iii) Proposition: No. This is an open sentence. We cannot determine its truth without knowing the value of $x$.
(iv) Proposition: Yes. It is a historical claim. Truth Value: F (Indira Gandhi was the first woman Prime Minister, while Pratibha Patil was the first woman President of India).
(v) Proposition: Yes. It is a universal mathematical property. Truth Value: T.
(vi) Proposition: Yes. Since the square of any real number is non-negative, $x^2 + 1$ is always $\geq 1$. Truth Value: T.
(vii) Proposition: Yes. It is an arithmetic calculation. Truth Value: F (since the sum is $\textsf{₹} 700$).
(viii) Proposition: No. The term "interesting" is subjective and varies from person to person.
(ix) Proposition: Yes. It is a mathematical statement. Truth Value: F (as there exist infinite sets like the set of Natural numbers $\mathbb{N}$).
(x) Proposition: No. This is an imperative sentence (a command).
(xi) Proposition: Yes. This is a Trigonometric Identity, which holds true regardless of the value of $\theta$. Truth Value: T.
(xii) Proposition: No. Sentences containing time-relative words like "tomorrow" change their truth value daily.
(xiii) Proposition: Yes. By the definition of prime numbers, $2$ is the smallest and only even prime. Truth Value: T.
(xiv) Proposition: No. The pronoun "He" is an unspecified referent; we do not know who is being discussed.
Negation of a Statement
The negation of a statement is defined as the assertion that the original statement is false. It is essentially the "denial" of the statement. In mathematical logic, negation is a unary operation or a modifier because it acts upon a single proposition rather than connecting two or more.
Notation and Basic Phrasing
If $p$ is a statement, then its negation is denoted by the symbol $\sim p$ (read as 'not $p$'). Other commonly used notations include $\neg p$, $p'$, or $\bar{p}$.
There are several standard ways to construct the negation of a given statement in English:
• By inserting the word "not" at the appropriate place.
• By prefixing the statement with "It is false that...".
• By prefixing the statement with "It is not the case that...".
Example:
Let $p$: "The rupee is the currency of India."
Then $\sim p$ can be written as:
1. The rupee is not the currency of India.
2. It is false that the rupee is the currency of India.
Negation of Mathematical Symbols
In mathematical contexts, the negation of specific symbols must be handled carefully to account for all logical possibilities (the law of the excluded middle).
| Original Symbol | Negated Symbol |
|---|---|
| $=$ (Equal to) | $\neq$ (Not equal to) |
| $>$ (Greater than) | $\leq$ (Less than or equal to) |
| $<$ (Less than) | $\geq$ (Greater than or equal to) |
| $\in$ (Belongs to) | $\notin$ (Does not belong to) |
Negation of Quantified Statements
Statements containing quantifiers like "All", "Every", and "Some" are often negated incorrectly in common speech. In logic, we follow specific rules:
1. Universal Quantifier (All / Every)
The negation of "All $X$ are $Y$" is "Not all $X$ are $Y$" or "There exists at least one $X$ which is not $Y$".
Formula: $\sim (\forall x, P(x)) \equiv \exists x, \sim P(x)$
2. Existential Quantifier (Some / There exists)
The negation of "Some $X$ are $Y$" or "There exists an $X$ such that $Y$" is "No $X$ is $Y$" or "All $X$ are not $Y$".
Formula: $\sim (\exists x, P(x)) \equiv \forall x, \sim P(x)$
Truth Table and Truth Value
The logical essence of negation is that it reverses the truth value. If a statement is true, its negation must be false, and vice versa.
$\sim(\sim p) = p$
…(i)
The truth table for negation is represented below:
| $p$ | $\sim p$ |
|---|---|
| $T$ | $F$ |
| $F$ | $T$ |
Example 1. Write the negation of the following propositions and find their truth values:
(a) $p$: Every prime number is an odd integer.
(b) $q$: $15 + 10 = 30$.
(c) $r$: There exists a real number $x$ such that $x^2 = -1$.
(d) $s$: The cost of the book is $\textsf{₹} 500$.
Answer:
(a) $\sim p$: There exists at least one prime number which is not an odd integer (or, Some prime numbers are even).
Explanation: Since $2$ is an even prime, $p$ is False, so $\sim p$ is True (T).
(b) $\sim q$: $15 + 10 \neq 30$ (or, It is false that $15 + 10 = 30$).
Explanation: Since $25 \neq 30$, the original statement $q$ is False, making $\sim q$ True (T).
(c) $\sim r$: For all real numbers $x$, $x^2 \neq -1$ (or, No real number $x$ satisfies $x^2 = -1$).
Explanation: Since the square of any real number is non-negative, $r$ is False, making $\sim r$ True (T).
(d) $\sim s$: The cost of the book is not $\textsf{₹} 500$.
Explanation: The truth value depends on the actual price of the book.
Example 2. Negate the following statement: "All Indian cities are clean and well-planned."
Answer:
The given statement contains a universal quantifier ("All") and a conjunction ("and"). According to De Morgan's Laws of logic:
Negation: "There exists at least one Indian city that is not clean or is not well-planned."
Compound Statements
In mathematical logic, just as complex numbers are built from real and imaginary parts, complex logical structures are built from simpler ones. We categorize statements based on their complexity and their ability to be decomposed into smaller units of meaning.
Simple Statements
A simple statement is a proposition that cannot be broken down into two or more smaller statements. It represents a single, atomic fact or assertion. In a simple statement, there is usually only one subject and one predicate related to a single idea.
Examples of Simple Statements:
1. $p:$ Mumbai is the financial capital of India.
2. $q:$ Every prime number greater than $2$ is odd.
3. $r:$ The cost of the ledger is $\textsf{₹} 450$.
Compound Statements
A compound statement is a statement that is formed by combining two or more simple statements using logical connectives. The words used to combine these statements (such as "and", "or", "if-then", "either-or") are called logical constants or connectives.
Component Statements
The individual simple statements that make up a compound statement are known as its component statements. When analyzing a compound statement, the first step is often to identify these building blocks.
Examples of Compound Statements:
1. Statement: The sun rises in the east and sets in the west.
$\bullet$ Component 1: The sun rises in the east.
$\bullet$ Component 2: The sun sets in the west.
2. Statement: Either Jaipur is in Rajasthan or it is in Gujarat.
$\bullet$ Component 1: Jaipur is in Rajasthan.
$\bullet$ Component 2: Jaipur is in Gujarat.
Comparison Table
| Feature | Simple Statement | Compound Statement |
|---|---|---|
| Decomposition | Cannot be broken down further. | Can be split into component statements. |
| Connectives | Does not contain logical connectives. | Uses connectives like "and", "or", etc. |
| Example | $\sqrt{3}$ is irrational. | $\sqrt{3}$ is irrational and $2$ is even. |
Example 1. Identify the component statements of the following compound statements and the connectives used:
(a) Zero is a positive number or a negative number.
(b) $121$ is a perfect square and it is an odd number.
(c) If a triangle is equilateral, then it is equiangular.
Answer:
(a) Analysis:
$\bullet$ Component 1 ($p$): Zero is a positive number.
$\bullet$ Component 2 ($q$): Zero is a negative number.
$\bullet$ Connective: or
(b) Analysis:
$\bullet$ Component 1 ($p$): $121$ is a perfect square.
$\bullet$ Component 2 ($q$): $121$ is an odd number.
$\bullet$ Connective: and
(c) Analysis:
$\bullet$ Component 1 ($p$): A triangle is equilateral.
$\bullet$ Component 2 ($q$): A triangle is equiangular.
$\bullet$ Connective: If...then
Example 2. Form a compound statement using the following simple statements and the connective "and":
$p:$ The total bill is $\textsf{₹} 1,200$.
$q:$ The payment was made via UPI.
Answer:
The compound statement formed by connecting $p$ and $q$ with "and" is:
"The total bill is $\textsf{₹} 1,200$ and the payment was made via UPI."
Logical Connectives and Quantifiers
In mathematics, we often combine simple statements to form more complex ones. Just as arithmetic uses operations like addition ($+$) and multiplication ($\times$), and set theory uses union ($\cup$) and intersection ($\cap$), mathematical reasoning employs Logical Connectives. These connectives allow us to evaluate the truth value of compound propositions based on their individual components.
Conjunction (The Connective 'And')
A Conjunction is a type of compound statement formed by joining two or more simple (atomic) statements using the logical operator "and". In the realm of mathematical logic, this operator is highly restrictive, requiring absolute truth from all its parts to remain valid.
Symbolism and Notation
If $p$ and $q$ are two component statements, their conjunction is written symbolically as $p \land q$. This is read as "p and q" or "the conjunction of p and q".
The individual statements $p$ and $q$ are referred to as conjuncts. It is important to note the Commutative Property of conjunction: the order of the conjuncts does not change the truth value of the compound statement. Therefore:
$p \land q \equiv q \land p$
Linguistic Nuances: Disguised Conjunctions
In standard English, we often avoid using the word "and" repeatedly to prevent sounding monotonous. However, logically, several other words perform the exact same function as a conjunction. These words indicate that both facts are being asserted simultaneously.
| Connective Word | Logical Function | Example from Indian Context |
|---|---|---|
| But / Yet | Indicates contrast but asserts both. | The train was late, but Arjun reached the office. |
| Although | Shows concession. | The item costs $\textsf{₹} 2,000$, although it is on sale. |
| Moreover / Also | Adds additional information. | The smartphone has a great camera, moreover it is affordable. |
| While | Shows simultaneous facts. | The GDP is rising, while inflation is controlled. |
The "Non-Connective" Use of 'And'
One must be careful not to assume that every appearance of the word "and" creates a compound statement. In certain sentences, "and" serves to describe a relationship between two objects rather than joining two independent thoughts. Such sentences are Simple Statements.
Example: "Lines $L_1$ and $L_2$ are parallel."
This cannot be broken into "Line $L_1$ is parallel" and "Line $L_2$ is parallel" because the concept of being "parallel" requires at least two entities to exist together. Thus, it remains a single atomic unit of logic.
Truth Value and Truth Table
The truth value of a conjunction is determined by the "Strength of Truth" rule. A conjunction is like a chain; it is only as strong as its weakest link. If even one component is False ($F$), the entire compound statement collapses into Falsehood.
| $p$ | $q$ | $p \land q$ |
|---|---|---|
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ |
| $F$ | $T$ | $F$ |
| $F$ | $F$ | $F$ |
Conclusion: $p \land q$ is True if and only if (iff) $p$ is True AND $q$ is True.
Example 1. Identify the component statements and find the truth value of: "$49$ is a perfect square and $3$ is a root of the equation $x^2 - 9 = 0$."
Answer:
Step 1: Identification of Components
$p$: $49$ is a perfect square.
$q$: $3$ is a root of the equation $x^2 - 9 = 0$.
Step 2: Evaluating Truth Values
For $p$: Since $7^2 = 49$, the statement $p$ is True (T).
For $q$: Substituting $x = 3$ in $x^2 - 9$:
$3^2 - 9 = 9 - 9 = 0$.
Since it satisfies the equation, $q$ is also True (T).
Step 3: Logical Result
Since both $p$ and $q$ are True, the compound statement $p \land q$ is True (T).
Example 2. Write the component statements and check the validity of: "The capital of Gujarat is Ahmedabad and the value of $\sqrt{4}$ is $\pm 2$."
Answer:
Components:
$p$: The capital of Gujarat is Ahmedabad.
$q$: The value of $\sqrt{4}$ is $\pm 2$.
Analysis:
1. The capital of Gujarat is Gandhinagar, not Ahmedabad. Therefore, $p$ is False (F).
2. In mathematics, the principal square root $\sqrt{4}$ is defined as $2$ (positive). Thus, $q$ is False (F).
Result:
Since both components are False, the compound statement is False (F).
Example 3. Form a compound statement using the following components and the 'But' connective, then find its truth value:
$r$: The cost of the book is $\textsf{₹} 850$.
$s$: $850$ is a prime number.
Answer:
Compound Statement: "The cost of the book is $\textsf{₹} 850$, but $850$ is a prime number."
Truth Value Check:
$\bullet$ Let's assume the first part $r$ is True based on the context of the book.
$\bullet$ For the second part $s$: Since $850$ ends in $0$, it is divisible by $2, 5,$ and $10$. Hence, it is not prime. $s$ is False (F).
Conclusion: Since one component is False, the entire statement is False (F).
Disjunction (The Connective 'Or')
A Disjunction is a compound statement formed by connecting two or more simple statements using the logical connective "or". In the language of logic, while a conjunction is restrictive, a disjunction is permissive; it requires only one of its components to be true for the entire statement to be valid.
Symbolism and Disjuncts
If $p$ and $q$ are two simple statements, their disjunction is represented symbolically as $p \lor q$ (read as "p or q"). The individual statements $p$ and $q$ that constitute the compound statement are called disjuncts.
Similar to conjunction, disjunction also follows the Commutative Law, meaning the order of the statements does not affect the logical outcome:
$p \lor q \equiv q \lor p$
Inclusive vs. Exclusive 'Or'
In ordinary English, the word "or" can be used in two distinct ways. Distinguishing between them is vital for mathematical accuracy.
1. Inclusive 'Or'
In this form, the statement is true if the first part is true, the second part is true, or both are true. In mathematics and most competitive exams, "or" is assumed to be inclusive unless stated otherwise.
Example: "To open a bank account in India, you must provide your Aadhaar Card or your PAN Card." (You can provide both, and the condition is still satisfied).
2. Exclusive 'Or'
In this form, the statement is true if exactly one part is true, but not both. It excludes the possibility of both events occurring simultaneously.
Example: "A person is either dead or alive." (A person cannot be both simultaneously).
Example: "The total bill is $\textsf{₹} 500$ or $\textsf{₹} 600$." (The bill can only be one specific amount).
Truth Value and Truth Table
The truth value of a disjunction $p \lor q$ is False (F) only when both component statements $p$ and $q$ are false. In all other scenarios (one true or both true), the compound statement remains true.
| $p$ | $q$ | $p \lor q$ |
|---|---|---|
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $T$ |
| $F$ | $T$ | $T$ |
| $F$ | $F$ | $F$ |
Example 1. Identify the component statements and determine if the "or" used is inclusive or exclusive: "Students can take Sanskrit or French as their third language."
Answer:
Component Statements:
$p$: Students can take Sanskrit as their third language.
$q$: Students can take French as their third language.
Nature of 'Or':
In most school systems, a student chooses only one language from the available options. Since a student cannot take both as a single choice for the same slot, the "or" used here is Exclusive.
Example 2. Find the truth value of the compound statement: "The square of an integer is positive or $\sqrt{9} = -3$."
Answer:
Step 1: Evaluate Component $p$
$p$: The square of an integer is positive.
Wait! If we consider the integer $0$, then $0^2 = 0$, which is neither positive nor negative. Therefore, the universal claim that the square of an integer (any integer) is positive is False (F).
Step 2: Evaluate Component $q$
$q$: $\sqrt{9} = -3$.
By mathematical convention, the principal square root $\sqrt{x}$ is always non-negative. Thus, $\sqrt{9} = 3$. Statement $q$ is False (F).
Step 3: Final Logical Value
Since both $p$ and $q$ are False ($F \lor F$), the entire compound statement is False (F).
Example 3. Check the truth value of the following: "$\textsf{₹} 1 = 100 \text{ Paise}$ or $2 + 2 = 5$."
Answer:
Analysis:
$\bullet$ Component 1 ($p$): $\textsf{₹} 1 = 100 \text{ Paise}$. This is True (T).
$\bullet$ Component 2 ($q$): $2 + 2 = 5$. This is False (F).
Result:
In a disjunction, if at least one component is true, the compound statement is true. Since $p$ is true, the truth value is True (T).
Negation of Compound Statements (De Morgan's Laws)
The negation of a compound statement involves a systematic transformation of its component statements and its logical connectives. The most fundamental rules governing these transformations are known as De Morgan's Laws, named after the British mathematician Augustus De Morgan. These laws describe how the negation of a conjunction or disjunction results in the swapping of the connectives 'and' and 'or'.
1. Negation of Conjunction (p ∧ q)
The negation of a conjunction states that it is false that both $p$ and $q$ are true. This is equivalent to saying that at least one of the component statements must be false. Mathematically, the negation of "p and q" is "not p or not q".
$\sim (p \land q) \equiv \sim p \lor \sim q$
Proof via Truth Table
We can prove this equivalence by comparing the truth values of $\sim (p \land q)$ and $\sim p \lor \sim q$ for all possible combinations of $p$ and $q$.
| $p$ | $q$ | $p \land q$ | $\sim (p \land q)$ | $\sim p$ | $\sim q$ | $\sim p \lor \sim q$ |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F |
| T | F | F | T | F | T | T |
| F | T | F | T | T | F | T |
| F | F | F | T | T | T | T |
Since the columns for $\sim (p \land q)$ and $\sim p \lor \sim q$ are identical, the law is verified.
2. Negation of Disjunction (p ∨ q)
The negation of a disjunction states that it is false that at least one of $p$ or $q$ is true. This is equivalent to asserting that both components are false. Mathematically, the negation of "p or q" is "not p and not q".
$\sim (p \lor q) \equiv \sim p \land \sim q$
Proof via Truth Table
Below is the truth table verification for the negation of a disjunction:
| $p$ | $q$ | $p \lor q$ | $\sim (p \lor q)$ | $\sim p$ | $\sim q$ | $\sim p \land \sim q$ |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F |
| T | F | T | F | F | T | F |
| F | T | T | F | T | F | F |
| F | F | F | T | T | T | T |
The identical nature of the 4th and 7th columns proves the identity $\sim (p \lor q) \equiv \sim p \land \sim q$.
Summary Rule
To negate a compound statement involving "and" or "or":
1. Negate each component statement.
2. Change "and" ($\land$) to "or" ($\lor$).
3. Change "or" ($\lor$) to "and" ($\land$).
Example 1. Write the negation of the following compound statement:
"The number $2$ is prime and the number $3$ is even."
Answer:
Step 1: Identify components
$p$: The number $2$ is prime.
$q$: The number $3$ is even.
Step 2: Apply De Morgan's Law
The given statement is $(p \land q)$. Its negation is $(\sim p \lor \sim q)$.
Negated Statement: "The number $2$ is not prime or the number $3$ is not even."
Example 2. Negate the statement: "Either the stock price is $\textsf{₹} 1,500$ or the dividend is $\textsf{₹} 50$."
Answer:
Step 1: Identify components
$p$: The stock price is $\textsf{₹} 1,500$.
$q$: The dividend is $\textsf{₹} 50$.
Step 2: Apply De Morgan's Law
The given statement is $(p \lor q)$. Its negation is $(\sim p \land \sim q)$.
Negated Statement: "The stock price is not $\textsf{₹} 1,500$ and the dividend is not $\textsf{₹} 50$."
Example 3. Find the negation of the mathematical statement: "$x + y = 10$ and $x - y < 5$."
Answer:
Let $p: x + y = 10$ and $q: x - y < 5$.
The negation is $\sim p \lor \sim q$.
1. Negation of $x + y = 10$ is $x + y \neq 10$.
2. Negation of $x - y < 5$ is $x - y \geq 5$.
Negated Statement: "$x + y \neq 10$ or $x - y \geq 5$."
Quantifiers
In mathematical logic, Quantifiers are symbols or phrases that specify the extent to which a predicate applies to a range of elements. They are used to turn open sentences into propositions by defining the quantity of the domain that satisfies a given property. These are essential for rigorous mathematical proofs.
Types of Quantifiers
There are two fundamental quantifiers used in mathematics, each serving a distinct logical purpose.
1. The Universal Quantifier ($\forall$)
The universal quantifier indicates that a property holds true for every element in a particular set. The symbol $\forall$ is an inverted 'A', standing for 'All'.
Common Phrases: "For all", "For every", "For each", "For any".
Example: $\forall x \in \mathbb{R}, x^2 \geq 0$. (For all real numbers $x$, the square of $x$ is non-negative).
2. The Existential Quantifier ($\exists$)
The existential quantifier indicates that there is at least one element in the set for which the property holds true. The symbol $\exists$ is a reversed 'E', standing for 'Exists'.
Common Phrases: "There exists", "There is at least one", "For some", "For at least one".
Example: $\exists x \in \mathbb{Z}$ such that $x + 5 = 10$. (There exists an integer $x$ such that $x + 5 = 10$).
Summary of Quantifiers
| Quantifier Name | Symbol | Standard Phrasing | Logical Meaning |
|---|---|---|---|
| Universal | $\forall$ | For all $x$... | True for every element in the domain. |
| Existential | $\exists$ | There exists $x$... | True for at least one element in the domain. |
The Importance of the Order of Quantifiers
When a mathematical statement involves more than one quantifier, their order is critical. Changing the order of $\forall$ and $\exists$ can completely transform the truth value and the meaning of the statement.
Consider the domain of positive real numbers $(x, y > 0)$:
Case 1: $\forall x, \exists y$ (Universal followed by Existential)
Statement: "For every positive real number $x$, there exists a positive real number $y$ such that $y < x$."
Analysis: This statement claims that for any number you pick, I can always find a smaller one. This is True. For any $x$, we can choose $y = \frac{x}{2}$.
Case 2: $\exists y, \forall x$ (Existential followed by Universal)
Statement: "There exists a positive real number $y$ such that for every positive real number $x$, we have $y < x$."
Analysis: This statement claims there is one specific positive number $y$ that is smaller than every other positive number. This is False because there is no smallest positive real number.
Negation of Quantified Statements
Negating a quantified statement involves swapping the quantifier and negating the property that follows it.
$\sim [\forall x, P(x)] \equiv \exists x, \sim P(x)$
[Negation of Universal]
$\sim [\exists x, P(x)] \equiv \forall x, \sim P(x)$
[Negation of Existential]
Example 1. Identify the quantifier used in the following statement and find its negation: "There exists a number which is equal to its square."
Answer:
Quantifier: Existential Quantifier ("There exists").
Symbolic form: $\exists x$ such that $x = x^2$.
Negation: "For every number $x$, $x \neq x^2$." (Or: "No number is equal to its square").
Truth Value check: The original statement is True ($0 = 0^2$ and $1 = 1^2$), so the negation is False.
Example 2. Write the negation of the following statement: "For every natural number $n$, $n + 1 > n$."
Answer:
Given Statement: $\forall n \in \mathbb{N}, n + 1 > n$.
Using the rule $\sim [\forall n, P(n)] \equiv \exists n, \sim P(n)$:
Negation: "There exists a natural number $n$ such that $n + 1 \leq n$."
Truth Value check: The original statement is True for all natural numbers, hence the negation is False.
Example 3. Translate the following into symbolic logic: "Every student in the class has a textbook."
Answer:
Let $S$ be the set of students in the class.
Let $T(x)$ be the property "student $x$ has a textbook."
Symbolic Representation: $\forall x \in S, T(x)$.
Implications
In mathematical reasoning, an Implication is a compound statement that expresses a logical relationship between two propositions. The most common form is the Conditional statement, which establishes a dependency where the truth of one statement leads to the truth of another. Unlike conjunction and disjunction, the order of statements in an implication is of paramount importance.
Conditional Statement (p → q)
In the study of logic, the Conditional Statement is perhaps the most vital structure. It represents a contract or a promise between two propositions. If the first part (the condition) is met, then the second part (the result) must follow. This relationship is directional and does not imply that the reverse is true.
Logical Structure: Antecedent and Consequent
A conditional statement is denoted as $p \to q$ (or $p \implies q$). It consists of two distinct parts:
1. Antecedent ($p$): Also called the hypothesis, premise, or sufficient condition. It is the "if" part of the sentence.
2. Consequent ($q$): Also called the conclusion or necessary condition. It is the "then" part of the sentence.
The Non-Commutative Nature
Unlike Conjunction ($p \land q$) or Disjunction ($p \lor q$), which are commutative, the order in a conditional statement is rigid. The statement $p \to q$ is not the same as $q \to p$.
Example: Consider the statement "If a person is in New Delhi, then they are in India."
$\bullet$ Correct ($p \to q$): Being in New Delhi guarantees being in India.
$\bullet$ Incorrect ($q \to p$): Being in India does not guarantee that the person is in New Delhi (they could be in Mumbai or Bengaluru).
Disguised Forms and Linguistic Variations
Conditional statements are often presented in various linguistic forms to test the student's grasp of logic. All the following are equivalent to $p \to q$:
| Form | Logical Meaning |
|---|---|
| $p$ only if $q$ | $p$ cannot happen unless $q$ happens. |
| $q$ if $p$ | The occurrence of $p$ is enough for $q$. |
| $q$ whenever $p$ | Every instance of $p$ is accompanied by $q$. |
| $q$ is necessary for $p$ | Without $q$, $p$ is impossible. |
| $p$ is sufficient for $q$ | $p$ is all you need to guarantee $q$. |
Necessary vs. Sufficient Conditions
Understanding the difference between Necessary and Sufficient conditions is crucial for solving "Statement and Assumption" type questions.
1. Sufficient Condition ($p$)
A condition $p$ is sufficient for $q$ if the truth of $p$ guarantees the truth of $q$.
Example: To get an 'A' grade, scoring above $90\%$ is sufficient. If you score $95\%$, you definitely get the 'A' grade.
2. Necessary Condition ($q$)
A condition $q$ is necessary for $p$ if $p$ cannot be true without $q$ being true.
Example: To sit for the board exam, having an admit card is necessary. While having the card doesn't guarantee you pass, you cannot even take the exam without it.
Analysis of the Truth Table
The truth value of $p \to q$ depends on the truth values of $p$ and $q$. There is only one scenario where the statement is considered False.
| $p$ (Hypothesis) | $q$ (Conclusion) | $p \to q$ (Result) |
|---|---|---|
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ |
| $F$ | $T$ | $T$ |
| $F$ | $F$ | $T$ |
Explanation of the "False" Case ($T \to F$):
This happens when the hypothesis is satisfied, but the promise is broken. If a politician says, "If I am elected, I will reduce the price of petrol to $\textsf{₹} 50$," and they are elected but do not reduce the price, their statement is proven False.
The Concept of Vacuous Truth ($F \to T$ and $F \to F$):
When the hypothesis $p$ is False, the statement $p \to q$ is automatically considered True because the condition was never met to begin with, so the promise cannot be "broken". This is known as a vacuously true statement.
Example 1. Rewrite the following statement in five different equivalent forms: "If a natural number $n$ is divisible by $10$, then it is divisible by $5$."
Answer:
Let $p$: $n$ is divisible by $10$, and $q$: $n$ is divisible by $5$.
The equivalent forms are:
1. $n$ is divisible by $10$ implies $n$ is divisible by $5$.
2. $n$ is divisible by $10$ only if $n$ is divisible by $5$.
3. $n$ is divisible by $10$ is a sufficient condition for $n$ to be divisible by $5$.
4. $n$ being divisible by $5$ is a necessary condition for $n$ to be divisible by $10$.
5. $n$ is divisible by $5$ whenever $n$ is divisible by $10$.
Example 2. Identify the necessary and sufficient conditions in the following implication: "For you to get a discount of $\textsf{₹} 500$, it is sufficient that you purchase items worth $\textsf{₹} 5,000$."
Answer:
In the form "$p$ is sufficient for $q$", the first part is the hypothesis and the second is the conclusion.
Sufficient Condition ($p$): You purchase items worth $\textsf{₹} 5,000$.
Necessary Condition ($q$): You get a discount of $\textsf{₹} 500$.
Explanation: Purchasing for $\textsf{₹} 5,000$ is enough to guarantee the discount. However, it is possible you could get the discount through other means (like a coupon), making the discount the necessary result of that specific purchase.
Converse, Contrapositive, and Biconditional Statements
Beyond the basic conditional statement, there are several logical variations that arise by reordering or negating the components. Understanding these variations is fundamental to mathematical proofs and deductive reasoning.
Converse of a Statement
The Converse of a conditional statement $p \to q$ is formed by interchanging the hypothesis and the conclusion. Symbolically, the converse is represented as $q \to p$.
It is a common logical fallacy to assume that if a statement is true, its converse must also be true. In reality, the truth value of the converse is independent of the original statement.
Example. Write the converse of the following statement and check its truth value: "If a natural number $n$ is divisible by $10$, then it is divisible by $5$."
Answer:
Original ($p \to q$): If $n$ is divisible by $10$, then $n$ is divisible by $5$. (True)
Converse ($q \to p$): "If a natural number $n$ is divisible by $5$, then it is divisible by $10$."
Truth Value: False. For example, the number $15$ is divisible by $5$ but not by $10$.
Contrapositive of a Statement
The Contrapositive of a conditional statement $p \to q$ is formed by negating both component statements and swapping their order. Symbolically, the contrapositive is $\sim q \to \sim p$.
The most important property of the contrapositive is that it is logically equivalent to the original statement. If the statement is True, the contrapositive is True; if the statement is False, the contrapositive is False.
Truth Table Verification
We can prove the logical equivalence of $p \to q$ and $\sim q \to \sim p$ by comparing their truth values:
| $p$ | $q$ | $p \to q$ | $\sim q$ | $\sim p$ | $\sim q \to \sim p$ |
|---|---|---|---|---|---|
| T | T | T | F | F | T |
| T | F | F | T | F | F |
| F | T | T | F | T | T |
| F | F | T | T | T | T |
Example. Write the contrapositive of: "If the total bill is $\textsf{₹} 2,000$, then the delivery is free."
Answer:
Original ($p \to q$): If the total bill is $\textsf{₹} 2,000$, then the delivery is free.
Contrapositive ($\sim q \to \sim p$): "If the delivery is not free, then the total bill is not $\textsf{₹} 2,000$."
Biconditional Statements ("If and only if")
A Biconditional statement is formed when a conditional and its converse are both true. It represents a "two-way" implication. Symbolically, it is denoted as $p \leftrightarrow q$ or $p \iff q$.
The phrasing "if and only if" (abbreviated as iff) indicates that $p$ is a necessary and sufficient condition for $q$.
$p \leftrightarrow q \equiv (p \to q) \land (q \to p)$
Truth Value of Biconditional
A biconditional statement is True only when both component statements have the same truth value. If one is true and the other is false, the biconditional is false.
Example. Rewrite the following as a biconditional statement: "If a triangle is equilateral, all its angles are $60^\circ$; and if all angles of a triangle are $60^\circ$, it is equilateral."
Answer:
This statement consists of $p \to q$ and its converse $q \to p$. It can be rephrased as:
"A triangle is equilateral if and only if all its angles are $60^\circ$."
Summary of Conditional Variations
For any conditional statement $p \to q$, the following variations exist:
| Variation | Symbolic Form | Equivalence |
|---|---|---|
| Original Statement | $p \to q$ | - |
| Converse | $q \to p$ | Equivalent to Inverse |
| Inverse | $\sim p \to \sim q$ | Equivalent to Converse |
| Contrapositive | $\sim q \to \sim p$ | Equivalent to Original |
| Biconditional | $p \leftrightarrow q$ | Original + Converse |
Example. Identify the hypothesis and conclusion, then write the contrapositive: "If $x$ is an even integer, then $x^2$ is divisible by $4$."
Answer:
Hypothesis ($p$): $x$ is an even integer.
Conclusion ($q$): $x^2$ is divisible by $4$.
To Negate:
$\sim q$: $x^2$ is not divisible by $4$
(Negation of conclusion)
$\sim p$: $x$ is not an even integer
(Negation of hypothesis)
Contrapositive Statement: "If $x^2$ is not divisible by $4$, then $x$ is not an even integer."
Hierarchy of Logical Connectivity
Determining necessary and sufficient conditions is key to identifying implications. The following structure summarizes these relationships:
1. Sufficient Condition: The "If" part ($p$). If $p$ occurs, $q$ must follow.
2. Necessary Condition: The "Then" part ($q$). For $p$ to occur, $q$ must be available.
3. Equivalence: When $p$ is both necessary and sufficient for $q$, we have a biconditional relationship ($p \iff q$).
Truth Values of Conditional and Biconditional Statements
Truth Values of Conditional Statements
The truth value of a conditional statement $p \to q$ (If $p$ then $q$) depends entirely on the truth values of its component statements. In mathematical logic, this relationship is often compared to a "logical contract." The contract is only considered broken if the condition ($p$) is fulfilled, but the promise ($q$) is not delivered.
The Truth Table for Conditional ($p \to q$)
A conditional statement is False only in one specific case: when the antecedent is True and the consequent is False. In all other scenarios, the implication is considered True.
| $p$ (Antecedent) | $q$ (Consequent) | $p \to q$ (Implication) |
|---|---|---|
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ |
| $F$ | $T$ | $T$ |
| $F$ | $F$ | $T$ |
Key Observations on Truth Values
1. Valid Implication
A True statement cannot imply a False statement. If the premise is true, the conclusion must also be true for the whole statement to remain valid. For instance:
"If New Delhi is the capital of India, then $\textsf{₹} 1 = 100 \text{ paise}$." ($T \to T$) is True.
2. The Concept of Vacuous Truth
When the antecedent ($p$) is False, the statement $p \to q$ is always True, regardless of the truth value of the consequent ($q$). This is often summarized by the phrase: "Starting with a false premise, you can prove anything."
Examples of statements that are Trivially True due to a false premise:
$\bullet$ If $2 + 2 = 5$, then the Earth is flat. ($F \to F \equiv T$)
$\bullet$ If pigs fly, then $\textsf{₹} 10 = \textsf{₹} 100$. ($F \to F \equiv T$)
3. Independence of Consequent
If the consequent ($q$) is True, the statement $p \to q$ is always True, regardless of whether $p$ is true or false.
Truth Values of Biconditional Statements
A Biconditional Statement ($p \leftrightarrow q$) is essentially the combination of $p \to q$ and $q \to p$. Therefore, it is only True when both $p$ and $q$ have the same truth value.
Comprehensive Truth Table
The following table illustrates the relationship between $p, q$, the conditionals, and the final biconditional value:
| $p$ | $q$ | $p \to q$ | $q \to p$ | $p \leftrightarrow q$ |
|---|---|---|---|---|
| $T$ | $T$ | $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ | $T$ | $F$ |
| $F$ | $T$ | $T$ | $F$ | $F$ |
| $F$ | $F$ | $T$ | $T$ | $T$ |
Example 1. Determine the truth value of the following statements:
(a) If $3 + 3 = 7$, then $5 + 5 = 10$.
(b) If $2 \times 2 = 4$, then Srinagar is in Tamil Nadu.
Answer:
(a) Analysis:
The antecedent $p: 3 + 3 = 7$ is False.
The consequent $q: 5 + 5 = 10$ is True.
Since the antecedent is false, the conditional statement $p \to q$ is True (T).
(b) Analysis:
The antecedent $p: 2 \times 2 = 4$ is True.
The consequent $q:$ Srinagar is in Tamil Nadu is False (Srinagar is in Jammu & Kashmir).
A true statement cannot imply a false one. Thus, $p \to q$ is False (F).
Example 2. Assign the truth value for the biconditional: "$10$ is an even number if and only if $10$ is divisible by $2$."
Answer:
Let $p: 10$ is an even number. (Truth Value: T)
Let $q: 10$ is divisible by $2$. (Truth Value: T)
Since both $p$ and $q$ are True, they have the same truth value.
Solution: The biconditional $p \leftrightarrow q$ is True (T).
Validating Statements
In mathematical reasoning, validation is the formal process of proving whether a given statement is true (valid) or false (invalid). Depending on the logical connectives used—such as "And", "Or", "If-then", or "If and only if"—different strategies and rules are applied to establish proof.
RULE 1: Validating Conjunction (Statements with 'AND')
To validate a compound statement joined by the logical connective 'AND' (symbolically represented as $p \land q$), we must verify the truth of every single component statement. In mathematical logic, a conjunction is considered a strict connective; if even one part of the statement is found to be false, the entire compound statement is invalidated.
General Procedure for Validation
If $r$ is a compound statement such that $r = p \land q$, then to show $r$ is True, we follow these logical steps:
1. Step 1: Isolate the first component statement $p$ and prove its validity independently.
2. Step 2: Isolate the second component statement $q$ and prove its validity independently.
If there are more than two components, every single one must be proven true. The truth value of the conjunction is governed by the following relationship:
$v(p \land q) = \min(v(p), v(q))$
Where $v(p)$ denotes the truth value ($1$ for True, $0$ for False).
Example. Check the validity of the following statement: "$121$ is a perfect square and $121$ is an odd number."
Answer:
Given: A compound statement $r$ connected by "and".
Let the component statements be:
$p: 121$ is a perfect square.
$q: 121$ is an odd number.
Proof:
For statement $p$:
$121 = 11 \times 11 = 11^2$
[Definition of perfect square] ... (i)
Since $121$ is the square of the natural number $11$, statement $p$ is True.
For statement $q$:
$121 = 2 \times 60 + 1$
[Form of $2n+1$] ... (ii)
Since $121$ leaves a remainder of $1$ when divided by $2$, it is an odd number. Thus, statement $q$ is True.
Conclusion: Since both $p$ and $q$ are true, the compound statement $r$ is Valid.
RULE 2: Validating Disjunction (Statements with 'OR')
Validation of an 'OR' statement (symbolically $p \lor q$) is fundamentally different from an 'AND' statement. For a disjunction to be true, it is sufficient that at least one of the component statements is true. In mathematical proofs, especially those involving variables, we often use a method of exhaustion or conditional assumption.
Validation Strategies
There are two primary ways to prove that "$p$ or $q$" is true:
Method 1: Direct Verification
If we can show that $p$ is always true, the truth value of $q$ becomes irrelevant. Similarly, if $q$ is always true, the disjunction is valid regardless of $p$.
Method 2: Conditional Assumption (Proof by Cases)
This is the most rigorous method used in higher mathematics. It involves assuming that one statement is false and then proving that the other must be true to maintain the logic.
Case 1: Assume $p$ is False $\implies$ Show that $q$ must be True.
Case 2: Assume $q$ is False $\implies$ Show that $p$ must be True.
If either of these cases is proven, the statement $p \lor q$ is mathematically validated.
Example. Prove the validity of the statement: "For any real number $x$, $x$ is a rational number or $x$ is an irrational number."
Answer:
To Prove: The statement $r: p \lor q$ is valid.
Where,
$p: x$ is a rational number.
$q: x$ is an irrational number.
Proof:
We use the Method of Conditional Assumption.
Let us assume that statement $p$ is False.
$x \notin \mathbb{Q}$
[Assumption: $x$ is not rational] ... (i)
By the definition of the set of Real Numbers ($\mathbb{R}$):
$\mathbb{R} = \mathbb{Q} \cup \mathbb{Q}^c$
[Union of Rationals and Irrationals]
If $x$ is a real number and $x \notin \mathbb{Q}$, then by the property of complements in the set of real numbers:
$x \in \mathbb{Q}^c$
[Hence $x$ is irrational] ... (ii)
This shows that statement $q$ is true whenever $p$ is false.
Conclusion: The disjunction is Valid.
RULE 3: Validating Implications (If-then Statements)
In mathematical logic, the statement "If $p$, then $q$" (represented as $p \to q$) is a conditional statement. Validating such a statement requires proving that whenever the hypothesis $p$ is true, the conclusion $q$ must also be true. There are three primary methods to establish this validity, along with a specific method to prove invalidity.
1. The Direct Method
In the Direct Method, we start by assuming that the antecedent (hypothesis) $p$ is true. Using established mathematical definitions, axioms, and previously proven theorems, we logically deduce that the consequent (conclusion) $q$ is also true.
Example. Prove that if $n$ is an odd integer, then $n^2$ is also an odd integer using the Direct Method.
Answer:
Given: $n$ is an odd integer.
To Prove: $n^2$ is an odd integer.
Proof:
Since $n$ is an odd integer, it can be written in the form:
$n = 2k + 1$
[where $k$ is some integer] ... (i)
To find the nature of $n^2$, we square both sides of equation (i):
$n^2 = (2k + 1)^2$
Expanding the right side using the identity $(a+b)^2 = a^2 + 2ab + b^2$:
$n^2 = 4k^2 + 4k + 1$
We can factor out $2$ from the first two terms:
$n^2 = 2(2k^2 + 2k) + 1$
Let $m = 2k^2 + 2k$. Since $k$ is an integer, $m$ is also an integer.
$n^2 = 2m + 1$
[Form of an odd integer] ... (ii)
Since $n^2$ is in the form $2m + 1$, it is an odd integer. Thus, the statement is valid.
2. The Contrapositive Method
The Contrapositive Method relies on the logical equivalence between a conditional statement and its contrapositive. Mathematically, $p \to q \equiv \sim q \to \sim p$. To prove "If $p$ then $q$", we instead prove that "If $q$ is false, then $p$ is false."
Example. Prove that for any integer $n$, if $n^2$ is even, then $n$ is even (using Contrapositive Method).
Answer:
Statement: If $n^2$ is even ($p$), then $n$ is even ($q$).
Contrapositive: If $n$ is not even ($\sim q$), then $n^2$ is not even ($\sim p$).
In other words: "If $n$ is odd, then $n^2$ is odd."
Proof:
Let $n$ be an odd integer. Then, $n = 2k + 1$ for some integer $k$.
$n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$.
Since $n^2$ is of the form $2m + 1$, $n^2$ is an odd integer.
Thus, we have shown that $\sim q \implies \sim p$. Since the contrapositive is true, the original statement "If $n^2$ is even, then $n$ is even" is valid.
3. The Contradiction Method
In the Contradiction Method (Reductio ad Absurdum), we assume that the entire statement is false. For $p \to q$ to be false, $p$ must be True and $q$ must be False. We then proceed with this assumption until we reach a mathematical impossibility (a contradiction).
Example. Prove that $\sqrt{2}$ is an irrational number using the Contradiction Method.
Answer:
Assumption: Suppose $\sqrt{2}$ is a rational number.
By definition of rational numbers, we can write:
$\sqrt{2} = \frac{a}{b}$
[where $a, b \in \mathbb{Z}, b \neq 0$ and $\gcd(a, b) = 1$] ... (i)
Squaring both sides of equation (i):
$2 = \frac{a^2}{b^2} \implies a^2 = 2b^2$
... (ii)
This implies $a^2$ is even, which means $a$ must be even. Let $a = 2k$. Substituting this into (ii):
$(2k)^2 = 2b^2 \implies 4k^2 = 2b^2 \implies b^2 = 2k^2$
This implies $b^2$ is even, which means $b$ must be even.
Since both $a$ and $b$ are even, they have a common factor of $2$. This contradicts our initial assumption that $\gcd(a, b) = 1$ (that the fraction is in simplest form).
Therefore, our assumption that $\sqrt{2}$ is rational is false. Thus, $\sqrt{2}$ is irrational.
4. Proving Invalidity: The Counter-Example Method
To prove that a conditional statement $p \to q$ is False, we use the Counter-Example Method. We must find at least one instance where the hypothesis $p$ is satisfied, but the conclusion $q$ is not.
Example. Check the validity of the statement: "If $n$ is a prime number, then $2^n - 1$ is also a prime number."
Answer:
Let us test the statement for different prime numbers $n$:
If $n = 2$ (prime): $2^2 - 1 = 3$ (prime). [True]
If $n = 3$ (prime): $2^3 - 1 = 7$ (prime). [True]
If $n = 5$ (prime): $2^5 - 1 = 31$ (prime). [True]
If $n = 11$ (prime):
$2^{11} - 1 = 2047$
Now, we check if $2047$ is prime. By testing factors:
$2047 = 23 \times 89$
[Composite Number]
Since $n=11$ is prime but $2^{11}-1$ is not prime, we have found a counter-example. Therefore, the original statement is invalid.
RULE 4: Validating Biconditional Statements
A Biconditional Statement, denoted by $p \iff q$, is a compound statement that asserts both $p \implies q$ and $q \implies p$ are true. To validate such a statement, we must perform a two-way proof. It is often phrased as "p if and only if q" or abbreviated as "p iff q".
Logical Requirements for Validation
In order to show that the statement "$p$ if and only if $q$" is true, the following steps must be strictly followed:
Step 1: Prove that "If p is true, then q is true" ($p \implies q$). This is known as the sufficiency part or the "only if" part.
Step 2: Prove that "If q is true, then p is true" ($q \implies p$). This is known as the necessity part or the "if" part.
Only when both implications are validated can we conclude that the biconditional statement is true.
Example. Validate the statement: "An integer $n$ is even if and only if $n^2$ is even."
Answer:
Given: $n \in \mathbb{Z}$.
To Prove: $n$ is even $\iff n^2$ is even.
Step 1: If $n$ is even, then $n^2$ is even ($p \implies q$)
Assume $n$ is an even integer.
$n = 2k$
[where $k$ is an integer] ... (i)
Squaring both sides of equation (i):
$n^2 = (2k)^2$
$n^2 = 4k^2$
$n^2 = 2(2k^2)$
$n^2 = 2m$
[where $m = 2k^2$ is an integer] ... (ii)
Since $n^2$ is a multiple of $2$, it is even. Thus, $p \implies q$ is true.
Step 2: If $n^2$ is even, then $n$ is even ($q \implies p$)
We use the Contrapositive Method to prove this part. We will show that if $n$ is not even (i.e., $n$ is odd), then $n^2$ is not even (i.e., $n^2$ is odd).
Assume $n$ is an odd integer.
$n = 2k + 1$
[where $k$ is an integer] ... (iii)
Squaring both sides of equation (iii):
$n^2 = (2k + 1)^2$
$n^2 = 4k^2 + 4k + 1$
$n^2 = 2(2k^2 + 2k) + 1$
$n^2 = 2j + 1$
[where $j = 2k^2 + 2k$ is an integer] ... (iv)
Since $n^2$ is in the form $2j + 1$, it is odd. Thus, the contrapositive is true, which implies $q \implies p$ is true.
Conclusion: Since both directions are proven, the biconditional statement is valid.
Method of Counter-Example
The Method of Counter-Example is the most effective way to disprove a mathematical statement that claims to be true for all elements in a domain (universal statements). To prove a statement is False, we do not need to show that it fails for every case; we only need to provide one single case where the conditions are met but the conclusion is not.
Logical Foundation
Mathematically, the negation of a universal statement "For all $x$, $P(x)$ is true" is "There exists an $x$ such that $P(x)$ is false."
$\sim [\forall x, P(x)] \equiv \exists x, \sim P(x)$
This single $x$ which makes $P(x)$ false is the counter-example.
Example 1. Check the validity of the statement: "For every prime number $p$, $p + 2$ is also a prime number."
Answer:
To check if this statement is valid, we look for a prime number $p$ such that $p + 2$ is not prime.
$\bullet$ If $p = 3$ (prime), then $p + 2 = 5$ (prime). [True]
$\bullet$ If $p = 5$ (prime), then $p + 2 = 7$ (prime). [True]
$\bullet$ If $p = 7$ (prime), let's calculate $p + 2$:
$p + 2 = 7 + 2 = 9$
Analyzing the number $9$:
$9 = 3 \times 3$
[Composite Number]
Since $9$ is not a prime number, the case $p = 7$ serves as a counter-example.
Conclusion: The statement is invalid (False).
Example 2. Disprove the following statement: "If a quadrilateral has all its angles equal, then it is a square."
Answer:
The statement claims that having four equal angles ($90^\circ$ each) is sufficient to be a square.
Counter-Example: Consider a Rectangle that is not a square.
In a rectangle, all angles are equal to $90^\circ$. However, the sides are not necessarily equal (e.g., length $= 10 \text{ cm}$, breadth $= 5 \text{ cm}$).
Since the condition (equal angles) is met but the conclusion (is a square) is not met, the statement is False.
Summary of Validation Methods
| Statement Type | Validation Goal | Primary Method |
|---|---|---|
| $p$ and $q$ | Show both are True. | Independent verification of $p$ and $q$. |
| $p$ or $q$ | Show at least one is True. | Assume $\sim p$ and prove $q$. |
| If $p$ then $q$ | Show $p$ implies $q$. | Direct, Contrapositive, or Contradiction. |
| $p$ iff $q$ | Show mutual implication. | Two-way proof ($p \to q$ and $q \to p$). |
| Universal Claim | Prove invalidity. | Finding a single Counter-example. |