Logic language

This chapter establishes the fundamental elements of propositional logic, defining key concepts such as statements, negation, implication, and biconditional relationships. A mastery of these principles is critical for developing rigorous mathematical arguments and forms the bedrock for all subsequent proof techniques and logical reasoning assessed in the CMI curriculum.

---

Chapter Contents

|

| Topic |

|---|-------| | 1 | Statements | | 2 | Negation | | 3 | Implication | | 4 | Biconditional | | 5 | Converse | | 6 | Contrapositive |

---

We begin with Statements.

Part 1: Statements

Statements

Overview

A statement is the basic unit of logic. Before handling implication, proof, negation, or quantifiers, one must first know what counts as a statement. In mathematical reasoning, a statement is a sentence that has a definite truth value. CMI-style logic questions often test whether a sentence is a statement, whether it is open or closed, and how statements combine through logical connectives. ---

Learning Objectives

---

Core Definition

---

What Is Not a Statement

---

Truth Values

For example:

• "There are infinitely many prime numbers" is a statement, and it is true.

• "The number $10$ is prime" is a statement, and it is false.

---

Open Sentences and Variables

---

Compound Statements

These are valid only when $P$ and $Q$ themselves are statements. ---

Simple Truth Intuition

---

Mathematical Statements

---

Minimal Worked Examples

Example 1 Is the sentence $\qquad x^2=4$ a statement? No, not by itself. The truth depends on the value of $x$. It is an open sentence, not a statement. --- Example 2 Is the sentence $\qquad \text{There exists } x\in\mathbb{R} \text{ such that } x^2=4$ a statement? Yes. It has a definite truth value, and in fact it is true. ---

Common Patterns

---

Common Mistakes

---

CMI Strategy

---

Practice Questions

:::question type="MCQ" question="Which of the following is a statement?" options=["$x+1=2$","Close the door.","$2+3=5$","What is your name?"] answer="C" hint="Look for a declarative sentence with fixed truth value." solution="The sentence $2+3=5$ is declarative and has a definite truth value, namely true. The others are either open, imperative, or interrogative. Hence the correct option is $\boxed{C}$." ::: :::question type="NAT" question="How many truth values can a statement have?" answer="2" hint="Use the standard logical setup." solution="A statement has exactly one truth value, and the possible truth values are true and false. So the number of possible truth values is $\boxed{2}$." ::: :::question type="MSQ" question="Which of the following are statements?" options=["$7$ is prime","$x>3$","There exists a real number $x$ such that $x^2=2$","Stop talking."] answer="A,C" hint="Check whether the sentence is closed and truth-valued." solution="1. True, this is a statement.

Not a statement by itself, because $x$ is unspecified.

A quantified sentence with definite truth value, so it is a statement.

A command, so not a statement.

Hence the correct answer is $\boxed{A,C}$." ::: :::question type="SUB" question="Explain why '$x$ is even' is not a statement, but 'There exists an integer $x$ such that $x$ is even' is a statement." answer="The first is an open sentence, while the second is quantified and has a definite truth value" hint="Focus on whether the variable is specified or quantified." solution="The expression '$x$ is even' depends on the value of $x$. Since no value of $x$ is given and no quantifier appears, the sentence does not yet have a definite truth value. Hence it is an open sentence, not a statement. On the other hand, 'There exists an integer $x$ such that $x$ is even' is quantified. It now has a definite truth value, and in fact it is true because $x=2$ is even. Therefore it is a statement." ::: ---

Summary

---

---

Part 2: Negation

Negation

Overview

Negation is one of the most basic but most frequently mishandled ideas in logic. In proof-based mathematics, negation is not just the act of inserting the word "not". It means forming a new statement whose truth value is exactly opposite to the original statement. In CMI-style questions, the main difficulty is usually with compound statements and quantified statements, where careless wording leads to logically incorrect negations. ---

Learning Objectives

---

Core Idea

---

Negation of Simple Statements

---

Negation of Compound Statements

These are among the most important laws in logic. ::: ---

Negation of Implication and Biconditional

---

Negation of Quantified Statements

---

Minimal Worked Examples

Example 1 Negate the statement $\qquad x > 2 \text{ and } x < 5$ Using De Morgan's law, $\qquad \lnot(x>2 \land x<5) \iff (x \le 2) \lor (x \ge 5)$ So the negation is $\qquad x \le 2 \text{ or } x \ge 5$ --- Example 2 Negate $\qquad \forall n \in \mathbb{N},\ n^2 \ge n$ Its negation is $\qquad \exists n \in \mathbb{N} \text{ such that } n^2 < n$ ---

Common Patterns

---

Common Mistakes

---

CMI Strategy

---

Practice Questions

:::question type="MCQ" question="The negation of the statement $x>3$ is" options=["$x<3$","$x\le 3$","$x\ge 3$","$x=3$"] answer="B" hint="Include the boundary value." solution="The negation of $x>3$ is every case where $x$ is not greater than $3$, namely $\qquad x \le 3$. Hence the correct option is $\boxed{B}$." ::: :::question type="NAT" question="If $P$ is false, what is the truth value of $\lnot P$? Write $1$ for true and $0$ for false." answer="1" hint="Negation reverses truth value." solution="If $P$ is false, then $\lnot P$ is true. Therefore the required code is $\boxed{1}$." ::: :::question type="MSQ" question="Which of the following are correct negations?" options=["The negation of $x\ge 2$ is $x<2$","The negation of $P\land Q$ is $\lnot P\lor\lnot Q$","The negation of $\forall x\,P(x)$ is $\exists x\,\lnot P(x)$","The negation of $P\implies Q$ is $P\land\lnot Q$"] answer="A,B,C,D" hint="Use the standard negation laws." solution="1. True. Negating $x\ge 2$ gives $x<2$.

True. This is De Morgan's law.

True. Universal negation becomes existential.

True. An implication fails exactly when $P$ is true and $Q$ is false.

Hence the correct answer is $\boxed{A,B,C,D}$." ::: :::question type="SUB" question="Negate the statement: 'For every real number $x$, if $x>1$ then $x^2>1$'." answer="There exists a real number $x$ such that $x>1$ and $x^2\le 1$" hint="Negate the universal quantifier first, then negate the implication." solution="The statement is $\qquad \forall x\in\mathbb{R},\ (x>1 \implies x^2>1)$ Its negation is $\qquad \exists x\in\mathbb{R} \text{ such that } \lnot(x>1 \implies x^2>1)$ Now $\qquad \lnot(P\implies Q) \iff P\land \lnot Q$ So the negation becomes $\qquad \exists x\in\mathbb{R} \text{ such that } x>1 \land x^2 \le 1$ Hence the required negation is $\qquad \boxed{\exists x\in\mathbb{R} \text{ such that } x>1 \text{ and } x^2 \le 1}$" ::: ---

Summary

---

---

Part 3: Implication

Implication

Overview

Implication is one of the central ideas of mathematical logic. Almost every theorem in mathematics has the form "if $P$, then $Q$". To use implications correctly, you must understand their meaning, their truth conditions, and the related ideas of necessary conditions, sufficient conditions, converse, and contrapositive. ---

Learning Objectives

---

Core Idea

Here:

• $P$ is called the hypothesis or antecedent,

• $Q$ is called the conclusion or consequent.

::: ---

Truth of an Implication

This is the most important logical fact about implication. ---

Why the False Case Is Unique

That is exactly the false case. ---

Vacuous Truth

Example: $\qquad \text{If }5>10,\text{ then }2+2=7$ This is true as a logical implication, because the hypothesis is false. ---

Necessary and Sufficient Conditions

Example: $\qquad \text{If a number is divisible by }4,\text{ then it is even}$ So:

• divisibility by $4$ is sufficient for being even,

• being even is necessary for divisibility by $4$.

::: ---

Equivalent Ways to Read an Implication

These all express the same logical direction. ---

Related Statements

---

Minimal Worked Examples

Example 1 Statement: $\qquad \text{If }n\text{ is divisible by }6,\text{ then }n\text{ is divisible by }3.$ This is true because divisibility by $6$ guarantees divisibility by $3$. Here:

• "$n$ divisible by $6$" is sufficient for "$n$ divisible by $3$"

• "$n$ divisible by $3$" is necessary for "$n$ divisible by $6$"

--- Example 2 Statement: $\qquad \text{If }x=2,\text{ then }x^2=4.$ This is true. But the converse $\qquad \text{If }x^2=4,\text{ then }x=2$ is false. So implication is not the same as equivalence. ---

Implication Versus Equivalence

Many exam questions test whether students confuse these two ideas. ---

Common Mistakes

---

CMI Strategy

---

Practice Questions

:::question type="MCQ" question="The implication $P \implies Q$ is false exactly when" options=["$P$ is false and $Q$ is true","$P$ is true and $Q$ is false","$P$ is false and $Q$ is false","$P$ is true and $Q$ is true"] answer="B" hint="Think about the unique failure case." solution="An implication $P \implies Q$ fails only when the hypothesis is true but the conclusion is false. Hence the correct option is $\boxed{B}$." ::: :::question type="NAT" question="How many rows of the truth table of $P \implies Q$ have the value true?" answer="3" hint="There are four possible truth assignments for $P$ and $Q$." solution="For two statements $P$ and $Q$, there are four possible truth assignments. The implication $P \implies Q$ is false only in the case $P=\text{true}$ and $Q=\text{false}$. Therefore it is true in the remaining three cases. Hence the answer is $\boxed{3}$." ::: :::question type="MSQ" question="Which of the following are correct interpretations of $P \implies Q$?" options=["$P$ is sufficient for $Q$","$Q$ is necessary for $P$","$P$ is necessary for $Q$","$Q$ whenever $P$"] answer="A,B,D" hint="Translate the statement carefully." solution="If $P \implies Q$, then $P$ is sufficient for $Q$, $Q$ is necessary for $P$, and the phrase '$Q$ whenever $P$' has the same meaning. The statement '$P$ is necessary for $Q$' reverses the direction and is not generally correct. Hence the correct answer is $\boxed{A,B,D}$." ::: :::question type="SUB" question="Explain why the statement 'If $n$ is divisible by $4$, then $n$ is even' shows that divisibility by $4$ is sufficient for evenness, and evenness is necessary for divisibility by $4$." answer="Because the statement has the form $P \implies Q$, where $P$ is sufficient for $Q$ and $Q$ is necessary for $P$" hint="Identify $P$ and $Q$." solution="Let $\qquad P=$ '$n$ is divisible by $4$' and $\qquad Q=$ '$n$ is even' The statement says $\qquad P \implies Q$ In any implication $P \implies Q$:

• $P$ is sufficient for $Q$,

• $Q$ is necessary for $P$.

Therefore divisibility by $4$ is sufficient for evenness, and evenness is necessary for divisibility by $4$." ::: ---

Summary

---

---

Part 4: Biconditional

Biconditional

Overview

The biconditional connects two statements in both directions. It expresses equivalence, exactness, and “if and only if” reasoning. In proof-based mathematics, biconditionals are crucial because many definitions and theorems are stated in this form. In exam problems, the main challenge is to understand that a biconditional requires two implications, not one. ---

Learning Objectives

---

Core Idea

This is also read as:

• “$P$ if and only if $Q$”

• “$P$ is equivalent to $Q$”

• “$P$ exactly when $Q$”

::: ---

Truth Condition

---

Relation to Implication

So a biconditional is stronger than a one-way implication. ---

Language Patterns

These wording differences are highly testable. ---

Biconditional in Mathematics

---

Proving a Biconditional

---

Minimal Worked Examples

Example 1 Consider the statement: $\qquad n\text{ is divisible by }6 \iff n\text{ is divisible by }2\text{ and }3$ This is true because divisibility by $6$ is equivalent to divisibility by both $2$ and $3$. --- Example 2 The statement $\qquad x^2=1 \iff x=1$ is false over $\mathbb{R}$ because $x=-1$ also satisfies $x^2=1$. So even if one direction looks tempting, the biconditional fails if the reverse direction fails. ---

Common Mistakes

---

CMI Strategy

---

Practice Questions

:::question type="MCQ" question="The statement $P\iff Q$ is equivalent to" options=["$P\implies Q$","$Q\implies P$","$(P\implies Q)\land(Q\implies P)$","$(P\lor Q)$"] answer="C" hint="A biconditional means both directions hold." solution="By definition, $\qquad P\iff Q \iff (P\implies Q)\land(Q\implies P)$. Hence the correct option is $\boxed{C}$." ::: :::question type="NAT" question="Write $1$ if the statement 'A biconditional is true whenever both component statements have the same truth value' is true, and write $0$ if it is false." answer="1" hint="Check the truth table for $\iff$." solution="A biconditional is true exactly when both component statements have the same truth value. So the given statement is true. Hence the required answer is $\boxed{1}$." ::: :::question type="MSQ" question="Which of the following statements are correct?" options=["$P\iff Q$ implies $P\implies Q$","$P\iff Q$ implies $Q\implies P$","To prove $P\iff Q$, it is enough to prove only $P\implies Q$","If $P$ and $Q$ always have the same truth value, then $P\iff Q$ is true"] answer="A,B,D" hint="Use the definition of biconditional carefully." solution="1. True, because $P\iff Q$ includes $P\implies Q$.

True, because $P\iff Q$ also includes $Q\implies P$.

False, one direction alone is not enough.

True, that is exactly the truth condition for biconditional.

Hence the correct answer is $\boxed{A,B,D}$." ::: :::question type="SUB" question="Explain why proving $P\iff Q$ usually requires proving two separate implications." answer="Because $P\iff Q$ means both $P\implies Q$ and $Q\implies P$." hint="Expand the meaning of biconditional." solution="The statement $\qquad P\iff Q$ means $\qquad (P\implies Q)\land(Q\implies P)$. So a biconditional is true only when both directions hold. Therefore, to prove $P\iff Q$, one usually proves first that $P\implies Q$, and then separately that $Q\implies P$. Without both parts, the equivalence is incomplete." ::: ---

Summary

---

---

Part 5: Converse

Converse

Overview

The converse of a statement is obtained by reversing the direction of an implication. This looks innocent, but in logic it is one of the most common sources of mistakes. In exam questions, students often assume that a true statement automatically has a true converse. That is false in general. ---

Learning Objectives

---

Core Idea

To form the converse, simply reverse the direction. ---

Main Warning

So the converse must be checked separately. ---

Converse Versus Other Related Statements

---

When the Converse Is True

Example: $\qquad \text{An integer is even if and only if its square is even}$ because both directions are true. ---

Minimal Worked Examples

Example 1 Original statement: $\qquad \text{If a figure is a square, then it is a rectangle.}$ Converse: $\qquad \text{If a figure is a rectangle, then it is a square.}$ The original statement is true, but the converse is false. --- Example 2 Original statement: $\qquad \text{If }x=2,\text{ then }x^2=4.$ Converse: $\qquad \text{If }x^2=4,\text{ then }x=2.$ This converse is false because $x=-2$ also satisfies $x^2=4$. ---

Counterexample Method

This is the standard exam method. ---

Common Question Patterns

---

Converse and Proofs

This is a very common proof error. ---

Common Mistakes

---

CMI Strategy

---

Practice Questions

:::question type="MCQ" question="The converse of $P \implies Q$ is" options=["$\neg Q \implies \neg P$","$Q \implies P$","$\neg P \implies \neg Q$","$P \implies \neg Q$"] answer="B" hint="The converse reverses the direction." solution="The converse of $P \implies Q$ is formed by reversing the implication. Therefore it is $Q \implies P$. Hence the correct option is $\boxed{B}$." ::: :::question type="NAT" question="How many of the statements $P \implies Q$, $Q \implies P$, $\neg Q \implies \neg P$, and $\neg P \implies \neg Q$ are always logically equivalent to the converse $Q \implies P$?" answer="2" hint="The converse is equivalent to its inverse." solution="The converse is $Q \implies P$. It is always logically equivalent to itself and to its inverse $\neg P \implies \neg Q$. It is not always equivalent to the original implication or its contrapositive. Hence the number is $\boxed{2}$." ::: :::question type="MSQ" question="Which of the following are true?" options=["The converse of $P \implies Q$ is $Q \implies P$","A true implication always has a true converse","A counterexample can disprove a converse","If both an implication and its converse are true, then we get an equivalence"] answer="A,C,D" hint="Think about reversal and counterexamples." solution="1. True. That is the definition of converse.

False. A true implication need not have a true converse.

True. One counterexample is enough to disprove a converse.

True. If both directions hold, then we have an equivalence.

Hence the correct answer is $\boxed{A,C,D}$." ::: :::question type="SUB" question="Give a counterexample to show that the converse of the statement 'If an integer is divisible by $4$, then it is even' is false." answer="$2$ is a counterexample" hint="Find an even number not divisible by $4$." solution="The converse of the statement is: $\qquad \text{If an integer is even, then it is divisible by }4.$ This is false. For example, the integer $2$ is even, but it is not divisible by $4$. Therefore $2$ is a counterexample, so the converse is false." ::: ---

Summary

---

---

Part 6: Contrapositive

Contrapositive

Overview

The contrapositive is one of the most important transformations of an implication. In logic and proofs, it is often far easier to prove the contrapositive of a statement than to prove the statement directly. In exam questions, this topic is usually tested through logical equivalence, proof methods, and confusion between contrapositive, converse, and inverse. ---

Learning Objectives

---

Core Idea

To form the contrapositive:

negate both parts,

reverse the direction.

---

Logical Equivalence

This means they always have the same truth value. This is called proof by contrapositive. ---

Truth-Table Insight

So they match in every possible case. ---

How Contrapositive Differs from Other Related Statements

---

Minimal Worked Examples

Example 1 Original statement: $\qquad \text{If an integer is divisible by }4,\text{ then it is even.}$ Let $\qquad P=$ "the integer is divisible by $4$" and $\qquad Q=$ "the integer is even" Then the contrapositive is: $\qquad \text{If an integer is not even, then it is not divisible by }4.$ This is true and often easier to justify. --- Example 2 Original statement: $\qquad \text{If }x^2=0,\text{ then }x=0.$ Contrapositive: $\qquad \text{If }x\ne 0,\text{ then }x^2\ne 0.$ This form is often more natural in algebraic proofs. ---

Why Contrapositive Proofs Are Useful

---

Standard Proof Template

---

Common Logical Examples

Be careful: the exact form of the negation matters. ---

Negation Accuracy

---

Common Mistakes

---

CMI Strategy

---

Practice Questions

:::question type="MCQ" question="The contrapositive of $P \implies Q$ is" options=["$Q \implies P$","$\neg P \implies \neg Q$","$\neg Q \implies \neg P$","$P \implies \neg Q$"] answer="C" hint="Negate both parts and reverse direction." solution="The contrapositive of $P \implies Q$ is obtained by negating both statements and reversing the order. Therefore it is $\neg Q \implies \neg P$. Hence the correct option is $\boxed{C}$." ::: :::question type="NAT" question="How many of the statements $P \implies Q$, $\neg Q \implies \neg P$, $Q \implies P$, and $\neg P \implies \neg Q$ are always logically equivalent to $P \implies Q$?" answer="2" hint="Think about contrapositive, converse, and inverse." solution="Among the given four statements:

• $P \implies Q$ is obviously equivalent to itself,

• $\neg Q \implies \neg P$ is the contrapositive, so it is equivalent,

• $Q \implies P$ is the converse and is not always equivalent,

• $\neg P \implies \neg Q$ is the inverse and is not always equivalent.

So the number of always equivalent statements is $\boxed{2}$." ::: :::question type="MSQ" question="Which of the following are true?" options=["The contrapositive of $P \implies Q$ is logically equivalent to $P \implies Q$","The converse of $P \implies Q$ is always logically equivalent to $P \implies Q$","To form the contrapositive, we negate both parts and reverse the direction","Proof by contrapositive is a valid method for proving an implication"] answer="A,C,D" hint="Only one of converse and contrapositive is always equivalent to the original." solution="1. True. The implication and its contrapositive are logically equivalent.

False. The converse is not always equivalent to the original implication.

True. That is exactly how the contrapositive is formed.

True. Proof by contrapositive is a standard valid proof method.

Hence the correct answer is $\boxed{A,C,D}$." ::: :::question type="SUB" question="Prove the statement: If an integer $n$ is not even, then $n^2$ is not even." answer="If $n$ is odd, then $n^2$ is odd, hence not even" hint="Write $n=2k+1$." solution="Assume that $n$ is not even. Then $n$ is odd, so for some integer $k$ we can write $\qquad n=2k+1$ Now square both sides: $\qquad n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1$ Thus $n^2$ is of the form $2m+1$, so it is odd. Therefore $n^2$ is not even. Hence the statement is proved." ::: ---

Summary

---

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="Consider the statement: 'If a number is even, then it is divisible by 2.' Which of the following is the contrapositive of this statement?" options=["If a number is divisible by 2, then it is even." , "If a number is not even, then it is not divisible by 2." , "If a number is not divisible by 2, then it is not even." , "A number is even and it is not divisible by 2."] answer="If a number is not divisible by 2, then it is not even." hint="The contrapositive of $P \implies Q$ is $\neg Q \implies \neg P$." solution="Let $P$ be 'a number is even' and $Q$ be 'it is divisible by 2'. The original statement is $P \implies Q$. The contrapositive is $\neg Q \implies \neg P$, which translates to 'If a number is not divisible by 2, then it is not even.' "
:::

:::question type="NAT" question="If $P$ is false and $Q$ is true, what is the truth value of the compound statement $(P \lor \neg Q) \iff (\neg P \land Q)$? (Represent True as 1, False as 0)" answer="0" hint="Evaluate each side of the biconditional separately based on the given truth values for $P$ and $Q$." solution="Given $P$ is false (F) and $Q$ is true (T).
First part: $(P \lor \neg Q)$
$\neg Q$ is false (F).
$P \lor \neg Q$ is F $\lor$ F, which is F.

Second part: $(\neg P \land Q)$
$\neg P$ is true (T).
$\neg P \land Q$ is T $\land$ T, which is T.

Finally, the biconditional: F $\iff$ T, which is F.
Representing False as 0, the answer is 0."
:::

:::question type="MCQ" question="The negation of the statement 'If it rains, then the match will be cancelled' is logically equivalent to which of the following?" options=["If it does not rain, then the match will not be cancelled." , "It rains and the match will not be cancelled." , "It does not rain or the match will be cancelled." , "If the match is cancelled, then it rains."] answer="It rains and the match will not be cancelled." hint="The negation of an implication $P \implies Q$ is $P \land \neg Q$." solution="Let $P$ be 'it rains' and $Q$ be 'the match will be cancelled'. The original statement is $P \implies Q$. The negation of this implication is $\neg(P \implies Q)$, which is logically equivalent to $P \land \neg Q$. This translates to 'It rains and the match will not be cancelled.'"
:::

:::question type="NAT" question="How many distinct rows are required in a truth table for a compound statement involving 5 distinct simple statements?" answer="32" hint="The number of rows in a truth table is determined by the number of simple statements involved." solution="For $n$ distinct simple statements, there are $2^n$ distinct rows in the truth table. For 5 distinct simple statements, there are $2^5 = 32$ rows."
:::

---

What's Next?