Discrete Mathematics \u2013 University Level \u2013 Pak Notes Hub<\/title>\r\n <link href=\"https:\/\/fonts.googleapis.com\/css2?family=Inter:wght@400;500;600;700&family=Fira+Code:wght@400;500&display=swap\" rel=\"stylesheet\"\/>\r\n <style>\r\n *, *::before, *::after { box-sizing: border-box; margin: 0; padding: 0; }\r\n :root {\r\n --green:#1a7a4a; --green-dark:#145f38; --green-light:#e8f5ee;\r\n --teal:#17a589; --accent:#f0b127; --dark:#1c2833; --mid:#566573;\r\n --light:#f4f6f7; --code-bg:#f0f4f8; --code-border:#2e86c1;\r\n --note-bg:#fef9e7; --note-border:#f0b127; --white:#ffffff;\r\n --radius:10px; --shadow:0 4px 24px rgba(26,122,74,.10);\r\n }\r\n html { scroll-behavior:smooth; }\r\n body { font-family:'Inter',sans-serif; background:#f2f6f3; color:var(--dark); line-height:1.7; font-size:15px; }\r\n\r\n \/* NAV *\/\r\n nav { position:sticky; top:0; z-index:100; background:var(--green-dark); padding:0 2rem; display:flex; align-items:center; justify-content:space-between; height:56px; box-shadow:0 2px 12px rgba(0,0,0,.25); }\r\n .nav-brand { color:#fff; font-weight:700; font-size:1.05rem; }\r\n .nav-brand span { color:#a9dfbf; }\r\n .nav-links { display:flex; gap:1.2rem; }\r\n .nav-links a { color:#d5f5e3; font-size:.85rem; font-weight:500; text-decoration:none; transition:color .2s; }\r\n .nav-links a:hover { color:#fff; }\r\n\r\n \/* HERO *\/\r\n .hero { background:linear-gradient(135deg,var(--green) 0%,#145f38 60%,#0d4527 100%); padding:5rem 2rem 4rem; text-align:center; position:relative; overflow:hidden; }\r\n .hero::before { content:'\u2211'; position:absolute; right:6%; top:50%; transform:translateY(-50%); font-size:9rem; font-family:'Times New Roman',serif; color:rgba(255,255,255,.06); font-weight:700; pointer-events:none; }\r\n .hero-tag { display:inline-block; background:rgba(255,255,255,.12); color:#a9dfbf; font-size:.78rem; font-weight:600; letter-spacing:1.5px; text-transform:uppercase; padding:.35rem 1rem; border-radius:100px; margin-bottom:1.2rem; border:1px solid rgba(169,223,163,.3); }\r\n .hero h1 { color:#fff; font-size:clamp(1.8rem,5vw,3rem); font-weight:700; line-height:1.15; margin-bottom:.8rem; }\r\n .hero h1 span { color:#a9dfbf; }\r\n .hero p { color:#d5f5e3; font-size:1.05rem; max-width:580px; margin:0 auto 2rem; }\r\n .hero-pills { display:flex; flex-wrap:wrap; justify-content:center; gap:.7rem; }\r\n .pill { background:rgba(255,255,255,.13); color:#e8f5ee; padding:.45rem 1.1rem; border-radius:100px; font-size:.82rem; font-weight:500; border:1px solid rgba(255,255,255,.18); }\r\n\r\n \/* LAYOUT *\/\r\n .page-wrap { max-width:940px; margin:0 auto; padding:2.5rem 1.5rem 4rem; display:grid; grid-template-columns:235px 1fr; gap:2.5rem; align-items:start; }\r\n\r\n \/* SIDEBAR *\/\r\n .sidebar { position:sticky; top:72px; background:var(--white); border-radius:var(--radius); box-shadow:var(--shadow); overflow:hidden; }\r\n .sidebar-title { background:var(--green); color:#fff; font-size:.75rem; font-weight:700; letter-spacing:1.2px; text-transform:uppercase; padding:.85rem 1.1rem; }\r\n .toc-list { list-style:none; padding:.5rem 0; max-height:calc(100vh - 130px); overflow-y:auto; }\r\n .toc-list li a { display:flex; align-items:center; gap:.55rem; padding:.4rem 1.1rem; color:var(--mid); font-size:.81rem; font-weight:500; text-decoration:none; transition:all .18s; border-left:3px solid transparent; }\r\n .toc-list li a:hover,.toc-list li a.active { color:var(--green); background:var(--green-light); border-left-color:var(--green); }\r\n .toc-num { display:inline-flex; align-items:center; justify-content:center; min-width:20px; height:20px; border-radius:4px; background:var(--green-light); color:var(--green); font-size:.7rem; font-weight:700; flex-shrink:0; }\r\n .toc-list li a.active .toc-num { background:var(--green); color:#fff; }\r\n\r\n \/* UNIT CARD *\/\r\n .unit { background:var(--white); border-radius:var(--radius); box-shadow:var(--shadow); margin-bottom:2.5rem; overflow:hidden; scroll-margin-top:72px; }\r\n .unit-header { background:linear-gradient(100deg,var(--green) 0%,#1d9560 100%); padding:1.4rem 1.8rem; }\r\n .unit-num-badge { background:rgba(255,255,255,.18); color:#a9dfbf; font-size:.72rem; font-weight:700; letter-spacing:1px; text-transform:uppercase; padding:.3rem .75rem; border-radius:100px; }\r\n .unit-header h2 { color:#fff; font-size:1.25rem; font-weight:700; line-height:1.25; margin-top:.35rem; }\r\n .unit-header p { color:#c8f0d8; font-size:.85rem; margin-top:.2rem; }\r\n .unit-body { padding:1.8rem; }\r\n\r\n \/* HEADINGS & TEXT *\/\r\n .unit-body h3 { font-size:1rem; font-weight:700; color:var(--green); margin:1.6rem 0 .7rem; padding-left:.85rem; border-left:3px solid var(--green); line-height:1.3; }\r\n .unit-body h3:first-child { margin-top:0; }\r\n .unit-body p { color:var(--dark); margin-bottom:.7rem; }\r\n .unit-body ul { list-style:none; padding:0; margin:.5rem 0 1rem; }\r\n .unit-body ul li { padding:.3rem 0 .3rem 1.5rem; position:relative; color:var(--dark); font-size:.93rem; }\r\n .unit-body ul li::before { content:'\u27a4'; position:absolute; left:0; color:var(--teal); font-size:.75rem; top:.45rem; }\r\n .unit-body code, .icode { font-family:'Fira Code',monospace; background:#eef2f5; color:#1a5276; padding:.1rem .4rem; border-radius:4px; font-size:.85em; }\r\n\r\n \/* CODE BLOCK *\/\r\n .code-block { background:var(--code-bg); border-left:4px solid var(--code-border); border-radius:6px; padding:1.1rem 1.3rem; margin:.9rem 0 1rem; overflow-x:auto; }\r\n .code-block pre { font-family:'Fira Code',monospace; font-size:.83rem; color:#1a3a54; line-height:1.75; white-space:pre; }\r\n .cm { color:#7f8c8d; } .kw { color:#1a5276; font-weight:600; } .st { color:#1e8449; }\r\n\r\n \/* TABLES *\/\r\n .data-table { width:100%; border-collapse:collapse; margin:.9rem 0 1.2rem; font-size:.87rem; border-radius:8px; overflow:hidden; box-shadow:0 1px 6px rgba(0,0,0,.06); }\r\n .data-table thead th { background:var(--green); color:#fff; padding:.7rem 1rem; text-align:left; font-weight:600; font-size:.82rem; }\r\n .data-table tbody tr:nth-child(even) { background:var(--green-light); }\r\n .data-table tbody tr:hover { background:#d4efdf; }\r\n .data-table td { padding:.6rem 1rem; border-bottom:1px solid #dce8e0; vertical-align:top; }\r\n .data-table td:first-child { font-weight:600; color:var(--green-dark); }\r\n\r\n \/* BOXES *\/\r\n .info-box { background:var(--note-bg); border:1px solid var(--note-border); border-radius:7px; padding:.85rem 1.1rem; margin:.9rem 0; font-size:.88rem; line-height:1.6; color:#7d6608; display:flex; align-items:flex-start; gap:.7rem; }\r\n .practice { background:var(--green-light); border:1.5px dashed var(--green); border-radius:8px; padding:.85rem 1.1rem; margin-top:1.4rem; color:var(--green-dark); font-size:.88rem; font-weight:500; }\r\n\r\n \/* FEATURE GRID *\/\r\n .feature-grid { display:grid; grid-template-columns:repeat(auto-fill,minmax(210px,1fr)); gap:.6rem; margin:.9rem 0 1.2rem; }\r\n .feature-item { background:var(--green-light); border-radius:7px; padding:.6rem .9rem; font-size:.85rem; display:flex; align-items:center; gap:.5rem; color:var(--green-dark); border:1px solid #a2d9b5; font-weight:500; }\r\n\r\n \/* CONCEPT GRID (cards) *\/\r\n .concept-grid { display:grid; grid-template-columns:repeat(auto-fill,minmax(190px,1fr)); gap:.8rem; margin:.9rem 0 1.2rem; }\r\n .concept-card { background:var(--green-light); border:1px solid #a2d9b5; border-radius:8px; padding:.85rem 1rem; }\r\n .concept-card .concept-name { font-weight:700; color:var(--green); font-size:.92rem; margin-bottom:.3rem; }\r\n .concept-card .concept-rule { font-size:.8rem; color:var(--mid); }\r\n\r\n \/* TOC CARD *\/\r\n #toc-section { background:var(--white); border-radius:var(--radius); box-shadow:var(--shadow); margin-bottom:2.5rem; overflow:hidden; }\r\n .toc-card-header { background:linear-gradient(100deg,var(--green) 0%,#1d9560 100%); padding:1.2rem 1.8rem; }\r\n .toc-card-header h2 { color:#fff; font-size:1.2rem; font-weight:700; }\r\n .toc-card-body { padding:1.4rem 1.8rem; }\r\n .toc-grid { display:grid; grid-template-columns:repeat(auto-fill,minmax(250px,1fr)); gap:.6rem; }\r\n .toc-item { background:var(--light); border-radius:7px; padding:.65rem 1rem; display:flex; align-items:center; gap:.75rem; text-decoration:none; color:var(--dark); font-size:.86rem; font-weight:500; border:1px solid #d5e5db; transition:all .18s; }\r\n .toc-item:hover { background:var(--green-light); border-color:var(--green); color:var(--green); transform:translateY(-1px); }\r\n .toc-badge { background:var(--green); color:#fff; font-size:.7rem; font-weight:700; min-width:22px; height:22px; border-radius:5px; display:inline-flex; align-items:center; justify-content:center; flex-shrink:0; }\r\n\r\n \/* CONGRATS *\/\r\n .congrats { background:linear-gradient(135deg,var(--green) 0%,#145f38 100%); border-radius:var(--radius); padding:2.5rem 2rem; text-align:center; color:#fff; margin-bottom:2.5rem; box-shadow:var(--shadow); }\r\n .congrats h2 { font-size:1.8rem; margin-bottom:.5rem; }\r\n .congrats p { color:#d5f5e3; font-size:1rem; }\r\n\r\n \/* PROGRESS + BACK TOP *\/\r\n .progress-bar { position:fixed; top:0; left:0; height:3px; background:var(--accent); z-index:200; transition:width .1s linear; width:0%; }\r\n #back-top { position:fixed; bottom:2rem; right:2rem; background:var(--green); color:#fff; width:42px; height:42px; border-radius:50%; border:none; cursor:pointer; font-size:1.1rem; box-shadow:0 4px 14px rgba(26,122,74,.35); display:flex; align-items:center; justify-content:center; opacity:0; transition:opacity .25s,transform .25s; pointer-events:none; }\r\n #back-top.visible { opacity:1; pointer-events:auto; }\r\n #back-top:hover { transform:translateY(-2px); }\r\n\r\n @media(max-width:720px){ .page-wrap{grid-template-columns:1fr;} .sidebar{position:static;display:none;} .hero::before{display:none;} nav .nav-links{display:none;} }\r\n <\/style>\r\n<\/head>\r\n<body>\r\n\r\n<div class=\"progress-bar\" id=\"progress\"><\/div>\r\n\r\n<nav>\r\n <div class=\"nav-brand\">Pak <span>Notes Hub<\/span><\/div>\r\n <div class=\"nav-links\">\r\n <a href=\"#toc-section\">Course Outline<\/a>\r\n <a href=\"#unit-1\">Start Learning<\/a>\r\n <a href=\"#unit-5\">Induction<\/a>\r\n <a href=\"#unit-8\">Graph Theory<\/a>\r\n <\/div>\r\n<\/nav>\r\n\r\n<section class=\"hero\">\r\n <div class=\"hero-tag\">\ud83d\udcd0 University Level \u2014 BS CS \/ BS IT<\/div>\r\n <h1>Discrete Mathematics<br\/><span>Complete Notes<\/span><\/h1>\r\n <p>Logic \u00b7 Sets \u00b7 Graph Theory \u00b7 Combinatorics \u00b7 Proofs \u2014 All in Easy English<\/p>\r\n <div class=\"hero-pills\">\r\n <span class=\"pill\">\ud83d\udd22 14 Units<\/span>\r\n <span class=\"pill\">\ud83c\udf93 University Level<\/span>\r\n <span class=\"pill\">\ud83d\udcca Examples<\/span>\r\n <span class=\"pill\">\ud83d\udcdd Practice Tasks<\/span>\r\n <span class=\"pill\">\ud83e\uddee Problem Solving<\/span>\r\n <\/div>\r\n<\/section>\r\n\r\n<div class=\"page-wrap\">\r\n\r\n \r\n <aside class=\"sidebar\">\r\n <div class=\"sidebar-title\">\ud83d\udccb Course Contents<\/div>\r\n <ul class=\"toc-list\" id=\"toc-nav\">\r\n <li><a href=\"#toc-section\"><span class=\"toc-num\">\ud83d\udccb<\/span> Contents<\/a><\/li>\r\n <li><a href=\"#unit-1\"><span class=\"toc-num\">1<\/span> Intro to Discrete Math<\/a><\/li>\r\n <li><a href=\"#unit-2\"><span class=\"toc-num\">2<\/span> Propositional Logic<\/a><\/li>\r\n <li><a href=\"#unit-3\"><span class=\"toc-num\">3<\/span> Predicate Logic<\/a><\/li>\r\n <li><a href=\"#unit-4\"><span class=\"toc-num\">4<\/span> Sets & Operations<\/a><\/li>\r\n <li><a href=\"#unit-5\"><span class=\"toc-num\">5<\/span> Relations & Functions<\/a><\/li>\r\n <li><a href=\"#unit-6\"><span class=\"toc-num\">6<\/span> Mathematical Induction<\/a><\/li>\r\n <li><a href=\"#unit-7\"><span class=\"toc-num\">7<\/span> Combinatorics<\/a><\/li>\r\n <li><a href=\"#unit-8\"><span class=\"toc-num\">8<\/span> Probability<\/a><\/li>\r\n <li><a href=\"#unit-9\"><span class=\"toc-num\">9<\/span> Graph Theory Basics<\/a><\/li>\r\n <li><a href=\"#unit-10\"><span class=\"toc-num\">10<\/span> Trees<\/a><\/li>\r\n <li><a href=\"#unit-11\"><span class=\"toc-num\">11<\/span> Boolean Algebra<\/a><\/li>\r\n <li><a href=\"#unit-12\"><span class=\"toc-num\">12<\/span> Recurrence Relations<\/a><\/li>\r\n <li><a href=\"#unit-13\"><span class=\"toc-num\">13<\/span> Counting Principles<\/a><\/li>\r\n <li><a href=\"#unit-14\"><span class=\"toc-num\">14<\/span> Proof Techniques<\/a><\/li>\r\n <\/ul>\r\n <\/aside>\r\n\r\n <main>\r\n\r\n \r\n <div id=\"toc-section\">\r\n <div class=\"toc-card-header\"><h2>\ud83d\udccb Table of Contents \u2014 14 Units<\/h2><\/div>\r\n <div class=\"toc-card-body\">\r\n <div class=\"toc-grid\">\r\n <a class=\"toc-item\" href=\"#unit-1\"><span class=\"toc-badge\">1<\/span> Introduction to Discrete Math<\/a>\r\n <a class=\"toc-item\" href=\"#unit-2\"><span class=\"toc-badge\">2<\/span> Propositional Logic<\/a>\r\n <a class=\"toc-item\" href=\"#unit-3\"><span class=\"toc-badge\">3<\/span> Predicate Logic & Quantifiers<\/a>\r\n <a class=\"toc-item\" href=\"#unit-4\"><span class=\"toc-badge\">4<\/span> Sets & Set Operations<\/a>\r\n <a class=\"toc-item\" href=\"#unit-5\"><span class=\"toc-badge\">5<\/span> Relations & Functions<\/a>\r\n <a class=\"toc-item\" href=\"#unit-6\"><span class=\"toc-badge\">6<\/span> Mathematical Induction<\/a>\r\n <a class=\"toc-item\" href=\"#unit-7\"><span class=\"toc-badge\">7<\/span> Combinatorics<\/a>\r\n <a class=\"toc-item\" href=\"#unit-8\"><span class=\"toc-badge\">8<\/span> Discrete Probability<\/a>\r\n <a class=\"toc-item\" href=\"#unit-9\"><span class=\"toc-badge\">9<\/span> Graph Theory Basics<\/a>\r\n <a class=\"toc-item\" href=\"#unit-10\"><span class=\"toc-badge\">10<\/span> Trees<\/a>\r\n <a class=\"toc-item\" href=\"#unit-11\"><span class=\"toc-badge\">11<\/span> Boolean Algebra<\/a>\r\n <a class=\"toc-item\" href=\"#unit-12\"><span class=\"toc-badge\">12<\/span> Recurrence Relations<\/a>\r\n <a class=\"toc-item\" href=\"#unit-13\"><span class=\"toc-badge\">13<\/span> Counting Principles<\/a>\r\n <a class=\"toc-item\" href=\"#unit-14\"><span class=\"toc-badge\">14<\/span> Proof Techniques<\/a>\r\n <\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-1\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 1<\/span>\r\n <h2>Introduction to Discrete Mathematics<\/h2>\r\n <p>What is Discrete Math and why do we study it?<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is Discrete Mathematics?<\/h3>\r\n <p><strong>Discrete Mathematics<\/strong> is the study of mathematical structures that are fundamentally <strong>discrete<\/strong> (separate, distinct) rather than continuous. It deals with objects that can only take specific, separated values.<\/p>\r\n <div class=\"info-box\">\ud83d\udca1 Think of discrete vs continuous like this: discrete is like counting people (1, 2, 3...), continuous is like measuring water (1.5 liters, 2.3 liters). Discrete Math deals with countable, distinct items!<\/div>\r\n\r\n <h3>Discrete vs Continuous Mathematics<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Feature<\/th><th>Discrete Mathematics<\/th><th>Continuous Mathematics<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Values<\/td><td>Separate, distinct, countable<\/td><td>Unbroken, smooth range<\/td><\/tr>\r\n <tr><td>Examples<\/td><td>Integers: 1, 2, 3, 4...<\/td><td>Real numbers: 1.5, 2.73, \u03c0<\/td><\/tr>\r\n <tr><td>Graph Type<\/td><td>Points, nodes, discrete steps<\/td><td>Smooth curves, flowing lines<\/td><\/tr>\r\n <tr><td>Operations<\/td><td>Counting, listing, logical operations<\/td><td>Calculus, limits, derivatives<\/td><\/tr>\r\n <tr><td>Used In<\/td><td>Computer Science, algorithms, cryptography<\/td><td>Physics, engineering, calculus<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Why is Discrete Math Important for Computer Science?<\/h3>\r\n <ul>\r\n <li><strong>Algorithm Design<\/strong> \u2014 Understanding complexity and efficiency<\/li>\r\n <li><strong>Data Structures<\/strong> \u2014 Trees, graphs, and networks<\/li>\r\n <li><strong>Logic & Proofs<\/strong> \u2014 Foundation of program correctness<\/li>\r\n <li><strong>Cryptography<\/strong> \u2014 Number theory and security<\/li>\r\n <li><strong>Database Theory<\/strong> \u2014 Relations and set operations<\/li>\r\n <li><strong>Artificial Intelligence<\/strong> \u2014 Logic, probability, graph search<\/li>\r\n <li><strong>Networking<\/strong> \u2014 Graph theory for network topology<\/li>\r\n <\/ul>\r\n\r\n <h3>Main Topics in Discrete Mathematics<\/h3>\r\n <div class=\"concept-grid\">\r\n <div class=\"concept-card\">\r\n <div class=\"concept-name\">Logic<\/div>\r\n <div class=\"concept-rule\">Propositional and predicate logic, truth tables<\/div>\r\n <\/div>\r\n <div class=\"concept-card\">\r\n <div class=\"concept-name\">Sets<\/div>\r\n <div class=\"concept-rule\">Collections of objects, operations, Venn diagrams<\/div>\r\n <\/div>\r\n <div class=\"concept-card\">\r\n <div class=\"concept-name\">Relations & Functions<\/div>\r\n <div class=\"concept-rule\">Mappings between sets, properties<\/div>\r\n <\/div>\r\n <div class=\"concept-card\">\r\n <div class=\"concept-name\">Combinatorics<\/div>\r\n <div class=\"concept-rule\">Counting techniques, permutations, combinations<\/div>\r\n <\/div>\r\n <div class=\"concept-card\">\r\n <div class=\"concept-name\">Graph Theory<\/div>\r\n <div class=\"concept-rule\">Networks, paths, trees, connectivity<\/div>\r\n <\/div>\r\n <div class=\"concept-card\">\r\n <div class=\"concept-name\">Proofs<\/div>\r\n <div class=\"concept-rule\">Mathematical reasoning, induction<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> Give 3 examples of discrete quantities and 3 examples of continuous quantities from real life. Explain why computer memory is discrete, not continuous.<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-2\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 2<\/span>\r\n <h2>Propositional Logic<\/h2>\r\n <p>Statements, truth values, and logical operators.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is a Proposition?<\/h3>\r\n <p>A <strong>proposition<\/strong> (or statement) is a declarative sentence that is either <strong>true (T)<\/strong> or <strong>false (F)<\/strong>, but not both. The truth value is either 1 (true) or 0 (false).<\/p>\r\n \r\n <h3>Examples of Propositions<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Statement<\/th><th>Proposition?<\/th><th>Reason<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>\"2 + 2 = 4\"<\/td><td>\u2713 Yes<\/td><td>Clearly true<\/td><\/tr>\r\n <tr><td>\"Paris is the capital of France\"<\/td><td>\u2713 Yes<\/td><td>True statement<\/td><\/tr>\r\n <tr><td>\"x + 5 = 10\"<\/td><td>\u2717 No<\/td><td>Depends on value of x<\/td><\/tr>\r\n <tr><td>\"Close the door!\"<\/td><td>\u2717 No<\/td><td>Command, not a statement<\/td><\/tr>\r\n <tr><td>\"What time is it?\"<\/td><td>\u2717 No<\/td><td>Question, not a statement<\/td><\/tr>\r\n <tr><td>\"This sentence is false\"<\/td><td>\u2717 No<\/td><td>Paradox \u2014 neither true nor false<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Logical Operators (Connectives)<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Operator<\/th><th>Symbol<\/th><th>Name<\/th><th>Meaning<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>NOT<\/td><td>\u00ac or ~<\/td><td>Negation<\/td><td>Opposite truth value<\/td><\/tr>\r\n <tr><td>AND<\/td><td>\u2227<\/td><td>Conjunction<\/td><td>Both must be true<\/td><\/tr>\r\n <tr><td>OR<\/td><td>\u2228<\/td><td>Disjunction<\/td><td>At least one must be true<\/td><\/tr>\r\n <tr><td>IF-THEN<\/td><td>\u2192<\/td><td>Implication<\/td><td>If p then q<\/td><\/tr>\r\n <tr><td>IF AND ONLY IF<\/td><td>\u2194<\/td><td>Biconditional<\/td><td>Both have same truth value<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Truth Tables<\/h3>\r\n \r\n <h3>1. Negation (NOT)<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>p<\/th><th>\u00acp<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>T<\/td><td>F<\/td><\/tr>\r\n <tr><td>F<\/td><td>T<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>2. Conjunction (AND)<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>p<\/th><th>q<\/th><th>p \u2227 q<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>T<\/td><td>T<\/td><td>T<\/td><\/tr>\r\n <tr><td>T<\/td><td>F<\/td><td>F<\/td><\/tr>\r\n <tr><td>F<\/td><td>T<\/td><td>F<\/td><\/tr>\r\n <tr><td>F<\/td><td>F<\/td><td>F<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>3. Disjunction (OR)<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>p<\/th><th>q<\/th><th>p \u2228 q<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>T<\/td><td>T<\/td><td>T<\/td><\/tr>\r\n <tr><td>T<\/td><td>F<\/td><td>T<\/td><\/tr>\r\n <tr><td>F<\/td><td>T<\/td><td>T<\/td><\/tr>\r\n <tr><td>F<\/td><td>F<\/td><td>F<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>4. Implication (IF-THEN)<\/h3>\r\n <p>p \u2192 q means \"if p then q\". It's false only when p is true and q is false.<\/p>\r\n <table class=\"data-table\">\r\n <thead><tr><th>p<\/th><th>q<\/th><th>p \u2192 q<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>T<\/td><td>T<\/td><td>T<\/td><\/tr>\r\n <tr><td>T<\/td><td>F<\/td><td>F<\/td><\/tr>\r\n <tr><td>F<\/td><td>T<\/td><td>T<\/td><\/tr>\r\n <tr><td>F<\/td><td>F<\/td><td>T<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>5. Biconditional (IF AND ONLY IF)<\/h3>\r\n <p>p \u2194 q is true when both have the same truth value.<\/p>\r\n <table class=\"data-table\">\r\n <thead><tr><th>p<\/th><th>q<\/th><th>p \u2194 q<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>T<\/td><td>T<\/td><td>T<\/td><\/tr>\r\n <tr><td>T<\/td><td>F<\/td><td>F<\/td><\/tr>\r\n <tr><td>F<\/td><td>T<\/td><td>F<\/td><\/tr>\r\n <tr><td>F<\/td><td>F<\/td><td>T<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <div class=\"info-box\">\ud83d\udca1 Memory Trick: AND (\u2227) is true only when BOTH are true. OR (\u2228) is true when AT LEAST ONE is true. Implication (\u2192) is false ONLY when true leads to false.<\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> Construct a truth table for (p \u2227 q) \u2192 r. Also, determine if \"If it rains, then the ground is wet\" is true when: (a) it rains and ground is wet (b) it doesn't rain and ground is dry.<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-3\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 3<\/span>\r\n <h2>Predicate Logic & Quantifiers<\/h2>\r\n <p>Variables, predicates, and universal\/existential quantifiers.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is Predicate Logic?<\/h3>\r\n <p><strong>Predicate logic<\/strong> (also called first-order logic) extends propositional logic by dealing with statements that contain variables. A <strong>predicate<\/strong> is a statement whose truth value depends on one or more variables.<\/p>\r\n \r\n <h3>Predicates vs Propositions<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Type<\/th><th>Example<\/th><th>Explanation<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Proposition<\/td><td>\"5 is odd\"<\/td><td>Fixed truth value (True)<\/td><\/tr>\r\n <tr><td>Predicate<\/td><td>\"x is odd\"<\/td><td>Truth depends on x<\/td><\/tr>\r\n <tr><td>Predicate<\/td><td>P(x): \"x > 10\"<\/td><td>True if x > 10, false otherwise<\/td><\/tr>\r\n <tr><td>Predicate<\/td><td>Q(x,y): \"x + y = 10\"<\/td><td>Depends on both x and y<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Quantifiers<\/h3>\r\n <p>Quantifiers allow us to make statements about \"all\" or \"some\" elements in a domain.<\/p>\r\n \r\n <h3>1. Universal Quantifier (\u2200)<\/h3>\r\n <p><strong>Symbol:<\/strong> \u2200 (for all, for every)<\/p>\r\n <p><strong>Meaning:<\/strong> \u2200x P(x) means \"P(x) is true for ALL values of x in the domain\"<\/p>\r\n <div class=\"code-block\"><pre>Example:\r\n\u2200x (x\u00b2 \u2265 0) means \"For all real numbers x, x\u00b2 is non-negative\"\r\nThis is TRUE for all real numbers.\r\n\r\n\u2200x (x > 5) means \"For all x, x is greater than 5\"\r\nThis is FALSE (not all numbers are > 5).<\/pre><\/div>\r\n\r\n <h3>2. Existential Quantifier (\u2203)<\/h3>\r\n <p><strong>Symbol:<\/strong> \u2203 (there exists, for some)<\/p>\r\n <p><strong>Meaning:<\/strong> \u2203x P(x) means \"P(x) is true for AT LEAST ONE value of x\"<\/p>\r\n <div class=\"code-block\"><pre>Example:\r\n\u2203x (x\u00b2 = 16) means \"There exists an x such that x\u00b2 = 16\"\r\nThis is TRUE (x = 4 or x = -4).\r\n\r\n\u2203x (x\u00b2 = -1) means \"There exists a real x such that x\u00b2 = -1\"\r\nThis is FALSE for real numbers.<\/pre><\/div>\r\n\r\n <h3>Negation of Quantifiers<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Statement<\/th><th>Negation<\/th><th>Explanation<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>\u2200x P(x)<\/td><td>\u2203x \u00acP(x)<\/td><td>\"Not all\" means \"at least one is not\"<\/td><\/tr>\r\n <tr><td>\u2203x P(x)<\/td><td>\u2200x \u00acP(x)<\/td><td>\"None exists\" means \"all are not\"<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Multiple Quantifiers<\/h3>\r\n <p>Order matters when using multiple quantifiers!<\/p>\r\n <div class=\"code-block\"><pre>\u2200x \u2203y (x + y = 0)\r\n\"For every x, there exists a y such that x + y = 0\"\r\nTRUE (for any x, we can choose y = -x)\r\n\r\n\u2203y \u2200x (x + y = 0)\r\n\"There exists a y such that for all x, x + y = 0\"\r\nFALSE (no single y works for ALL x)<\/pre><\/div>\r\n\r\n <h3>Translating English to Logic<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>English Statement<\/th><th>Logical Form<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>All students passed<\/td><td>\u2200x (Student(x) \u2192 Passed(x))<\/td><\/tr>\r\n <tr><td>Some student failed<\/td><td>\u2203x (Student(x) \u2227 Failed(x))<\/td><\/tr>\r\n <tr><td>No student cheated<\/td><td>\u00ac\u2203x (Student(x) \u2227 Cheated(x))<\/td><\/tr>\r\n <tr><td>Not all birds can fly<\/td><td>\u00ac\u2200x (Bird(x) \u2192 CanFly(x))<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <div class=\"info-box\">\ud83d\udca1 Key Rule: \u2200x usually pairs with \u2192 (implication), while \u2203x usually pairs with \u2227 (and). Example: \"All dogs bark\" = \u2200x (Dog(x) \u2192 Barks(x)), \"Some cats are black\" = \u2203x (Cat(x) \u2227 Black(x))<\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> Translate to logic: (1) \"Every number has a successor\" (2) \"There is a smallest prime number\" (3) \"Not every equation has a solution\". Also find the negation of \u2200x \u2203y (x < y).<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-4\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 4<\/span>\r\n <h2>Sets & Set Operations<\/h2>\r\n <p>Collections of objects and operations on them.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is a Set?<\/h3>\r\n <p>A <strong>set<\/strong> is a well-defined collection of distinct objects, called <strong>elements<\/strong> or <strong>members<\/strong>. Sets are usually denoted by capital letters (A, B, C) and elements by lowercase letters.<\/p>\r\n <div class=\"code-block\"><pre>A = {1, 2, 3, 4, 5}\r\nB = {red, blue, green}\r\nC = {x | x is an even number} \u2190 set-builder notation\r\n\r\n\u2208 means \"is an element of\"\r\n\u2209 means \"is not an element of\"\r\n\r\n3 \u2208 A (3 is in A)\r\n6 \u2209 A (6 is not in A)<\/pre><\/div>\r\n\r\n <h3>Types of Sets<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Type<\/th><th>Definition<\/th><th>Example<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Finite Set<\/td><td>Has limited number of elements<\/td><td>A = {1, 2, 3}<\/td><\/tr>\r\n <tr><td>Infinite Set<\/td><td>Has unlimited elements<\/td><td>\u2115 = {1, 2, 3, ...}<\/td><\/tr>\r\n <tr><td>Empty Set<\/td><td>Contains no elements<\/td><td>\u2205 or { }<\/td><\/tr>\r\n <tr><td>Singleton Set<\/td><td>Contains exactly one element<\/td><td>{5}<\/td><\/tr>\r\n <tr><td>Universal Set<\/td><td>Contains all elements under consideration<\/td><td>U<\/td><\/tr>\r\n <tr><td>Subset<\/td><td>All elements of A are in B<\/td><td>A \u2286 B<\/td><\/tr>\r\n <tr><td>Proper Subset<\/td><td>A \u2286 B but A \u2260 B<\/td><td>A \u2282 B<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Set Operations<\/h3>\r\n \r\n <h3>1. Union (\u222a)<\/h3>\r\n <p>A \u222a B contains all elements that are in A OR in B (or in both).<\/p>\r\n <div class=\"code-block\"><pre>A = {1, 2, 3}\r\nB = {3, 4, 5}\r\nA \u222a B = {1, 2, 3, 4, 5}<\/pre><\/div>\r\n\r\n <h3>2. Intersection (\u2229)<\/h3>\r\n <p>A \u2229 B contains only elements that are in BOTH A AND B.<\/p>\r\n <div class=\"code-block\"><pre>A = {1, 2, 3}\r\nB = {3, 4, 5}\r\nA \u2229 B = {3}<\/pre><\/div>\r\n\r\n <h3>3. Difference (\u2212)<\/h3>\r\n <p>A \u2212 B contains elements in A but NOT in B.<\/p>\r\n <div class=\"code-block\"><pre>A = {1, 2, 3}\r\nB = {3, 4, 5}\r\nA \u2212 B = {1, 2}<\/pre><\/div>\r\n\r\n <h3>4. Complement (A' or \u0100)<\/h3>\r\n <p>A' contains all elements in the universal set U that are NOT in A.<\/p>\r\n <div class=\"code-block\"><pre>U = {1, 2, 3, 4, 5, 6}\r\nA = {1, 2, 3}\r\nA' = {4, 5, 6}<\/pre><\/div>\r\n\r\n <h3>5. Cartesian Product (\u00d7)<\/h3>\r\n <p>A \u00d7 B is the set of all ordered pairs (a, b) where a \u2208 A and b \u2208 B.<\/p>\r\n <div class=\"code-block\"><pre>A = {1, 2}\r\nB = {x, y}\r\nA \u00d7 B = {(1,x), (1,y), (2,x), (2,y)}\r\n\r\n|A \u00d7 B| = |A| \u00d7 |B| = 2 \u00d7 2 = 4<\/pre><\/div>\r\n\r\n <h3>Set Identities (Laws)<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Law<\/th><th>Union Form<\/th><th>Intersection Form<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Identity<\/td><td>A \u222a \u2205 = A<\/td><td>A \u2229 U = A<\/td><\/tr>\r\n <tr><td>Domination<\/td><td>A \u222a U = U<\/td><td>A \u2229 \u2205 = \u2205<\/td><\/tr>\r\n <tr><td>Idempotent<\/td><td>A \u222a A = A<\/td><td>A \u2229 A = A<\/td><\/tr>\r\n <tr><td>Complement<\/td><td>A \u222a A' = U<\/td><td>A \u2229 A' = \u2205<\/td><\/tr>\r\n <tr><td>Commutative<\/td><td>A \u222a B = B \u222a A<\/td><td>A \u2229 B = B \u2229 A<\/td><\/tr>\r\n <tr><td>Associative<\/td><td>(A\u222aB)\u222aC = A\u222a(B\u222aC)<\/td><td>(A\u2229B)\u2229C = A\u2229(B\u2229C)<\/td><\/tr>\r\n <tr><td>Distributive<\/td><td>A\u222a(B\u2229C) = (A\u222aB)\u2229(A\u222aC)<\/td><td>A\u2229(B\u222aC) = (A\u2229B)\u222a(A\u2229C)<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>De Morgan's Laws for Sets<\/h3>\r\n <div class=\"code-block\"><pre>(A \u222a B)' = A' \u2229 B'\r\n(A \u2229 B)' = A' \u222a B'\r\n\r\n\"The complement of a union is the intersection of complements\"\r\n\"The complement of an intersection is the union of complements\"<\/pre><\/div>\r\n\r\n <div class=\"info-box\">\ud83d\udca1 Venn Diagrams help visualize sets! Union combines circles, intersection is the overlap, difference removes one from another, complement is everything outside the circle.<\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> If A = {1,2,3,4}, B = {3,4,5,6}, C = {5,6,7,8}, find: (1) A \u222a B (2) A \u2229 B (3) A \u2212 B (4) (A \u222a B) \u2229 C. Also prove (A \u2229 B)' = A' \u222a B' using an example.<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-5\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 5<\/span>\r\n <h2>Relations & Functions<\/h2>\r\n <p>Mappings between sets and their properties.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is a Relation?<\/h3>\r\n <p>A <strong>relation<\/strong> R from set A to set B is a subset of the Cartesian product A \u00d7 B. It shows how elements of A are related to elements of B.<\/p>\r\n <div class=\"code-block\"><pre>A = {1, 2, 3}\r\nB = {4, 5}\r\nR = {(1,4), (2,5), (3,4)} \u2190 relation from A to B\r\n\r\nWe write: 1 R 4 (1 is related to 4)<\/pre><\/div>\r\n\r\n <h3>Types of Relations<\/h3>\r\n <p>For a relation R on a set A (from A to A):<\/p>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Property<\/th><th>Definition<\/th><th>Example<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Reflexive<\/td><td>Every element relates to itself: \u2200x (x R x)<\/td><td>\u2264 (every number \u2264 itself)<\/td><\/tr>\r\n <tr><td>Symmetric<\/td><td>If x R y then y R x<\/td><td>= (if x = y then y = x)<\/td><\/tr>\r\n <tr><td>Antisymmetric<\/td><td>If x R y and y R x, then x = y<\/td><td>\u2264 (if x\u2264y and y\u2264x, then x=y)<\/td><\/tr>\r\n <tr><td>Transitive<\/td><td>If x R y and y R z, then x R z<\/td><td>< (if x<y and y<z, then x<z)<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Equivalence Relation<\/h3>\r\n <p>A relation that is <strong>reflexive, symmetric, and transitive<\/strong> is called an equivalence relation.<\/p>\r\n <div class=\"code-block\"><pre>Example: \"=\" (equality) is an equivalence relation\r\n- Reflexive: x = x\r\n- Symmetric: if x = y, then y = x\r\n- Transitive: if x = y and y = z, then x = z<\/pre><\/div>\r\n\r\n <h3>What is a Function?<\/h3>\r\n <p>A <strong>function<\/strong> f from A to B (written f: A \u2192 B) is a special relation where every element in A is related to EXACTLY ONE element in B.<\/p>\r\n <div class=\"code-block\"><pre>f: A \u2192 B\r\nA is the <strong>domain<\/strong>\r\nB is the <strong>codomain<\/strong>\r\nThe set of actual output values is the <strong>range<\/strong>\r\n\r\nExample:\r\nf(x) = x\u00b2\r\nDomain: \u211d (all real numbers)\r\nCodomain: \u211d\r\nRange: [0, \u221e) (non-negative reals only)<\/pre><\/div>\r\n\r\n <h3>Types of Functions<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Type<\/th><th>Definition<\/th><th>Diagram<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>One-to-One (Injective)<\/td><td>Different inputs \u2192 different outputs<br\/>If f(x\u2081) = f(x\u2082), then x\u2081 = x\u2082<\/td><td>Each output has at most one input<\/td><\/tr>\r\n <tr><td>Onto (Surjective)<\/td><td>Every element in codomain is an output<br\/>Range = Codomain<\/td><td>Every output is used<\/td><\/tr>\r\n <tr><td>Bijective<\/td><td>Both one-to-one AND onto<\/td><td>Perfect pairing \u2014 each input has exactly one output, and vice versa<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Function Examples<\/h3>\r\n <div class=\"code-block\"><pre><strong>One-to-One but NOT Onto:<\/strong>\r\nf: \u211d \u2192 \u211d, f(x) = 2x\r\nOne-to-one: different x \u2192 different 2x\r\nNot onto: odd numbers never appear as outputs\r\n\r\n<strong>Onto but NOT One-to-One:<\/strong>\r\nf: \u211d \u2192 \u211d, f(x) = x\u00b2\r\nOnto [0,\u221e): all non-negative numbers are outputs\r\nNot one-to-one: f(2) = f(-2) = 4\r\n\r\n<strong>Bijective:<\/strong>\r\nf: \u211d \u2192 \u211d, f(x) = x + 5\r\nOne-to-one: different x \u2192 different x+5\r\nOnto: every real number y = x+5 for some x<\/pre><\/div>\r\n\r\n <h3>Composition of Functions<\/h3>\r\n <p>If f: A \u2192 B and g: B \u2192 C, then (g \u2218 f): A \u2192 C is defined as (g \u2218 f)(x) = g(f(x))<\/p>\r\n <div class=\"code-block\"><pre>f(x) = x + 3\r\ng(x) = 2x\r\n\r\n(g \u2218 f)(x) = g(f(x)) = g(x+3) = 2(x+3) = 2x + 6\r\n(f \u2218 g)(x) = f(g(x)) = f(2x) = 2x + 3\r\n\r\nNote: g \u2218 f \u2260 f \u2218 g (order matters!)<\/pre><\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> Let R = {(1,1), (2,2), (1,2), (2,1)} on set {1,2}. Check if R is reflexive, symmetric, and transitive. Also, determine if f(x) = 3x \u2212 5 is one-to-one, onto, or bijective from \u211d to \u211d.<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-6\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 6<\/span>\r\n <h2>Mathematical Induction<\/h2>\r\n <p>Proving statements for all natural numbers \u2014 the domino effect.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is Mathematical Induction?<\/h3>\r\n <p><strong>Mathematical induction<\/strong> is a proof technique used to prove statements about all natural numbers (or integers). Think of it like dominoes \u2014 if the first falls and each domino knocks down the next, all dominoes will fall!<\/p>\r\n <div class=\"info-box\">\ud83d\udca1 Induction has two steps: (1) Base Case \u2014 prove it's true for n=1 (first domino falls), (2) Inductive Step \u2014 prove if it's true for n=k, then it's also true for n=k+1 (each domino knocks the next).<\/div>\r\n\r\n <h3>Principle of Mathematical Induction<\/h3>\r\n <p>To prove a statement P(n) is true for all n \u2265 1:<\/p>\r\n <ul>\r\n <li><strong>Step 1 (Base Case):<\/strong> Prove P(1) is true<\/li>\r\n <li><strong>Step 2 (Inductive Hypothesis):<\/strong> Assume P(k) is true for some arbitrary k \u2265 1<\/li>\r\n <li><strong>Step 3 (Inductive Step):<\/strong> Using the assumption, prove P(k+1) is true<\/li>\r\n <li><strong>Conclusion:<\/strong> By induction, P(n) is true for all n \u2265 1<\/li>\r\n <\/ul>\r\n\r\n <h3>Example 1: Sum of First n Natural Numbers<\/h3>\r\n <p><strong>Prove:<\/strong> 1 + 2 + 3 + ... + n = n(n+1)\/2<\/p>\r\n <div class=\"code-block\"><pre><strong>Step 1: Base Case (n=1)<\/strong>\r\nLeft side: 1\r\nRight side: 1(1+1)\/2 = 1\r\n\u2713 True for n=1\r\n\r\n<strong>Step 2: Inductive Hypothesis<\/strong>\r\nAssume true for n=k:\r\n1 + 2 + 3 + ... + k = k(k+1)\/2\r\n\r\n<strong>Step 3: Inductive Step (prove for n=k+1)<\/strong>\r\nNeed to show: 1 + 2 + ... + k + (k+1) = (k+1)(k+2)\/2\r\n\r\nLeft side:\r\n= [1 + 2 + ... + k] + (k+1)\r\n= k(k+1)\/2 + (k+1) [using hypothesis]\r\n= k(k+1)\/2 + 2(k+1)\/2\r\n= [k(k+1) + 2(k+1)]\/2\r\n= (k+1)(k+2)\/2 [factoring]\r\n= Right side \u2713\r\n\r\n<strong>Conclusion:<\/strong> By induction, formula is true for all n \u2265 1.<\/pre><\/div>\r\n\r\n <h3>Example 2: Power Inequality<\/h3>\r\n <p><strong>Prove:<\/strong> 2\u207f > n for all n \u2265 1<\/p>\r\n <div class=\"code-block\"><pre><strong>Base Case (n=1):<\/strong>\r\n2\u00b9 = 2 > 1 \u2713\r\n\r\n<strong>Inductive Hypothesis:<\/strong>\r\nAssume 2^k > k for some k \u2265 1\r\n\r\n<strong>Inductive Step (prove 2^(k+1) > k+1):<\/strong>\r\n2^(k+1) = 2 \u00b7 2^k\r\n > 2 \u00b7 k [using hypothesis: 2^k > k]\r\n = k + k\r\n \u2265 k + 1 [since k \u2265 1]\r\n\u2234 2^(k+1) > k+1 \u2713\r\n\r\n<strong>Conclusion:<\/strong> By induction, 2\u207f > n for all n \u2265 1.<\/pre><\/div>\r\n\r\n <h3>Strong Induction<\/h3>\r\n <p>In <strong>strong induction<\/strong>, we assume P(1), P(2), ..., P(k) are ALL true (not just P(k)), then prove P(k+1).<\/p>\r\n <div class=\"code-block\"><pre>Regular Induction: Assume P(k) \u2192 Prove P(k+1)\r\nStrong Induction: Assume P(1)\u2227P(2)\u2227...\u2227P(k) \u2192 Prove P(k+1)\r\n\r\nUse strong induction when proving P(k+1) requires\r\ninformation from multiple previous cases.<\/pre><\/div>\r\n\r\n <h3>Common Mistakes in Induction<\/h3>\r\n <ul>\r\n <li><strong>Forgetting Base Case<\/strong> \u2014 Always prove for n=1 (or starting value)<\/li>\r\n <li><strong>Not Using Hypothesis<\/strong> \u2014 Must explicitly use P(k) assumption in step 3<\/li>\r\n <li><strong>Proving Wrong Direction<\/strong> \u2014 Must prove P(k) \u2192 P(k+1), not the reverse<\/li>\r\n <li><strong>Circular Reasoning<\/strong> \u2014 Don't assume what you're trying to prove<\/li>\r\n <\/ul>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> Use induction to prove: (1) 1 + 3 + 5 + ... + (2n\u22121) = n\u00b2 (2) 3\u207f > 2n + 1 for all n \u2265 2. Show all three steps clearly.<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-7\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 7<\/span>\r\n <h2>Combinatorics \u2014 Counting Techniques<\/h2>\r\n <p>Permutations, combinations, and the art of counting.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is Combinatorics?<\/h3>\r\n <p><strong>Combinatorics<\/strong> is the branch of mathematics concerned with counting, arranging, and combining objects. It answers questions like \"How many ways can we arrange these items?\" or \"How many subsets can we choose?\"<\/p>\r\n\r\n <h3>Fundamental Counting Principles<\/h3>\r\n \r\n <h3>1. Addition Principle (OR)<\/h3>\r\n <p>If task A can be done in <strong>m<\/strong> ways and task B can be done in <strong>n<\/strong> ways, and they CANNOT be done together, then either A OR B can be done in <strong>m + n<\/strong> ways.<\/p>\r\n <div class=\"code-block\"><pre>Example: Travel from City X to City Y\r\n- By train: 3 routes\r\n- By bus: 5 routes\r\nTotal ways = 3 + 5 = 8 ways<\/pre><\/div>\r\n\r\n <h3>2. Multiplication Principle (AND)<\/h3>\r\n <p>If task A can be done in <strong>m<\/strong> ways and task B can be done in <strong>n<\/strong> ways, and both must be done, then A AND B can be done in <strong>m \u00d7 n<\/strong> ways.<\/p>\r\n <div class=\"code-block\"><pre>Example: Password with 1 letter + 1 digit\r\n- Letters: 26 ways\r\n- Digits: 10 ways\r\nTotal passwords = 26 \u00d7 10 = 260<\/pre><\/div>\r\n\r\n <h3>Permutations (Order Matters)<\/h3>\r\n <p>A <strong>permutation<\/strong> is an arrangement of objects where ORDER matters.<\/p>\r\n \r\n <h3>Permutation of n Objects<\/h3>\r\n <p>Number of ways to arrange n distinct objects = <strong>n!<\/strong> (n factorial)<\/p>\r\n <div class=\"code-block\"><pre>n! = n \u00d7 (n-1) \u00d7 (n-2) \u00d7 ... \u00d7 2 \u00d7 1\r\n\r\nExample: Arrange 4 books on a shelf\r\n4! = 4 \u00d7 3 \u00d7 2 \u00d7 1 = 24 ways<\/pre><\/div>\r\n\r\n <h3>Permutation of r Objects from n<\/h3>\r\n <p>P(n, r) or nPr = number of ways to arrange r objects chosen from n objects<\/p>\r\n <div class=\"code-block\"><pre>P(n, r) = n!\/(n-r)!\r\n\r\nExample: Choose and arrange 3 winners from 10 contestants\r\nP(10, 3) = 10!\/(10-3)! = 10!\/7! = 10\u00d79\u00d78 = 720 ways<\/pre><\/div>\r\n\r\n <h3>Combinations (Order Doesn't Matter)<\/h3>\r\n <p>A <strong>combination<\/strong> is a selection of objects where ORDER does NOT matter.<\/p>\r\n <div class=\"code-block\"><pre>C(n, r) or nCr = n!\/[r!(n-r)!]\r\n\r\nAlso written as (n choose r) or \u207fC\u1d63\r\n\r\nExample: Choose 3 students from 10 for a committee\r\nC(10, 3) = 10!\/[3!(10-3)!]\r\n = 10!\/(3!\u00d77!)\r\n = (10\u00d79\u00d78)\/(3\u00d72\u00d71)\r\n = 120 ways<\/pre><\/div>\r\n\r\n <h3>Permutation vs Combination<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Feature<\/th><th>Permutation<\/th><th>Combination<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Order<\/td><td>Matters<\/td><td>Does NOT matter<\/td><\/tr>\r\n <tr><td>Formula<\/td><td>P(n,r) = n!\/(n-r)!<\/td><td>C(n,r) = n!\/[r!(n-r)!]<\/td><\/tr>\r\n <tr><td>Example<\/td><td>PIN code 1234 \u2260 4321<\/td><td>Team {A,B,C} = {C,B,A}<\/td><\/tr>\r\n <tr><td>Result<\/td><td>Always larger<\/td><td>Always smaller<\/td><\/tr>\r\n <tr><td>Relationship<\/td><td colspan=\"2\">P(n,r) = r! \u00d7 C(n,r)<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Special Cases<\/h3>\r\n <div class=\"code-block\"><pre>C(n, 0) = 1 (one way to choose nothing)\r\nC(n, n) = 1 (one way to choose everything)\r\nC(n, r) = C(n, n-r) (symmetry property)\r\n\r\nExample: C(10, 3) = C(10, 7) = 120<\/pre><\/div>\r\n\r\n <h3>Permutations with Repetition<\/h3>\r\n <p>When objects are not all distinct:<\/p>\r\n <div class=\"code-block\"><pre>n!\/(n\u2081! \u00d7 n\u2082! \u00d7 ... \u00d7 n\u2096!)\r\n\r\nwhere n\u2081, n\u2082, ..., n\u2096 are counts of repeated objects\r\n\r\nExample: Arrange letters in \"MISSISSIPPI\"\r\nTotal letters = 11\r\nM:1, I:4, S:4, P:2\r\n\r\nArrangements = 11!\/(1!\u00d74!\u00d74!\u00d72!) = 34,650<\/pre><\/div>\r\n\r\n <h3>Common Problem Types<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Question Type<\/th><th>Use<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Arrange\/Order items<\/td><td>Permutation<\/td><\/tr>\r\n <tr><td>Select\/Choose items (no order)<\/td><td>Combination<\/td><\/tr>\r\n <tr><td>Form teams\/committees<\/td><td>Combination<\/td><\/tr>\r\n <tr><td>Assign ranks\/positions<\/td><td>Permutation<\/td><\/tr>\r\n <tr><td>Passwords\/PINs<\/td><td>Permutation with repetition allowed<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (1) How many 4-digit PINs can be formed using digits 0-9 with repetition? (2) How many ways can 5 people be seated in a row? (3) From 15 students, how many ways can we select a team of 4? (4) Arrange letters in \"BANANA\".<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-8\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 8<\/span>\r\n <h2>Discrete Probability<\/h2>\r\n <p>Calculating chances and likelihood of events.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is Probability?<\/h3>\r\n <p><strong>Probability<\/strong> measures how likely an event is to occur. It's a number between 0 (impossible) and 1 (certain).<\/p>\r\n <div class=\"code-block\"><pre>P(Event) = (Number of favorable outcomes) \/ (Total number of possible outcomes)\r\n\r\nP(E) \u2208 [0, 1]\r\nP(certain event) = 1\r\nP(impossible event) = 0<\/pre><\/div>\r\n\r\n <h3>Basic Probability Example<\/h3>\r\n <div class=\"code-block\"><pre>Rolling a fair die (6 faces: 1,2,3,4,5,6):\r\n\r\nP(getting 4) = 1\/6\r\nP(getting even) = 3\/6 = 1\/2 (faces: 2,4,6)\r\nP(getting \u2264 6) = 6\/6 = 1 (certain)\r\nP(getting 7) = 0\/6 = 0 (impossible)<\/pre><\/div>\r\n\r\n <h3>Complement Rule<\/h3>\r\n <p>The probability that an event does NOT occur:<\/p>\r\n <div class=\"code-block\"><pre>P(not E) = 1 \u2212 P(E)\r\nor\r\nP(E') = 1 \u2212 P(E)\r\n\r\nExample: P(not getting 4) = 1 \u2212 1\/6 = 5\/6<\/pre><\/div>\r\n\r\n <h3>Addition Rule (OR)<\/h3>\r\n <p>For mutually exclusive events (cannot happen together):<\/p>\r\n <div class=\"code-block\"><pre>P(A or B) = P(A \u222a B) = P(A) + P(B)\r\n\r\nExample: Drawing a card\r\nP(Ace or King) = P(Ace) + P(King)\r\n = 4\/52 + 4\/52 = 8\/52 = 2\/13<\/pre><\/div>\r\n\r\n <p>For non-mutually exclusive events (can happen together):<\/p>\r\n <div class=\"code-block\"><pre>P(A or B) = P(A) + P(B) \u2212 P(A and B)\r\n\r\nExample: Drawing a card\r\nP(Heart or King) = P(Heart) + P(King) \u2212 P(King of Hearts)\r\n = 13\/52 + 4\/52 \u2212 1\/52\r\n = 16\/52 = 4\/13<\/pre><\/div>\r\n\r\n <h3>Multiplication Rule (AND)<\/h3>\r\n <p>For independent events (one doesn't affect the other):<\/p>\r\n <div class=\"code-block\"><pre>P(A and B) = P(A \u2229 B) = P(A) \u00d7 P(B)\r\n\r\nExample: Flipping two coins\r\nP(both heads) = P(H on first) \u00d7 P(H on second)\r\n = 1\/2 \u00d7 1\/2 = 1\/4<\/pre><\/div>\r\n\r\n <h3>Conditional Probability<\/h3>\r\n <p>Probability of A given that B has occurred:<\/p>\r\n <div class=\"code-block\"><pre>P(A|B) = P(A \u2229 B) \/ P(B)\r\n\r\nExample: Two dice rolled, sum is 8\r\nP(first die is 3 | sum is 8)\r\n\r\nOutcomes where sum = 8: (2,6),(3,5),(4,4),(5,3),(6,2) = 5 outcomes\r\nOutcomes where first = 3 and sum = 8: (3,5) = 1 outcome\r\n\r\nP(first=3 | sum=8) = 1\/5<\/pre><\/div>\r\n\r\n <h3>Independent vs Dependent Events<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Type<\/th><th>Definition<\/th><th>Example<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Independent<\/td><td>One event doesn't affect the other<br\/>P(A|B) = P(A)<\/td><td>Flipping two coins<\/td><\/tr>\r\n <tr><td>Dependent<\/td><td>One event affects the other<br\/>P(A|B) \u2260 P(A)<\/td><td>Drawing cards without replacement<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Expected Value<\/h3>\r\n <p>The average outcome if an experiment is repeated many times:<\/p>\r\n <div class=\"code-block\"><pre>E(X) = \u03a3 [x \u00d7 P(x)]\r\n\r\nExample: Rolling a die\r\nE(X) = 1\u00d7(1\/6) + 2\u00d7(1\/6) + 3\u00d7(1\/6) + 4\u00d7(1\/6) + 5\u00d7(1\/6) + 6\u00d7(1\/6)\r\n = (1+2+3+4+5+6)\/6\r\n = 21\/6 = 3.5<\/pre><\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (1) A box has 5 red and 3 blue balls. What's P(red)? (2) If you flip 3 coins, what's P(at least 2 heads)? (3) Two cards drawn without replacement from 52 cards. What's P(both aces)?<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-9\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 9<\/span>\r\n <h2>Graph Theory Basics<\/h2>\r\n <p>Vertices, edges, and network connections.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is a Graph?<\/h3>\r\n <p>A <strong>graph<\/strong> G = (V, E) is a collection of <strong>vertices<\/strong> (nodes) V and <strong>edges<\/strong> (connections) E that connect pairs of vertices. Graphs model relationships and networks.<\/p>\r\n <div class=\"info-box\">\ud83d\udca1 Real-world graphs: Social networks (friends as vertices, friendships as edges), road maps (cities as vertices, roads as edges), computer networks (devices as vertices, connections as edges).<\/div>\r\n\r\n <h3>Graph Terminology<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Term<\/th><th>Definition<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Vertex (Node)<\/td><td>A point in the graph<\/td><\/tr>\r\n <tr><td>Edge (Link)<\/td><td>Connection between two vertices<\/td><\/tr>\r\n <tr><td>Adjacent Vertices<\/td><td>Two vertices connected by an edge<\/td><\/tr>\r\n <tr><td>Degree<\/td><td>Number of edges connected to a vertex<\/td><\/tr>\r\n <tr><td>Path<\/td><td>Sequence of vertices connected by edges<\/td><\/tr>\r\n <tr><td>Cycle<\/td><td>Path that starts and ends at the same vertex<\/td><\/tr>\r\n <tr><td>Connected Graph<\/td><td>There's a path between every pair of vertices<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Types of Graphs<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Type<\/th><th>Description<\/th><th>Example<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Undirected Graph<\/td><td>Edges have no direction (bidirectional)<\/td><td>Friendship network<\/td><\/tr>\r\n <tr><td>Directed Graph (Digraph)<\/td><td>Edges have direction (arrows)<\/td><td>Twitter followers<\/td><\/tr>\r\n <tr><td>Weighted Graph<\/td><td>Edges have associated weights\/costs<\/td><td>Road network with distances<\/td><\/tr>\r\n <tr><td>Simple Graph<\/td><td>No loops, no multiple edges<\/td><td>Most common type<\/td><\/tr>\r\n <tr><td>Complete Graph Kn<\/td><td>Every vertex connected to every other<\/td><td>K\u2084 has 6 edges<\/td><\/tr>\r\n <tr><td>Bipartite Graph<\/td><td>Vertices split into two sets, edges only between sets<\/td><td>Students-Courses matching<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Degree of a Vertex<\/h3>\r\n <p>The <strong>degree<\/strong> of a vertex is the number of edges connected to it.<\/p>\r\n <div class=\"code-block\"><pre>In undirected graph:\r\ndeg(v) = number of edges at vertex v\r\n\r\nIn directed graph:\r\nin-degree = number of edges coming IN\r\nout-degree = number of edges going OUT<\/pre><\/div>\r\n\r\n <h3>Handshaking Lemma<\/h3>\r\n <p>The sum of all vertex degrees equals twice the number of edges:<\/p>\r\n <div class=\"code-block\"><pre>\u03a3 deg(v) = 2|E|\r\n\r\nWhy? Each edge contributes 1 to the degree of TWO vertices.\r\n\r\nCorollary: In any graph, the number of vertices\r\nwith odd degree is EVEN.<\/pre><\/div>\r\n\r\n <h3>Paths and Cycles<\/h3>\r\n <ul>\r\n <li><strong>Path:<\/strong> Sequence of vertices where each adjacent pair is connected by an edge<\/li>\r\n <li><strong>Simple Path:<\/strong> No vertex is repeated<\/li>\r\n <li><strong>Cycle:<\/strong> Path that starts and ends at the same vertex<\/li>\r\n <li><strong>Simple Cycle:<\/strong> Cycle with no repeated vertices (except first\/last)<\/li>\r\n <\/ul>\r\n\r\n <h3>Euler and Hamilton Paths<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Type<\/th><th>Definition<\/th><th>Exists When<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Euler Path<\/td><td>Path that visits every EDGE exactly once<\/td><td>0 or 2 vertices of odd degree<\/td><\/tr>\r\n <tr><td>Euler Circuit<\/td><td>Euler path that starts\/ends at same vertex<\/td><td>All vertices have even degree<\/td><\/tr>\r\n <tr><td>Hamilton Path<\/td><td>Path that visits every VERTEX exactly once<\/td><td>No simple rule (NP-complete)<\/td><\/tr>\r\n <tr><td>Hamilton Circuit<\/td><td>Hamilton path that starts\/ends at same vertex<\/td><td>No simple rule<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Graph Representation<\/h3>\r\n \r\n <h3>1. Adjacency Matrix<\/h3>\r\n <p>A matrix where entry (i,j) = 1 if edge exists between vertex i and j, otherwise 0.<\/p>\r\n <div class=\"code-block\"><pre>Graph: A-B, B-C, A-C\r\n\r\n A B C\r\nA [ 0 1 1 ]\r\nB [ 1 0 1 ]\r\nC [ 1 1 0 ]<\/pre><\/div>\r\n\r\n <h3>2. Adjacency List<\/h3>\r\n <p>For each vertex, list its adjacent vertices.<\/p>\r\n <div class=\"code-block\"><pre>A: [B, C]\r\nB: [A, C]\r\nC: [A, B]<\/pre><\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (1) Draw a graph with 5 vertices and 7 edges. Calculate each vertex's degree. (2) Verify the handshaking lemma. (3) Determine if a graph with degrees [2,2,3,3,4] is possible.<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-10\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 10<\/span>\r\n <h2>Trees<\/h2>\r\n <p>Special graphs \u2014 hierarchical structures without cycles.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is a Tree?<\/h3>\r\n <p>A <strong>tree<\/strong> is a connected graph with NO cycles. It's the most fundamental hierarchical structure in computer science.<\/p>\r\n <div class=\"info-box\">\ud83d\udca1 Real-world trees: File system directories, organization charts, family trees, decision trees, HTML DOM, binary search trees in databases.<\/div>\r\n\r\n <h3>Properties of Trees<\/h3>\r\n <ul>\r\n <li>A tree with n vertices has exactly <strong>n \u2212 1<\/strong> edges<\/li>\r\n <li>There is exactly <strong>one path<\/strong> between any two vertices<\/li>\r\n <li>Removing any edge disconnects the tree<\/li>\r\n <li>Adding any edge creates exactly one cycle<\/li>\r\n <li>A tree is a <strong>minimally connected<\/strong> graph<\/li>\r\n <\/ul>\r\n\r\n <h3>Tree Terminology<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Term<\/th><th>Definition<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Root<\/td><td>The topmost vertex (in rooted trees)<\/td><\/tr>\r\n <tr><td>Parent<\/td><td>Vertex directly above another<\/td><\/tr>\r\n <tr><td>Child<\/td><td>Vertex directly below another<\/td><\/tr>\r\n <tr><td>Leaf (Terminal)<\/td><td>Vertex with no children<\/td><\/tr>\r\n <tr><td>Internal Vertex<\/td><td>Vertex with at least one child<\/td><\/tr>\r\n <tr><td>Sibling<\/td><td>Vertices with the same parent<\/td><\/tr>\r\n <tr><td>Ancestor<\/td><td>Any vertex on path from root to this vertex<\/td><\/tr>\r\n <tr><td>Descendant<\/td><td>Any vertex in subtree rooted at this vertex<\/td><\/tr>\r\n <tr><td>Level<\/td><td>Distance from root (root is level 0)<\/td><\/tr>\r\n <tr><td>Height<\/td><td>Maximum level in the tree<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Types of Trees<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Type<\/th><th>Description<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Binary Tree<\/td><td>Each vertex has at most 2 children (left and right)<\/td><\/tr>\r\n <tr><td>Full Binary Tree<\/td><td>Every vertex has 0 or 2 children<\/td><\/tr>\r\n <tr><td>Complete Binary Tree<\/td><td>All levels filled except possibly the last, filled left to right<\/td><\/tr>\r\n <tr><td>Perfect Binary Tree<\/td><td>All internal vertices have 2 children, all leaves at same level<\/td><\/tr>\r\n <tr><td>Binary Search Tree (BST)<\/td><td>Left child < parent < right child<\/td><\/tr>\r\n <tr><td>Spanning Tree<\/td><td>Subgraph that includes all vertices and is a tree<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Binary Tree Properties<\/h3>\r\n <div class=\"code-block\"><pre>For a binary tree with n vertices:\r\n- Maximum number of vertices at level i = 2^i\r\n- Maximum vertices in tree of height h = 2^(h+1) \u2212 1\r\n- Minimum height for n vertices = \u2308log\u2082(n+1)\u2309 \u2212 1\r\n\r\nFor a perfect binary tree:\r\n- Height h \u2192 vertices = 2^(h+1) \u2212 1\r\n- Height h \u2192 leaves = 2^h<\/pre><\/div>\r\n\r\n <h3>Tree Traversal Methods<\/h3>\r\n <p>Ways to visit all vertices in a tree:<\/p>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Method<\/th><th>Order<\/th><th>Use Case<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Preorder<\/td><td>Root \u2192 Left \u2192 Right<\/td><td>Copy a tree, prefix expression<\/td><\/tr>\r\n <tr><td>Inorder<\/td><td>Left \u2192 Root \u2192 Right<\/td><td>BST gives sorted order<\/td><\/tr>\r\n <tr><td>Postorder<\/td><td>Left \u2192 Right \u2192 Root<\/td><td>Delete a tree, postfix expression<\/td><\/tr>\r\n <tr><td>Level-order (BFS)<\/td><td>Level by level, left to right<\/td><td>Shortest path, level-wise processing<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Spanning Trees<\/h3>\r\n <p>A <strong>spanning tree<\/strong> of a connected graph G is a subgraph that:<\/p>\r\n <ul>\r\n <li>Includes all vertices of G<\/li>\r\n <li>Is a tree (connected, no cycles)<\/li>\r\n <li>Has exactly n \u2212 1 edges (where n = number of vertices)<\/li>\r\n <\/ul>\r\n\r\n <h3>Minimum Spanning Tree (MST)<\/h3>\r\n <p>For a weighted graph, the MST is the spanning tree with minimum total edge weight.<\/p>\r\n <div class=\"code-block\"><pre>Algorithms to find MST:\r\n1. Kruskal's Algorithm \u2014 Sort edges, add smallest without creating cycle\r\n2. Prim's Algorithm \u2014 Start from a vertex, grow tree by adding cheapest edge<\/pre><\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (1) Draw a binary tree with 7 vertices. Identify root, leaves, and height. (2) For tree with root A, children B,C; B has children D,E; C has child F \u2014 write preorder, inorder, and postorder traversals. (3) How many edges in a tree with 15 vertices?<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-11\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 11<\/span>\r\n <h2>Boolean Algebra<\/h2>\r\n <p>Mathematical foundation of digital logic and computer circuits.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is Boolean Algebra?<\/h3>\r\n <p><strong>Boolean algebra<\/strong> is a branch of mathematics that deals with variables that have only two possible values: <strong>true (1)<\/strong> or <strong>false (0)<\/strong>. It's the mathematical foundation of digital electronics and computer logic.<\/p>\r\n\r\n <h3>Boolean Operations<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Operation<\/th><th>Symbol<\/th><th>Name<\/th><th>Result<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>AND<\/td><td>\u00b7 or \u2227<\/td><td>Conjunction<\/td><td>1 only if both are 1<\/td><\/tr>\r\n <tr><td>OR<\/td><td>+ or \u2228<\/td><td>Disjunction<\/td><td>1 if at least one is 1<\/td><\/tr>\r\n <tr><td>NOT<\/td><td>' or \u00ac<\/td><td>Negation<\/td><td>Flips the value<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Boolean Algebra Laws<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Law<\/th><th>AND Form<\/th><th>OR Form<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Identity<\/td><td>x \u00b7 1 = x<\/td><td>x + 0 = x<\/td><\/tr>\r\n <tr><td>Null\/Domination<\/td><td>x \u00b7 0 = 0<\/td><td>x + 1 = 1<\/td><\/tr>\r\n <tr><td>Idempotent<\/td><td>x \u00b7 x = x<\/td><td>x + x = x<\/td><\/tr>\r\n <tr><td>Complement<\/td><td>x \u00b7 x' = 0<\/td><td>x + x' = 1<\/td><\/tr>\r\n <tr><td>Involution<\/td><td colspan=\"2\">(x')' = x<\/td><\/tr>\r\n <tr><td>Commutative<\/td><td>x \u00b7 y = y \u00b7 x<\/td><td>x + y = y + x<\/td><\/tr>\r\n <tr><td>Associative<\/td><td>(x\u00b7y)\u00b7z = x\u00b7(y\u00b7z)<\/td><td>(x+y)+z = x+(y+z)<\/td><\/tr>\r\n <tr><td>Distributive<\/td><td>x\u00b7(y+z) = x\u00b7y + x\u00b7z<\/td><td>x+(y\u00b7z) = (x+y)\u00b7(x+z)<\/td><\/tr>\r\n <tr><td>Absorption<\/td><td>x\u00b7(x+y) = x<\/td><td>x + x\u00b7y = x<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>De Morgan's Laws<\/h3>\r\n <div class=\"code-block\"><pre>(x \u00b7 y)' = x' + y'\r\n(x + y)' = x' \u00b7 y'\r\n\r\nIn words:\r\n\"The complement of AND is OR of complements\"\r\n\"The complement of OR is AND of complements\"<\/pre><\/div>\r\n\r\n <h3>Simplification Example<\/h3>\r\n <div class=\"code-block\"><pre>Simplify: F = x\u00b7y + x\u00b7y'\r\n\r\nStep 1: Factor out x\r\nF = x\u00b7(y + y')\r\n\r\nStep 2: Apply complement law: y + y' = 1\r\nF = x\u00b71\r\n\r\nStep 3: Apply identity law: x\u00b71 = x\r\nF = x\r\n\r\nResult: The expression simplifies to just x!<\/pre><\/div>\r\n\r\n <h3>Boolean Functions<\/h3>\r\n <p>A Boolean function maps Boolean inputs to a Boolean output:<\/p>\r\n <div class=\"code-block\"><pre>f(x, y, z) = x\u00b7y' + x'\u00b7z\r\n\r\nTruth table:\r\nx y z | f\r\n0 0 0 | 0\r\n0 0 1 | 1\r\n0 1 0 | 0\r\n0 1 1 | 1\r\n1 0 0 | 1\r\n1 0 1 | 1\r\n1 1 0 | 0\r\n1 1 1 | 0<\/pre><\/div>\r\n\r\n <h3>Canonical Forms<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Form<\/th><th>Description<\/th><th>Example<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Sum of Products (SOP)<\/td><td>OR of AND terms (minterms)<\/td><td>x'y + xy'<\/td><\/tr>\r\n <tr><td>Product of Sums (POS)<\/td><td>AND of OR terms (maxterms)<\/td><td>(x+y)\u00b7(x'+y')<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <div class=\"info-box\">\ud83d\udca1 Boolean algebra is directly implemented in computer circuits using logic gates (AND, OR, NOT gates). Every computation in a computer ultimately reduces to Boolean operations!<\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (1) Simplify: F = x\u00b7y + x\u00b7y' + x'\u00b7y using Boolean laws. (2) Prove De Morgan's law (x+y)' = x'\u00b7y' using a truth table. (3) Convert F = x'y'z + xyz' to Product of Sums form.<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-12\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 12<\/span>\r\n <h2>Recurrence Relations<\/h2>\r\n <p>Sequences defined recursively \u2014 solving recursive formulas.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is a Recurrence Relation?<\/h3>\r\n <p>A <strong>recurrence relation<\/strong> is an equation that defines a sequence based on previous terms. Each term is expressed as a function of earlier terms.<\/p>\r\n <div class=\"info-box\">\ud83d\udca1 Famous example: Fibonacci sequence \u2014 each number is the sum of the previous two: F(n) = F(n-1) + F(n-2), with F(0)=0, F(1)=1.<\/div>\r\n\r\n <h3>Components of a Recurrence Relation<\/h3>\r\n <ul>\r\n <li><strong>Recurrence equation:<\/strong> The recursive formula<\/li>\r\n <li><strong>Initial conditions:<\/strong> Base case values<\/li>\r\n <\/ul>\r\n <div class=\"code-block\"><pre>Example: a_n = 2\u00b7a_(n-1) + 3 with a_0 = 1\r\n\r\na_0 = 1 (initial condition)\r\na_1 = 2\u00b71 + 3 = 5\r\na_2 = 2\u00b75 + 3 = 13\r\na_3 = 2\u00b713 + 3 = 29\r\n...<\/pre><\/div>\r\n\r\n <h3>Types of Recurrence Relations<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Type<\/th><th>Form<\/th><th>Example<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Linear Homogeneous<\/td><td>a_n = c\u2081\u00b7a_(n-1) + c\u2082\u00b7a_(n-2)<\/td><td>a_n = 3a_(n-1) \u2212 2a_(n-2)<\/td><\/tr>\r\n <tr><td>Linear Non-Homogeneous<\/td><td>a_n = c\u2081\u00b7a_(n-1) + f(n)<\/td><td>a_n = 2a_(n-1) + n<\/td><\/tr>\r\n <tr><td>First-Order<\/td><td>Depends on one previous term<\/td><td>a_n = 2a_(n-1) + 1<\/td><\/tr>\r\n <tr><td>Second-Order<\/td><td>Depends on two previous terms<\/td><td>a_n = a_(n-1) + a_(n-2)<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Solving Linear Homogeneous Recurrence Relations<\/h3>\r\n <p>For: a_n = c\u2081\u00b7a_(n-1) + c\u2082\u00b7a_(n-2)<\/p>\r\n <p><strong>Step 1:<\/strong> Form characteristic equation: r\u00b2 = c\u2081\u00b7r + c\u2082<\/p>\r\n <p><strong>Step 2:<\/strong> Solve for roots r\u2081, r\u2082<\/p>\r\n <p><strong>Step 3:<\/strong> General solution depends on roots:<\/p>\r\n <ul>\r\n <li>Two distinct roots: a_n = A\u00b7r\u2081\u207f + B\u00b7r\u2082\u207f<\/li>\r\n <li>One repeated root r: a_n = (A + B\u00b7n)\u00b7r\u207f<\/li>\r\n <\/ul>\r\n <p><strong>Step 4:<\/strong> Use initial conditions to find A and B<\/p>\r\n\r\n <h3>Example: Solve a_n = 5a_(n-1) \u2212 6a_(n-2), a_0=1, a_1=4<\/h3>\r\n <div class=\"code-block\"><pre><strong>Step 1: Characteristic equation<\/strong>\r\nr\u00b2 = 5r \u2212 6\r\nr\u00b2 \u2212 5r + 6 = 0\r\n(r \u2212 2)(r \u2212 3) = 0\r\nr\u2081 = 2, r\u2082 = 3\r\n\r\n<strong>Step 2: General solution (two distinct roots)<\/strong>\r\na_n = A\u00b72\u207f + B\u00b73\u207f\r\n\r\n<strong>Step 3: Apply initial conditions<\/strong>\r\na_0 = 1: A\u00b72\u2070 + B\u00b73\u2070 = 1 \u2192 A + B = 1\r\na_1 = 4: A\u00b72\u00b9 + B\u00b73\u00b9 = 4 \u2192 2A + 3B = 4\r\n\r\nSolve system:\r\nFrom first: B = 1 \u2212 A\r\nSubstitute: 2A + 3(1\u2212A) = 4\r\n 2A + 3 \u2212 3A = 4\r\n \u2212A = 1\r\n A = \u22121, B = 2\r\n\r\n<strong>Step 4: Final solution<\/strong>\r\na_n = \u22121\u00b72\u207f + 2\u00b73\u207f = 2\u00b73\u207f \u2212 2\u207f\r\n\r\nVerify: a_0 = 2\u00b71 \u2212 1 = 1 \u2713\r\n a_1 = 2\u00b73 \u2212 2 = 4 \u2713<\/pre><\/div>\r\n\r\n <h3>Famous Recurrence Relations<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Sequence<\/th><th>Recurrence<\/th><th>Initial<\/th><th>Closed Form<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Fibonacci<\/td><td>F_n = F_(n-1) + F_(n-2)<\/td><td>F_0=0, F_1=1<\/td><td>F_n = (\u03c6\u207f \u2212 \u03c8\u207f)\/\u221a5<\/td><\/tr>\r\n <tr><td>Geometric<\/td><td>a_n = r\u00b7a_(n-1)<\/td><td>a_0 = a<\/td><td>a_n = a\u00b7r\u207f<\/td><\/tr>\r\n <tr><td>Arithmetic<\/td><td>a_n = a_(n-1) + d<\/td><td>a_0 = a<\/td><td>a_n = a + n\u00b7d<\/td><\/tr>\r\n <tr><td>Tower of Hanoi<\/td><td>T_n = 2T_(n-1) + 1<\/td><td>T_1 = 1<\/td><td>T_n = 2\u207f \u2212 1<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (1) Solve a_n = 4a_(n-1) \u2212 4a_(n-2) with a_0=0, a_1=1. (2) Find closed form for a_n = a_(n-1) + 2 with a_0=3. (3) Verify that F_5 = 5 using Fibonacci recurrence F_n = F_(n-1) + F_(n-2).<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-13\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 13<\/span>\r\n <h2>Counting Principles & Pigeonhole Principle<\/h2>\r\n <p>Advanced counting techniques and a powerful proof tool.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>Inclusion-Exclusion Principle<\/h3>\r\n <p>For counting elements in unions of sets, avoiding double-counting:<\/p>\r\n <div class=\"code-block\"><pre><strong>For two sets:<\/strong>\r\n|A \u222a B| = |A| + |B| \u2212 |A \u2229 B|\r\n\r\n<strong>For three sets:<\/strong>\r\n|A \u222a B \u222a C| = |A| + |B| + |C|\r\n \u2212 |A \u2229 B| \u2212 |A \u2229 C| \u2212 |B \u2229 C|\r\n + |A \u2229 B \u2229 C|\r\n\r\nPattern: Add individual, subtract pairs, add triples...<\/pre><\/div>\r\n\r\n <h3>Example: Inclusion-Exclusion<\/h3>\r\n <div class=\"code-block\"><pre>In a class of 50 students:\r\n- 30 study Math\r\n- 25 study Physics\r\n- 10 study both\r\n\r\nHow many study at least one subject?\r\n\r\n|M \u222a P| = |M| + |P| \u2212 |M \u2229 P|\r\n = 30 + 25 \u2212 10\r\n = 45 students<\/pre><\/div>\r\n\r\n <h3>Pigeonhole Principle<\/h3>\r\n <p><strong>Simple version:<\/strong> If n+1 objects are placed into n boxes, then at least one box contains more than one object.<\/p>\r\n <div class=\"info-box\">\ud83d\udca1 Think of it like this: If 13 people are in a room, at least 2 were born in the same month (13 people, 12 months = pigeonhole principle!)<\/div>\r\n\r\n <h3>Generalized Pigeonhole Principle<\/h3>\r\n <p>If n objects are placed into k boxes, then at least one box contains at least <strong>\u2308n\/k\u2309<\/strong> objects.<\/p>\r\n <div class=\"code-block\"><pre>\u2308 \u2309 is the ceiling function (rounds up)\r\n\r\nExample: 50 students, 7 days of the week\r\nAt least one day has: \u230850\/7\u2309 = \u23087.14\u2309 = 8 students born on it<\/pre><\/div>\r\n\r\n <h3>Pigeonhole Principle Examples<\/h3>\r\n <div class=\"code-block\"><pre><strong>Example 1: Handshakes<\/strong>\r\nIn any group of 6 people, either:\r\n- 3 people mutually know each other, OR\r\n- 3 people are mutual strangers\r\n\r\n<strong>Example 2: Socks<\/strong>\r\nYou have 10 black socks and 10 white socks in a drawer.\r\nHow many must you grab (in the dark) to guarantee a matching pair?\r\n\r\nAnswer: 3 socks\r\n(2 colors = 2 boxes, so 3rd sock must match one)\r\n\r\n<strong>Example 3: Integers<\/strong>\r\nAmong any 5 integers, at least two have the same remainder\r\nwhen divided by 4.\r\n\r\nProof: 4 possible remainders (0,1,2,3) = 4 boxes\r\n 5 integers = 5 objects\r\n By pigeonhole: \u23085\/4\u2309 = 2 must have same remainder<\/pre><\/div>\r\n\r\n <h3>Counting with Restrictions<\/h3>\r\n \r\n <h3>1. Arrangements with Restrictions<\/h3>\r\n <div class=\"code-block\"><pre><strong>Problem:<\/strong> Arrange 5 people in a row where 2 specific people\r\nmust sit together.\r\n\r\n<strong>Solution:<\/strong> Treat the 2 as one unit\r\n- Units to arrange: 4 (the pair + 3 others) = 4! ways\r\n- Ways to arrange the pair internally = 2! ways\r\n- Total = 4! \u00d7 2! = 24 \u00d7 2 = 48 ways<\/pre><\/div>\r\n\r\n <h3>2. Distributing Objects into Boxes<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Objects<\/th><th>Boxes<\/th><th>Formula<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Distinct<\/td><td>Distinct<\/td><td>k^n (each object has k choices)<\/td><\/tr>\r\n <tr><td>Identical<\/td><td>Distinct<\/td><td>C(n+k-1, k-1) = stars and bars<\/td><\/tr>\r\n <tr><td>Distinct<\/td><td>Identical<\/td><td>Stirling numbers (complex)<\/td><\/tr>\r\n <tr><td>Identical<\/td><td>Identical<\/td><td>Integer partitions<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Stars and Bars Method<\/h3>\r\n <p>Distributing n identical objects into k distinct boxes:<\/p>\r\n <div class=\"code-block\"><pre>Number of ways = C(n + k \u2212 1, k \u2212 1)\r\n\r\nExample: Distribute 5 identical candies among 3 children\r\nC(5 + 3 \u2212 1, 3 \u2212 1) = C(7, 2) = 21 ways\r\n\r\nVisual: \u2605\u2605\u2605\u2605\u2605 with 2 bars | to separate:\r\n\u2605\u2605|\u2605|\u2605\u2605 means child1 gets 2, child2 gets 1, child3 gets 2<\/pre><\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (1) In a class of 40, 25 play cricket, 20 play football, 10 play both. How many play neither? (2) Show that among 13 people, at least 2 share a birth month. (3) Distribute 8 identical books among 4 students using stars and bars.<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-14\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 14<\/span>\r\n <h2>Proof Techniques<\/h2>\r\n <p>Methods to prove mathematical statements \u2014 the foundation of rigorous thinking.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is a Mathematical Proof?<\/h3>\r\n <p>A <strong>proof<\/strong> is a logical argument that establishes the truth of a mathematical statement beyond any doubt. It uses axioms, definitions, and previously proven results.<\/p>\r\n\r\n <h3>Types of Proof Techniques<\/h3>\r\n \r\n <h3>1. Direct Proof<\/h3>\r\n <p>Start with assumptions (hypothesis), use logical steps, arrive at conclusion.<\/p>\r\n <p><strong>Structure:<\/strong> Assume P is true \u2192 ... logical steps ... \u2192 Therefore Q is true<\/p>\r\n <div class=\"code-block\"><pre><strong>Example: Prove that if n is even, then n\u00b2 is even.<\/strong>\r\n\r\nProof:\r\nAssume n is even.\r\nThen n = 2k for some integer k (definition of even)\r\nn\u00b2 = (2k)\u00b2 = 4k\u00b2 = 2(2k\u00b2)\r\nSince 2k\u00b2 is an integer, n\u00b2 = 2m where m = 2k\u00b2\r\nTherefore n\u00b2 is even. \u220e<\/pre><\/div>\r\n\r\n <h3>2. Proof by Contrapositive<\/h3>\r\n <p>To prove P \u2192 Q, instead prove \u00acQ \u2192 \u00acP (contrapositive is logically equivalent)<\/p>\r\n <div class=\"code-block\"><pre><strong>Example: Prove if n\u00b2 is odd, then n is odd.<\/strong>\r\n\r\nInstead, prove: if n is even, then n\u00b2 is even\r\n(contrapositive of original statement)\r\n\r\nAssume n is even.\r\nn = 2k\r\nn\u00b2 = 4k\u00b2 = 2(2k\u00b2) \u2190 even\r\nTherefore, if n is even, n\u00b2 is even.\r\n\r\nBy contrapositive: if n\u00b2 is odd, then n is odd. \u220e<\/pre><\/div>\r\n\r\n <h3>3. Proof by Contradiction<\/h3>\r\n <p>Assume the statement is FALSE, derive a contradiction, conclude it must be TRUE.<\/p>\r\n <p><strong>Structure:<\/strong> Assume \u00acP \u2192 ... \u2192 Contradiction! \u2192 Therefore P must be true<\/p>\r\n <div class=\"code-block\"><pre><strong>Example: Prove \u221a2 is irrational.<\/strong>\r\n\r\nProof by contradiction:\r\nAssume \u221a2 is rational.\r\nThen \u221a2 = p\/q where p,q are integers, q\u22600, in lowest terms\r\n\r\n\u221a2 = p\/q\r\n2 = p\u00b2\/q\u00b2\r\np\u00b2 = 2q\u00b2 \u2190 p\u00b2 is even, so p is even\r\nLet p = 2k\r\n(2k)\u00b2 = 2q\u00b2\r\n4k\u00b2 = 2q\u00b2\r\nq\u00b2 = 2k\u00b2 \u2190 q\u00b2 is even, so q is even\r\n\r\nBut p and q are both even, contradicting \"lowest terms\"!\r\nTherefore \u221a2 must be irrational. \u220e<\/pre><\/div>\r\n\r\n <h3>4. Proof by Cases<\/h3>\r\n <p>Break the proof into exhaustive cases, prove each separately.<\/p>\r\n <div class=\"code-block\"><pre><strong>Example: Prove that n\u00b2 + n is even for all integers n.<\/strong>\r\n\r\nCase 1: n is even\r\nn = 2k\r\nn\u00b2 + n = (2k)\u00b2 + 2k = 4k\u00b2 + 2k = 2(2k\u00b2 + k) \u2190 even\r\n\r\nCase 2: n is odd\r\nn = 2k + 1\r\nn\u00b2 + n = (2k+1)\u00b2 + (2k+1)\r\n = 4k\u00b2 + 4k + 1 + 2k + 1\r\n = 4k\u00b2 + 6k + 2\r\n = 2(2k\u00b2 + 3k + 1) \u2190 even\r\n\r\nAll cases covered, so n\u00b2 + n is always even. \u220e<\/pre><\/div>\r\n\r\n <h3>5. Proof by Counterexample<\/h3>\r\n <p>To disprove a universal statement (\u2200x P(x)), find ONE example where it's false.<\/p>\r\n <div class=\"code-block\"><pre><strong>Disprove: \"All prime numbers are odd\"<\/strong>\r\n\r\nCounterexample: 2 is prime and even.\r\nTherefore the statement is FALSE. \u220e<\/pre><\/div>\r\n\r\n <h3>6. Mathematical Induction<\/h3>\r\n <p>(Already covered in Unit 6 \u2014 used to prove statements for all natural numbers)<\/p>\r\n\r\n <h3>Proof Strategies Summary<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Method<\/th><th>When to Use<\/th><th>Key Idea<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Direct Proof<\/td><td>P \u2192 Q seems straightforward<\/td><td>Assume P, deduce Q<\/td><\/tr>\r\n <tr><td>Contrapositive<\/td><td>\u00acQ \u2192 \u00acP is easier than P \u2192 Q<\/td><td>Prove equivalent statement<\/td><\/tr>\r\n <tr><td>Contradiction<\/td><td>Existence proofs, irrationality<\/td><td>Assume \u00acP leads to absurdity<\/td><\/tr>\r\n <tr><td>Cases<\/td><td>Natural divisions exist (even\/odd)<\/td><td>Exhaust all possibilities<\/td><\/tr>\r\n <tr><td>Counterexample<\/td><td>Disproving universal claims<\/td><td>Find one exception<\/td><\/tr>\r\n <tr><td>Induction<\/td><td>Statements about all integers \u2265 n<\/td><td>Base + inductive step<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Common Proof-Writing Tips<\/h3>\r\n <ul>\r\n <li><strong>Start clearly:<\/strong> State what you're proving<\/li>\r\n <li><strong>Use definitions:<\/strong> Apply precise mathematical definitions<\/li>\r\n <li><strong>Show all steps:<\/strong> Don't skip logical leaps<\/li>\r\n <li><strong>Use proper notation:<\/strong> \u2200, \u2203, \u2192, \u21d4 correctly<\/li>\r\n <li><strong>End with \u220e or QED:<\/strong> Signals proof is complete<\/li>\r\n <li><strong>Check logic:<\/strong> Each step must follow from previous<\/li>\r\n <\/ul>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (1) Prove directly: if n is odd, then n + 1 is even. (2) Prove by contradiction: there are infinitely many prime numbers. (3) Prove by cases: |xy| = |x|\u00b7|y| for all real numbers x, y.<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"congrats\">\r\n <h2>\ud83c\udf89 Congratulations!<\/h2>\r\n <p>You have completed the Discrete Mathematics Course by Pak Notes Hub! You now understand Logic, Sets, Graph Theory, Combinatorics, Proofs and more. Best of luck in your exams and future studies! \ud83c\udf1f<\/p>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"summary\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Summary<\/span>\r\n <h2>\ud83d\udcca Course Summary \u2014 14 Units<\/h2>\r\n <p>Quick reference of all topics covered.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <table class=\"data-table\">\r\n <thead>\r\n <tr>\r\n <th style=\"width:50px\">#<\/th>\r\n <th style=\"width:200px\">Unit<\/th>\r\n <th>Key Concepts<\/th>\r\n <\/tr>\r\n <\/thead>\r\n <tbody>\r\n <tr><td>1<\/td><td>Introduction to Discrete Math<\/td><td>Discrete vs continuous, applications in CS<\/td><\/tr>\r\n <tr><td>2<\/td><td>Propositional Logic<\/td><td>Propositions, truth tables, logical operators (\u2227, \u2228, \u2192, \u2194)<\/td><\/tr>\r\n <tr><td>3<\/td><td>Predicate Logic & Quantifiers<\/td><td>Predicates, \u2200 (universal), \u2203 (existential), negation rules<\/td><\/tr>\r\n <tr><td>4<\/td><td>Sets & Set Operations<\/td><td>Union, intersection, difference, complement, Cartesian product, De Morgan's laws<\/td><\/tr>\r\n <tr><td>5<\/td><td>Relations & Functions<\/td><td>Types of relations, equivalence relations, one-to-one, onto, bijective functions<\/td><\/tr>\r\n <tr><td>6<\/td><td>Mathematical Induction<\/td><td>Base case, inductive hypothesis, inductive step, strong induction<\/td><\/tr>\r\n <tr><td>7<\/td><td>Combinatorics<\/td><td>Permutations P(n,r), combinations C(n,r), counting principles<\/td><\/tr>\r\n <tr><td>8<\/td><td>Discrete Probability<\/td><td>Basic probability, addition rule, multiplication rule, conditional probability, expected value<\/td><\/tr>\r\n <tr><td>9<\/td><td>Graph Theory Basics<\/td><td>Vertices, edges, degree, paths, cycles, Euler and Hamilton paths, graph representation<\/td><\/tr>\r\n <tr><td>10<\/td><td>Trees<\/td><td>Tree properties, binary trees, traversal methods (preorder, inorder, postorder), spanning trees<\/td><\/tr>\r\n <tr><td>11<\/td><td>Boolean Algebra<\/td><td>Boolean operations, laws, De Morgan's laws, simplification, SOP and POS forms<\/td><\/tr>\r\n <tr><td>12<\/td><td>Recurrence Relations<\/td><td>Recursive sequences, solving linear recurrences, characteristic equations, Fibonacci<\/td><\/tr>\r\n <tr><td>13<\/td><td>Counting Principles<\/td><td>Inclusion-exclusion principle, pigeonhole principle, stars and bars method<\/td><\/tr>\r\n <tr><td>14<\/td><td>Proof Techniques<\/td><td>Direct proof, contrapositive, contradiction, cases, counterexample, induction<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>\ud83d\udd11 Key Formulas \u2014 Quick Reference<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Concept<\/th><th>Formula<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Permutation<\/td><td>P(n,r) = n!\/(n\u2212r)!<\/td><\/tr>\r\n <tr><td>Combination<\/td><td>C(n,r) = n!\/[r!(n\u2212r)!]<\/td><\/tr>\r\n <tr><td>Pigeonhole Principle<\/td><td>\u2308n\/k\u2309 objects in at least one box<\/td><\/tr>\r\n <tr><td>Inclusion-Exclusion<\/td><td>|A\u222aB| = |A| + |B| \u2212 |A\u2229B|<\/td><\/tr>\r\n <tr><td>Handshaking Lemma<\/td><td>\u03a3 deg(v) = 2|E|<\/td><\/tr>\r\n <tr><td>Tree Edges<\/td><td>|E| = |V| \u2212 1<\/td><\/tr>\r\n <tr><td>Binary Tree Max Vertices<\/td><td>2^(h+1) \u2212 1<\/td><\/tr>\r\n <tr><td>Stars and Bars<\/td><td>C(n+k\u22121, k\u22121)<\/td><\/tr>\r\n <tr><td>Probability<\/td><td>P(E) = favorable\/total<\/td><\/tr>\r\n <tr><td>De Morgan's Laws<\/td><td>(A\u222aB)' = A'\u2229B', (A\u2229B)' = A'\u222aB'<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n <\/div>\r\n <\/div>\r\n\r\n <\/main>\r\n<\/div>\r\n\r\n\r\n<button id=\"back-top\" aria-label=\"Back to top\">\u2191<\/button>\r\n\r\n<script>\r\n\/\/ Progress bar\r\nwindow.addEventListener('scroll', () => {\r\n const winScroll = document.body.scrollTop || document.documentElement.scrollTop;\r\n const height = document.documentElement.scrollHeight - document.documentElement.clientHeight;\r\n const scrolled = (winScroll \/ height) * 100;\r\n document.getElementById('progress').style.width = scrolled + '%';\r\n});\r\n\r\n\/\/ Back to top button\r\nconst backTop = document.getElementById('back-top');\r\nwindow.addEventListener('scroll', () => {\r\n if (window.pageYOffset > 300) {\r\n backTop.classList.add('visible');\r\n } else {\r\n backTop.classList.remove('visible');\r\n }\r\n});\r\nbackTop.addEventListener('click', () => {\r\n window.scrollTo({ top: 0, behavior: 'smooth' });\r\n});\r\n\r\n\/\/ Active TOC highlighting\r\nconst sections = document.querySelectorAll('.unit');\r\nconst navLinks = document.querySelectorAll('.toc-list a');\r\n\r\nwindow.addEventListener('scroll', () => {\r\n let current = '';\r\n sections.forEach(section => {\r\n const sectionTop = section.offsetTop;\r\n const sectionHeight = section.clientHeight;\r\n if (pageYOffset >= sectionTop - 100) {\r\n current = section.getAttribute('id');\r\n }\r\n });\r\n\r\n navLinks.forEach(link => {\r\n link.classList.remove('active');\r\n if (link.getAttribute('href') === '#' + current) {\r\n link.classList.add('active');\r\n }\r\n });\r\n});\r\n<\/script>\r\n\r\n<\/body>\r\n<\/html>\r\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>Discrete Mathematics \u2013 University Level \u2013 Pak Notes Hub Pak Notes Hub Course Outline Start Learning Induction Graph Theory \ud83d\udcd0 University Level \u2014 BS CS \/ BS IT Discrete MathematicsComplete Notes Logic \u00b7 Sets \u00b7 Graph Theory \u00b7 Combinatorics \u00b7 Proofs \u2014 All in Easy English \ud83d\udd22 14 Units \ud83c\udf93 University Level \ud83d\udcca Examples \ud83d\udcdd […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_angie_page":false,"footnotes":""},"class_list":["post-456","page","type-page","status-publish","hentry"],"_hostinger_reach_plugin_has_subscription_block":false,"_hostinger_reach_plugin_is_elementor":false,"_links":{"self":[{"href":"https:\/\/paknoteshub.online\/index.php?rest_route=\/wp\/v2\/pages\/456","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/paknoteshub.online\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/paknoteshub.online\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/paknoteshub.online\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/paknoteshub.online\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=456"}],"version-history":[{"count":7,"href":"https:\/\/paknoteshub.online\/index.php?rest_route=\/wp\/v2\/pages\/456\/revisions"}],"predecessor-version":[{"id":464,"href":"https:\/\/paknoteshub.online\/index.php?rest_route=\/wp\/v2\/pages\/456\/revisions\/464"}],"wp:attachment":[{"href":"https:\/\/paknoteshub.online\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=456"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}

\n\t\t\t\t

\n\t\t\t\t\t

\n\t\t\t\t

\n\t\t\t\t\t\r\n\r\n\r\n \r\n \r\n Discrete Mathematics \u2013 University Level \u2013 Pak Notes Hub<\/title>\r\n <link href=\"https:\/\/fonts.googleapis.com\/css2?family=Inter:wght@400;500;600;700&family=Fira+Code:wght@400;500&display=swap\" rel=\"stylesheet\"\/>\r\n <style>\r\n *, *::before, *::after { box-sizing: border-box; margin: 0; padding: 0; }\r\n :root {\r\n --green:#1a7a4a; --green-dark:#145f38; --green-light:#e8f5ee;\r\n --teal:#17a589; --accent:#f0b127; --dark:#1c2833; --mid:#566573;\r\n --light:#f4f6f7; --code-bg:#f0f4f8; --code-border:#2e86c1;\r\n --note-bg:#fef9e7; --note-border:#f0b127; --white:#ffffff;\r\n --radius:10px; --shadow:0 4px 24px rgba(26,122,74,.10);\r\n }\r\n html { scroll-behavior:smooth; }\r\n body { font-family:'Inter',sans-serif; background:#f2f6f3; color:var(--dark); line-height:1.7; font-size:15px; }\r\n\r\n \/* NAV *\/\r\n nav { position:sticky; top:0; z-index:100; background:var(--green-dark); padding:0 2rem; display:flex; align-items:center; justify-content:space-between; height:56px; box-shadow:0 2px 12px rgba(0,0,0,.25); }\r\n .nav-brand { color:#fff; font-weight:700; font-size:1.05rem; }\r\n .nav-brand span { color:#a9dfbf; }\r\n .nav-links { display:flex; gap:1.2rem; }\r\n .nav-links a { color:#d5f5e3; font-size:.85rem; font-weight:500; text-decoration:none; transition:color .2s; }\r\n .nav-links a:hover { color:#fff; }\r\n\r\n \/* HERO *\/\r\n .hero { background:linear-gradient(135deg,var(--green) 0%,#145f38 60%,#0d4527 100%); padding:5rem 2rem 4rem; text-align:center; position:relative; overflow:hidden; }\r\n .hero::before { content:'\u2211'; position:absolute; right:6%; top:50%; transform:translateY(-50%); font-size:9rem; font-family:'Times New Roman',serif; color:rgba(255,255,255,.06); font-weight:700; pointer-events:none; }\r\n .hero-tag { display:inline-block; background:rgba(255,255,255,.12); color:#a9dfbf; font-size:.78rem; font-weight:600; letter-spacing:1.5px; text-transform:uppercase; padding:.35rem 1rem; border-radius:100px; margin-bottom:1.2rem; border:1px solid rgba(169,223,163,.3); }\r\n .hero h1 { color:#fff; font-size:clamp(1.8rem,5vw,3rem); font-weight:700; line-height:1.15; margin-bottom:.8rem; }\r\n .hero h1 span { color:#a9dfbf; }\r\n .hero p { color:#d5f5e3; font-size:1.05rem; max-width:580px; margin:0 auto 2rem; }\r\n .hero-pills { display:flex; flex-wrap:wrap; justify-content:center; gap:.7rem; }\r\n .pill { background:rgba(255,255,255,.13); color:#e8f5ee; padding:.45rem 1.1rem; border-radius:100px; font-size:.82rem; font-weight:500; border:1px solid rgba(255,255,255,.18); }\r\n\r\n \/* LAYOUT *\/\r\n .page-wrap { max-width:940px; margin:0 auto; padding:2.5rem 1.5rem 4rem; display:grid; grid-template-columns:235px 1fr; gap:2.5rem; align-items:start; }\r\n\r\n \/* SIDEBAR *\/\r\n .sidebar { position:sticky; top:72px; background:var(--white); border-radius:var(--radius); box-shadow:var(--shadow); overflow:hidden; }\r\n .sidebar-title { background:var(--green); color:#fff; font-size:.75rem; font-weight:700; letter-spacing:1.2px; text-transform:uppercase; padding:.85rem 1.1rem; }\r\n .toc-list { list-style:none; padding:.5rem 0; max-height:calc(100vh - 130px); overflow-y:auto; }\r\n .toc-list li a { display:flex; align-items:center; gap:.55rem; padding:.4rem 1.1rem; color:var(--mid); font-size:.81rem; font-weight:500; text-decoration:none; transition:all .18s; border-left:3px solid transparent; }\r\n .toc-list li a:hover,.toc-list li a.active { color:var(--green); background:var(--green-light); border-left-color:var(--green); }\r\n .toc-num { display:inline-flex; align-items:center; justify-content:center; min-width:20px; height:20px; border-radius:4px; background:var(--green-light); color:var(--green); font-size:.7rem; font-weight:700; flex-shrink:0; }\r\n .toc-list li a.active .toc-num { background:var(--green); color:#fff; }\r\n\r\n \/* UNIT CARD *\/\r\n .unit { background:var(--white); border-radius:var(--radius); box-shadow:var(--shadow); margin-bottom:2.5rem; overflow:hidden; scroll-margin-top:72px; }\r\n .unit-header { background:linear-gradient(100deg,var(--green) 0%,#1d9560 100%); padding:1.4rem 1.8rem; }\r\n .unit-num-badge { background:rgba(255,255,255,.18); color:#a9dfbf; font-size:.72rem; font-weight:700; letter-spacing:1px; text-transform:uppercase; padding:.3rem .75rem; border-radius:100px; }\r\n .unit-header h2 { color:#fff; font-size:1.25rem; font-weight:700; line-height:1.25; margin-top:.35rem; }\r\n .unit-header p { color:#c8f0d8; font-size:.85rem; margin-top:.2rem; }\r\n .unit-body { padding:1.8rem; }\r\n\r\n \/* HEADINGS & TEXT *\/\r\n .unit-body h3 { font-size:1rem; font-weight:700; color:var(--green); margin:1.6rem 0 .7rem; padding-left:.85rem; border-left:3px solid var(--green); line-height:1.3; }\r\n .unit-body h3:first-child { margin-top:0; }\r\n .unit-body p { color:var(--dark); margin-bottom:.7rem; }\r\n .unit-body ul { list-style:none; padding:0; margin:.5rem 0 1rem; }\r\n .unit-body ul li { padding:.3rem 0 .3rem 1.5rem; position:relative; color:var(--dark); font-size:.93rem; }\r\n .unit-body ul li::before { content:'\u27a4'; position:absolute; left:0; color:var(--teal); font-size:.75rem; top:.45rem; }\r\n .unit-body code, .icode { font-family:'Fira Code',monospace; background:#eef2f5; color:#1a5276; padding:.1rem .4rem; border-radius:4px; font-size:.85em; }\r\n\r\n \/* CODE BLOCK *\/\r\n .code-block { background:var(--code-bg); border-left:4px solid var(--code-border); border-radius:6px; padding:1.1rem 1.3rem; margin:.9rem 0 1rem; overflow-x:auto; }\r\n .code-block pre { font-family:'Fira Code',monospace; font-size:.83rem; color:#1a3a54; line-height:1.75; white-space:pre; }\r\n .cm { color:#7f8c8d; } .kw { color:#1a5276; font-weight:600; } .st { color:#1e8449; }\r\n\r\n \/* TABLES *\/\r\n .data-table { width:100%; border-collapse:collapse; margin:.9rem 0 1.2rem; font-size:.87rem; border-radius:8px; overflow:hidden; box-shadow:0 1px 6px rgba(0,0,0,.06); }\r\n .data-table thead th { background:var(--green); color:#fff; padding:.7rem 1rem; text-align:left; font-weight:600; font-size:.82rem; }\r\n .data-table tbody tr:nth-child(even) { background:var(--green-light); }\r\n .data-table tbody tr:hover { background:#d4efdf; }\r\n .data-table td { padding:.6rem 1rem; border-bottom:1px solid #dce8e0; vertical-align:top; }\r\n .data-table td:first-child { font-weight:600; color:var(--green-dark); }\r\n\r\n \/* BOXES *\/\r\n .info-box { background:var(--note-bg); border:1px solid var(--note-border); border-radius:7px; padding:.85rem 1.1rem; margin:.9rem 0; font-size:.88rem; line-height:1.6; color:#7d6608; display:flex; align-items:flex-start; gap:.7rem; }\r\n .practice { background:var(--green-light); border:1.5px dashed var(--green); border-radius:8px; padding:.85rem 1.1rem; margin-top:1.4rem; color:var(--green-dark); font-size:.88rem; font-weight:500; }\r\n\r\n \/* FEATURE GRID *\/\r\n .feature-grid { display:grid; grid-template-columns:repeat(auto-fill,minmax(210px,1fr)); gap:.6rem; margin:.9rem 0 1.2rem; }\r\n .feature-item { background:var(--green-light); border-radius:7px; padding:.6rem .9rem; font-size:.85rem; display:flex; align-items:center; gap:.5rem; color:var(--green-dark); border:1px solid #a2d9b5; font-weight:500; }\r\n\r\n \/* CONCEPT GRID (cards) *\/\r\n .concept-grid { display:grid; grid-template-columns:repeat(auto-fill,minmax(190px,1fr)); gap:.8rem; margin:.9rem 0 1.2rem; }\r\n .concept-card { background:var(--green-light); border:1px solid #a2d9b5; border-radius:8px; padding:.85rem 1rem; }\r\n .concept-card .concept-name { font-weight:700; color:var(--green); font-size:.92rem; margin-bottom:.3rem; }\r\n .concept-card .concept-rule { font-size:.8rem; color:var(--mid); }\r\n\r\n \/* TOC CARD *\/\r\n #toc-section { background:var(--white); border-radius:var(--radius); box-shadow:var(--shadow); margin-bottom:2.5rem; overflow:hidden; }\r\n .toc-card-header { background:linear-gradient(100deg,var(--green) 0%,#1d9560 100%); padding:1.2rem 1.8rem; }\r\n .toc-card-header h2 { color:#fff; font-size:1.2rem; font-weight:700; }\r\n .toc-card-body { padding:1.4rem 1.8rem; }\r\n .toc-grid { display:grid; grid-template-columns:repeat(auto-fill,minmax(250px,1fr)); gap:.6rem; }\r\n .toc-item { background:var(--light); border-radius:7px; padding:.65rem 1rem; display:flex; align-items:center; gap:.75rem; text-decoration:none; color:var(--dark); font-size:.86rem; font-weight:500; border:1px solid #d5e5db; transition:all .18s; }\r\n .toc-item:hover { background:var(--green-light); border-color:var(--green); color:var(--green); transform:translateY(-1px); }\r\n .toc-badge { background:var(--green); color:#fff; font-size:.7rem; font-weight:700; min-width:22px; height:22px; border-radius:5px; display:inline-flex; align-items:center; justify-content:center; flex-shrink:0; }\r\n\r\n \/* CONGRATS *\/\r\n .congrats { background:linear-gradient(135deg,var(--green) 0%,#145f38 100%); border-radius:var(--radius); padding:2.5rem 2rem; text-align:center; color:#fff; margin-bottom:2.5rem; box-shadow:var(--shadow); }\r\n .congrats h2 { font-size:1.8rem; margin-bottom:.5rem; }\r\n .congrats p { color:#d5f5e3; font-size:1rem; }\r\n\r\n \/* PROGRESS + BACK TOP *\/\r\n .progress-bar { position:fixed; top:0; left:0; height:3px; background:var(--accent); z-index:200; transition:width .1s linear; width:0%; }\r\n #back-top { position:fixed; bottom:2rem; right:2rem; background:var(--green); color:#fff; width:42px; height:42px; border-radius:50%; border:none; cursor:pointer; font-size:1.1rem; box-shadow:0 4px 14px rgba(26,122,74,.35); display:flex; align-items:center; justify-content:center; opacity:0; transition:opacity .25s,transform .25s; pointer-events:none; }\r\n #back-top.visible { opacity:1; pointer-events:auto; }\r\n #back-top:hover { transform:translateY(-2px); }\r\n\r\n @media(max-width:720px){ .page-wrap{grid-template-columns:1fr;} .sidebar{position:static;display:none;} .hero::before{display:none;} nav .nav-links{display:none;} }\r\n <\/style>\r\n<\/head>\r\n<body>\r\n\r\n<div class=\"progress-bar\" id=\"progress\"><\/div>\r\n\r\n<nav>\r\n <div class=\"nav-brand\">Pak <span>Notes Hub<\/span><\/div>\r\n <div class=\"nav-links\">\r\n <a href=\"#toc-section\">Course Outline<\/a>\r\n <a href=\"#unit-1\">Start Learning<\/a>\r\n <a href=\"#unit-5\">Induction<\/a>\r\n <a href=\"#unit-8\">Graph Theory<\/a>\r\n <\/div>\r\n<\/nav>\r\n\r\n<section class=\"hero\">\r\n <div class=\"hero-tag\">\ud83d\udcd0 University Level \u2014 BS CS \/ BS IT<\/div>\r\n <h1>Discrete Mathematics<br\/><span>Complete Notes<\/span><\/h1>\r\n <p>Logic \u00b7 Sets \u00b7 Graph Theory \u00b7 Combinatorics \u00b7 Proofs \u2014 All in Easy English<\/p>\r\n <div class=\"hero-pills\">\r\n <span class=\"pill\">\ud83d\udd22 14 Units<\/span>\r\n <span class=\"pill\">\ud83c\udf93 University Level<\/span>\r\n <span class=\"pill\">\ud83d\udcca Examples<\/span>\r\n <span class=\"pill\">\ud83d\udcdd Practice Tasks<\/span>\r\n <span class=\"pill\">\ud83e\uddee Problem Solving<\/span>\r\n <\/div>\r\n<\/section>\r\n\r\n<div class=\"page-wrap\">\r\n\r\n \r\n <aside class=\"sidebar\">\r\n <div class=\"sidebar-title\">\ud83d\udccb Course Contents<\/div>\r\n <ul class=\"toc-list\" id=\"toc-nav\">\r\n <li><a href=\"#toc-section\"><span class=\"toc-num\">\ud83d\udccb<\/span> Contents<\/a><\/li>\r\n <li><a href=\"#unit-1\"><span class=\"toc-num\">1<\/span> Intro to Discrete Math<\/a><\/li>\r\n <li><a href=\"#unit-2\"><span class=\"toc-num\">2<\/span> Propositional Logic<\/a><\/li>\r\n <li><a href=\"#unit-3\"><span class=\"toc-num\">3<\/span> Predicate Logic<\/a><\/li>\r\n <li><a href=\"#unit-4\"><span class=\"toc-num\">4<\/span> Sets & Operations<\/a><\/li>\r\n <li><a href=\"#unit-5\"><span class=\"toc-num\">5<\/span> Relations & Functions<\/a><\/li>\r\n <li><a href=\"#unit-6\"><span class=\"toc-num\">6<\/span> Mathematical Induction<\/a><\/li>\r\n <li><a href=\"#unit-7\"><span class=\"toc-num\">7<\/span> Combinatorics<\/a><\/li>\r\n <li><a href=\"#unit-8\"><span class=\"toc-num\">8<\/span> Probability<\/a><\/li>\r\n <li><a href=\"#unit-9\"><span class=\"toc-num\">9<\/span> Graph Theory Basics<\/a><\/li>\r\n <li><a href=\"#unit-10\"><span class=\"toc-num\">10<\/span> Trees<\/a><\/li>\r\n <li><a href=\"#unit-11\"><span class=\"toc-num\">11<\/span> Boolean Algebra<\/a><\/li>\r\n <li><a href=\"#unit-12\"><span class=\"toc-num\">12<\/span> Recurrence Relations<\/a><\/li>\r\n <li><a href=\"#unit-13\"><span class=\"toc-num\">13<\/span> Counting Principles<\/a><\/li>\r\n <li><a href=\"#unit-14\"><span class=\"toc-num\">14<\/span> Proof Techniques<\/a><\/li>\r\n <\/ul>\r\n <\/aside>\r\n\r\n <main>\r\n\r\n \r\n <div id=\"toc-section\">\r\n <div class=\"toc-card-header\"><h2>\ud83d\udccb Table of Contents \u2014 14 Units<\/h2><\/div>\r\n <div class=\"toc-card-body\">\r\n <div class=\"toc-grid\">\r\n <a class=\"toc-item\" href=\"#unit-1\"><span class=\"toc-badge\">1<\/span> Introduction to Discrete Math<\/a>\r\n <a class=\"toc-item\" href=\"#unit-2\"><span class=\"toc-badge\">2<\/span> Propositional Logic<\/a>\r\n <a class=\"toc-item\" href=\"#unit-3\"><span class=\"toc-badge\">3<\/span> Predicate Logic & Quantifiers<\/a>\r\n <a class=\"toc-item\" href=\"#unit-4\"><span class=\"toc-badge\">4<\/span> Sets & Set Operations<\/a>\r\n <a class=\"toc-item\" href=\"#unit-5\"><span class=\"toc-badge\">5<\/span> Relations & Functions<\/a>\r\n <a class=\"toc-item\" href=\"#unit-6\"><span class=\"toc-badge\">6<\/span> Mathematical Induction<\/a>\r\n <a class=\"toc-item\" href=\"#unit-7\"><span class=\"toc-badge\">7<\/span> Combinatorics<\/a>\r\n <a class=\"toc-item\" href=\"#unit-8\"><span class=\"toc-badge\">8<\/span> Discrete Probability<\/a>\r\n <a class=\"toc-item\" href=\"#unit-9\"><span class=\"toc-badge\">9<\/span> Graph Theory Basics<\/a>\r\n <a class=\"toc-item\" href=\"#unit-10\"><span class=\"toc-badge\">10<\/span> Trees<\/a>\r\n <a class=\"toc-item\" href=\"#unit-11\"><span class=\"toc-badge\">11<\/span> Boolean Algebra<\/a>\r\n <a class=\"toc-item\" href=\"#unit-12\"><span class=\"toc-badge\">12<\/span> Recurrence Relations<\/a>\r\n <a class=\"toc-item\" href=\"#unit-13\"><span class=\"toc-badge\">13<\/span> Counting Principles<\/a>\r\n <a class=\"toc-item\" href=\"#unit-14\"><span class=\"toc-badge\">14<\/span> Proof Techniques<\/a>\r\n <\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-1\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 1<\/span>\r\n <h2>Introduction to Discrete Mathematics<\/h2>\r\n <p>What is Discrete Math and why do we study it?<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is Discrete Mathematics?<\/h3>\r\n <p><strong>Discrete Mathematics<\/strong> is the study of mathematical structures that are fundamentally <strong>discrete<\/strong> (separate, distinct) rather than continuous. It deals with objects that can only take specific, separated values.<\/p>\r\n <div class=\"info-box\">\ud83d\udca1 Think of discrete vs continuous like this: discrete is like counting people (1, 2, 3...), continuous is like measuring water (1.5 liters, 2.3 liters). Discrete Math deals with countable, distinct items!<\/div>\r\n\r\n <h3>Discrete vs Continuous Mathematics<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Feature<\/th><th>Discrete Mathematics<\/th><th>Continuous Mathematics<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Values<\/td><td>Separate, distinct, countable<\/td><td>Unbroken, smooth range<\/td><\/tr>\r\n <tr><td>Examples<\/td><td>Integers: 1, 2, 3, 4...<\/td><td>Real numbers: 1.5, 2.73, \u03c0<\/td><\/tr>\r\n <tr><td>Graph Type<\/td><td>Points, nodes, discrete steps<\/td><td>Smooth curves, flowing lines<\/td><\/tr>\r\n <tr><td>Operations<\/td><td>Counting, listing, logical operations<\/td><td>Calculus, limits, derivatives<\/td><\/tr>\r\n <tr><td>Used In<\/td><td>Computer Science, algorithms, cryptography<\/td><td>Physics, engineering, calculus<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Why is Discrete Math Important for Computer Science?<\/h3>\r\n <ul>\r\n <li><strong>Algorithm Design<\/strong> \u2014 Understanding complexity and efficiency<\/li>\r\n <li><strong>Data Structures<\/strong> \u2014 Trees, graphs, and networks<\/li>\r\n <li><strong>Logic & Proofs<\/strong> \u2014 Foundation of program correctness<\/li>\r\n <li><strong>Cryptography<\/strong> \u2014 Number theory and security<\/li>\r\n <li><strong>Database Theory<\/strong> \u2014 Relations and set operations<\/li>\r\n <li><strong>Artificial Intelligence<\/strong> \u2014 Logic, probability, graph search<\/li>\r\n <li><strong>Networking<\/strong> \u2014 Graph theory for network topology<\/li>\r\n <\/ul>\r\n\r\n <h3>Main Topics in Discrete Mathematics<\/h3>\r\n <div class=\"concept-grid\">\r\n <div class=\"concept-card\">\r\n <div class=\"concept-name\">Logic<\/div>\r\n <div class=\"concept-rule\">Propositional and predicate logic, truth tables<\/div>\r\n <\/div>\r\n <div class=\"concept-card\">\r\n <div class=\"concept-name\">Sets<\/div>\r\n <div class=\"concept-rule\">Collections of objects, operations, Venn diagrams<\/div>\r\n <\/div>\r\n <div class=\"concept-card\">\r\n <div class=\"concept-name\">Relations & Functions<\/div>\r\n <div class=\"concept-rule\">Mappings between sets, properties<\/div>\r\n <\/div>\r\n <div class=\"concept-card\">\r\n <div class=\"concept-name\">Combinatorics<\/div>\r\n <div class=\"concept-rule\">Counting techniques, permutations, combinations<\/div>\r\n <\/div>\r\n <div class=\"concept-card\">\r\n <div class=\"concept-name\">Graph Theory<\/div>\r\n <div class=\"concept-rule\">Networks, paths, trees, connectivity<\/div>\r\n <\/div>\r\n <div class=\"concept-card\">\r\n <div class=\"concept-name\">Proofs<\/div>\r\n <div class=\"concept-rule\">Mathematical reasoning, induction<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> Give 3 examples of discrete quantities and 3 examples of continuous quantities from real life. Explain why computer memory is discrete, not continuous.<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-2\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 2<\/span>\r\n <h2>Propositional Logic<\/h2>\r\n <p>Statements, truth values, and logical operators.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is a Proposition?<\/h3>\r\n <p>A <strong>proposition<\/strong> (or statement) is a declarative sentence that is either <strong>true (T)<\/strong> or <strong>false (F)<\/strong>, but not both. The truth value is either 1 (true) or 0 (false).<\/p>\r\n \r\n <h3>Examples of Propositions<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Statement<\/th><th>Proposition?<\/th><th>Reason<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>\"2 + 2 = 4\"<\/td><td>\u2713 Yes<\/td><td>Clearly true<\/td><\/tr>\r\n <tr><td>\"Paris is the capital of France\"<\/td><td>\u2713 Yes<\/td><td>True statement<\/td><\/tr>\r\n <tr><td>\"x + 5 = 10\"<\/td><td>\u2717 No<\/td><td>Depends on value of x<\/td><\/tr>\r\n <tr><td>\"Close the door!\"<\/td><td>\u2717 No<\/td><td>Command, not a statement<\/td><\/tr>\r\n <tr><td>\"What time is it?\"<\/td><td>\u2717 No<\/td><td>Question, not a statement<\/td><\/tr>\r\n <tr><td>\"This sentence is false\"<\/td><td>\u2717 No<\/td><td>Paradox \u2014 neither true nor false<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Logical Operators (Connectives)<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Operator<\/th><th>Symbol<\/th><th>Name<\/th><th>Meaning<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>NOT<\/td><td>\u00ac or ~<\/td><td>Negation<\/td><td>Opposite truth value<\/td><\/tr>\r\n <tr><td>AND<\/td><td>\u2227<\/td><td>Conjunction<\/td><td>Both must be true<\/td><\/tr>\r\n <tr><td>OR<\/td><td>\u2228<\/td><td>Disjunction<\/td><td>At least one must be true<\/td><\/tr>\r\n <tr><td>IF-THEN<\/td><td>\u2192<\/td><td>Implication<\/td><td>If p then q<\/td><\/tr>\r\n <tr><td>IF AND ONLY IF<\/td><td>\u2194<\/td><td>Biconditional<\/td><td>Both have same truth value<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Truth Tables<\/h3>\r\n \r\n <h3>1. Negation (NOT)<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>p<\/th><th>\u00acp<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>T<\/td><td>F<\/td><\/tr>\r\n <tr><td>F<\/td><td>T<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>2. Conjunction (AND)<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>p<\/th><th>q<\/th><th>p \u2227 q<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>T<\/td><td>T<\/td><td>T<\/td><\/tr>\r\n <tr><td>T<\/td><td>F<\/td><td>F<\/td><\/tr>\r\n <tr><td>F<\/td><td>T<\/td><td>F<\/td><\/tr>\r\n <tr><td>F<\/td><td>F<\/td><td>F<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>3. Disjunction (OR)<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>p<\/th><th>q<\/th><th>p \u2228 q<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>T<\/td><td>T<\/td><td>T<\/td><\/tr>\r\n <tr><td>T<\/td><td>F<\/td><td>T<\/td><\/tr>\r\n <tr><td>F<\/td><td>T<\/td><td>T<\/td><\/tr>\r\n <tr><td>F<\/td><td>F<\/td><td>F<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>4. Implication (IF-THEN)<\/h3>\r\n <p>p \u2192 q means \"if p then q\". It's false only when p is true and q is false.<\/p>\r\n <table class=\"data-table\">\r\n <thead><tr><th>p<\/th><th>q<\/th><th>p \u2192 q<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>T<\/td><td>T<\/td><td>T<\/td><\/tr>\r\n <tr><td>T<\/td><td>F<\/td><td>F<\/td><\/tr>\r\n <tr><td>F<\/td><td>T<\/td><td>T<\/td><\/tr>\r\n <tr><td>F<\/td><td>F<\/td><td>T<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>5. Biconditional (IF AND ONLY IF)<\/h3>\r\n <p>p \u2194 q is true when both have the same truth value.<\/p>\r\n <table class=\"data-table\">\r\n <thead><tr><th>p<\/th><th>q<\/th><th>p \u2194 q<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>T<\/td><td>T<\/td><td>T<\/td><\/tr>\r\n <tr><td>T<\/td><td>F<\/td><td>F<\/td><\/tr>\r\n <tr><td>F<\/td><td>T<\/td><td>F<\/td><\/tr>\r\n <tr><td>F<\/td><td>F<\/td><td>T<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <div class=\"info-box\">\ud83d\udca1 Memory Trick: AND (\u2227) is true only when BOTH are true. OR (\u2228) is true when AT LEAST ONE is true. Implication (\u2192) is false ONLY when true leads to false.<\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> Construct a truth table for (p \u2227 q) \u2192 r. Also, determine if \"If it rains, then the ground is wet\" is true when: (a) it rains and ground is wet (b) it doesn't rain and ground is dry.<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-3\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 3<\/span>\r\n <h2>Predicate Logic & Quantifiers<\/h2>\r\n <p>Variables, predicates, and universal\/existential quantifiers.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is Predicate Logic?<\/h3>\r\n <p><strong>Predicate logic<\/strong> (also called first-order logic) extends propositional logic by dealing with statements that contain variables. A <strong>predicate<\/strong> is a statement whose truth value depends on one or more variables.<\/p>\r\n \r\n <h3>Predicates vs Propositions<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Type<\/th><th>Example<\/th><th>Explanation<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Proposition<\/td><td>\"5 is odd\"<\/td><td>Fixed truth value (True)<\/td><\/tr>\r\n <tr><td>Predicate<\/td><td>\"x is odd\"<\/td><td>Truth depends on x<\/td><\/tr>\r\n <tr><td>Predicate<\/td><td>P(x): \"x > 10\"<\/td><td>True if x > 10, false otherwise<\/td><\/tr>\r\n <tr><td>Predicate<\/td><td>Q(x,y): \"x + y = 10\"<\/td><td>Depends on both x and y<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Quantifiers<\/h3>\r\n <p>Quantifiers allow us to make statements about \"all\" or \"some\" elements in a domain.<\/p>\r\n \r\n <h3>1. Universal Quantifier (\u2200)<\/h3>\r\n <p><strong>Symbol:<\/strong> \u2200 (for all, for every)<\/p>\r\n <p><strong>Meaning:<\/strong> \u2200x P(x) means \"P(x) is true for ALL values of x in the domain\"<\/p>\r\n <div class=\"code-block\"><pre>Example:\r\n\u2200x (x\u00b2 \u2265 0) means \"For all real numbers x, x\u00b2 is non-negative\"\r\nThis is TRUE for all real numbers.\r\n\r\n\u2200x (x > 5) means \"For all x, x is greater than 5\"\r\nThis is FALSE (not all numbers are > 5).<\/pre><\/div>\r\n\r\n <h3>2. Existential Quantifier (\u2203)<\/h3>\r\n <p><strong>Symbol:<\/strong> \u2203 (there exists, for some)<\/p>\r\n <p><strong>Meaning:<\/strong> \u2203x P(x) means \"P(x) is true for AT LEAST ONE value of x\"<\/p>\r\n <div class=\"code-block\"><pre>Example:\r\n\u2203x (x\u00b2 = 16) means \"There exists an x such that x\u00b2 = 16\"\r\nThis is TRUE (x = 4 or x = -4).\r\n\r\n\u2203x (x\u00b2 = -1) means \"There exists a real x such that x\u00b2 = -1\"\r\nThis is FALSE for real numbers.<\/pre><\/div>\r\n\r\n <h3>Negation of Quantifiers<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Statement<\/th><th>Negation<\/th><th>Explanation<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>\u2200x P(x)<\/td><td>\u2203x \u00acP(x)<\/td><td>\"Not all\" means \"at least one is not\"<\/td><\/tr>\r\n <tr><td>\u2203x P(x)<\/td><td>\u2200x \u00acP(x)<\/td><td>\"None exists\" means \"all are not\"<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Multiple Quantifiers<\/h3>\r\n <p>Order matters when using multiple quantifiers!<\/p>\r\n <div class=\"code-block\"><pre>\u2200x \u2203y (x + y = 0)\r\n\"For every x, there exists a y such that x + y = 0\"\r\nTRUE (for any x, we can choose y = -x)\r\n\r\n\u2203y \u2200x (x + y = 0)\r\n\"There exists a y such that for all x, x + y = 0\"\r\nFALSE (no single y works for ALL x)<\/pre><\/div>\r\n\r\n <h3>Translating English to Logic<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>English Statement<\/th><th>Logical Form<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>All students passed<\/td><td>\u2200x (Student(x) \u2192 Passed(x))<\/td><\/tr>\r\n <tr><td>Some student failed<\/td><td>\u2203x (Student(x) \u2227 Failed(x))<\/td><\/tr>\r\n <tr><td>No student cheated<\/td><td>\u00ac\u2203x (Student(x) \u2227 Cheated(x))<\/td><\/tr>\r\n <tr><td>Not all birds can fly<\/td><td>\u00ac\u2200x (Bird(x) \u2192 CanFly(x))<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <div class=\"info-box\">\ud83d\udca1 Key Rule: \u2200x usually pairs with \u2192 (implication), while \u2203x usually pairs with \u2227 (and). Example: \"All dogs bark\" = \u2200x (Dog(x) \u2192 Barks(x)), \"Some cats are black\" = \u2203x (Cat(x) \u2227 Black(x))<\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> Translate to logic: (1) \"Every number has a successor\" (2) \"There is a smallest prime number\" (3) \"Not every equation has a solution\". Also find the negation of \u2200x \u2203y (x < y).<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-4\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 4<\/span>\r\n <h2>Sets & Set Operations<\/h2>\r\n <p>Collections of objects and operations on them.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is a Set?<\/h3>\r\n <p>A <strong>set<\/strong> is a well-defined collection of distinct objects, called <strong>elements<\/strong> or <strong>members<\/strong>. Sets are usually denoted by capital letters (A, B, C) and elements by lowercase letters.<\/p>\r\n <div class=\"code-block\"><pre>A = {1, 2, 3, 4, 5}\r\nB = {red, blue, green}\r\nC = {x | x is an even number} \u2190 set-builder notation\r\n\r\n\u2208 means \"is an element of\"\r\n\u2209 means \"is not an element of\"\r\n\r\n3 \u2208 A (3 is in A)\r\n6 \u2209 A (6 is not in A)<\/pre><\/div>\r\n\r\n <h3>Types of Sets<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Type<\/th><th>Definition<\/th><th>Example<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Finite Set<\/td><td>Has limited number of elements<\/td><td>A = {1, 2, 3}<\/td><\/tr>\r\n <tr><td>Infinite Set<\/td><td>Has unlimited elements<\/td><td>\u2115 = {1, 2, 3, ...}<\/td><\/tr>\r\n <tr><td>Empty Set<\/td><td>Contains no elements<\/td><td>\u2205 or { }<\/td><\/tr>\r\n <tr><td>Singleton Set<\/td><td>Contains exactly one element<\/td><td>{5}<\/td><\/tr>\r\n <tr><td>Universal Set<\/td><td>Contains all elements under consideration<\/td><td>U<\/td><\/tr>\r\n <tr><td>Subset<\/td><td>All elements of A are in B<\/td><td>A \u2286 B<\/td><\/tr>\r\n <tr><td>Proper Subset<\/td><td>A \u2286 B but A \u2260 B<\/td><td>A \u2282 B<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Set Operations<\/h3>\r\n \r\n <h3>1. Union (\u222a)<\/h3>\r\n <p>A \u222a B contains all elements that are in A OR in B (or in both).<\/p>\r\n <div class=\"code-block\"><pre>A = {1, 2, 3}\r\nB = {3, 4, 5}\r\nA \u222a B = {1, 2, 3, 4, 5}<\/pre><\/div>\r\n\r\n <h3>2. Intersection (\u2229)<\/h3>\r\n <p>A \u2229 B contains only elements that are in BOTH A AND B.<\/p>\r\n <div class=\"code-block\"><pre>A = {1, 2, 3}\r\nB = {3, 4, 5}\r\nA \u2229 B = {3}<\/pre><\/div>\r\n\r\n <h3>3. Difference (\u2212)<\/h3>\r\n <p>A \u2212 B contains elements in A but NOT in B.<\/p>\r\n <div class=\"code-block\"><pre>A = {1, 2, 3}\r\nB = {3, 4, 5}\r\nA \u2212 B = {1, 2}<\/pre><\/div>\r\n\r\n <h3>4. Complement (A' or \u0100)<\/h3>\r\n <p>A' contains all elements in the universal set U that are NOT in A.<\/p>\r\n <div class=\"code-block\"><pre>U = {1, 2, 3, 4, 5, 6}\r\nA = {1, 2, 3}\r\nA' = {4, 5, 6}<\/pre><\/div>\r\n\r\n <h3>5. Cartesian Product (\u00d7)<\/h3>\r\n <p>A \u00d7 B is the set of all ordered pairs (a, b) where a \u2208 A and b \u2208 B.<\/p>\r\n <div class=\"code-block\"><pre>A = {1, 2}\r\nB = {x, y}\r\nA \u00d7 B = {(1,x), (1,y), (2,x), (2,y)}\r\n\r\n|A \u00d7 B| = |A| \u00d7 |B| = 2 \u00d7 2 = 4<\/pre><\/div>\r\n\r\n <h3>Set Identities (Laws)<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Law<\/th><th>Union Form<\/th><th>Intersection Form<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Identity<\/td><td>A \u222a \u2205 = A<\/td><td>A \u2229 U = A<\/td><\/tr>\r\n <tr><td>Domination<\/td><td>A \u222a U = U<\/td><td>A \u2229 \u2205 = \u2205<\/td><\/tr>\r\n <tr><td>Idempotent<\/td><td>A \u222a A = A<\/td><td>A \u2229 A = A<\/td><\/tr>\r\n <tr><td>Complement<\/td><td>A \u222a A' = U<\/td><td>A \u2229 A' = \u2205<\/td><\/tr>\r\n <tr><td>Commutative<\/td><td>A \u222a B = B \u222a A<\/td><td>A \u2229 B = B \u2229 A<\/td><\/tr>\r\n <tr><td>Associative<\/td><td>(A\u222aB)\u222aC = A\u222a(B\u222aC)<\/td><td>(A\u2229B)\u2229C = A\u2229(B\u2229C)<\/td><\/tr>\r\n <tr><td>Distributive<\/td><td>A\u222a(B\u2229C) = (A\u222aB)\u2229(A\u222aC)<\/td><td>A\u2229(B\u222aC) = (A\u2229B)\u222a(A\u2229C)<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>De Morgan's Laws for Sets<\/h3>\r\n <div class=\"code-block\"><pre>(A \u222a B)' = A' \u2229 B'\r\n(A \u2229 B)' = A' \u222a B'\r\n\r\n\"The complement of a union is the intersection of complements\"\r\n\"The complement of an intersection is the union of complements\"<\/pre><\/div>\r\n\r\n <div class=\"info-box\">\ud83d\udca1 Venn Diagrams help visualize sets! Union combines circles, intersection is the overlap, difference removes one from another, complement is everything outside the circle.<\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> If A = {1,2,3,4}, B = {3,4,5,6}, C = {5,6,7,8}, find: (1) A \u222a B (2) A \u2229 B (3) A \u2212 B (4) (A \u222a B) \u2229 C. Also prove (A \u2229 B)' = A' \u222a B' using an example.<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-5\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 5<\/span>\r\n <h2>Relations & Functions<\/h2>\r\n <p>Mappings between sets and their properties.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is a Relation?<\/h3>\r\n <p>A <strong>relation<\/strong> R from set A to set B is a subset of the Cartesian product A \u00d7 B. It shows how elements of A are related to elements of B.<\/p>\r\n <div class=\"code-block\"><pre>A = {1, 2, 3}\r\nB = {4, 5}\r\nR = {(1,4), (2,5), (3,4)} \u2190 relation from A to B\r\n\r\nWe write: 1 R 4 (1 is related to 4)<\/pre><\/div>\r\n\r\n <h3>Types of Relations<\/h3>\r\n <p>For a relation R on a set A (from A to A):<\/p>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Property<\/th><th>Definition<\/th><th>Example<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Reflexive<\/td><td>Every element relates to itself: \u2200x (x R x)<\/td><td>\u2264 (every number \u2264 itself)<\/td><\/tr>\r\n <tr><td>Symmetric<\/td><td>If x R y then y R x<\/td><td>= (if x = y then y = x)<\/td><\/tr>\r\n <tr><td>Antisymmetric<\/td><td>If x R y and y R x, then x = y<\/td><td>\u2264 (if x\u2264y and y\u2264x, then x=y)<\/td><\/tr>\r\n <tr><td>Transitive<\/td><td>If x R y and y R z, then x R z<\/td><td>< (if x<y and y<z, then x<z)<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Equivalence Relation<\/h3>\r\n <p>A relation that is <strong>reflexive, symmetric, and transitive<\/strong> is called an equivalence relation.<\/p>\r\n <div class=\"code-block\"><pre>Example: \"=\" (equality) is an equivalence relation\r\n- Reflexive: x = x\r\n- Symmetric: if x = y, then y = x\r\n- Transitive: if x = y and y = z, then x = z<\/pre><\/div>\r\n\r\n <h3>What is a Function?<\/h3>\r\n <p>A <strong>function<\/strong> f from A to B (written f: A \u2192 B) is a special relation where every element in A is related to EXACTLY ONE element in B.<\/p>\r\n <div class=\"code-block\"><pre>f: A \u2192 B\r\nA is the <strong>domain<\/strong>\r\nB is the <strong>codomain<\/strong>\r\nThe set of actual output values is the <strong>range<\/strong>\r\n\r\nExample:\r\nf(x) = x\u00b2\r\nDomain: \u211d (all real numbers)\r\nCodomain: \u211d\r\nRange: [0, \u221e) (non-negative reals only)<\/pre><\/div>\r\n\r\n <h3>Types of Functions<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Type<\/th><th>Definition<\/th><th>Diagram<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>One-to-One (Injective)<\/td><td>Different inputs \u2192 different outputs<br\/>If f(x\u2081) = f(x\u2082), then x\u2081 = x\u2082<\/td><td>Each output has at most one input<\/td><\/tr>\r\n <tr><td>Onto (Surjective)<\/td><td>Every element in codomain is an output<br\/>Range = Codomain<\/td><td>Every output is used<\/td><\/tr>\r\n <tr><td>Bijective<\/td><td>Both one-to-one AND onto<\/td><td>Perfect pairing \u2014 each input has exactly one output, and vice versa<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Function Examples<\/h3>\r\n <div class=\"code-block\"><pre><strong>One-to-One but NOT Onto:<\/strong>\r\nf: \u211d \u2192 \u211d, f(x) = 2x\r\nOne-to-one: different x \u2192 different 2x\r\nNot onto: odd numbers never appear as outputs\r\n\r\n<strong>Onto but NOT One-to-One:<\/strong>\r\nf: \u211d \u2192 \u211d, f(x) = x\u00b2\r\nOnto [0,\u221e): all non-negative numbers are outputs\r\nNot one-to-one: f(2) = f(-2) = 4\r\n\r\n<strong>Bijective:<\/strong>\r\nf: \u211d \u2192 \u211d, f(x) = x + 5\r\nOne-to-one: different x \u2192 different x+5\r\nOnto: every real number y = x+5 for some x<\/pre><\/div>\r\n\r\n <h3>Composition of Functions<\/h3>\r\n <p>If f: A \u2192 B and g: B \u2192 C, then (g \u2218 f): A \u2192 C is defined as (g \u2218 f)(x) = g(f(x))<\/p>\r\n <div class=\"code-block\"><pre>f(x) = x + 3\r\ng(x) = 2x\r\n\r\n(g \u2218 f)(x) = g(f(x)) = g(x+3) = 2(x+3) = 2x + 6\r\n(f \u2218 g)(x) = f(g(x)) = f(2x) = 2x + 3\r\n\r\nNote: g \u2218 f \u2260 f \u2218 g (order matters!)<\/pre><\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> Let R = {(1,1), (2,2), (1,2), (2,1)} on set {1,2}. Check if R is reflexive, symmetric, and transitive. Also, determine if f(x) = 3x \u2212 5 is one-to-one, onto, or bijective from \u211d to \u211d.<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-6\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 6<\/span>\r\n <h2>Mathematical Induction<\/h2>\r\n <p>Proving statements for all natural numbers \u2014 the domino effect.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is Mathematical Induction?<\/h3>\r\n <p><strong>Mathematical induction<\/strong> is a proof technique used to prove statements about all natural numbers (or integers). Think of it like dominoes \u2014 if the first falls and each domino knocks down the next, all dominoes will fall!<\/p>\r\n <div class=\"info-box\">\ud83d\udca1 Induction has two steps: (1) Base Case \u2014 prove it's true for n=1 (first domino falls), (2) Inductive Step \u2014 prove if it's true for n=k, then it's also true for n=k+1 (each domino knocks the next).<\/div>\r\n\r\n <h3>Principle of Mathematical Induction<\/h3>\r\n <p>To prove a statement P(n) is true for all n \u2265 1:<\/p>\r\n <ul>\r\n <li><strong>Step 1 (Base Case):<\/strong> Prove P(1) is true<\/li>\r\n <li><strong>Step 2 (Inductive Hypothesis):<\/strong> Assume P(k) is true for some arbitrary k \u2265 1<\/li>\r\n <li><strong>Step 3 (Inductive Step):<\/strong> Using the assumption, prove P(k+1) is true<\/li>\r\n <li><strong>Conclusion:<\/strong> By induction, P(n) is true for all n \u2265 1<\/li>\r\n <\/ul>\r\n\r\n <h3>Example 1: Sum of First n Natural Numbers<\/h3>\r\n <p><strong>Prove:<\/strong> 1 + 2 + 3 + ... + n = n(n+1)\/2<\/p>\r\n <div class=\"code-block\"><pre><strong>Step 1: Base Case (n=1)<\/strong>\r\nLeft side: 1\r\nRight side: 1(1+1)\/2 = 1\r\n\u2713 True for n=1\r\n\r\n<strong>Step 2: Inductive Hypothesis<\/strong>\r\nAssume true for n=k:\r\n1 + 2 + 3 + ... + k = k(k+1)\/2\r\n\r\n<strong>Step 3: Inductive Step (prove for n=k+1)<\/strong>\r\nNeed to show: 1 + 2 + ... + k + (k+1) = (k+1)(k+2)\/2\r\n\r\nLeft side:\r\n= [1 + 2 + ... + k] + (k+1)\r\n= k(k+1)\/2 + (k+1) [using hypothesis]\r\n= k(k+1)\/2 + 2(k+1)\/2\r\n= [k(k+1) + 2(k+1)]\/2\r\n= (k+1)(k+2)\/2 [factoring]\r\n= Right side \u2713\r\n\r\n<strong>Conclusion:<\/strong> By induction, formula is true for all n \u2265 1.<\/pre><\/div>\r\n\r\n <h3>Example 2: Power Inequality<\/h3>\r\n <p><strong>Prove:<\/strong> 2\u207f > n for all n \u2265 1<\/p>\r\n <div class=\"code-block\"><pre><strong>Base Case (n=1):<\/strong>\r\n2\u00b9 = 2 > 1 \u2713\r\n\r\n<strong>Inductive Hypothesis:<\/strong>\r\nAssume 2^k > k for some k \u2265 1\r\n\r\n<strong>Inductive Step (prove 2^(k+1) > k+1):<\/strong>\r\n2^(k+1) = 2 \u00b7 2^k\r\n > 2 \u00b7 k [using hypothesis: 2^k > k]\r\n = k + k\r\n \u2265 k + 1 [since k \u2265 1]\r\n\u2234 2^(k+1) > k+1 \u2713\r\n\r\n<strong>Conclusion:<\/strong> By induction, 2\u207f > n for all n \u2265 1.<\/pre><\/div>\r\n\r\n <h3>Strong Induction<\/h3>\r\n <p>In <strong>strong induction<\/strong>, we assume P(1), P(2), ..., P(k) are ALL true (not just P(k)), then prove P(k+1).<\/p>\r\n <div class=\"code-block\"><pre>Regular Induction: Assume P(k) \u2192 Prove P(k+1)\r\nStrong Induction: Assume P(1)\u2227P(2)\u2227...\u2227P(k) \u2192 Prove P(k+1)\r\n\r\nUse strong induction when proving P(k+1) requires\r\ninformation from multiple previous cases.<\/pre><\/div>\r\n\r\n <h3>Common Mistakes in Induction<\/h3>\r\n <ul>\r\n <li><strong>Forgetting Base Case<\/strong> \u2014 Always prove for n=1 (or starting value)<\/li>\r\n <li><strong>Not Using Hypothesis<\/strong> \u2014 Must explicitly use P(k) assumption in step 3<\/li>\r\n <li><strong>Proving Wrong Direction<\/strong> \u2014 Must prove P(k) \u2192 P(k+1), not the reverse<\/li>\r\n <li><strong>Circular Reasoning<\/strong> \u2014 Don't assume what you're trying to prove<\/li>\r\n <\/ul>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> Use induction to prove: (1) 1 + 3 + 5 + ... + (2n\u22121) = n\u00b2 (2) 3\u207f > 2n + 1 for all n \u2265 2. Show all three steps clearly.<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-7\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 7<\/span>\r\n <h2>Combinatorics \u2014 Counting Techniques<\/h2>\r\n <p>Permutations, combinations, and the art of counting.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is Combinatorics?<\/h3>\r\n <p><strong>Combinatorics<\/strong> is the branch of mathematics concerned with counting, arranging, and combining objects. It answers questions like \"How many ways can we arrange these items?\" or \"How many subsets can we choose?\"<\/p>\r\n\r\n <h3>Fundamental Counting Principles<\/h3>\r\n \r\n <h3>1. Addition Principle (OR)<\/h3>\r\n <p>If task A can be done in <strong>m<\/strong> ways and task B can be done in <strong>n<\/strong> ways, and they CANNOT be done together, then either A OR B can be done in <strong>m + n<\/strong> ways.<\/p>\r\n <div class=\"code-block\"><pre>Example: Travel from City X to City Y\r\n- By train: 3 routes\r\n- By bus: 5 routes\r\nTotal ways = 3 + 5 = 8 ways<\/pre><\/div>\r\n\r\n <h3>2. Multiplication Principle (AND)<\/h3>\r\n <p>If task A can be done in <strong>m<\/strong> ways and task B can be done in <strong>n<\/strong> ways, and both must be done, then A AND B can be done in <strong>m \u00d7 n<\/strong> ways.<\/p>\r\n <div class=\"code-block\"><pre>Example: Password with 1 letter + 1 digit\r\n- Letters: 26 ways\r\n- Digits: 10 ways\r\nTotal passwords = 26 \u00d7 10 = 260<\/pre><\/div>\r\n\r\n <h3>Permutations (Order Matters)<\/h3>\r\n <p>A <strong>permutation<\/strong> is an arrangement of objects where ORDER matters.<\/p>\r\n \r\n <h3>Permutation of n Objects<\/h3>\r\n <p>Number of ways to arrange n distinct objects = <strong>n!<\/strong> (n factorial)<\/p>\r\n <div class=\"code-block\"><pre>n! = n \u00d7 (n-1) \u00d7 (n-2) \u00d7 ... \u00d7 2 \u00d7 1\r\n\r\nExample: Arrange 4 books on a shelf\r\n4! = 4 \u00d7 3 \u00d7 2 \u00d7 1 = 24 ways<\/pre><\/div>\r\n\r\n <h3>Permutation of r Objects from n<\/h3>\r\n <p>P(n, r) or nPr = number of ways to arrange r objects chosen from n objects<\/p>\r\n <div class=\"code-block\"><pre>P(n, r) = n!\/(n-r)!\r\n\r\nExample: Choose and arrange 3 winners from 10 contestants\r\nP(10, 3) = 10!\/(10-3)! = 10!\/7! = 10\u00d79\u00d78 = 720 ways<\/pre><\/div>\r\n\r\n <h3>Combinations (Order Doesn't Matter)<\/h3>\r\n <p>A <strong>combination<\/strong> is a selection of objects where ORDER does NOT matter.<\/p>\r\n <div class=\"code-block\"><pre>C(n, r) or nCr = n!\/[r!(n-r)!]\r\n\r\nAlso written as (n choose r) or \u207fC\u1d63\r\n\r\nExample: Choose 3 students from 10 for a committee\r\nC(10, 3) = 10!\/[3!(10-3)!]\r\n = 10!\/(3!\u00d77!)\r\n = (10\u00d79\u00d78)\/(3\u00d72\u00d71)\r\n = 120 ways<\/pre><\/div>\r\n\r\n <h3>Permutation vs Combination<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Feature<\/th><th>Permutation<\/th><th>Combination<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Order<\/td><td>Matters<\/td><td>Does NOT matter<\/td><\/tr>\r\n <tr><td>Formula<\/td><td>P(n,r) = n!\/(n-r)!<\/td><td>C(n,r) = n!\/[r!(n-r)!]<\/td><\/tr>\r\n <tr><td>Example<\/td><td>PIN code 1234 \u2260 4321<\/td><td>Team {A,B,C} = {C,B,A}<\/td><\/tr>\r\n <tr><td>Result<\/td><td>Always larger<\/td><td>Always smaller<\/td><\/tr>\r\n <tr><td>Relationship<\/td><td colspan=\"2\">P(n,r) = r! \u00d7 C(n,r)<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Special Cases<\/h3>\r\n <div class=\"code-block\"><pre>C(n, 0) = 1 (one way to choose nothing)\r\nC(n, n) = 1 (one way to choose everything)\r\nC(n, r) = C(n, n-r) (symmetry property)\r\n\r\nExample: C(10, 3) = C(10, 7) = 120<\/pre><\/div>\r\n\r\n <h3>Permutations with Repetition<\/h3>\r\n <p>When objects are not all distinct:<\/p>\r\n <div class=\"code-block\"><pre>n!\/(n\u2081! \u00d7 n\u2082! \u00d7 ... \u00d7 n\u2096!)\r\n\r\nwhere n\u2081, n\u2082, ..., n\u2096 are counts of repeated objects\r\n\r\nExample: Arrange letters in \"MISSISSIPPI\"\r\nTotal letters = 11\r\nM:1, I:4, S:4, P:2\r\n\r\nArrangements = 11!\/(1!\u00d74!\u00d74!\u00d72!) = 34,650<\/pre><\/div>\r\n\r\n <h3>Common Problem Types<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Question Type<\/th><th>Use<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Arrange\/Order items<\/td><td>Permutation<\/td><\/tr>\r\n <tr><td>Select\/Choose items (no order)<\/td><td>Combination<\/td><\/tr>\r\n <tr><td>Form teams\/committees<\/td><td>Combination<\/td><\/tr>\r\n <tr><td>Assign ranks\/positions<\/td><td>Permutation<\/td><\/tr>\r\n <tr><td>Passwords\/PINs<\/td><td>Permutation with repetition allowed<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (1) How many 4-digit PINs can be formed using digits 0-9 with repetition? (2) How many ways can 5 people be seated in a row? (3) From 15 students, how many ways can we select a team of 4? (4) Arrange letters in \"BANANA\".<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-8\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 8<\/span>\r\n <h2>Discrete Probability<\/h2>\r\n <p>Calculating chances and likelihood of events.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is Probability?<\/h3>\r\n <p><strong>Probability<\/strong> measures how likely an event is to occur. It's a number between 0 (impossible) and 1 (certain).<\/p>\r\n <div class=\"code-block\"><pre>P(Event) = (Number of favorable outcomes) \/ (Total number of possible outcomes)\r\n\r\nP(E) \u2208 [0, 1]\r\nP(certain event) = 1\r\nP(impossible event) = 0<\/pre><\/div>\r\n\r\n <h3>Basic Probability Example<\/h3>\r\n <div class=\"code-block\"><pre>Rolling a fair die (6 faces: 1,2,3,4,5,6):\r\n\r\nP(getting 4) = 1\/6\r\nP(getting even) = 3\/6 = 1\/2 (faces: 2,4,6)\r\nP(getting \u2264 6) = 6\/6 = 1 (certain)\r\nP(getting 7) = 0\/6 = 0 (impossible)<\/pre><\/div>\r\n\r\n <h3>Complement Rule<\/h3>\r\n <p>The probability that an event does NOT occur:<\/p>\r\n <div class=\"code-block\"><pre>P(not E) = 1 \u2212 P(E)\r\nor\r\nP(E') = 1 \u2212 P(E)\r\n\r\nExample: P(not getting 4) = 1 \u2212 1\/6 = 5\/6<\/pre><\/div>\r\n\r\n <h3>Addition Rule (OR)<\/h3>\r\n <p>For mutually exclusive events (cannot happen together):<\/p>\r\n <div class=\"code-block\"><pre>P(A or B) = P(A \u222a B) = P(A) + P(B)\r\n\r\nExample: Drawing a card\r\nP(Ace or King) = P(Ace) + P(King)\r\n = 4\/52 + 4\/52 = 8\/52 = 2\/13<\/pre><\/div>\r\n\r\n <p>For non-mutually exclusive events (can happen together):<\/p>\r\n <div class=\"code-block\"><pre>P(A or B) = P(A) + P(B) \u2212 P(A and B)\r\n\r\nExample: Drawing a card\r\nP(Heart or King) = P(Heart) + P(King) \u2212 P(King of Hearts)\r\n = 13\/52 + 4\/52 \u2212 1\/52\r\n = 16\/52 = 4\/13<\/pre><\/div>\r\n\r\n <h3>Multiplication Rule (AND)<\/h3>\r\n <p>For independent events (one doesn't affect the other):<\/p>\r\n <div class=\"code-block\"><pre>P(A and B) = P(A \u2229 B) = P(A) \u00d7 P(B)\r\n\r\nExample: Flipping two coins\r\nP(both heads) = P(H on first) \u00d7 P(H on second)\r\n = 1\/2 \u00d7 1\/2 = 1\/4<\/pre><\/div>\r\n\r\n <h3>Conditional Probability<\/h3>\r\n <p>Probability of A given that B has occurred:<\/p>\r\n <div class=\"code-block\"><pre>P(A|B) = P(A \u2229 B) \/ P(B)\r\n\r\nExample: Two dice rolled, sum is 8\r\nP(first die is 3 | sum is 8)\r\n\r\nOutcomes where sum = 8: (2,6),(3,5),(4,4),(5,3),(6,2) = 5 outcomes\r\nOutcomes where first = 3 and sum = 8: (3,5) = 1 outcome\r\n\r\nP(first=3 | sum=8) = 1\/5<\/pre><\/div>\r\n\r\n <h3>Independent vs Dependent Events<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Type<\/th><th>Definition<\/th><th>Example<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Independent<\/td><td>One event doesn't affect the other<br\/>P(A|B) = P(A)<\/td><td>Flipping two coins<\/td><\/tr>\r\n <tr><td>Dependent<\/td><td>One event affects the other<br\/>P(A|B) \u2260 P(A)<\/td><td>Drawing cards without replacement<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Expected Value<\/h3>\r\n <p>The average outcome if an experiment is repeated many times:<\/p>\r\n <div class=\"code-block\"><pre>E(X) = \u03a3 [x \u00d7 P(x)]\r\n\r\nExample: Rolling a die\r\nE(X) = 1\u00d7(1\/6) + 2\u00d7(1\/6) + 3\u00d7(1\/6) + 4\u00d7(1\/6) + 5\u00d7(1\/6) + 6\u00d7(1\/6)\r\n = (1+2+3+4+5+6)\/6\r\n = 21\/6 = 3.5<\/pre><\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (1) A box has 5 red and 3 blue balls. What's P(red)? (2) If you flip 3 coins, what's P(at least 2 heads)? (3) Two cards drawn without replacement from 52 cards. What's P(both aces)?<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-9\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 9<\/span>\r\n <h2>Graph Theory Basics<\/h2>\r\n <p>Vertices, edges, and network connections.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is a Graph?<\/h3>\r\n <p>A <strong>graph<\/strong> G = (V, E) is a collection of <strong>vertices<\/strong> (nodes) V and <strong>edges<\/strong> (connections) E that connect pairs of vertices. Graphs model relationships and networks.<\/p>\r\n <div class=\"info-box\">\ud83d\udca1 Real-world graphs: Social networks (friends as vertices, friendships as edges), road maps (cities as vertices, roads as edges), computer networks (devices as vertices, connections as edges).<\/div>\r\n\r\n <h3>Graph Terminology<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Term<\/th><th>Definition<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Vertex (Node)<\/td><td>A point in the graph<\/td><\/tr>\r\n <tr><td>Edge (Link)<\/td><td>Connection between two vertices<\/td><\/tr>\r\n <tr><td>Adjacent Vertices<\/td><td>Two vertices connected by an edge<\/td><\/tr>\r\n <tr><td>Degree<\/td><td>Number of edges connected to a vertex<\/td><\/tr>\r\n <tr><td>Path<\/td><td>Sequence of vertices connected by edges<\/td><\/tr>\r\n <tr><td>Cycle<\/td><td>Path that starts and ends at the same vertex<\/td><\/tr>\r\n <tr><td>Connected Graph<\/td><td>There's a path between every pair of vertices<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Types of Graphs<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Type<\/th><th>Description<\/th><th>Example<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Undirected Graph<\/td><td>Edges have no direction (bidirectional)<\/td><td>Friendship network<\/td><\/tr>\r\n <tr><td>Directed Graph (Digraph)<\/td><td>Edges have direction (arrows)<\/td><td>Twitter followers<\/td><\/tr>\r\n <tr><td>Weighted Graph<\/td><td>Edges have associated weights\/costs<\/td><td>Road network with distances<\/td><\/tr>\r\n <tr><td>Simple Graph<\/td><td>No loops, no multiple edges<\/td><td>Most common type<\/td><\/tr>\r\n <tr><td>Complete Graph Kn<\/td><td>Every vertex connected to every other<\/td><td>K\u2084 has 6 edges<\/td><\/tr>\r\n <tr><td>Bipartite Graph<\/td><td>Vertices split into two sets, edges only between sets<\/td><td>Students-Courses matching<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Degree of a Vertex<\/h3>\r\n <p>The <strong>degree<\/strong> of a vertex is the number of edges connected to it.<\/p>\r\n <div class=\"code-block\"><pre>In undirected graph:\r\ndeg(v) = number of edges at vertex v\r\n\r\nIn directed graph:\r\nin-degree = number of edges coming IN\r\nout-degree = number of edges going OUT<\/pre><\/div>\r\n\r\n <h3>Handshaking Lemma<\/h3>\r\n <p>The sum of all vertex degrees equals twice the number of edges:<\/p>\r\n <div class=\"code-block\"><pre>\u03a3 deg(v) = 2|E|\r\n\r\nWhy? Each edge contributes 1 to the degree of TWO vertices.\r\n\r\nCorollary: In any graph, the number of vertices\r\nwith odd degree is EVEN.<\/pre><\/div>\r\n\r\n <h3>Paths and Cycles<\/h3>\r\n <ul>\r\n <li><strong>Path:<\/strong> Sequence of vertices where each adjacent pair is connected by an edge<\/li>\r\n <li><strong>Simple Path:<\/strong> No vertex is repeated<\/li>\r\n <li><strong>Cycle:<\/strong> Path that starts and ends at the same vertex<\/li>\r\n <li><strong>Simple Cycle:<\/strong> Cycle with no repeated vertices (except first\/last)<\/li>\r\n <\/ul>\r\n\r\n <h3>Euler and Hamilton Paths<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Type<\/th><th>Definition<\/th><th>Exists When<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Euler Path<\/td><td>Path that visits every EDGE exactly once<\/td><td>0 or 2 vertices of odd degree<\/td><\/tr>\r\n <tr><td>Euler Circuit<\/td><td>Euler path that starts\/ends at same vertex<\/td><td>All vertices have even degree<\/td><\/tr>\r\n <tr><td>Hamilton Path<\/td><td>Path that visits every VERTEX exactly once<\/td><td>No simple rule (NP-complete)<\/td><\/tr>\r\n <tr><td>Hamilton Circuit<\/td><td>Hamilton path that starts\/ends at same vertex<\/td><td>No simple rule<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Graph Representation<\/h3>\r\n \r\n <h3>1. Adjacency Matrix<\/h3>\r\n <p>A matrix where entry (i,j) = 1 if edge exists between vertex i and j, otherwise 0.<\/p>\r\n <div class=\"code-block\"><pre>Graph: A-B, B-C, A-C\r\n\r\n A B C\r\nA [ 0 1 1 ]\r\nB [ 1 0 1 ]\r\nC [ 1 1 0 ]<\/pre><\/div>\r\n\r\n <h3>2. Adjacency List<\/h3>\r\n <p>For each vertex, list its adjacent vertices.<\/p>\r\n <div class=\"code-block\"><pre>A: [B, C]\r\nB: [A, C]\r\nC: [A, B]<\/pre><\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (1) Draw a graph with 5 vertices and 7 edges. Calculate each vertex's degree. (2) Verify the handshaking lemma. (3) Determine if a graph with degrees [2,2,3,3,4] is possible.<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-10\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 10<\/span>\r\n <h2>Trees<\/h2>\r\n <p>Special graphs \u2014 hierarchical structures without cycles.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is a Tree?<\/h3>\r\n <p>A <strong>tree<\/strong> is a connected graph with NO cycles. It's the most fundamental hierarchical structure in computer science.<\/p>\r\n <div class=\"info-box\">\ud83d\udca1 Real-world trees: File system directories, organization charts, family trees, decision trees, HTML DOM, binary search trees in databases.<\/div>\r\n\r\n <h3>Properties of Trees<\/h3>\r\n <ul>\r\n <li>A tree with n vertices has exactly <strong>n \u2212 1<\/strong> edges<\/li>\r\n <li>There is exactly <strong>one path<\/strong> between any two vertices<\/li>\r\n <li>Removing any edge disconnects the tree<\/li>\r\n <li>Adding any edge creates exactly one cycle<\/li>\r\n <li>A tree is a <strong>minimally connected<\/strong> graph<\/li>\r\n <\/ul>\r\n\r\n <h3>Tree Terminology<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Term<\/th><th>Definition<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Root<\/td><td>The topmost vertex (in rooted trees)<\/td><\/tr>\r\n <tr><td>Parent<\/td><td>Vertex directly above another<\/td><\/tr>\r\n <tr><td>Child<\/td><td>Vertex directly below another<\/td><\/tr>\r\n <tr><td>Leaf (Terminal)<\/td><td>Vertex with no children<\/td><\/tr>\r\n <tr><td>Internal Vertex<\/td><td>Vertex with at least one child<\/td><\/tr>\r\n <tr><td>Sibling<\/td><td>Vertices with the same parent<\/td><\/tr>\r\n <tr><td>Ancestor<\/td><td>Any vertex on path from root to this vertex<\/td><\/tr>\r\n <tr><td>Descendant<\/td><td>Any vertex in subtree rooted at this vertex<\/td><\/tr>\r\n <tr><td>Level<\/td><td>Distance from root (root is level 0)<\/td><\/tr>\r\n <tr><td>Height<\/td><td>Maximum level in the tree<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Types of Trees<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Type<\/th><th>Description<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Binary Tree<\/td><td>Each vertex has at most 2 children (left and right)<\/td><\/tr>\r\n <tr><td>Full Binary Tree<\/td><td>Every vertex has 0 or 2 children<\/td><\/tr>\r\n <tr><td>Complete Binary Tree<\/td><td>All levels filled except possibly the last, filled left to right<\/td><\/tr>\r\n <tr><td>Perfect Binary Tree<\/td><td>All internal vertices have 2 children, all leaves at same level<\/td><\/tr>\r\n <tr><td>Binary Search Tree (BST)<\/td><td>Left child < parent < right child<\/td><\/tr>\r\n <tr><td>Spanning Tree<\/td><td>Subgraph that includes all vertices and is a tree<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Binary Tree Properties<\/h3>\r\n <div class=\"code-block\"><pre>For a binary tree with n vertices:\r\n- Maximum number of vertices at level i = 2^i\r\n- Maximum vertices in tree of height h = 2^(h+1) \u2212 1\r\n- Minimum height for n vertices = \u2308log\u2082(n+1)\u2309 \u2212 1\r\n\r\nFor a perfect binary tree:\r\n- Height h \u2192 vertices = 2^(h+1) \u2212 1\r\n- Height h \u2192 leaves = 2^h<\/pre><\/div>\r\n\r\n <h3>Tree Traversal Methods<\/h3>\r\n <p>Ways to visit all vertices in a tree:<\/p>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Method<\/th><th>Order<\/th><th>Use Case<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Preorder<\/td><td>Root \u2192 Left \u2192 Right<\/td><td>Copy a tree, prefix expression<\/td><\/tr>\r\n <tr><td>Inorder<\/td><td>Left \u2192 Root \u2192 Right<\/td><td>BST gives sorted order<\/td><\/tr>\r\n <tr><td>Postorder<\/td><td>Left \u2192 Right \u2192 Root<\/td><td>Delete a tree, postfix expression<\/td><\/tr>\r\n <tr><td>Level-order (BFS)<\/td><td>Level by level, left to right<\/td><td>Shortest path, level-wise processing<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Spanning Trees<\/h3>\r\n <p>A <strong>spanning tree<\/strong> of a connected graph G is a subgraph that:<\/p>\r\n <ul>\r\n <li>Includes all vertices of G<\/li>\r\n <li>Is a tree (connected, no cycles)<\/li>\r\n <li>Has exactly n \u2212 1 edges (where n = number of vertices)<\/li>\r\n <\/ul>\r\n\r\n <h3>Minimum Spanning Tree (MST)<\/h3>\r\n <p>For a weighted graph, the MST is the spanning tree with minimum total edge weight.<\/p>\r\n <div class=\"code-block\"><pre>Algorithms to find MST:\r\n1. Kruskal's Algorithm \u2014 Sort edges, add smallest without creating cycle\r\n2. Prim's Algorithm \u2014 Start from a vertex, grow tree by adding cheapest edge<\/pre><\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (1) Draw a binary tree with 7 vertices. Identify root, leaves, and height. (2) For tree with root A, children B,C; B has children D,E; C has child F \u2014 write preorder, inorder, and postorder traversals. (3) How many edges in a tree with 15 vertices?<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-11\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 11<\/span>\r\n <h2>Boolean Algebra<\/h2>\r\n <p>Mathematical foundation of digital logic and computer circuits.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is Boolean Algebra?<\/h3>\r\n <p><strong>Boolean algebra<\/strong> is a branch of mathematics that deals with variables that have only two possible values: <strong>true (1)<\/strong> or <strong>false (0)<\/strong>. It's the mathematical foundation of digital electronics and computer logic.<\/p>\r\n\r\n <h3>Boolean Operations<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Operation<\/th><th>Symbol<\/th><th>Name<\/th><th>Result<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>AND<\/td><td>\u00b7 or \u2227<\/td><td>Conjunction<\/td><td>1 only if both are 1<\/td><\/tr>\r\n <tr><td>OR<\/td><td>+ or \u2228<\/td><td>Disjunction<\/td><td>1 if at least one is 1<\/td><\/tr>\r\n <tr><td>NOT<\/td><td>' or \u00ac<\/td><td>Negation<\/td><td>Flips the value<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Boolean Algebra Laws<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Law<\/th><th>AND Form<\/th><th>OR Form<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Identity<\/td><td>x \u00b7 1 = x<\/td><td>x + 0 = x<\/td><\/tr>\r\n <tr><td>Null\/Domination<\/td><td>x \u00b7 0 = 0<\/td><td>x + 1 = 1<\/td><\/tr>\r\n <tr><td>Idempotent<\/td><td>x \u00b7 x = x<\/td><td>x + x = x<\/td><\/tr>\r\n <tr><td>Complement<\/td><td>x \u00b7 x' = 0<\/td><td>x + x' = 1<\/td><\/tr>\r\n <tr><td>Involution<\/td><td colspan=\"2\">(x')' = x<\/td><\/tr>\r\n <tr><td>Commutative<\/td><td>x \u00b7 y = y \u00b7 x<\/td><td>x + y = y + x<\/td><\/tr>\r\n <tr><td>Associative<\/td><td>(x\u00b7y)\u00b7z = x\u00b7(y\u00b7z)<\/td><td>(x+y)+z = x+(y+z)<\/td><\/tr>\r\n <tr><td>Distributive<\/td><td>x\u00b7(y+z) = x\u00b7y + x\u00b7z<\/td><td>x+(y\u00b7z) = (x+y)\u00b7(x+z)<\/td><\/tr>\r\n <tr><td>Absorption<\/td><td>x\u00b7(x+y) = x<\/td><td>x + x\u00b7y = x<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>De Morgan's Laws<\/h3>\r\n <div class=\"code-block\"><pre>(x \u00b7 y)' = x' + y'\r\n(x + y)' = x' \u00b7 y'\r\n\r\nIn words:\r\n\"The complement of AND is OR of complements\"\r\n\"The complement of OR is AND of complements\"<\/pre><\/div>\r\n\r\n <h3>Simplification Example<\/h3>\r\n <div class=\"code-block\"><pre>Simplify: F = x\u00b7y + x\u00b7y'\r\n\r\nStep 1: Factor out x\r\nF = x\u00b7(y + y')\r\n\r\nStep 2: Apply complement law: y + y' = 1\r\nF = x\u00b71\r\n\r\nStep 3: Apply identity law: x\u00b71 = x\r\nF = x\r\n\r\nResult: The expression simplifies to just x!<\/pre><\/div>\r\n\r\n <h3>Boolean Functions<\/h3>\r\n <p>A Boolean function maps Boolean inputs to a Boolean output:<\/p>\r\n <div class=\"code-block\"><pre>f(x, y, z) = x\u00b7y' + x'\u00b7z\r\n\r\nTruth table:\r\nx y z | f\r\n0 0 0 | 0\r\n0 0 1 | 1\r\n0 1 0 | 0\r\n0 1 1 | 1\r\n1 0 0 | 1\r\n1 0 1 | 1\r\n1 1 0 | 0\r\n1 1 1 | 0<\/pre><\/div>\r\n\r\n <h3>Canonical Forms<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Form<\/th><th>Description<\/th><th>Example<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Sum of Products (SOP)<\/td><td>OR of AND terms (minterms)<\/td><td>x'y + xy'<\/td><\/tr>\r\n <tr><td>Product of Sums (POS)<\/td><td>AND of OR terms (maxterms)<\/td><td>(x+y)\u00b7(x'+y')<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <div class=\"info-box\">\ud83d\udca1 Boolean algebra is directly implemented in computer circuits using logic gates (AND, OR, NOT gates). Every computation in a computer ultimately reduces to Boolean operations!<\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (1) Simplify: F = x\u00b7y + x\u00b7y' + x'\u00b7y using Boolean laws. (2) Prove De Morgan's law (x+y)' = x'\u00b7y' using a truth table. (3) Convert F = x'y'z + xyz' to Product of Sums form.<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-12\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 12<\/span>\r\n <h2>Recurrence Relations<\/h2>\r\n <p>Sequences defined recursively \u2014 solving recursive formulas.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is a Recurrence Relation?<\/h3>\r\n <p>A <strong>recurrence relation<\/strong> is an equation that defines a sequence based on previous terms. Each term is expressed as a function of earlier terms.<\/p>\r\n <div class=\"info-box\">\ud83d\udca1 Famous example: Fibonacci sequence \u2014 each number is the sum of the previous two: F(n) = F(n-1) + F(n-2), with F(0)=0, F(1)=1.<\/div>\r\n\r\n <h3>Components of a Recurrence Relation<\/h3>\r\n <ul>\r\n <li><strong>Recurrence equation:<\/strong> The recursive formula<\/li>\r\n <li><strong>Initial conditions:<\/strong> Base case values<\/li>\r\n <\/ul>\r\n <div class=\"code-block\"><pre>Example: a_n = 2\u00b7a_(n-1) + 3 with a_0 = 1\r\n\r\na_0 = 1 (initial condition)\r\na_1 = 2\u00b71 + 3 = 5\r\na_2 = 2\u00b75 + 3 = 13\r\na_3 = 2\u00b713 + 3 = 29\r\n...<\/pre><\/div>\r\n\r\n <h3>Types of Recurrence Relations<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Type<\/th><th>Form<\/th><th>Example<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Linear Homogeneous<\/td><td>a_n = c\u2081\u00b7a_(n-1) + c\u2082\u00b7a_(n-2)<\/td><td>a_n = 3a_(n-1) \u2212 2a_(n-2)<\/td><\/tr>\r\n <tr><td>Linear Non-Homogeneous<\/td><td>a_n = c\u2081\u00b7a_(n-1) + f(n)<\/td><td>a_n = 2a_(n-1) + n<\/td><\/tr>\r\n <tr><td>First-Order<\/td><td>Depends on one previous term<\/td><td>a_n = 2a_(n-1) + 1<\/td><\/tr>\r\n <tr><td>Second-Order<\/td><td>Depends on two previous terms<\/td><td>a_n = a_(n-1) + a_(n-2)<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Solving Linear Homogeneous Recurrence Relations<\/h3>\r\n <p>For: a_n = c\u2081\u00b7a_(n-1) + c\u2082\u00b7a_(n-2)<\/p>\r\n <p><strong>Step 1:<\/strong> Form characteristic equation: r\u00b2 = c\u2081\u00b7r + c\u2082<\/p>\r\n <p><strong>Step 2:<\/strong> Solve for roots r\u2081, r\u2082<\/p>\r\n <p><strong>Step 3:<\/strong> General solution depends on roots:<\/p>\r\n <ul>\r\n <li>Two distinct roots: a_n = A\u00b7r\u2081\u207f + B\u00b7r\u2082\u207f<\/li>\r\n <li>One repeated root r: a_n = (A + B\u00b7n)\u00b7r\u207f<\/li>\r\n <\/ul>\r\n <p><strong>Step 4:<\/strong> Use initial conditions to find A and B<\/p>\r\n\r\n <h3>Example: Solve a_n = 5a_(n-1) \u2212 6a_(n-2), a_0=1, a_1=4<\/h3>\r\n <div class=\"code-block\"><pre><strong>Step 1: Characteristic equation<\/strong>\r\nr\u00b2 = 5r \u2212 6\r\nr\u00b2 \u2212 5r + 6 = 0\r\n(r \u2212 2)(r \u2212 3) = 0\r\nr\u2081 = 2, r\u2082 = 3\r\n\r\n<strong>Step 2: General solution (two distinct roots)<\/strong>\r\na_n = A\u00b72\u207f + B\u00b73\u207f\r\n\r\n<strong>Step 3: Apply initial conditions<\/strong>\r\na_0 = 1: A\u00b72\u2070 + B\u00b73\u2070 = 1 \u2192 A + B = 1\r\na_1 = 4: A\u00b72\u00b9 + B\u00b73\u00b9 = 4 \u2192 2A + 3B = 4\r\n\r\nSolve system:\r\nFrom first: B = 1 \u2212 A\r\nSubstitute: 2A + 3(1\u2212A) = 4\r\n 2A + 3 \u2212 3A = 4\r\n \u2212A = 1\r\n A = \u22121, B = 2\r\n\r\n<strong>Step 4: Final solution<\/strong>\r\na_n = \u22121\u00b72\u207f + 2\u00b73\u207f = 2\u00b73\u207f \u2212 2\u207f\r\n\r\nVerify: a_0 = 2\u00b71 \u2212 1 = 1 \u2713\r\n a_1 = 2\u00b73 \u2212 2 = 4 \u2713<\/pre><\/div>\r\n\r\n <h3>Famous Recurrence Relations<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Sequence<\/th><th>Recurrence<\/th><th>Initial<\/th><th>Closed Form<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Fibonacci<\/td><td>F_n = F_(n-1) + F_(n-2)<\/td><td>F_0=0, F_1=1<\/td><td>F_n = (\u03c6\u207f \u2212 \u03c8\u207f)\/\u221a5<\/td><\/tr>\r\n <tr><td>Geometric<\/td><td>a_n = r\u00b7a_(n-1)<\/td><td>a_0 = a<\/td><td>a_n = a\u00b7r\u207f<\/td><\/tr>\r\n <tr><td>Arithmetic<\/td><td>a_n = a_(n-1) + d<\/td><td>a_0 = a<\/td><td>a_n = a + n\u00b7d<\/td><\/tr>\r\n <tr><td>Tower of Hanoi<\/td><td>T_n = 2T_(n-1) + 1<\/td><td>T_1 = 1<\/td><td>T_n = 2\u207f \u2212 1<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (1) Solve a_n = 4a_(n-1) \u2212 4a_(n-2) with a_0=0, a_1=1. (2) Find closed form for a_n = a_(n-1) + 2 with a_0=3. (3) Verify that F_5 = 5 using Fibonacci recurrence F_n = F_(n-1) + F_(n-2).<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-13\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 13<\/span>\r\n <h2>Counting Principles & Pigeonhole Principle<\/h2>\r\n <p>Advanced counting techniques and a powerful proof tool.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>Inclusion-Exclusion Principle<\/h3>\r\n <p>For counting elements in unions of sets, avoiding double-counting:<\/p>\r\n <div class=\"code-block\"><pre><strong>For two sets:<\/strong>\r\n|A \u222a B| = |A| + |B| \u2212 |A \u2229 B|\r\n\r\n<strong>For three sets:<\/strong>\r\n|A \u222a B \u222a C| = |A| + |B| + |C|\r\n \u2212 |A \u2229 B| \u2212 |A \u2229 C| \u2212 |B \u2229 C|\r\n + |A \u2229 B \u2229 C|\r\n\r\nPattern: Add individual, subtract pairs, add triples...<\/pre><\/div>\r\n\r\n <h3>Example: Inclusion-Exclusion<\/h3>\r\n <div class=\"code-block\"><pre>In a class of 50 students:\r\n- 30 study Math\r\n- 25 study Physics\r\n- 10 study both\r\n\r\nHow many study at least one subject?\r\n\r\n|M \u222a P| = |M| + |P| \u2212 |M \u2229 P|\r\n = 30 + 25 \u2212 10\r\n = 45 students<\/pre><\/div>\r\n\r\n <h3>Pigeonhole Principle<\/h3>\r\n <p><strong>Simple version:<\/strong> If n+1 objects are placed into n boxes, then at least one box contains more than one object.<\/p>\r\n <div class=\"info-box\">\ud83d\udca1 Think of it like this: If 13 people are in a room, at least 2 were born in the same month (13 people, 12 months = pigeonhole principle!)<\/div>\r\n\r\n <h3>Generalized Pigeonhole Principle<\/h3>\r\n <p>If n objects are placed into k boxes, then at least one box contains at least <strong>\u2308n\/k\u2309<\/strong> objects.<\/p>\r\n <div class=\"code-block\"><pre>\u2308 \u2309 is the ceiling function (rounds up)\r\n\r\nExample: 50 students, 7 days of the week\r\nAt least one day has: \u230850\/7\u2309 = \u23087.14\u2309 = 8 students born on it<\/pre><\/div>\r\n\r\n <h3>Pigeonhole Principle Examples<\/h3>\r\n <div class=\"code-block\"><pre><strong>Example 1: Handshakes<\/strong>\r\nIn any group of 6 people, either:\r\n- 3 people mutually know each other, OR\r\n- 3 people are mutual strangers\r\n\r\n<strong>Example 2: Socks<\/strong>\r\nYou have 10 black socks and 10 white socks in a drawer.\r\nHow many must you grab (in the dark) to guarantee a matching pair?\r\n\r\nAnswer: 3 socks\r\n(2 colors = 2 boxes, so 3rd sock must match one)\r\n\r\n<strong>Example 3: Integers<\/strong>\r\nAmong any 5 integers, at least two have the same remainder\r\nwhen divided by 4.\r\n\r\nProof: 4 possible remainders (0,1,2,3) = 4 boxes\r\n 5 integers = 5 objects\r\n By pigeonhole: \u23085\/4\u2309 = 2 must have same remainder<\/pre><\/div>\r\n\r\n <h3>Counting with Restrictions<\/h3>\r\n \r\n <h3>1. Arrangements with Restrictions<\/h3>\r\n <div class=\"code-block\"><pre><strong>Problem:<\/strong> Arrange 5 people in a row where 2 specific people\r\nmust sit together.\r\n\r\n<strong>Solution:<\/strong> Treat the 2 as one unit\r\n- Units to arrange: 4 (the pair + 3 others) = 4! ways\r\n- Ways to arrange the pair internally = 2! ways\r\n- Total = 4! \u00d7 2! = 24 \u00d7 2 = 48 ways<\/pre><\/div>\r\n\r\n <h3>2. Distributing Objects into Boxes<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Objects<\/th><th>Boxes<\/th><th>Formula<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Distinct<\/td><td>Distinct<\/td><td>k^n (each object has k choices)<\/td><\/tr>\r\n <tr><td>Identical<\/td><td>Distinct<\/td><td>C(n+k-1, k-1) = stars and bars<\/td><\/tr>\r\n <tr><td>Distinct<\/td><td>Identical<\/td><td>Stirling numbers (complex)<\/td><\/tr>\r\n <tr><td>Identical<\/td><td>Identical<\/td><td>Integer partitions<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Stars and Bars Method<\/h3>\r\n <p>Distributing n identical objects into k distinct boxes:<\/p>\r\n <div class=\"code-block\"><pre>Number of ways = C(n + k \u2212 1, k \u2212 1)\r\n\r\nExample: Distribute 5 identical candies among 3 children\r\nC(5 + 3 \u2212 1, 3 \u2212 1) = C(7, 2) = 21 ways\r\n\r\nVisual: \u2605\u2605\u2605\u2605\u2605 with 2 bars | to separate:\r\n\u2605\u2605|\u2605|\u2605\u2605 means child1 gets 2, child2 gets 1, child3 gets 2<\/pre><\/div>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (1) In a class of 40, 25 play cricket, 20 play football, 10 play both. How many play neither? (2) Show that among 13 people, at least 2 share a birth month. (3) Distribute 8 identical books among 4 students using stars and bars.<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"unit-14\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Unit 14<\/span>\r\n <h2>Proof Techniques<\/h2>\r\n <p>Methods to prove mathematical statements \u2014 the foundation of rigorous thinking.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <h3>What is a Mathematical Proof?<\/h3>\r\n <p>A <strong>proof<\/strong> is a logical argument that establishes the truth of a mathematical statement beyond any doubt. It uses axioms, definitions, and previously proven results.<\/p>\r\n\r\n <h3>Types of Proof Techniques<\/h3>\r\n \r\n <h3>1. Direct Proof<\/h3>\r\n <p>Start with assumptions (hypothesis), use logical steps, arrive at conclusion.<\/p>\r\n <p><strong>Structure:<\/strong> Assume P is true \u2192 ... logical steps ... \u2192 Therefore Q is true<\/p>\r\n <div class=\"code-block\"><pre><strong>Example: Prove that if n is even, then n\u00b2 is even.<\/strong>\r\n\r\nProof:\r\nAssume n is even.\r\nThen n = 2k for some integer k (definition of even)\r\nn\u00b2 = (2k)\u00b2 = 4k\u00b2 = 2(2k\u00b2)\r\nSince 2k\u00b2 is an integer, n\u00b2 = 2m where m = 2k\u00b2\r\nTherefore n\u00b2 is even. \u220e<\/pre><\/div>\r\n\r\n <h3>2. Proof by Contrapositive<\/h3>\r\n <p>To prove P \u2192 Q, instead prove \u00acQ \u2192 \u00acP (contrapositive is logically equivalent)<\/p>\r\n <div class=\"code-block\"><pre><strong>Example: Prove if n\u00b2 is odd, then n is odd.<\/strong>\r\n\r\nInstead, prove: if n is even, then n\u00b2 is even\r\n(contrapositive of original statement)\r\n\r\nAssume n is even.\r\nn = 2k\r\nn\u00b2 = 4k\u00b2 = 2(2k\u00b2) \u2190 even\r\nTherefore, if n is even, n\u00b2 is even.\r\n\r\nBy contrapositive: if n\u00b2 is odd, then n is odd. \u220e<\/pre><\/div>\r\n\r\n <h3>3. Proof by Contradiction<\/h3>\r\n <p>Assume the statement is FALSE, derive a contradiction, conclude it must be TRUE.<\/p>\r\n <p><strong>Structure:<\/strong> Assume \u00acP \u2192 ... \u2192 Contradiction! \u2192 Therefore P must be true<\/p>\r\n <div class=\"code-block\"><pre><strong>Example: Prove \u221a2 is irrational.<\/strong>\r\n\r\nProof by contradiction:\r\nAssume \u221a2 is rational.\r\nThen \u221a2 = p\/q where p,q are integers, q\u22600, in lowest terms\r\n\r\n\u221a2 = p\/q\r\n2 = p\u00b2\/q\u00b2\r\np\u00b2 = 2q\u00b2 \u2190 p\u00b2 is even, so p is even\r\nLet p = 2k\r\n(2k)\u00b2 = 2q\u00b2\r\n4k\u00b2 = 2q\u00b2\r\nq\u00b2 = 2k\u00b2 \u2190 q\u00b2 is even, so q is even\r\n\r\nBut p and q are both even, contradicting \"lowest terms\"!\r\nTherefore \u221a2 must be irrational. \u220e<\/pre><\/div>\r\n\r\n <h3>4. Proof by Cases<\/h3>\r\n <p>Break the proof into exhaustive cases, prove each separately.<\/p>\r\n <div class=\"code-block\"><pre><strong>Example: Prove that n\u00b2 + n is even for all integers n.<\/strong>\r\n\r\nCase 1: n is even\r\nn = 2k\r\nn\u00b2 + n = (2k)\u00b2 + 2k = 4k\u00b2 + 2k = 2(2k\u00b2 + k) \u2190 even\r\n\r\nCase 2: n is odd\r\nn = 2k + 1\r\nn\u00b2 + n = (2k+1)\u00b2 + (2k+1)\r\n = 4k\u00b2 + 4k + 1 + 2k + 1\r\n = 4k\u00b2 + 6k + 2\r\n = 2(2k\u00b2 + 3k + 1) \u2190 even\r\n\r\nAll cases covered, so n\u00b2 + n is always even. \u220e<\/pre><\/div>\r\n\r\n <h3>5. Proof by Counterexample<\/h3>\r\n <p>To disprove a universal statement (\u2200x P(x)), find ONE example where it's false.<\/p>\r\n <div class=\"code-block\"><pre><strong>Disprove: \"All prime numbers are odd\"<\/strong>\r\n\r\nCounterexample: 2 is prime and even.\r\nTherefore the statement is FALSE. \u220e<\/pre><\/div>\r\n\r\n <h3>6. Mathematical Induction<\/h3>\r\n <p>(Already covered in Unit 6 \u2014 used to prove statements for all natural numbers)<\/p>\r\n\r\n <h3>Proof Strategies Summary<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Method<\/th><th>When to Use<\/th><th>Key Idea<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Direct Proof<\/td><td>P \u2192 Q seems straightforward<\/td><td>Assume P, deduce Q<\/td><\/tr>\r\n <tr><td>Contrapositive<\/td><td>\u00acQ \u2192 \u00acP is easier than P \u2192 Q<\/td><td>Prove equivalent statement<\/td><\/tr>\r\n <tr><td>Contradiction<\/td><td>Existence proofs, irrationality<\/td><td>Assume \u00acP leads to absurdity<\/td><\/tr>\r\n <tr><td>Cases<\/td><td>Natural divisions exist (even\/odd)<\/td><td>Exhaust all possibilities<\/td><\/tr>\r\n <tr><td>Counterexample<\/td><td>Disproving universal claims<\/td><td>Find one exception<\/td><\/tr>\r\n <tr><td>Induction<\/td><td>Statements about all integers \u2265 n<\/td><td>Base + inductive step<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>Common Proof-Writing Tips<\/h3>\r\n <ul>\r\n <li><strong>Start clearly:<\/strong> State what you're proving<\/li>\r\n <li><strong>Use definitions:<\/strong> Apply precise mathematical definitions<\/li>\r\n <li><strong>Show all steps:<\/strong> Don't skip logical leaps<\/li>\r\n <li><strong>Use proper notation:<\/strong> \u2200, \u2203, \u2192, \u21d4 correctly<\/li>\r\n <li><strong>End with \u220e or QED:<\/strong> Signals proof is complete<\/li>\r\n <li><strong>Check logic:<\/strong> Each step must follow from previous<\/li>\r\n <\/ul>\r\n\r\n <div class=\"practice\"><strong>\u270f\ufe0f Practice:<\/strong> (1) Prove directly: if n is odd, then n + 1 is even. (2) Prove by contradiction: there are infinitely many prime numbers. (3) Prove by cases: |xy| = |x|\u00b7|y| for all real numbers x, y.<\/div>\r\n <\/div>\r\n <\/div>\r\n\r\n \r\n <div class=\"congrats\">\r\n <h2>\ud83c\udf89 Congratulations!<\/h2>\r\n <p>You have completed the Discrete Mathematics Course by Pak Notes Hub! You now understand Logic, Sets, Graph Theory, Combinatorics, Proofs and more. Best of luck in your exams and future studies! \ud83c\udf1f<\/p>\r\n <\/div>\r\n\r\n \r\n <div class=\"unit\" id=\"summary\">\r\n <div class=\"unit-header\">\r\n <span class=\"unit-num-badge\">Summary<\/span>\r\n <h2>\ud83d\udcca Course Summary \u2014 14 Units<\/h2>\r\n <p>Quick reference of all topics covered.<\/p>\r\n <\/div>\r\n <div class=\"unit-body\">\r\n <table class=\"data-table\">\r\n <thead>\r\n <tr>\r\n <th style=\"width:50px\">#<\/th>\r\n <th style=\"width:200px\">Unit<\/th>\r\n <th>Key Concepts<\/th>\r\n <\/tr>\r\n <\/thead>\r\n <tbody>\r\n <tr><td>1<\/td><td>Introduction to Discrete Math<\/td><td>Discrete vs continuous, applications in CS<\/td><\/tr>\r\n <tr><td>2<\/td><td>Propositional Logic<\/td><td>Propositions, truth tables, logical operators (\u2227, \u2228, \u2192, \u2194)<\/td><\/tr>\r\n <tr><td>3<\/td><td>Predicate Logic & Quantifiers<\/td><td>Predicates, \u2200 (universal), \u2203 (existential), negation rules<\/td><\/tr>\r\n <tr><td>4<\/td><td>Sets & Set Operations<\/td><td>Union, intersection, difference, complement, Cartesian product, De Morgan's laws<\/td><\/tr>\r\n <tr><td>5<\/td><td>Relations & Functions<\/td><td>Types of relations, equivalence relations, one-to-one, onto, bijective functions<\/td><\/tr>\r\n <tr><td>6<\/td><td>Mathematical Induction<\/td><td>Base case, inductive hypothesis, inductive step, strong induction<\/td><\/tr>\r\n <tr><td>7<\/td><td>Combinatorics<\/td><td>Permutations P(n,r), combinations C(n,r), counting principles<\/td><\/tr>\r\n <tr><td>8<\/td><td>Discrete Probability<\/td><td>Basic probability, addition rule, multiplication rule, conditional probability, expected value<\/td><\/tr>\r\n <tr><td>9<\/td><td>Graph Theory Basics<\/td><td>Vertices, edges, degree, paths, cycles, Euler and Hamilton paths, graph representation<\/td><\/tr>\r\n <tr><td>10<\/td><td>Trees<\/td><td>Tree properties, binary trees, traversal methods (preorder, inorder, postorder), spanning trees<\/td><\/tr>\r\n <tr><td>11<\/td><td>Boolean Algebra<\/td><td>Boolean operations, laws, De Morgan's laws, simplification, SOP and POS forms<\/td><\/tr>\r\n <tr><td>12<\/td><td>Recurrence Relations<\/td><td>Recursive sequences, solving linear recurrences, characteristic equations, Fibonacci<\/td><\/tr>\r\n <tr><td>13<\/td><td>Counting Principles<\/td><td>Inclusion-exclusion principle, pigeonhole principle, stars and bars method<\/td><\/tr>\r\n <tr><td>14<\/td><td>Proof Techniques<\/td><td>Direct proof, contrapositive, contradiction, cases, counterexample, induction<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n\r\n <h3>\ud83d\udd11 Key Formulas \u2014 Quick Reference<\/h3>\r\n <table class=\"data-table\">\r\n <thead><tr><th>Concept<\/th><th>Formula<\/th><\/tr><\/thead>\r\n <tbody>\r\n <tr><td>Permutation<\/td><td>P(n,r) = n!\/(n\u2212r)!<\/td><\/tr>\r\n <tr><td>Combination<\/td><td>C(n,r) = n!\/[r!(n\u2212r)!]<\/td><\/tr>\r\n <tr><td>Pigeonhole Principle<\/td><td>\u2308n\/k\u2309 objects in at least one box<\/td><\/tr>\r\n <tr><td>Inclusion-Exclusion<\/td><td>|A\u222aB| = |A| + |B| \u2212 |A\u2229B|<\/td><\/tr>\r\n <tr><td>Handshaking Lemma<\/td><td>\u03a3 deg(v) = 2|E|<\/td><\/tr>\r\n <tr><td>Tree Edges<\/td><td>|E| = |V| \u2212 1<\/td><\/tr>\r\n <tr><td>Binary Tree Max Vertices<\/td><td>2^(h+1) \u2212 1<\/td><\/tr>\r\n <tr><td>Stars and Bars<\/td><td>C(n+k\u22121, k\u22121)<\/td><\/tr>\r\n <tr><td>Probability<\/td><td>P(E) = favorable\/total<\/td><\/tr>\r\n <tr><td>De Morgan's Laws<\/td><td>(A\u222aB)' = A'\u2229B', (A\u2229B)' = A'\u222aB'<\/td><\/tr>\r\n <\/tbody>\r\n <\/table>\r\n <\/div>\r\n <\/div>\r\n\r\n <\/main>\r\n<\/div>\r\n\r\n\r\n<button id=\"back-top\" aria-label=\"Back to top\">\u2191<\/button>\r\n\r\n<script>\r\n\/\/ Progress bar\r\nwindow.addEventListener('scroll', () => {\r\n const winScroll = document.body.scrollTop || document.documentElement.scrollTop;\r\n const height = document.documentElement.scrollHeight - document.documentElement.clientHeight;\r\n const scrolled = (winScroll \/ height) * 100;\r\n document.getElementById('progress').style.width = scrolled + '%';\r\n});\r\n\r\n\/\/ Back to top button\r\nconst backTop = document.getElementById('back-top');\r\nwindow.addEventListener('scroll', () => {\r\n if (window.pageYOffset > 300) {\r\n backTop.classList.add('visible');\r\n } else {\r\n backTop.classList.remove('visible');\r\n }\r\n});\r\nbackTop.addEventListener('click', () => {\r\n window.scrollTo({ top: 0, behavior: 'smooth' });\r\n});\r\n\r\n\/\/ Active TOC highlighting\r\nconst sections = document.querySelectorAll('.unit');\r\nconst navLinks = document.querySelectorAll('.toc-list a');\r\n\r\nwindow.addEventListener('scroll', () => {\r\n let current = '';\r\n sections.forEach(section => {\r\n const sectionTop = section.offsetTop;\r\n const sectionHeight = section.clientHeight;\r\n if (pageYOffset >= sectionTop - 100) {\r\n current = section.getAttribute('id');\r\n }\r\n });\r\n\r\n navLinks.forEach(link => {\r\n link.classList.remove('active');\r\n if (link.getAttribute('href') === '#' + current) {\r\n link.classList.add('active');\r\n }\r\n });\r\n});\r\n<\/script>\r\n\r\n<\/body>\r\n<\/html>\r\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"<p>Discrete Mathematics \u2013 University Level \u2013 Pak Notes Hub Pak Notes Hub Course Outline Start Learning Induction Graph Theory \ud83d\udcd0 University Level \u2014 BS CS \/ BS IT Discrete MathematicsComplete Notes Logic \u00b7 Sets \u00b7 Graph Theory \u00b7 Combinatorics \u00b7 Proofs \u2014 All in Easy English \ud83d\udd22 14 Units \ud83c\udf93 University Level \ud83d\udcca Examples \ud83d\udcdd […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_angie_page":false,"footnotes":""},"class_list":["post-456","page","type-page","status-publish","hentry"],"_hostinger_reach_plugin_has_subscription_block":false,"_hostinger_reach_plugin_is_elementor":false,"_links":{"self":[{"href":"https:\/\/paknoteshub.online\/index.php?rest_route=\/wp\/v2\/pages\/456","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/paknoteshub.online\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/paknoteshub.online\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/paknoteshub.online\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/paknoteshub.online\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=456"}],"version-history":[{"count":7,"href":"https:\/\/paknoteshub.online\/index.php?rest_route=\/wp\/v2\/pages\/456\/revisions"}],"predecessor-version":[{"id":464,"href":"https:\/\/paknoteshub.online\/index.php?rest_route=\/wp\/v2\/pages\/456\/revisions\/464"}],"wp:attachment":[{"href":"https:\/\/paknoteshub.online\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=456"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}