Mathematics for AI Engineers

Mathematical Logic is the formal language of reasoning in mathematics and computer science. It provides the rigorous syntactic and semantic rules that underpin digital circuit design, compiler construction, formal verification, algorithm correctness proofs, database query optimization, and artificial intelligence knowledge representation.

This module covers Propositional Logic, Truth Tables, Logical Connectives, Quantifiers (First-Order Logic), and Proof Techniques.

What You'll Learn#

By the end of this module, you will be able to:

Math Notation & Pronunciation Guide#

Propositional Connectives:

• ¬ or ~ — pronounced "not" or "negation" — inverts truth value (¬p)
• ∧ — pronounced "and" or "conjunction" — true only when both are true (p ∧ q)
• ∨ — pronounced "or" or "disjunction" — true when at least one is true (p ∨ q)
• ⊕ — pronounced "xor" or "exclusive or" — true when exactly one is true (p ⊕ q)
• ⟹ or → — pronounced "implies" or "if-then" — conditional statement (p ⟹ q)
• ⟺ or ↔ — pronounced "if and only if" (iff) — biconditional statement (p ⟺ q)
• ≡ — pronounced "is logically equivalent to" — identical truth table columns (p ≡ q)
• ⊤ (or T) — pronounced "tautology" or "true"
• ⊥ (or F) — pronounced "contradiction" or "false"

First-Order Logic Quantifiers:

• ∀ — pronounced "for all" or "for every" — Universal Quantifier (∀x P(x))
• ∃ — pronounced "there exists" or "for some" — Existential Quantifier (∃x P(x))
• ∃! — pronounced "there exists uniquely" or "there is exactly one" (∃!x P(x))

Key Concepts#

1. Propositions & Truth Values#

What is a Proposition? A proposition (or statement) is a declarative sentence that is either strictly True (T) or strictly False (F), but not both simultaneously.

Sentence                                      | Proposition? | Truth Value
----------------------------------------------|--------------|-------------
"Paris is the capital of France."             | YES          | True (T)
"2 + 3 = 7"                                   | YES          | False (F)
"Python is an interpreted programming lang."  | YES          | True (T)
"What time is it?"                            | NO (Question)| N/A
"Please submit your assignment."              | NO (Command) | N/A
"x + 5 = 12"                                  | NO (Open eq) | Depends on x
"This statement is false."                    | NO (Paradox) | Neither T nor F

2. Logical Connectives & Compound Statements#

Compound propositions are formed by combining atomic propositions using logical operators (connectives).

                Master Truth Table for Basic Connectives
+-------+-------+----------+---------------+--------------+----------------+
|   p   |   q   | Negation |  Conjunction  | Disjunction  |  Exclusive OR  |
|       |       |  (¬ p)   |    (p ∧ q)    |   (p ∨ q)    |    (p ⊕ q)     |
+-------+-------+----------+---------------+--------------+----------------+
|   T   |   T   |    F     |       T       |      T       |       F        |
|   T   |   F   |    F     |       F       |      T       |       T        |
|   F   |   T   |    T     |       F       |      T       |       T        |
|   F   |   F   |    T     |       F       |      F       |       F        |
+-------+-------+----------+---------------+--------------+----------------+

1. Negation (¬p): Flips T ↔ F.
2. Conjunction (p ∧ q): True if and only if BOTH p and q are true. (Analogous to Set Intersection ∩).
3. Disjunction (p ∨ q): True if AT LEAST ONE of p or q is true. (Analogous to Set Union ∪).
4. Exclusive OR (p ⊕ q): True if EXACTLY ONE is true, but false if both are true. (Analogous to Symmetric Difference △).

# Boolean logic in Python
p = True
q = False

print("NOT p (¬p):", not p)          # False
print("p AND q (p ∧ q):", p and q)   # False
print("p OR q (p ∨ q):", p or q)     # True
print("p XOR q (p ⊕ q):", p ^ q)     # True

3. Conditional (p ⟹ q) & Biconditional (p ⟺ q)#

3.1 The Conditional (Implication: p ⟹ q)#

In the implication p ⟹ q:

• p is called the Hypothesis / Antecedent / Premise.
• q is called the Conclusion / Consequent.

       Truth Table for Conditional and Biconditional
+-------+-------+-------------------------+-------------------------+
|   p   |   q   | Conditional (p ⟹ q)     | Biconditional (p ⟺ q)   |
+-------+-------+-------------------------+-------------------------+
|   T   |   T   |            T            |            T            |
|   T   |   F   |            F  (Violation)|           F            |
|   F   |   T   |            T  (Vacuous) |            F            |
|   F   |   F   |            T  (Vacuous) |            T            |
+-------+-------+-------------------------+-------------------------+

GATE Translation Cheat Sheet for Conditional Statements (p ⟹ q):

In GATE exams, questions regularly test your ability to correctly identify the Hypothesis (p) vs. the Conclusion (q) in natural language sentences:

Fundamental Equivalence of Implication:

p ⟹ q ≡ ¬p ∨ q

3.2 The Biconditional (p ⟺ q)#

p ⟺ q states "p if and only if q" (often written iff). It is True whenever p and q share the exact same truth value (T ⟺ T and F ⟺ F).

p ⟺ q ≡ (p ⟹ q) ∧ (q ⟹ p)

4. Converse, Inverse, and Contrapositive#

Given any conditional statement p ⟹ q, three related conditional statements can be formed:

        Comparison of Truth Tables for Related Conditionals
+---+---+---------------+---------------+-----------------+--------------------+
| p | q | p ⟹ q (Orig)  | q ⟹ p (Conv)  | ¬p ⟹ ¬q (Inv)  | ¬q ⟹ ¬p (Contra)   |
+---+---+---------------+---------------+-----------------+--------------------+
| T | T |       T       |       T       |        T        |         T          |
| T | F |       F       |       T       |        T        |         F          |
| F | T |       T       |       F       |        F        |         T          |
| F | F |       T       |       T       |        T        |         T          |
+---+---+---------------+---------------+-----------------+--------------------+

5. Truth Tables, Tautologies, Contradictions & Contingencies#

Compound propositions are classified based on the truth values in their final column:

1. Tautology (⊤ or T): A compound proposition that is True for every possible truth assignment of its variables (e.g., p ∨ ¬p, p ⟹ p).
2. Contradiction (⊥ or F): A compound proposition that is False for every possible truth assignment (e.g., p ∧ ¬p).
3. Contingency: A compound proposition that is neither a tautology nor a contradiction (it is True for some assignments and False for others).

# Truth Table Generator in Python
def truth_table_3var():
    print(" p | q | r | (p ∧ q) → r | (p → r) ∨ (q → r)")
    print("-" * 46)
    for p in [True, False]:
        for q in [True, False]:
            for r in [True, False]:
                lhs = (not (p and q)) or r
                rhs = ((not p) or r) or ((not q) or r)
                print(f" {int(p)} | {int(q)} | {int(r)} |      {int(lhs)}      |        {int(rhs)}       | Equivalent: {lhs == rhs}")

truth_table_3var()

6. Laws of Logical Equivalence#

Two propositions P and Q are logically equivalent (P ≡ Q) if and only if P ⟺ Q is a tautology.

7. Predicates & Quantifiers (First-Order Logic)#

A predicate P(x) is a statement containing variable x. Once a domain of discourse D is specified, quantifiers turn predicates into complete propositions.

7.1 Universal Quantifier (∀x P(x))#

• Meaning: "P(x) is true for ALL x in domain D."
• Condition for True: P(x) is true for every element in D.
• Condition for False: Finding a single counterexample c in D where P(c) is false.

7.2 Existential Quantifier (∃x P(x))#

• Meaning: "There EXISTS at least one x in domain D such that P(x) is true."
• Condition for True: Finding at least one witness c in D where P(c) is true.
• Condition for False: P(x) is false for every element in D.

7.3 Multi-Variable Predicates & Translation Patterns (GATE AIR 1 Core Rules)#

In GATE, questions frequently involve binary relational predicates P(x, y) (e.g., M(x, y): "x knows y", L(x, y): "x loves y", D(x, y): "x divides y") over a domain D.

╔══════════════════════════════════════════════════════════════════════════════════════════════════╗
║                                 THE GOLDEN QUANTIFIER RULE                                        ║
║  1. Universal Quantifier (∀x) naturally pairs with IMPLICATION (→)                               ║
║     "Every student who studies passes"  ⟹  ∀x (Student(x) ∧ Studies(x) → Passes(x))              ║
║     [Trap: Using ∧ with ∀ makes it assert EVERY object in the universe is a student!]            ║
║                                                                                                  ║
║  2. Existential Quantifier (∃x) naturally pairs with CONJUNCTION (∧)                             ║
║     "There is a student who passes"     ⟹  ∃x (Student(x) ∧ Passes(x))                           ║
║     [Trap: Using → with ∃ is vacuously True if any non-student exists in the universe!]          ║
╚══════════════════════════════════════════════════════════════════════════════════════════════════╝

The Celebrity / Master Problem Pattern:#

Consider predicate M(x, y) meaning "x knows y":

1. "Person y is known by everyone else (excluding themselves)":

   ∀x ((x ≠ y) ⟹ M(x, y))

2. "Person y knows nobody else (excluding themselves)":

   ∀x ((x ≠ y) ⟹ ¬M(y, x))

3. "There exists a person y who knows nobody else, but is known by everyone else": Combining the two properties with an existential witness y:

   (∃y)(∀x)((x ≠ y) ⟹ (M(x, y) ∧ ¬M(y, x)))

7.4 Uniqueness Quantification (∃!x) & "Exactly One" Translation Rules#

The uniqueness quantifier ∃!x P(x) asserts that there exists one and only one element in domain D satisfying predicate P.

Two Core Components of "Exactly One":#

1. Existence (At least one): ∃y P(y)
2. Uniqueness (At most one): Any other entity z ≠ y cannot satisfy P, or equivalently, if P(z) holds, then z must be y.

Standard Logical Forms of "Everyone has exactly one mother":#

Let mother(y, x) denote "y is the mother of x" and noteq(x, y) denote x ≠ y:

• Form 1: Universal Non-Equality Implication (GATE Standard Form):

  ∀x ∃y [mother(y, x) ∧ ∀z (noteq(z, y) ⟹ ¬mother(z, x))] (For every x, there is a mother y, and anyone z distinct from y is NOT a mother of x)

• Form 2: Existential Negation via De Morgan's Law (Equivalent Form):

  ∀x ∃y [mother(y, x) ∧ ¬∃z (noteq(z, y) ∧ mother(z, x))] (For every x, there is a mother y, and NO person z distinct from y is also a mother of x)

• Form 3: Contrapositive Equivalence:

  ∀x ∃y [mother(y, x) ∧ ∀z (mother(z, x) ⟹ ¬noteq(z, y))] (If z is also a mother of x, then z MUST be y)

7.5 Quantifier Inference & Implication Rules (GATE AIR 1 Core)#

In GATE, questions frequently test implication strength between quantified formulas (i.e., whether Premise A ⟹ Conclusion B).

1. The Fundamental Quantifier Swap Theorem:#

∃y ∀x φ(x, y) ⟹ ∀x ∃y φ(x, y)

• Why it holds: If one universal witness y works for all x simultaneously (∃y ∀x), then for every x, we can simply choose that same witness y (∀x ∃y).
• The Converse is FALSE: ∀x ∃y φ(x, y) DOES NOT imply ∃y ∀x φ(x, y).
  (Example over integers: "Every number has a successor" [∀x ∃y (y = x+1)] is True, but "There is a single number that is successor to all numbers" [∃y ∀x (y = x+1)] is False!)

2. Quantifier Movement Over Implication (Scope Rules):#

When variable y does not occur free in P(x):

• ∃y [P(x) ⟹ Q(x, y)] ≡ P(x) ⟹ ∃y Q(x, y)
• ∀y [P(x) ⟹ Q(x, y)] ≡ P(x) ⟹ ∀y Q(x, y)

3. AIR 1 Implication Testing Framework:#

To test whether Premise A implies Target G: ∀x [P(x) ⟹ ∃y Q(x, y)]:

• Universal Consequent Dominance: If ∀x ∀y Q(x, y) is True, then ∃y Q(x, y) is always True. Because Anything ⟹ True ≡ True, the conjecture is guaranteed to hold.
• Existential Scope Insufficiency: A premise asserting only existence for a single instance ∃x [...] can never imply a universal claim ∀x [...] over an infinite domain.

8. Negating Quantified Statements#

To negate quantified statements, we use De Morgan's Laws for Quantifiers:

• ¬(∀x P(x)) ≡ ∃x ¬P(x)
• ¬(∃x P(x)) ≡ ∀x ¬P(x)

Original Statement                | Symbolic Form    | Negated Form      | English Negation
----------------------------------|------------------|-------------------|-----------------------------
"All students passed the exam."   | ∀x Passed(x)     | ∃x ¬Passed(x)     | "Some student did not pass."
"Some integers are negative."     | ∃x Negative(x)   | ∀x ¬Negative(x)   | "All integers are non-neg."
"Every prime number is odd."      | ∀x Odd(x)        | ∃x ¬Odd(x)        | "There is an even prime (2)."

9. Methods of Mathematical Proof in Computer Science#

Proof techniques form the foundation for proving algorithm termination, time complexity lower bounds, and software correctness.

9.1 Direct Proof (p ⟹ q)#

Assume hypothesis p is true, apply definitions and algebraic steps, and show that conclusion q must be true.

• Example: Prove that if n is odd, then n² is odd.
  • Proof: n = 2k + 1 ⟹ n² = (2k+1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd. ∎

9.2 Proof by Contraposition (¬q ⟹ ¬p)#

Instead of proving p ⟹ q, prove the logically equivalent contrapositive ¬q ⟹ ¬p.

• Example: Prove that if 3n + 2 is odd, then n is odd.
  • Contrapositive: If n is even (n = 2k), then 3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1) is even. Thus ¬q ⟹ ¬p is proven. ∎

9.3 Proof by Contradiction (Reductio ad Absurdum)#

To prove proposition p, assume ¬p is true. Derive a logical impossibility or contradiction (such as 1 = 0 or k is both even and odd). Hence, ¬p must be false, so p is true.

• Example: Proof that √2 is irrational, or Euclid's proof of the infinitude of primes.

9.4 Proof by Counterexample#

To disprove a universal statement ∀x P(x), it suffices to construct one concrete instance c where P(c) is false.

• Example: "All prime numbers are odd." Counterexample: n = 2 is prime and even.

9.5 Principle of Mathematical Induction (PMI in First-Order Logic)#

Mathematical induction is a fundamental proof technique for establishing that a predicate P(x) holds for all natural numbers ℕ = {0, 1, 2, ...}.

The Formal Axiom of Induction:#

(P(0) ∧ ∀x [P(x) ⟹ P(x+1)]) ⟹ ∀x P(x)

• Base Case (P(0)): Proves that the property holds for the minimal starting element x = 0.
• Inductive Step (∀x [P(x) ⟹ P(x+1)]): Proves that truth transfers from any number x to its immediate successor x + 1 (the "domino effect").
• Universal Conclusion (∀x P(x)): Because 0 holds, 1 holds; because 1 holds, 2 holds; and so forth, guaranteeing P(x) for all x ∈ ℕ.

10. Boolean Satisfiability (SAT) & Logic Gates#

10.1 Logic Gates in Hardware Architecture#

Digital computers implement propositional logic directly using transistors:

• AND Gate (∧): Output 1 only if all inputs are 1.
• OR Gate (∨): Output 1 if any input is 1.
• NOT Gate / Inverter (¬): Inverts input (0 ↔ 1).
• NAND / NOR Gates: Universal gates that can implement any boolean function.

10.2 Conjunctive Normal Form (CNF) & SAT#

• Literal: A variable x or its negation ¬x.
• Clause: A disjunction (OR) of literals: (x₁ ∨ ¬x₂ ∨ x₃).
• CNF (Conjunctive Normal Form): An AND of OR clauses: (x₁ ∨ x₂) ∧ (¬x₁ ∨ x₃) ∧ (¬x₂ ∨ ¬x₃)

TL;DR — Quick Recall Reference#

Additional Resources#

Interactive:

• Truth Table Generator & Evaluator
• Logic Gate Simulator

Academic References:

• Discrete Mathematics and Its Applications by Kenneth H. Rosen (Chapter 1: The Foundations: Logic and Proofs)
• NPTEL Discrete Mathematics by Prof. Sudarshan Iyengar (IIT Ropar — Week 3: Logic)