Fundamentals of Discrete Mathematics

Fundamentals of Discrete Mathematics

Welcome to this comprehensive module on the core concepts of discrete mathematics that underpin computer science and algorithmic thinking. In this course we will explore five essential topics:

• Type systems and integer arithmetic
• Logical equivalences and implication
• Injective (one‑to‑one) functions
• Greatest common divisor (GCD) via divisibility diagrams
• Chinese Remainder Theorem (CRT) and modular solutions

Each section provides clear explanations, illustrative examples, and key take‑aways that are SEO‑optimized for learners searching for "discrete mathematics fundamentals", "type system Z vs N", "logical equivalence of implication", "injective function definition", "gcd of 60 and 18", and "Chinese Remainder Theorem example".

1. Type Systems: Why 3 − 5 Gets Type Z Instead of N

In many formal languages, such as the theoretical language Disco, types are used to guarantee that expressions evaluate to values within a specific set. The two most common numeric types are:

• N – the set of natural numbers (0, 1, 2, …); always non‑negative.
• Z – the set of integers (…, −2, −1, 0, 1, 2, …).

When the expression 3 - 5 is evaluated, the result is −2. Because the outcome can be negative, the language must assign the broader integer type Z to preserve correctness. This decision follows a fundamental principle:

Any arithmetic operation that may produce a negative result must be typed as Z, not N.

Key takeaway: The type system reflects the possible range of results. Subtraction is not guaranteed to stay within the natural numbers, so the expression receives the integer type.

2. Logical Equivalence: Translating p → q

Implication (p → q) is one of the core connectives in propositional logic. A frequently used core equivalence, derived from the truth table of implication, is:

p → q ≡ ¬p ∨ q

To see why, consider the four possible truth assignments:

• If p is false, the implication is automatically true, matching the disjunction ¬p ∨ q.
• If p is true, the truth of the implication depends on q. When q is true, both sides are true; when q is false, both sides are false.

This equivalence is essential for simplifying logical expressions, proving theorems, and converting statements into conjunctive normal form (CNF) for SAT solvers.

Key takeaway: The implication p → q can always be rewritten as ¬p ∨ q, a form that is easier to manipulate in proofs and algorithms.

3. Injective Functions: What Must Hold for f : A → B?

An injective (or one‑to‑one) function preserves distinctness: different inputs produce different outputs. Formally, the defining property is:

∀a₁, a₂ ∈ A, f(a₁) = f(a₂) ⇒ a₁ = a₂

This statement means that if two elements of the domain map to the same element of the codomain, then those two domain elements must actually be the same element. The converse—"if a₁ ≠ a₂ then f(a₁) ≠ f(a₂)"—is logically equivalent but less convenient for proofs because it involves a negated premise.

Note that injectivity does not require the function to be surjective (onto). The range of f may be a proper subset of B. Also, the statement "a₁ = a₂ ⇒ f(a₁) = f(a₂)" holds for any function, not just injective ones, and therefore does not characterize injectivity.

Key takeaway: The hallmark of an injective function is the implication f(a₁) = f(a₂) ⇒ a₁ = a₂. This property is used extensively in proofs of uniqueness, cryptographic hash functions, and data structure invariants.

4. Greatest Common Divisor via Divisibility Diagrams

The greatest common divisor (GCD) of two integers is the largest integer that divides both numbers without remainder. A visual tool called a divisibility diagram (or Hasse diagram for the divisor lattice) helps to identify the GCD quickly.

Consider the numbers 60 and 18:

• Prime factorization of 60: 2² × 3 × 5
• Prime factorization of 18: 2 × 3²

The common prime factors are 2 and 3. Taking the lowest exponent for each yields 2¹ × 3¹ = 6. In the divisibility diagram, 6 appears as the highest node that is a divisor of both 60 and 18, confirming that gcd(60, 18) = 6.

Key takeaway: The GCD can be found by intersecting the prime factor sets of the two numbers, or by locating the greatest common node in a divisibility diagram.

5. Chinese Remainder Theorem: Solving a System Modulo 210

The Chinese Remainder Theorem (CRT) provides a systematic way to solve simultaneous congruences when the moduli are pairwise coprime. The problem statement is:

    x ≡ 1 (mod 5)
    x ≡ 2 (mod 6)
    x ≡ 3 (mod 7)
  

First, note that the moduli 5, 6, and 7 are not all pairwise coprime because 6 shares a factor 2 with 5? Actually 5 and 6 are coprime, 5 and 7 are coprime, but 6 and 7 are also coprime, so the product is 5 × 6 × 7 = 210. The CRT guarantees a unique solution modulo 210.

We solve step‑by‑step:

1. Compute the total modulus M = 210.
2. For each congruence, compute M_i = M / m_i:
   • M₁ = 210 / 5 = 42
   • M₂ = 210 / 6 = 35
   • M₃ = 210 / 7 = 30
3. Find the modular inverses y_i such that M_i·y_i ≡ 1 (mod m_i):
   • For m₁ = 5, solve 42·y₁ ≡ 1 (mod 5). Since 42 ≡ 2 (mod 5), we need 2·y₁ ≡ 1 (mod 5). The inverse is y₁ = 3 because 2·3 = 6 ≡ 1 (mod 5).
   • For m₂ = 6, solve 35·y₂ ≡ 1 (mod 6). 35 ≡ 5 (mod 6), so 5·y₂ ≡ 1 (mod 6). The inverse is y₂ = 5 because 5·5 = 25 ≡ 1 (mod 6).
   • For m₃ = 7, solve 30·y₃ ≡ 1 (mod 7). 30 ≡ 2 (mod 7), so 2·y₃ ≡ 1 (mod 7). The inverse is y₃ = 4 because 2·4 = 8 ≡ 1 (mod 7).
4. Combine the pieces using the CRT formula:

           x = Σ (a_i·M_i·y_i) mod M
           = 1·42·3 + 2·35·5 + 3·30·4 mod 210
           = 126 + 350 + 360 mod 210
           = 836 mod 210
           = 206
         

The unique solution is x ≡ 206 (mod 210). Any integer congruent to 206 modulo 210 satisfies all three original congruences.

Key takeaway: The CRT reduces a system of congruences to a single modular equation, and the method of constructing the solution via the product of moduli, partial products, and modular inverses is a repeatable algorithm used in cryptography, computer algebra, and coding theory.

Course Summary and Further Study

In this module we have covered:

• Why subtraction may force a type to be Z rather than N.
• The core logical equivalence p → q ≡ ¬p ∨ q.
• The precise definition of injective functions.
• How to compute the GCD using prime factorization and divisibility diagrams.
• A step‑by‑step application of the Chinese Remainder Theorem yielding the solution 206 (mod 210).

These concepts form the backbone of discrete mathematics and are directly applicable to algorithm design, formal verification, and cryptographic protocols. For deeper exploration, consider studying:

• Advanced type theory and dependent types.
• Resolution and natural deduction in propositional logic.
• Bijective functions and their role in combinatorial proofs.
• Euclidean algorithm for efficient GCD computation.
• CRT extensions to non‑coprime moduli and applications in RSA.

Continue practicing with additional problems, and use this guide as a reference when encountering similar topics in your computer science coursework.