Notes (Thai) - Discrete Mathematics & Graph Theory

บันทึกย่อสาระสำคัญ (Thai) ของวิชาวิยุตคณิตสำหรับวิศวกรคอมพิวเตอร์

  • Page 1–2: แนวคิดพื้นฐาน

    • Discrete Mathematics คือการศึกษาสิ่งที่ไม่ต่อเนื่อง ไม่เป็นอนันต์ในลักษณะรบกวนต่อเนตเวิร์กคอมพิวเตอร์
    • ความสำคัญของตรรกศาสตร์และคณิตศาสตร์ในการพิสูจน์ความถูกต้องของวิธีคิดทางคอมพิวเตอร์
    • คำศัพท์พื้นฐาน: proof, proposition, axiom, theorem, lemma, corollary, conjecture, inference (ตรรกะ), predicate, quantifier
    • ตัวอย่างสั้น ๆ: ประโยคพิสูจน์เท่ากับจริง/เท็จผ่านหลักฐานจาก axioms และสัจพจน์ เช่น
    • Example:
      2+3=5
    • Example: ∀n ∈ ℕ, n^2 + n + 41 เป็นจำนวนเฉพาะ (ขยายในเนื้อหาและข้อจำกัด)
    • แนวคิดการอนุมานตรรกะและการพิสูจน์ทางคณิตศาสตร์ไม่ใช่เฉพาะคณิตศาสตร์เท่านั้น แต่อยู่ในชีวิตประจำวันด้วย

  • 1.2 Terminology (นิยามพื้นฐาน)

    • Definition (นิยาม): กำหนดคำจำกัดความเพื่อสะดวกในการใช้งาน
    • Axiom (สัจพจน์): ประพจน์ที่สมมุติว่าเป็นจริงเสมอ
    • Conjecture (บทคาดเดา): ประพจน์ที่คิดว่าน่าจะจริงแต่ยังพิสูจน์ไม่ได้
    • Theorem (ทฤษฎีบท): ประพจน์ที่พิสูจน์แล้วว่าเป็นจริง
    • Lemma (บทตั้ง): ประพจน์ที่พิสูจน์ได้แต่มีบทบาทรองในทฤษฎีบทที่สำคัญกว่า
    • Corollary (บทแทรก): ประพจน์ที่พิสูจน์ได้จากทฤษฎีบทที่พิสูจน์แล้ว
    • Proposition/Inference: กระบวนการสืบเหตุผล/อนุมานจากข้อมูล

  • 2. Logical reasoning (เหตุผลเชิงตรรกะ)

    • 2.1 Logical operators (ตัวดำเนินการตรรกะ)
    • and: P \land Q เป็นจริงเมื่อ P และ Q เป็นจริง
    • or: P \lor Q เป็นจริงเมื่ออย่างน้อยหนึ่งเป็นจริง
    • implies: P \(implies) Q จริงเมื่อ P เป็นจริงแล้ว Q ต้องจริง; ถ้า P is false แล้วผลลัพธ์เป็นได้ทั้งจริง/เท็จ
    • if and only if: P \leftrightarrow Q จริงเมื่อทั้งสองทิศทางเป็นจริง
    • negation: \neg P เท่ากับ P เป็นเท็จ
    • precedence & associativity (ลำดับความสำคัญและการนิยาม) ของตรรกะเทียบเท่ากับคณิตศาสตร์แบบทั่วไป
    • truth tables (ตารางค่าความจริง) และตัวอย่างการประยุกต์
    • 2.2 Logical inference
    • Inference rules (กฎอนุมาน) เช่น modus ponens, modus tollens, intro/elimination rules
    • ตัวอย่าง: ถ้าคุณอ่านหนังสือแล้วผ่านวิชา, ถ้าอ่านหนังสือจะผ่าน และถ้าไม่อ่านจะตกวิชา → สรุปว่าุณอ่านหนังสือแล้วจะผ่าน? (ดูกรณี) โดยใช้กฎ • -INTRO, -ELIM, AXIOM
    • 2.3 Proving equivalence
    • ความหมายของ equivalence (สมมูล) ระหว่าง P ⇒ Q และ Q ⇒ P
    • contrapositive: (P ⇒ Q) ≡ (¬Q ⇒ ¬P)
    • 2.4 Quantifiers
    • Universal quantifier: \forall x ∈ D: P(x) เป็นจริงเมื่อ P(x) จริงสำหรับทุก x ในโดเมน D
    • Existential quantifier: \exists x ∈ D: P(x) เป็นจริงเมื่อมีอย่างน้อยหนึ่ง x ใน D ที่ P(x) จริง
    • Nested quantifiers, scope, และ negating quantifiers
    • Example: prime(n) เกมตัวอย่างในเอกสาร
    • 2.5 Predicate formalization
    • ตัวอย่าง predicate เช่น divides(a,b): a|b แปลว่า ∃ c ∈ ℤ : b = a c
    • predicate เช่น prime(n): n ∈ ℤ, n > 1 และ ∀ d ∈ ℤ: d|n ⇒ d ∈ {1,n}
    • 2.6 Proof by cases
    • กรณีต่าง ๆ ที่สม่ำเสมอในผลลัพธ์
    • 2.7 Proof by contradiction
    • ใช้ negation และ contrapositive เพื่อหาข้อพิสูจน์โดยข้อขัดแย้ง
    • ตัวอย่าง: √2 เป็นจำนวนนอตรรกยะ (irrational) โดยใช้การพิสูจน์โดยข้อขัดแย้ง
    • 2.8 Proof of uniqueness
    • วิธีแสดงว่ามีค่าเพียงค่าเดียวที่ทำให้ประพจน์จริง เช่น ∃! x ∈ ℤ ∀ y ∈ ℤ: x y = x

  • 3 Collections (เซต/รายการ/ความสัมพันธ์)

    • 3.1 Sets (เซต)
    • นิยาม: เซตคือ collection ที่ไม่มีสมาชิกซ้ำและไม่เรียงลำดับ;
      ตัวอย่าง: A ⊆ B, A ∪ B, A ∩ B, A − B, A ⊆ B
    • power set pow(A) = { X | X ⊆ A } หรือ 2^A
    • ความสัมพันธ์ระหว่าง logic และ sets: ∧ ↔ ∩, ∨ ↔ ∪, ¬ ↔ complement, ⟹ ↔ ⊆, ⟺ ↔ =
    • 3.1.1 Connections between logic and sets (สอดคล้องระหว่างตรรกะกับเซต)
    • 3.1.2 Power sets
    • Theorem: x ∈ A ⇔ {x} ∈ pow(A)
    • 3.2 Lists (ลิสต์)
    • ตรงกับ tuples; concatenation ++ defined recursively
    • 3.3 Relations (ความสัมพันธ์)
    • R ⊆ A × B; domain(A) and codomain(B)
    • graph of a relation; image R(a); R(A) as image of A under R
    • inverse relation R^{-1}
    • properties of relations: reflexive, irreflexive, symmetric, antisymmetric, transitive
    • functions, total functions, injections, surjections, bijections
    • relational compositions: S ∘ R
    • 3.1.1 ถอดความ: ความสัมพันธ์และเซตเชื่อมโยงกับตรรกะและการคำนวณ

  • 4 Induction (อุปนัย)

    • 4.1 Inductive definitions: base case และ inductive case
    • 4.2 Structural induction: กรณีฐานและ inductive step สำหรับโครงสร้างที่นิยามโดย inductive definitions
    • 4.3 Proof by induction: ใช้ induction axiom
    • 4.3.1 Problem solving using induction: ตัวอย่างสวนหย่อมลายตัว L และการพิสูจน์
    • 4.3.2 Induction pitfalls: ตัวอย่าง not! (ล้มพิสูจน์ด้วยเหตุผลผิด) เช่น unstacking game
    • 4.4 Strong induction: นิยามและความแตกต่างจาก ordinary induction (IH holds for all smaller cases)
    • 4.4.1 The unstacking game (ตัวอย่าง strong induction)
    • 4.4.2 Induction vs strong induction: strong ใช้งานสะดวกกว่าในบางกรณี
    • 4.5 Loop invariants (ตัวยืนของลูป)
    • Establishment (initialization): ตรวจสอบ invariants ก่อน loop เริ่มต้น
    • Preservation (maintenance): invariants ยังคงจริงหลังรอบทุกครั้ง
    • Postcondition: ตรวจสอบผลลัพธ์เมื่อ loop สิ้นสุด
    • Termination: แสดงว่า loop จะจบเมื่อเงื่อนไขหยุดทำงาน
    • ตัวอย่าง: insertion sort; มีการวิเคราะห์ invariant ทั้ง outer loop และ inner loop

  • 5 Automata theory (ทฤษฎีออโตมาตา)

    • 5.1 State machines (เครื่องสถานะ)
    • deterministic vs nondeterministic
    • ปฏิบัติการด้วย state diagrams และ formal definitions
    • 5.2 Invariants (ตัวยืนในออโตมาตา)
    • ตัวอย่าง: invariant ในกรณี automata ที่เดิน diag ให้เป็นจริงตลอดเวลา
    • 5.3 Deterministic Finite Automata (DFA)
    • components: Q, q0, Σ, δ, F; δ : Q × Σ → Q (total); accept states F
    • 5.4 Regular languages
    • ภาษาใดที่มี DFA รับรู้เป็น regular language
    • ตัวอย่างภาษา: w ลงท้ายด้วย 1 หรือ w ลงท้ายด้วย 0, ฯลฯ
    • 5.4.1 Automata construction (Construction of DFAs) และ Regular operations
    • 5.5 Nondeterministic Finite Automata (NFA)
    • δ : Q × Σ_ε → P(Q) (ε-transitions allowed)
    • accept if any computation path ends in accept state
    • การแปลง NFA เป็น DFA (subset construction) ตาม Theorem 5.5.6
    • 5.6 Regular expressions (REs)
    • REs สามารถแทน languages ที่ DFA รับรู้ได้
    • การแปลง DFA → GNFA → RE (process of eliminating states)
    • เรื่องของ epsilon-transitions และการชดเชย transitions เมื่อกำจัด states
    • 5.7 Nonregular languages
    • ตัวอย่างเช่น B = {0^n 1^n | n ≥ 0}, C = {w | w มีจำนวน 0 และ 1 เท่ากัน}, D = {w | w มี 01 และ 10 เป็น substrings ที่เท่ากัน}
    • Pumping lemmas: pumping lemma for regular languages (Theorem 5.7.4)
    • 5.8 Context-free grammars (CFG) และ Pushdown automata (PDA)
    • CFG: V, Σ, R, S, รูปแบบ production rules ในแบบ N → (V ∪ Σ)^* และรูปแบบทั่วไป
    • CFG ตัวอย่าง: S → 0S1 ∣ ε; B = {0^n 1^n | n ≥ 0}
    • PDA: PDA เป็น automaton ที่มี stack เพื่อรับ CFL
    • non-context-free languages เช่น {a^n b^n c^n}, {ww} (เหมือนข้อมูลที่กล่าวถึง)

  • 6 Sums and products (ผลรวมและผลคูณ)

    • 6.1 Annuity (เงินงวด) และ break-even value
    • 6.2 Sums: การเขียนสรุปผลรวมแบบปิด (closed form)
    • 6.3 Approximating sums (ประมาณผลรวม)
    • Increasing function: lower bound via integral, upper bound via sum; leading term ~ 2/3 n^{3/2} for sqrt(i) (นำเข้าสูตรใหญ่)
    • Decreasing function: similar bounds
    • 6.4 Products: แปลงไปสู่การหาผลรวมด้วย ln และ exponents
    • 6.5 Harmonic numbers: Hn = ∑{i=1}^n 1/i; bounds via integrals and asymptotics H_n ~ ln n; ใช้กรณีที่นำไปวางไม้เหนือโต๊ะ

  • 7 Combinatorics (การนับ)

    • 7.1 Counting rules (กฎการนับพื้นฐาน)
    • 7.1.1 Product rule: จำนวนวิธีเลือกหลายชุดในลำดับเดียวกันคือ product ของขนาดแต่ละชุด
      • ตัวอย่าง: การกินอาหาร 3 มื้อในแต่ละมื้อมีตัวเลือกต่าง ๆ
      • สูตร: |A1 × A2 × … × An| = ∏ |A_i|
    • 7.1.2 Sum rule: ถ้า sets ที่ไม่ทับซ้อนกัน (pairwise disjoint) แล้วรวมกันได้โดยบวก
    • 7.1.3 Generalized product rule (ไล่เรียงมุมมองของตำแหน่ง)
      • สถานะที่มีความยาว k, จำนวนมุมมอง: m1, m2, …, mk; |S| = ∏ m_i
    • 7.1.4 Division rule: ถ้า f: A → B เป็น k-to-1 mapping, และ |A| = k |B|, จำนวนวิธีใน A มีค่าเป็น k เท่า B
    • 7.1.5 Subset rule: จำนวน subsetsของเซตขนาด n ที่มีขนาด k คือ
      {n \choose k} = \frac{n!}{k!(n-k)!} . (Pascal's triangle context)
    • 7.2 Stars and bars (ถังขนมกับไม้คั่น)
    • วิธีแก้ปัญหาการแจกจ่าย n ชิ้นให้ k คุก (แต่ละส่วนมีอย่างน้อย 1) หรือเช่นแจก 10 ชิ้นให้ 4 รสที่ต่างกัน
    • Reduction: ปรับให้เป็นปัญหาการแจกแบบเดิมที่มีสูตร ${n-1 \choose k-1}$
    • 7.3 Combinatorial proofs (การพิสูจน์ด้วยการนับแบบ combinatorial)
    • ตัวอย่าง: Proving identities like ${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$ โดย reasoning ผ่านการเลือกทีมหรือการแจกจ่าย
    • 7.4 Pigeonhole Principle (หลักช่องนกพิราบ)
    • Axiom และรูปนัย: ถ้ามีนกมากกว่าจำนวนช่อง ต้องมีช่องที่มีอย่างน้อย k+1 ตัว
    • 7.5 Binomial Theorem (ทฤษฎีบททวินาม)
    • $(a+b)^n = \sum_{k=0}^n {n \choose k} a^{n-k} b^k$
    • 7.6 Inclusion–exclusion (การบวก–ลบแบบรวม–ตัดซ้ำ)
    • กรณี 2 ชุด, 3 ชุด และกรณีหลายชุดให้รวมส่วนที่ซ้อนซ้อนอยู่ใน intersections

  • 8 Graph theory (ทฤษฎีกราฟ)

    • 8.1 Basics of graph theory
    • Graph = (V, E): vertices set V และ edges set E (แต่ละ edge คือ pair ของ vertices)
    • adjaceny: u ∼ v ถ้า {u,v} ∈ E
    • degree deg(v): จำนวน edges ที่ v เชื่อมกับ
    • subgraphs: กราฟย่อย (V′ ⊆ V, E′ ⊆ E, และทุก edge ∈ E′ ต้องมี endpoints ใน V′)
    • isomorphism: กราฟ G และ H เป็น isomorphic ถ้าสามารถจับคู่ vertices เพื่อให้ edges ตรงกัน
    • 8.2 Euler tours and trails
    • Euler trail: traversal ผ่านทุก edge exactly once (ไม่จำเป็นต้องเริ่ม/จบที่เดียวกัน)
    • Euler tour: Euler trail ที่เริ่มต้นและจบที่ vertex เดียวกัน
    • Theorem (สำหรับ connected graphs):
      • G มี Euler tour ก็ต่อเมื่อทุก vertex มี degree เป็นจำนวนเต็มอย่างน้อย 0 และตามลำดับ
      • G มี Euler trail ก็ต่อเมื่อมี exactly 2 vertices with odd degree และเริ่มต้น/จบที่ vertex เหล่านั้น
    • ตัวอย่าง: กราฟที่มี degree ของจุดต่าง ๆ เป็น 3 (odd) ทำให้ไม่มี Euler tour แต่มี Euler trail ระหว่างจุดที่มี degree เป็น 3
    • 8.3 Graph coloring & 8.3.1 Bipartite graphs
    • การระบายสีกราฟให้เพื่อนกันต่างสีเมื่อ edge เชื่อมระหว่างชุด (สีอาจนำไปสู่ bipartite property)
    • 8.4 Planar graphs (กราฟในระนาบ) – ภาพรวม

หมายเหตุสำคัญในการเตรียมสอบ:

  • เน้นความเข้าใจในแนวคิดหลักและวิธีการพิสูจน์มากกว่าคำตอบจำเพาะ
  • จดจำนิยามและตัวอย่างสำคัญ ได้แก่ proof, axiom, proposition, theorem, lemma, corollary; universal/existential/negating quantifiers; mechanisms ของการพิสูจน์ด้วย induction, strong induction, loop invariants; periodic properties ของ automata (DFA/NFA) และการใช้งาน Pumping Lemma; การสร้าง CFG/PDA และแนวคิด nonregular/non-CFL languages; ปรัชญาและวิธีคิดใน combinatorics และ graph theory
  • ทบทวนสูตรสำคัญใน LaTeX เช่น
    • ทฤษฎีบททวินาม: (a+b)^n = \sum_{k=0}^{n} {n \choose k} a^{n-k} b^k
    • Subset: {n \choose k} = \frac{n!}{k!(n-k)!}
    • ความสัมพันธ์ระหว่างการนับในกราฟ: \sum_{v \in V} deg(v) = 2|E|
  • คำศัพท์ที่มักสับสน: pump in/out, GNFA, NFA vs DFA, isomorphism, planarity