Show description
MAT 243: Discrete Mathematical Structures - Complete Guide
MAT 243: Discrete Mathematical Structures - Complete Guide
MAT 243: Discrete Mathematical Structures
A Comprehensive Guide to Mastering Foundational Topics in Discrete Mathematics
Table of Contents
1. Propositional Logic
2. Predicates and Quantifiers
3. Rules of Inference and Proof Techniques
4. Set Theory
5. Functions, Sequences, and Summation
6. Algorithms and Growth of Functions
7. Elementary Number Theory
8. Mathematical Induction and Recursion
9. Combinatorics and Counting Principles
10. Relations
Glossary
1. Propositional Logic
Propositional logic forms the foundation of mathematical reasoning and computer science. A proposition is a declarative statement that is either true or false, but not both.
Basic Logical Operators
Negation (¬): If p is true, then ¬p is false, and vice versa.
Conjunction (∧): p ∧ q is true only when both p and q are true.
Disjunction (∨): p ∨ q is false only when both p and q are false.
Implication (→): p → q is false only when p is true and q is false.
Biconditional (↔): p ↔ q is true when p and q have the same truth value.
Truth Tables
Truth tables enumerate all possible truth value assignments for propositions. They are essential for verifying logical equivalences and analyzing complex statements.
Example: Truth Table for Implication
p
q
p → q
T
T
T
T
F
F
F
T
T
F
F
T
Notice that an implication is only false when the hypothesis is true and the conclusion is false. This counterintuitive behavior is crucial in mathematical proofs.
Logical Equivalences
Two compound propositions are logically equivalent if they have the same truth values in all possible cases.…
MAT 243: Discrete Mathematical Structures - Complete Guide
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>MAT 243: Discrete Mathematical Structures - Complete Guide</title>
<style>
* {
margin: 0;
padding: 0;
box-sizing: border-box;
}
body {
font-family: 'Georgia', 'Times New Roman', serif;
background: #ffffff;
color: #1a1a1a;
line-height: 1.8;
padding: 20px;
}
.container {
max-width: 1200px;
margin: 0 auto;
background: #ffffff;
padding: 40px;
}
h1 {
color: #c41e3a;
font-size: 2.5em;
margin-bottom: 10px;
border-bottom: 4px solid #ffd700;
padding-bottom: 15px;
}
h2 {
color: #c41e3a;
font-size: 1.8em;
margin-top: 40px;
margin-bottom: 20px;
border-left: 5px solid #ffd700;
padding-left: 15px;
}
h3 {
color: #1a1a1a;
font-size: 1.4em;
margin-top: 25px;
margin-bottom: 15px;
font-weight: bold;
}
p {
margin-bottom: 15px;
text-align: justify;
}
.subtitle {
color: #666;
font-size: 1.2em;
margin-bottom: 30px;
font-style: italic;
}
.section {
margin-bottom: 50px;
}
.example-box {
background: #f8f8f8;
border-left: 4px solid #c41e3a;
padding: 20px;
margin: 20px 0;
border-radius: 4px;
}
.theorem-box {
background: #fffbf0;
border: 2px solid #ffd700;
padding: 20px;
margin: 20px 0;
border-radius: 4px;
}
.math-display {
font-family: 'Courier New', monospace;
font-size: 1.1em;
padding: 15px;
background: #f5f5f5;
border-radius: 4px;
margin: 15px 0;
text-align: center;
line-height: 2;
}
.code-display {
font-family: 'Courier New', monospace;
font-size: 0.95em;
padding: 20px;
background: #1a1a1a;
color: #ffd700;
border-radius: 4px;
margin: 15px 0;
overflow-x: auto;
white-space: pre;
}
table {
width: 100%;
border-collapse: collapse;
margin: 20px 0;
background: #fff;
}
th {
background: #c41e3a;
color: #fff;
padding: 12px;
text-align: left;
font-weight: bold;
}
td {
border: 1px solid #ddd;
padding: 12px;
}
tr:nth-child(even) {
background: #f9f9f9;
}
.truth-table {
width: auto;
margin: 20px auto;
display: table;
}
.truth-table th {
background: #1a1a1a;
}
ul, ol {
margin-left: 30px;
margin-bottom: 15px;
}
li {
margin-bottom: 8px;
}
.highlight {
background: #fff4cc;
padding: 2px 5px;
border-radius: 3px;
}
.glossary-term {
font-weight: bold;
color: #c41e3a;
}
.glossary-section {
background: #f8f8f8;
padding: 30px;
border-radius: 8px;
margin-top: 40px;
}
.visual-box {
border: 2px solid #1a1a1a;
padding: 20px;
margin: 20px 0;
text-align: center;
background: #fafafa;
}
.venn-diagram {
display: inline-block;
position: relative;
width: 300px;
height: 200px;
margin: 20px;
}
.circle {
position: absolute;
width: 150px;
height: 150px;
border-radius: 50%;
opacity: 0.6;
border: 3px solid #1a1a1a;
}
.circle-a {
background: #ff6b6b;
left: 30px;
top: 25px;
}
.circle-b {
background: #ffd700;
left: 120px;
top: 25px;
}
.key-concept {
background: #fff;
border: 2px solid #ffd700;
padding: 15px;
margin: 15px 0;
border-radius: 4px;
}
.nav-toc {
background: #1a1a1a;
color: #fff;
padding: 20px;
margin-bottom: 30px;
border-radius: 4px;
}
.nav-toc a {
color: #ffd700;
text-decoration: none;
display: block;
padding: 5px 0;
}
.nav-toc a:hover {
color: #c41e3a;
}
.proof-steps {
margin-left: 40px;
counter-reset: proof-counter;
}
.proof-steps li {
counter-increment: proof-counter;
margin-bottom: 12px;
}
.proof-steps li::marker {
content: "(" counter(proof-counter) ") ";
color: #c41e3a;
font-weight: bold;
}
</style>
</head>
<body>
<div class="container">
<h1>MAT 243: Discrete Mathematical Structures</h1>
<p class="subtitle">A Comprehensive Guide to Mastering Foundational Topics in Discrete Mathematics</p>
<div class="nav-toc">
<h3 style="color: #ffd700; margin-bottom: 15px;">Table of Contents</h3>
<a href="#logic">1. Propositional Logic</a>
<a href="#predicates">2. Predicates and Quantifiers</a>
<a href="#proofs">3. Rules of Inference and Proof Techniques</a>
<a href="#sets">4. Set Theory</a>
<a href="#functions">5. Functions, Sequences, and Summation</a>
<a href="#algorithms">6. Algorithms and Growth of Functions</a>
<a href="#number-theory">7. Elementary Number Theory</a>
<a href="#induction">8. Mathematical Induction and Recursion</a>
<a href="#combinatorics">9. Combinatorics and Counting Principles</a>
<a href="#relations">10. Relations</a>
<a href="#glossary">Glossary</a>
</div>
<div id="logic" class="section">
<h2>1. Propositional Logic</h2>
<p>Propositional logic forms the foundation of mathematical reasoning and computer science. A proposition is a declarative statement that is either true or false, but not both.</p>
<h3>Basic Logical Operators</h3>
<div class="key-concept">
<strong>Negation (¬):</strong> If p is true, then ¬p is false, and vice versa.
</div>
<div class="key-concept">
<strong>Conjunction (∧):</strong> p ∧ q is true only when both p and q are true.
</div>
<div class="key-concept">
<strong>Disjunction (∨):</strong> p ∨ q is false only when both p and q are false.
</div>
<div class="key-concept">
<strong>Implication (→):</strong> p → q is false only when p is true and q is false.
</div>
<div class="key-concept">
<strong>Biconditional (↔):</strong> p ↔ q is true when p and q have the same truth value.
</div>
<h3>Truth Tables</h3>
<p>Truth tables enumerate all possible truth value assignments for propositions. They are essential for verifying logical equivalences and analyzing complex statements.</p>
<div class="example-box">
<strong>Example: Truth Table for Implication</strong>
<table class="truth-table">
<tr>
<th>p</th>
<th>q</th>
<th>p → q</th>
</tr>
<tr>
<td>T</td>
<td>T</td>
<td>T</td>
</tr>
<tr>
<td>T</td>
<td>F</td>
<td>F</td>
</tr>
<tr>
<td>F</td>
<td>T</td>
<td>T</td>
</tr>
<tr>
<td>F</td>
<td>F</td>
<td>T</td>
</tr>
</table>
<p>Notice that an implication is only false when the hypothesis is true and the conclusion is false. This counterintuitive behavior is crucial in mathematical proofs.</p>
</div>
<h3>Logical Equivalences</h3>
<p>Two compound propositions are logically equivalent if they have the same truth values in all possible cases. We denote logical equivalence with ≡.</p>
<div class="theorem-box">
<strong>Key Equivalences:</strong>
<div class="math-display">
De Morgan's Laws:
<br>¬(p ∧ q) ≡ ¬p ∨ ¬q
<br>¬(p ∨ q) ≡ ¬p ∧ ¬q
<br><br>
Implication:
<br>p → q ≡ ¬p ∨ q
<br>p → q ≡ ¬q → ¬p (contrapositive)
<br><br>
Double Negation:
<br>¬(¬p) ≡ p
</div>
</div>
<h3>Applications in Computer Science</h3>
<p>Propositional logic is fundamental to:</p>
<ul>
<li>Digital circuit design (AND, OR, NOT gates)</li>
<li>Boolean algebra and bit manipulation</li>
<li>Conditional statements in programming</li>
<li>Database queries and search algorithms</li>
<li>Artificial intelligence and automated reasoning</li>
</ul>
<div class="example-box">
<strong>Programming Example:</strong>
<div class="code-display">function checkAccess(isAdmin, hasPermission, isOwner) {
// Logical expression: access granted if
// (admin OR has permission) AND (not suspended)
return (isAdmin || hasPermission) && isOwner;
}
// This mirrors the logical statement:
// access = (A ∨ P) ∧ O</div>
</div>
</div>
<div id="predicates" class="section">
<h2>2. Predicates and Quantifiers</h2>
<p>Predicates extend propositional logic by allowing variables and quantifiers. A predicate is a statement involving variables that becomes a proposition when the variables are assigned values.</p>
<h3>Universal Quantifier (∀)</h3>
<div class="key-concept">
∀x P(x) means "P(x) is true for all values of x in the domain"
</div>
<div class="example-box">
<strong>Example:</strong> Let P(x) be "x² ≥ 0"
<br>∀x ∈ ℝ, P(x) is TRUE (every real number squared is non-negative)
</div>
<h3>Existential Quantifier (∃)</h3>
<div class="key-concept">
∃x P(x) means "there exists at least one x such that P(x) is true"
</div>
<div class="example-box">
<strong>Example:</strong> Let Q(x) be "x² = 2"
<br>∃x ∈ ℝ, Q(x) is TRUE (√2 satisfies this)
<br>∃x ∈ ℚ, Q(x) is FALSE (no rational number squares to 2)
</div>
<h3>Nested Quantifiers</h3>
<p>Order matters crucially when quantifiers are nested. Consider these different statements:</p>
<div class="math-display">
∀x ∃y (x < y)
<br>"For every x, there exists a y greater than x" (TRUE for real numbers)
<br><br>
∃y ∀x (x < y)
<br>"There exists a y that is greater than all x" (FALSE for real numbers)
</div>
<h3>Negating Quantified Statements</h3>
<div class="theorem-box">
<strong>Negation Rules:</strong>
<div class="math-display">
¬(∀x P(x)) ≡ ∃x ¬P(x)
<br><br>
¬(∃x P(x)) ≡ ∀x ¬P(x)
</div>
</div>
<div class="example-box">
<strong>Example:</strong> Negate "All students passed the exam"
<br>Original: ∀x (Student(x) → Passed(x))
<br>Negation: ∃x (Student(x) ∧ ¬Passed(x))
<br>In English: "There exists a student who did not pass"
</div>
</div>
<div id="proofs" class="section">
<h2>3. Rules of Inference and Proof Techniques</h2>
<p>Mathematical proofs are logical arguments that establish the truth of mathematical statements. Mastering proof techniques is essential for mathematical maturity.</p>
<h3>Rules of Inference</h3>
<div class="theorem-box">
<strong>Modus Ponens:</strong>
<div class="math-display">
p → q
<br>p
<br>∴ q
</div>
</div>
<div class="theorem-box">
<strong>Modus Tollens:</strong>
<div class="math-display">
p → q
<br>¬q
<br>∴ ¬p
</div>
</div>
<div class="theorem-box">
<strong>Hypothetical Syllogism:</strong>
<div class="math-display">
p → q
<br>q → r
<br>∴ p → r
</div>
</div>
<h3>Direct Proof</h3>
<p>To prove p → q directly, assume p is true and show that q must follow logically.</p>
<div class="example-box">
<strong>Theorem:</strong> If n is an odd integer, then n² is odd.
<br><br>
<strong>Proof:</strong>
<ol class="proof-steps">
<li>Assume n is odd. Then n = 2k + 1 for some integer k.</li>
<li>Consider n² = (2k + 1)² = 4k² + 4k + 1</li>
<li>Factor: n² = 2(2k² + 2k) + 1</li>
<li>Let m = 2k² + 2k, which is an integer.</li>
<li>Then n² = 2m + 1, which is odd by definition. ∎</li>
</ol>
</div>
<h3>Proof by Contrapositive</h3>
<p>To prove p → q, instead prove ¬q → ¬p (the contrapositive).</p>
<div class="example-box">
<strong>Theorem:</strong> If n² is even, then n is even.
<br><br>
<strong>Proof (by contrapositive):</strong>
<ol class="proof-steps">
<li>We prove: if n is odd, then n² is odd.</li>
<li>Assume n is odd. Then n = 2k + 1 for some integer k.</li>
<li>n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1</li>
<li>Therefore n² is odd.</li>
<li>By contrapositive, if n² is even, then n must be even. ∎</li>
</ol>
</div>
<h3>Proof by Contradiction</h3>
<p>Assume the statement is false and derive a logical contradiction.</p>
<div class="example-box">
<strong>Theorem:</strong> √2 is irrational.
<br><br>
<strong>Proof (by contradiction):</strong>
<ol class="proof-steps">
<li>Assume √2 is rational. Then √2 = p/q where p, q are integers with no common factors (lowest terms).</li>
<li>Squaring both sides: 2 = p²/q²</li>
<li>Therefore: 2q² = p²</li>
<li>This means p² is even, so p must be even (by previous theorem).</li>
<li>Let p = 2k. Then 2q² = (2k)² = 4k²</li>
<li>Dividing by 2: q² = 2k²</li>
<li>This means q² is even, so q is even.</li>
<li>But if both p and q are even, they share a common factor of 2.</li>
<li>This contradicts our assumption that p/q is in lowest terms.</li>
<li>Therefore, √2 must be irrational. ∎</li>
</ol>
</div>
<h3>Constructive vs Non-Constructive Proofs</h3>
<p>A constructive proof explicitly constructs an example, while a non-constructive proof shows existence without construction.</p>
<div class="example-box">
<strong>Non-Constructive Example:</strong> There exist irrational numbers a and b such that a^b is rational.
<br><br>
<strong>Proof:</strong> Consider √2^√2. Either it's rational (and we're done), or it's irrational. If it's irrational, let a = √2^√2 and b = √2. Then:
<div class="math-display">
a^b = (√2^√2)^√2 = √2^(√2·√2) = √2^2 = 2
</div>
Which is rational. Therefore, such numbers exist. ∎
</div>
</div>
<div id="sets" class="section">
<h2>4. Set Theory</h2>
<p>Set theory provides the foundation for modern mathematics. A set is an unordered collection of distinct objects called elements or members.</p>
<h3>Set Notation and Definitions</h3>
<div class="math-display">
A = {1, 2, 3, 4, 5} (roster notation)
<br>B = {x ∈ ℕ | x < 6} (set-builder notation)
<br>∅ or {} (empty set)
</div>
<h3>Set Operations</h3>
<div class="key-concept">
<strong>Union (A ∪ B):</strong> All elements in A or B or both
<br><strong>Intersection (A ∩ B):</strong> All elements in both A and B
<br><strong>Difference (A - B):</strong> All elements in A but not in B
<br><strong>Complement (A̅):</strong> All elements in the universal set U not in A
</div>
<div class="visual-box">
<h4>Venn Diagram: A ∪ B</h4>
<div class="venn-diagram">
<div class="circle circle-a"></div>
<div class="circle circle-b"></div>
</div>
<p>The shaded regions show the union of sets A and B</p>
</div>
<h3>Set Identities</h3>
<div class="theorem-box">
<strong>De Morgan's Laws for Sets:</strong>
<div class="math-display">
(A ∪ B)̅ = A̅ ∩ B̅
<br>(A ∩ B)̅ = A̅ ∪ B̅
</div>
</div>
<div class="theorem-box">
<strong>Distributive Laws:</strong>
<div class="math-display">
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
<br>A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
</div>
</div>
<h3>Cardinality and Power Sets</h3>
<p>The cardinality |A| is the number of elements in set A. The power set P(A) is the set of all subsets of A.</p>
<div class="example-box">
<strong>Example:</strong> Let A = {1, 2, 3}
<br>|A| = 3
<br>P(A) = {∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}
<br>|P(A)| = 2³ = 8
<br><br>
<strong>General Rule:</strong> If |A| = n, then |P(A)| = 2ⁿ
</div>
<h3>Cartesian Product</h3>
<p>The Cartesian product A × B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B.</p>
<div class="example-box">
<strong>Example:</strong> A = {1, 2}, B = {x, y}
<br>A × B = {(1,x), (1,y), (2,x), (2,y)}
<br>|A × B| = |A| · |B| = 2 · 2 = 4
</div>
</div>
<div id="functions" class="section">
<h2>5. Functions, Sequences, and Summation</h2>
<h3>Functions</h3>
<p>A function f: A → B assigns to each element of A (domain) exactly one element of B (codomain). The range is the set of all actual outputs.</p>
<div class="key-concept">
<strong>Injective (One-to-One):</strong> Different inputs produce different outputs
<br>∀x₁, x₂ ∈ A, if f(x₁) = f(x₂), then x₁ = x₂
</div>
<div class="key-concept">
<strong>Surjective (Onto):</strong> Every element in the codomain is mapped to
<br>∀y ∈ B, ∃x ∈ A such that f(x) = y
</div>
<div class="key-concept">
<strong>Bijective:</strong> Both injective and surjective (perfect one-to-one correspondence)
</div>
<div class="example-box">
<strong>Examples:</strong>
<br>f(x) = 2x (ℝ → ℝ) is injective and surjective (bijective)
<br>g(x) = x² (ℝ → ℝ) is neither injective (g(-2) = g(2)) nor surjective (no x gives -1)
<br>h(x) = x² (ℝ⁺ → ℝ⁺) is bijective when domain and codomain are restricted to non-negative reals
</div>
<h3>Function Composition and Inverse</h3>
<div class="math-display">
Composition: (g ∘ f)(x) = g(f(x))
<br><br>
Inverse: f⁻¹ exists if and only if f is bijective
<br>f(f⁻¹(x)) = x and f⁻¹(f(x)) = x
</div>
<h3>Sequences</h3>
<p>A sequence is a function from positive integers to a set. We typically write aₙ instead of a(n).</p>
<div class="example-box">
<strong>Arithmetic Sequence:</strong> aₙ = a₁ + (n-1)d
<br>Example: 2, 5, 8, 11, 14, ... (d = 3)
<br><br>
<strong>Geometric Sequence:</strong> aₙ = a₁ · rⁿ⁻¹
<br>Example: 3, 6, 12, 24, 48, ... (r = 2)
</div>
<h3>Summation Notation</h3>
<div class="math-display">
Σ(i=1 to n) i = n(n+1)/2
<br><br>
Σ(i=1 to n) i² = n(n+1)(2n+1)/6
<br><br>
Σ(i=0 to n) rⁱ = (rⁿ⁺¹ - 1)/(r - 1) for r ≠ 1
</div>
<div class="example-box">
<strong>Example:</strong> Calculate Σ(i=1 to 100) i
<br>Using the formula: 100(101)/2 = 5050
</div>
</div>
<div id="algorithms" class="section">
<h2>6. Algorithms and Growth of Functions</h2>
<h3>Big-O Notation</h3>
<p>Big-O notation describes the asymptotic upper bound of an algorithm's time or space complexity.</p>
<div class="key-concept">
f(n) = O(g(n)) if there exist constants c > 0 and n₀ > 0 such that
<br>0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀
</div>
<h3>Common Complexity Classes</h3>
<table>
<tr>
<th>Notation</th>
<th>Name</th>
<th>Example</th>
</tr>
<tr>
<td>O(1)</td>
<td>Constant</td>
<td>Array access, hash table lookup</td>
</tr>
<tr>
<td>O(log n)</td>
<td>Logarithmic</td>
<td>Binary search, balanced tree operations</td>
</tr>
<tr>
<td>O(n)</td>
<td>Linear</td>
<td>Linear search, array traversal</td>
</tr>
<tr>
<td>O(n log n)</td>
<td>Linearithmic</td>
<td>Efficient sorting (merge sort, heap sort)</td>
</tr>
<tr>
<td>O(n²)</td>
<td>Quadratic</td>
<td>Nested loops, bubble sort</td>
</tr>
<tr>
<td>O(2ⁿ)</td>
<td>Exponential</td>
<td>Recursive fibonacci, subset generation</td>
</tr>
<tr>
<td>O(n!)</td>
<td>Factorial</td>
<td>Permutation generation, traveling salesman brute force</td>
</tr>
</table>
<div class="example-box">
<strong>Algorithm Analysis Example:</strong>
<div class="code-display">function findMax(arr) {
let max = arr[0]; // O(1)
for (let i = 1; i < arr.length; i++) { // O(n)
if (arr[i] > max) { // O(1)
max = arr[i]; // O(1)
}
}
return max; // O(1)
}
// Overall complexity: O(n)</div>
</div>
<h3>Big-Omega and Big-Theta</h3>
<div class="key-concept">
<strong>Ω(g(n)):</strong> Lower bound - f(n) grows at least as fast as g(n)
<br><strong>Θ(g(n)):</strong> Tight bound - f(n) grows at the same rate as g(n)
</div>
<div class="example-box">
<strong>Example:</strong> For f(n) = 3n² + 5n + 2:
<br>f(n) = O(n²) - upper bound
<br>f(n) = Ω(n²) - lower bound
<br>f(n) = Θ(n²) - tight bound
</div>
</div>
<div id="number-theory" class="section">
<h2>7. Elementary Number Theory</h2>
<h3>Divisibility</h3>
<div class="key-concept">
a | b (a divides b) if there exists an integer k such that b = ak
</div>
<div class="theorem-box">
<strong>Properties of Divisibility:</strong>
<ul>
<li>If a | b and b | c, then a | c (transitivity)</li>
<li>If a | b and a | c, then a | (b + c) and a | (b - c)</li>
<li>If a | b, then a | bc for any integer c</li>
</ul>
</div>
<h3>Prime Numbers</h3>
<p>A prime number is an integer greater than 1 that has no positive divisors other than 1 and itself.</p>
<div class="theorem-box">
<strong>Fundamental Theorem of Arithmetic:</strong> Every integer greater than 1 can be uniquely represented as a product of prime numbers (up to ordering).
</div>
<div class="example-box">
<strong>Example:</strong>
<br>84 = 2² × 3 × 7
<br>100 = 2² × 5²
<br>1001 = 7 × 11 × 13
</div>
<h3>Greatest Common Divisor (GCD)</h3>
<p>The GCD of two integers is the largest positive integer that divides both numbers.</p>
<div class="theorem-box">
<strong>Euclidean Algorithm:</strong>
<div class="code-display">function gcd(a, b) {
while (b !== 0) {
let temp = b;
b = a % b;
a = temp;
}
return a;
}
// Example: gcd(48, 18)
// 48 = 2 × 18 + 12
// 18 = 1 × 12 + 6
// 12 = 2 × 6 + 0
// GCD = 6</div>
</div>
<h3>Modular Arithmetic</h3>
<p>a ≡ b (mod m) means m divides (a - b), or equivalently, a and b have the same remainder when divided by m.</p>
<div class="example-box">
<strong>Examples:</strong>
<br>17 ≡ 5 (mod 12) because 17 - 5 = 12
<br>-3 ≡ 7 (mod 10) because -3 - 7 = -10
</div>
<div class="theorem-box">
<strong>Properties:</strong>
<br>If a ≡ b (mod m) and c ≡ d (mod m), then:
<ul>
<li>a + c ≡ b + d (mod m)</li>
<li>a × c ≡ b × d (mod m)</li>
<li>aⁿ ≡ bⁿ (mod m)</li>
</ul>
</div>
</div>
<div id="induction" class="section">
<h2>8. Mathematical Induction and Recursion</h2>
<h3>Principle of Mathematical Induction</h3>
<p>To prove ∀n ≥ n₀, P(n) is true:</p>
<ol>
<li><strong>Base Case:</strong> Show P(n₀) is true</li>
<li><strong>Inductive Step:</strong> Show that if P(k) is true, then P(k+1) is true</li>
<li><strong>Conclusion:</strong> By induction, P(n) is true for all n ≥ n₀</li>
</ol>
<div class="example-box">
<strong>Theorem:</strong> Prove that Σ(i=1 to n) i = n(n+1)/2 for all n ≥ 1
<br><br>
<strong>Proof:</strong>
<ol class="proof-steps">
<li><strong>Base Case (n=1):</strong> LHS = 1, RHS = 1(2)/2 = 1. ✓</li>
<li><strong>Inductive Hypothesis:</strong> Assume true for n = k:
<br>Σ(i=1 to k) i = k(k+1)/2</li>
<li><strong>Inductive Step:</strong> Prove for n = k+1:
<br>Σ(i=1 to k+1) i = [Σ(i=1 to k) i] + (k+1)
<br>= k(k+1)/2 + (k+1) [by hypothesis]
<br>= (k+1)[k/2 + 1]
<br>= (k+1)(k+2)/2
<br>= (k+1)((k+1)+1)/2 ✓</li>
<li><strong>Conclusion:</strong> By induction, the formula holds for all n ≥ 1. ∎</li>
</ol>
</div>
<h3>Strong Induction</h3>
<p>In strong induction, we assume P(n₀), P(n₀+1), ..., P(k) are all true when proving P(k+1).</p>
<div class="example-box">
<strong>Theorem:</strong> Every integer n ≥ 2 can be written as a product of primes.
<br><br>
<strong>Proof (by strong induction):</strong>
<ol class="proof-steps">
<li><strong>Base Case:</strong> n = 2 is prime, so it's trivially a product of primes (itself).</li>
<li><strong>Inductive Hypothesis:</strong> Assume every integer from 2 to k can be written as a product of primes.</li>
<li><strong>Inductive Step:</strong> Consider k+1:
<br>Case 1: If k+1 is prime, we're done.
<br>Case 2: If k+1 is composite, then k+1 = ab where 2 ≤ a, b ≤ k.
<br>By the inductive hypothesis, both a and b can be written as products of primes.
<br>Therefore, k+1 = ab is also a product of primes.</li>
<li><strong>Conclusion:</strong> By strong induction, every integer n ≥ 2 is a product of primes. ∎</li>
</ol>
</div>
<h3>Recursion</h3>
<p>A recursive definition defines an object in terms of itself with a base case.</p>
<div class="example-box">
<strong>Factorial Function:</strong>
<div class="code-display">function factorial(n) {
if (n === 0) return 1; // base case
return n * factorial(n-1); // recursive case
}
// factorial(5) = 5 × 4 × 3 × 2 × 1 = 120</div>
</div>
<div class="example-box">
<strong>Fibonacci Sequence:</strong>
<div class="math-display">
F(0) = 0
<br>F(1) = 1
<br>F(n) = F(n-1) + F(n-2) for n ≥ 2
</div>
<div class="code-display">function fibonacci(n) {
if (n <= 1) return n;
return fibonacci(n-1) + fibonacci(n-2);
}
// Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...</div>
</div>
<h3>Structural Induction</h3>
<p>Used to prove properties about recursively defined structures like trees, lists, or formal languages.</p>
</div>
<div id="combinatorics" class="section">
<h2>9. Combinatorics and Counting Principles</h2>
<h3>Basic Counting Principles</h3>
<div class="key-concept">
<strong>Product Rule:</strong> If there are n₁ ways to do task 1 and n₂ ways to do task 2, there are n₁ × n₂ ways to do both tasks.
</div>
<div class="key-concept">
<strong>Sum Rule:</strong> If there are n₁ ways to do task 1 and n₂ ways to do task 2 (and they're mutually exclusive), there are n₁ + n₂ ways to do either task.
</div>
<h3>Permutations</h3>
<p>A permutation is an arrangement where order matters.</p>
<div class="math-display">
P(n, r) = n!/(n-r)!
<br><br>
Number of ways to arrange r objects from n distinct objects
</div>
<div class="example-box">
<strong>Example:</strong> How many ways can we arrange 3 books from a shelf of 5?
<br>P(5, 3) = 5!/(5-3)! = 5!/2! = 120/2 = 60 ways
</div>
<h3>Combinations</h3>
<p>A combination is a selection where order doesn't matter.</p>
<div class="math-display">
C(n, r) = n!/(r!(n-r)!)
<br><br>
Also written as (n choose r) or ⁿCᵣ
</div>
<div class="example-box">
<strong>Example:</strong> How many ways can we choose 3 books from 5?
<br>C(5, 3) = 5!/(3!×2!) = 120/(6×2) = 10 ways
</div>
<h3>Binomial Theorem</h3>
<div class="theorem-box">
<div class="math-display">
(x + y)ⁿ = Σ(k=0 to n) C(n,k) xⁿ⁻ᵏ yᵏ
</div>
</div>
<div class="example-box">
<strong>Example:</strong> (x + y)³ = C(3,0)x³ + C(3,1)x²y + C(3,2)xy² + C(3,3)y³
<br>= x³ + 3x²y + 3xy² + y³
</div>
<h3>Pigeonhole Principle</h3>
<div class="theorem-box">
If n items are put into m containers and n > m, then at least one container must contain more than one item.
<br><br>
<strong>Generalized:</strong> If n items are put into m containers, at least one container has ⌈n/m⌉ items.
</div>
<div class="example-box">
<strong>Example:</strong> In any group of 13 people, at least 2 were born in the same month.
<br>(13 people, 12 months → by pigeonhole principle)
</div>
<h3>Inclusion-Exclusion Principle</h3>
<div class="theorem-box">
<div class="math-display">
|A ∪ B| = |A| + |B| - |A ∩ B|
<br><br>
|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|
</div>
</div>
<div class="example-box">
<strong>Example:</strong> In a class of 30 students, 20 play soccer, 15 play basketball, and 10 play both. How many play at least one sport?
<br>|S ∪ B| = 20 + 15 - 10 = 25 students
</div>
<h3>Basic Probability</h3>
<div class="key-concept">
P(E) = |E| / |S|
<br>where E is an event and S is the sample space
</div>
<div class="example-box">
<strong>Example:</strong> Probability of rolling a sum of 7 with two dice:
<br>Favorable outcomes: (1,6), (2,5), (3,4), (4,3), (5,2), (6,1) = 6 outcomes
<br>Total outcomes: 6 × 6 = 36
<br>P(sum = 7) = 6/36 = 1/6
</div>
</div>
<div id="relations" class="section">
<h2>10. Relations</h2>
<h3>Binary Relations</h3>
<p>A binary relation R from set A to set B is a subset of A × B. We write aRb to mean (a,b) ∈ R.</p>
<h3>Properties of Relations</h3>
<div class="key-concept">
<strong>Reflexive:</strong> ∀a ∈ A, aRa
<br>(Every element relates to itself)
</div>
<div class="key-concept">
<strong>Symmetric:</strong> ∀a,b ∈ A, if aRb then bRa
<br>(If a relates to b, then b relates to a)
</div>
<div class="key-concept">
<strong>Transitive:</strong> ∀a,b,c ∈ A, if aRb and bRc then aRc
<br>(Relation chains together)
</div>
<div class="key-concept">
<strong>Antisymmetric:</strong> ∀a,b ∈ A, if aRb and bRa then a = b
<br>(Different elements can't relate both ways)
</div>
<h3>Equivalence Relations</h3>
<p>A relation that is reflexive, symmetric, and transitive is an equivalence relation.</p>
<div class="example-box">
<strong>Examples of Equivalence Relations:</strong>
<ul>
<li>Equality (=) on any set</li>
<li>Congruence modulo n: a ≡ b (mod n)</li>
<li>"Has the same age as" on people</li>
<li>"Is similar to" on triangles</li>
</ul>
</div>
<h3>Equivalence Classes</h3>
<p>For an equivalence relation R on set A, the equivalence class of element a is:</p>
<div class="math-display">
[a] = {b ∈ A | aRb}
</div>
<div class="example-box">
<strong>Example:</strong> Consider integers under congruence mod 3
<br>[0] = {..., -6, -3, 0, 3, 6, 9, ...}
<br>[1] = {..., -5, -2, 1, 4, 7, 10, ...}
<br>[2] = {..., -4, -1, 2, 5, 8, 11, ...}
<br><br>
These three equivalence classes partition the integers.
</div>
<h3>Partial Orders</h3>
<p>A relation that is reflexive, antisymmetric, and transitive is a partial order.</p>
<div class="example-box">
<strong>Examples of Partial Orders:</strong>
<ul>
<li>≤ on real numbers</li>
<li>⊆ (subset relation) on sets</li>
<li>"Divides" (|) on positive integers</li>
<li>Lexicographic ordering on strings</li>
</ul>
</div>
<h3>Hasse Diagrams</h3>
<p>A Hasse diagram is a visual representation of a partial order, showing elements as nodes with lines connecting comparable elements (smaller below larger).</p>
<div class="visual-box">
<p><strong>Hasse Diagram Example:</strong> Divisibility on {1, 2, 3, 4, 6, 12}</p>
<div class="math-display">
12
<br>/ \
<br>6 4
<br>/ \ /
<br>3 2
<br>\ /
<br>1
</div>
<p>This shows the divisibility relationships (reading bottom to top)</p>
</div>
<h3>Applications in Computer Science</h3>
<ul>
<li><strong>Equivalence Relations:</strong> Used in compiler design for register allocation, in databases for entity resolution</li>
<li><strong>Partial Orders:</strong> Task scheduling, topological sorting, type systems</li>
<li><strong>Reflexive Transitive Closure:</strong> Reachability in graphs, program analysis</li>
</ul>
<div class="example-box">
<strong>Code Example: Checking Transitivity</strong>
<div class="code-display">function isTransitive(relation, set) {
for (let a of set) {
for (let b of set) {
for (let c of set) {
if (relation(a, b) && relation(b, c)) {
if (!relation(a, c)) {
return false; // Found violation
}
}
}
}
}
return true;
}</div>
</div>
</div>
<div id="glossary" class="glossary-section">
<h2>Comprehensive Glossary</h2>
<p><span class="glossary-term">Algorithm:</span> A finite sequence of well-defined instructions to solve a problem or perform a computation.</p>
<p><span class="glossary-term">Antisymmetric:</span> A relation R where if aRb and bRa, then a = b.</p>
<p><span class="glossary-term">Bijection:</span> A function that is both injective (one-to-one) and surjective (onto).</p>
<p><span class="glossary-term">Biconditional:</span> A logical statement p ↔ q that is true when both p and q have the same truth value.</p>
<p><span class="glossary-term">Big-O Notation:</span> A mathematical notation describing the limiting behavior of a function, used to classify algorithms.</p>
<p><span class="glossary-term">Binomial Coefficient:</span> The number C(n,k) representing the number of ways to choose k items from n items.</p>
<p><span class="glossary-term">Cardinality:</span> The number of elements in a set, denoted |A|.</p>
<p><span class="glossary-term">Cartesian Product:</span> The set A × B of all ordered pairs (a,b) where a ∈ A and b ∈ B.</p>
<p><span class="glossary-term">Codomain:</span> The set of all possible output values of a function.</p>
<p><span class="glossary-term">Combination:</span> A selection of items where order doesn't matter.</p>
<p><span class="glossary-term">Complement:</span> The set of all elements not in a given set (relative to a universal set).</p>
<p><span class="glossary-term">Composite Number:</span> An integer greater than 1 that is not prime (has factors other than 1 and itself).</p>
<p><span class="glossary-term">Conjunction:</span> The logical operation AND (∧), true only when both operands are true.</p>
<p><span class="glossary-term">Contrapositive:</span> The statement ¬q → ¬p, logically equivalent to p → q.</p>
<p><span class="glossary-term">Converse:</span> The statement q → p, obtained by swapping hypothesis and conclusion of p → q.</p>
<p><span class="glossary-term">Countable:</span> A set that can be put in one-to-one correspondence with natural numbers or a subset thereof.</p>
<p><span class="glossary-term">Direct Proof:</span> Proving p → q by assuming p and logically deriving q.</p>
<p><span class="glossary-term">Disjunction:</span> The logical operation OR (∨), false only when both operands are false.</p>
<p><span class="glossary-term">Divisibility:</span> Integer a divides integer b (a|b) if b = ka for some integer k.</p>
<p><span class="glossary-term">Domain:</span> The set of all possible input values for a function.</p>
<p><span class="glossary-term">Empty Set:</span> The set containing no elements, denoted ∅ or {}.</p>
<p><span class="glossary-term">Equivalence Class:</span> The set of all elements related to a given element under an equivalence relation.</p>
<p><span class="glossary-term">Equivalence Relation:</span> A relation that is reflexive, symmetric, and transitive.</p>
<p><span class="glossary-term">Euclidean Algorithm:</span> An efficient algorithm for computing the greatest common divisor of two integers.</p>
<p><span class="glossary-term">Existential Quantifier:</span> The symbol ∃ meaning "there exists."</p>
<p><span class="glossary-term">Function:</span> A relation that assigns exactly one output to each input.</p>
<p><span class="glossary-term">Greatest Common Divisor (GCD):</span> The largest positive integer that divides two given integers.</p>
<p><span class="glossary-term">Hasse Diagram:</span> A graph representation of a partial order showing comparable elements.</p>
<p><span class="glossary-term">Implication:</span> The logical statement p → q, false only when p is true and q is false.</p>
<p><span class="glossary-term">Inclusion-Exclusion Principle:</span> A counting technique for finding the size of a union of sets.</p>
<p><span class="glossary-term">Induction:</span> A proof technique establishing a statement for all natural numbers.</p>
<p><span class="glossary-term">Injection:</span> A function where different inputs produce different outputs (one-to-one).</p>
<p><span class="glossary-term">Integer:</span> A whole number that can be positive, negative, or zero.</p>
<p><span class="glossary-term">Intersection:</span> The set A ∩ B containing elements in both A and B.</p>
<p><span class="glossary-term">Inverse Function:</span> A function f⁻¹ that "undoes" f, existing only for bijections.</p>
<p><span class="glossary-term">Logical Equivalence:</span> Two statements having the same truth value in all cases.</p>
<p><span class="glossary-term">Mathematical Induction:</span> Proving a statement by showing base case and inductive step.</p>
<p><span class="glossary-term">Modular Arithmetic:</span> Arithmetic where numbers "wrap around" upon reaching a modulus.</p>
<p><span class="glossary-term">Modus Ponens:</span> The rule of inference: from p → q and p, conclude q.</p>
<p><span class="glossary-term">Modus Tollens:</span> The rule of inference: from p → q and ¬q, conclude ¬p.</p>
<p><span class="glossary-term">Negation:</span> The logical NOT operation (¬), reversing truth value.</p>
<p><span class="glossary-term">Partial Order:</span> A relation that is reflexive, antisymmetric, and transitive.</p>
<p><span class="glossary-term">Partition:</span> A collection of disjoint subsets whose union is the original set.</p>
<p><span class="glossary-term">Permutation:</span> An arrangement of objects where order matters.</p>
<p><span class="glossary-term">Pigeonhole Principle:</span> If n items are put into m containers with n > m, at least one container has multiple items.</p>
<p><span class="glossary-term">Power Set:</span> The set P(A) of all subsets of set A.</p>
<p><span class="glossary-term">Predicate:</span> A statement involving variables that becomes a proposition when values are assigned.</p>
<p><span class="glossary-term">Prime Number:</span> An integer greater than 1 divisible only by 1 and itself.</p>
<p><span class="glossary-term">Proof by Contradiction:</span> Assuming the negation of the statement and deriving a contradiction.</p>
<p><span class="glossary-term">Proof by Contrapositive:</span> Proving p → q by proving ¬q → ¬p.</p>
<p><span class="glossary-term">Proposition:</span> A declarative statement that is either true or false.</p>
<p><span class="glossary-term">Range:</span> The set of actual output values produced by a function.</p>
<p><span class="glossary-term">Recurrence Relation:</span> An equation defining a sequence in terms of previous terms.</p>
<p><span class="glossary-term">Recursion:</span> Defining something in terms of itself with a base case.</p>
<p><span class="glossary-term">Reflexive:</span> A relation R where every element relates to itself (aRa for all a).</p>
<p><span class="glossary-term">Relation:</span> A subset of the Cartesian product of two sets.</p>
<p><span class="glossary-term">Sequence:</span> An ordered list of numbers, typically defined by a formula or recurrence.</p>
<p><span class="glossary-term">Set:</span> An unordered collection of distinct objects.</p>
<p><span class="glossary-term">Strong Induction:</span> Induction assuming all previous cases when proving the next case.</p>
<p><span class="glossary-term">Subset:</span> Set A is a subset of B (A ⊆ B) if every element of A is in B.</p>
<p><span class="glossary-term">Summation:</span> The notation Σ representing the sum of a sequence of terms.</p>
<p><span class="glossary-term">Surjection:</span> A function where every element in the codomain is mapped to (onto).</p>
<p><span class="glossary-term">Symmetric:</span> A relation R where if aRb then bRa.</p>
<p><span class="glossary-term">Tautology:</span> A compound proposition that is always true.</p>
<p><span class="glossary-term">Transitive:</span> A relation R where if aRb and bRc, then aRc.</p>
<p><span class="glossary-term">Truth Table:</span> A table showing all possible truth value combinations for a logical statement.</p>
<p><span class="glossary-term">Union:</span> The set A ∪ B containing elements in A or B or both.</p>
<p><span class="glossary-term">Universal Quantifier:</span> The symbol ∀ meaning "for all."</p>
<p><span class="glossary-term">Universe (Universal Set):</span> The set of all elements under consideration in a particular context.</p>
<p><span class="glossary-term">Vacuous Truth:</span> A conditional statement that is true because its hypothesis is false.</p>
<p><span class="glossary-term">Venn Diagram:</span> A visual representation of set relationships using overlapping shapes.</p>
</div>
<div style="margin-top: 60px; padding: 30px; background: #1a1a1a; color: #fff; text-align: center; border-radius: 8px;">
<h3 style="color: #ffd700; margin-bottom: 15px;">Study Tips</h3>
<p>Master these concepts through practice. Work problems daily, connect ideas across topics, and always understand <em>why</em> methods work, not just how to apply them. Discrete mathematics is the foundation of computer science—every algorithm, data structure, and complexity analysis builds on these principles.</p>
</div>
</div>
</body>
</html>