MR%28B%299+2026

Administrative and Course Information

• Course: Mathematical Reasoning 2026
• Instructor: Vivek Tewary
• Date: 18 August 2026
• Section: Section B
• Topic: 9. Logic III

Fundamental Logical Laws and Equivalences

• De Morgan's Laws:

  • Negation of Conjunction (AND):$\neg (P \land Q) \equiv (\neg P \lor \neg Q)$
    • Rule: "And" transforms to "Or" under negation, accompanied by the negation of both component statements.
  • Negation of Disjunction (OR):$\neg (P \lor Q) \equiv (\neg P \land \neg Q)$
    • Rule: "Or" transforms to "And" under negation, accompanied by the negation of both component statements.

• Commutativity:

  • $P \lor Q \equiv Q \lor P$
  • $P \land Q \equiv Q \land P$

• Associativity:

  • $P \lor (Q \lor R) \equiv (P \lor Q) \lor R$
  • $P \land (Q \land R) \equiv (P \land Q) \land R$

• Distributivity:

  • $P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)$
  • $P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$

• Equivalences Involving Conditionals:

  • $P \implies Q \equiv \neg P \lor Q$
  • $\neg (P \implies Q) \equiv P \land \neg Q$
  • $P \implies Q \equiv (\neg Q \implies \neg P)$

Negation of Compound and Quantified Statements

• Verification of $\neg (P \implies Q) \equiv P \land \neg Q$:
  • Conceptual Foundation: The only scenario in which the conditional $P \implies Q$ evaluates to false is when $P$ is true and $Q$ is false.
  • Truth Table Verification:

*   **Algebraic Proof:**

        $\neg (P \implies Q) \equiv \neg (\neg P \lor Q)$$\equiv \neg (\neg P) \land \neg Q$$\equiv P \land \neg Q$

*   **Verbal Illustration:**
    *   Original Statement: "It is not the case that if it will rain, then I will get drenched."
    *   Logically Equivalent Statement: "It will rain and I will not get drenched."

• Quantified Negation Examples:

  • Example 1:

    • Original Statement: "For every natural number $x$, if $x$ is prime then $x$ is not rational."
    • Predicate Definition: Let $P(x)$ denote "$x$ is prime."
    • Formal Representation: $\forall x \in \mathbb{N}, (P(x) \implies (x \notin \mathbb{Q}))$
    • Negation Formulation: $\exists x \in \mathbb{N}, (P(x) \land (x \in \mathbb{Q}))$
    • Verbal Negation: "There is a natural number $x$ such that $x$ is prime and it is rational."

  • Example 2:

    • Original Statement: "There is a real number $a$ for which $a + x = x$ for every real number $x$"
    • Predicate Definition: Let $P(a, x)$ denote "$a + x = x$".
    • Formal Representation: $\exists a \in \mathbb{R}, (\forall x \in \mathbb{R}, P(a, x))$
    • Negation Formulation: $\forall a \in \mathbb{R}, (\exists x \in \mathbb{R}, \neg P(a, x))$
    • Verbal Negation: "For every real number $a$, there is a real number $x$ such that $a + x \neq x$"

  • Example 3:

    • Original Statement: "If $x$ is a rational number and $x > 0$, then $\tan(x)$ is not a rational number."
    • Formal Representation: $\forall x \in \mathbb{R}, (((x \in \mathbb{Q}) \land (x > 0)) \implies (\tan(x) \notin \mathbb{Q}))$
    • Negation Formulation: $\exists x \in \mathbb{R}, (((x \in \mathbb{Q}) \land (x > 0)) \land (\tan(x) \in \mathbb{Q}))$
    • Verbal Negation: "There is a real number $x$ which is positive, rational and $\tan(x)$ is also rational."

  • Example 4:

    • Original Statement: "For every prime number $p$, there is another prime number $q$ with $q > p$"
    • Domain Set Definition: Let $\mathbb{P}$ denote the set of all prime numbers.
    • Formal Representation: $\forall p \in \mathbb{P}, (\exists q \in \mathbb{P}, (q > p))$
    • Negation Formulation: $\exists p \in \mathbb{P}, (\forall q \in \mathbb{P}, (q \le p))$
    • Verbal Negation: "There is a prime number $p$ such that all other prime numbers are not more than $p$"

Converse and Contrapositive

• Converse:

  • Definition: Given the conditional statement $P \implies Q$, the conditional statement $Q \implies P$ is called the converse.
  • Truth Value Relationship: The truth of the conditional statement does not imply the truth of its converse.
  • Real-World Example: While it is considered true that global warming is caused by methane, the converse (methane is caused by global warming) is not true.

• Contrapositive:

  • Definition: Given the conditional statement $P \implies Q$, the conditional statement $\neg Q \implies \neg P$ is called the contrapositive.
  • Truth Value Relationship: The truth of a conditional statement is logically equivalent to the truth of its contrapositive.
  • Real-World Example: "If the sun is out, then it is hot" is logically equivalent to "If it is not hot, then the sun is not out."

• Verification of Contrapositive Equivalence ($P \implies Q \equiv (\neg Q \implies \neg P)$):

  • Truth Table Verification:

| $P$ | $Q$ | $\neg P$ | $\neg Q$ | $$