คณิตศาสตร์ไม่ต่อเนื่อง: ชุดสรุปเร่งรัด

สรุปสูตร ขั้นตอนวิธีทำที่สำคัญของทุกหัวข้อ และโจทย์ฝึก 8 ข้อ พร้อมเฉลยละเอียดไว้ท้ายเล่ม

โจทย์ใหม่กลับไปที่รายวิชา

ในหน้าต่างพิมพ์ ให้เลือก “บันทึกเป็น PDF” เพื่อเก็บสำเนาไว้ในอุปกรณ์ของคุณ

1สูตรและวิธีทำ

ตรรกศาสตร์ประพจน์และการพิสูจน์

แถวของตารางค่าความจริง
2ⁿ
นัยสำคัญ (ถ้า–แล้ว)
p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
นิเสธของนัย
¬(p → q) ≡ p ∧ ¬q
เงื่อนไขสองทาง
p ↔ q ≡ (p → q) ∧ (q → p)
กฎของเดอมอร์แกน
¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
กฎการแจกแจง
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
นิเสธของตัวบ่งปริมาณ
¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
โมดัสโพเนนส์ โมดัสโทลเลนส์
p → q, p ⊢ q; p → q, ¬q ⊢ ¬p

วิธีการ

  1. นับจำนวนตัวแปรที่ต่างกัน ตารางค่าความจริงมี 2ⁿ แถว โดยเริ่มจากแถวที่ทุกตัวเป็น 1
  2. ให้ทุกประพจน์ย่อยมีคอลัมน์ของตัวเอง และเติมคอลัมน์จากด้านในออกมาด้านนอก
  3. ใช้กฎของตัวเชื่อมแต่ละตัว: → เป็น 0 เฉพาะเมื่อ 1 → 0 และ ↔ เป็น 1 เมื่อทั้งสองข้างมีค่าเท่ากัน
  4. สำหรับความสมมูล ให้เปรียบเทียบคอลัมน์สุดท้ายทีละแถว สำหรับการอ้างเหตุผล ให้ดูเฉพาะแถวที่ทุกสมมติฐานเป็น 1
  5. การหานิเสธของข้อความที่มีตัวบ่งปริมาณ ให้ย้าย ¬ เข้าไปด้านใน สลับ ∀ กับ ∃ และใส่นิเสธให้สูตรด้านใน

เซต ความสัมพันธ์ และฟังก์ชัน

สองเซต
|A ∪ B| = |A| + |B| − |A ∩ B|
สามเซต
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
ผลต่างและคอมพลีเมนต์
A − B = A ∩ B′, |A′| = |U| − |A|
เพาเวอร์เซตและผลคูณคาร์ทีเซียน
|𝒫(A)| = 2|A|, |A × B| = |A|·|B|
เซตย่อยขนาด k
C(n, k) = n!/(k!(n − k)!)
ฟังก์ชัน A → B
nᵐ; injective n!/(n − m)!; surjective Σ (−1)ᵏ C(n, k)(n − k)ᵐ
ความสัมพันธ์บน n สมาชิก
2n²; reflexive 2n² − n; symmetric 2n(n+1)/2
ฟังก์ชันประกอบ
(g ∘ f)(x) = g(f(x))

วิธีการ

  1. วาดแผนภาพเวนน์แล้วพิจารณาทีละบริเวณว่าบริเวณใดเป็นของนิพจน์เซต
  2. สำหรับโจทย์การนับ ให้เติมบริเวณจากตรงกลางออกไป คือทุกเซตก่อน แล้วเป็นคู่ จากนั้นเป็นเซตเดี่ยว และสุดท้ายคือด้านนอก
  3. ใช้หลักการเพิ่มเข้า–ตัดออกเพื่อตรวจสอบ: |A ∪ B| = |A| + |B| − |A ∩ B|
  4. สำหรับความสัมพันธ์ ให้ทดสอบสมบัติแต่ละข้อกับทุกคู่ และยกตัวอย่างค้านหนึ่งตัวอย่างเมื่อสมบัตินั้นไม่เป็นจริง
  5. สำหรับฟังก์ชัน ให้นับลูกศรที่ชี้เข้าแต่ละสมาชิกของ B ถ้ามากที่สุดหนึ่งลูกคือฟังก์ชันหนึ่งต่อหนึ่ง ถ้าอย่างน้อยหนึ่งลูกคือฟังก์ชันทั่วถึง

ทฤษฎีกราฟ

เล็มมาการจับมือ
Σ deg(v) = 2|E|
กราฟบริบูรณ์
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
กราฟปรกติ
|E| = n·k/2
ต้นไม้และป่า
|E| = n − 1, |E| = n − c
ใบของต้นไม้
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
ออยเลอร์
วงจร: ดีกรีเป็นคู่ทุกจุดยอด; ทางเดิน: มีดีกรีคี่พอดี 2 จุดยอด
วงจรแฮมิลตันใน Kn
(n − 1)!/2
การปรับค่าของไดก์สตรา
d(v) = min(d(v), d(u) + w(u, v))
วอล์กความยาว L
(Mᴸ)ij

วิธีการ

  1. เขียนดีกรีของทุกจุดยอด ผลบวกของดีกรีเท่ากับสองเท่าของจำนวนเส้นเชื่อม
  2. สำหรับโจทย์ออยเลอร์ ให้ตรวจว่ากราฟเชื่อมโยงกัน และนับจุดยอดที่มีดีกรีคี่
  3. สำหรับต้นไม้ ให้ใช้ว่ามี n − 1 เส้นเชื่อม และเล็มมาการจับมือ
  4. สำหรับไดก์สตรา ให้เก็บตารางระยะทางชั่วคราว และยืนยันจุดยอดที่ยังไม่ยืนยันซึ่งมีค่าน้อยที่สุดในแต่ละรอบ
  5. สำหรับต้นไม้ทอดข้ามค่าน้อยที่สุด ให้เรียงเส้นเชื่อมตามน้ำหนักและข้ามทุกเส้นที่ทำให้เกิดวัฏจักร (ครัสคัล) หรือขยายต้นไม้ต้นเดียวจากจุดยอดเริ่มต้น (พริม)

ทฤษฎีจำนวนและเลขคณิตมอดูลาร์

การหารที่มีเศษ
a = q·n + r, 0 ≤ r < n
ยูคลิด
gcd(a, b) = gcd(b, a mod b)
ตัวคูณร่วมน้อย
lcm(a, b) = a·b/gcd(a, b)
อินเวอร์ส
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
ความสอดคล้องเชิงเส้น
a·x ≡ b → x ≡ a⁻¹·b (mod n)
ฟังก์ชันโทเทียนต์ของออยเลอร์
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
แฟร์มา
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n

วิธีการ

  1. ลดทุกจำนวนมอดูโล n ก่อน เศษจะอยู่ระหว่าง 0 ถึง n − 1
  2. สำหรับ ห.ร.ม. ให้หารซ้ำด้วยขั้นตอนวิธีของยูคลิด เศษที่ไม่เป็นศูนย์ตัวสุดท้ายคือ ห.ร.ม.
  3. สำหรับตัวผกผัน ให้ทำขั้นตอนวิธีแบบขยาย และเก็บสัมประสิทธิ์ของ a ถ้าเป็นลบให้บวก n
  4. แก้ a·x ≡ b โดยคูณด้วย a⁻¹ รวมสองความสอดคล้องโดยเขียน x = r₁ + m₁k
  5. สำหรับเลขยกกำลัง ให้เขียนเลขชี้กำลังเป็นเลขฐานสองแล้วยกกำลังสองซ้ำ ใน RSA จะได้ d = e⁻¹ mod φ(n) โดย φ(n) = (p − 1)(q − 1)

2โจทย์ฝึก

1.ตรรกศาสตร์ประพจน์และการพิสูจน์ปานกลาง
ซ้ำซ้อน (tautology)ขัดแย้ง (contradiction)contingency

(p ∨ r) ∧ (¬p ∧ ¬r) เป็น tautology, contradiction หรือ contingency ให้คลิกคำตอบของคุณ

(p ∨ r) ∧ (¬p ∧ ¬r)
  1. 1ซ้ำซ้อน (tautology)
  2. 2ขัดแย้ง (contradiction)
  3. 3contingency
2.ตรรกศาสตร์ประพจน์และการพิสูจน์ยาก
aba → b¬a¬b11100100

การอ้างเหตุผลที่มีสมมติฐาน a → b; ¬a และบทสรุป ¬b ไม่สมเหตุสมผล ให้คลิกแถวของตารางค่าความจริงที่เป็นตัวอย่างค้าน

a → b¬a∴ ¬b
  1. 1a = 1, b = 1
  2. 2a = 1, b = 0
  3. 3a = 0, b = 1
  4. 4a = 0, b = 0
3.เซต ความสัมพันธ์ และฟังก์ชันปานกลาง
1234

R = {(1, 4), (2, 2), (3, 3), (3, 4), (4, 3)} เป็นความสัมพันธ์บน {1, 2, 3, 4} ต้องเพิ่มคู่อันดับให้ R อย่างน้อยกี่คู่ k เพื่อให้เป็นความสัมพันธ์สะท้อน

R = {(1, 4), (2, 2), (3, 3), (3, 4), (4, 3)}
k =
4.เซต ความสัมพันธ์ และฟังก์ชันยาก
AB1234abcหนึ่งต่อหนึ่ง แต่ไม่ทั่วถึงทั่วถึง แต่ไม่หนึ่งต่อหนึ่งหนึ่งต่อหนึ่งทั่วถึงไม่ใช่ทั้งสองอย่าง

แผนภาพลูกศรแสดงฟังก์ชัน f: A → B โดย A = {1, 2, 3, 4} และ B = {a, b, c} ให้คลิกคำอธิบายที่ตรงกับ f

f = {(1, a), (2, a), (3, c), (4, c)}
  1. 1หนึ่งต่อหนึ่ง แต่ไม่ทั่วถึง
  2. 2ทั่วถึง แต่ไม่หนึ่งต่อหนึ่ง
  3. 3หนึ่งต่อหนึ่งทั่วถึง
  4. 4ไม่ใช่ทั้งสองอย่าง
5.ทฤษฎีกราฟปานกลาง

ต้นไม้มี 4 จุดยอดดีกรี 3, 2 จุดยอดดีกรี 2 และจุดยอดอื่นทั้งหมดเป็นใบ (ดีกรี 1) มีกี่ใบ L

4 × deg 32 × deg 2
L =
6.ทฤษฎีกราฟยาก
36529541311ABCDEF

ใช้ขั้นตอนวิธีของไดก์สตราเพื่อหาความยาว d(F) ของเส้นทางที่สั้นที่สุดจาก A ไป F ในกราฟถ่วงน้ำหนัก

เริ่มต้น: Aสิ้นสุด: F
d(F) =
7.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ปานกลาง

จงหาฟังก์ชันโทเทียนต์ของออยเลอร์ φ(49) ซึ่งเป็นจำนวนของจำนวนเต็มตั้งแต่ 1 ถึง 49 ที่เป็นจำนวนเฉพาะสัมพัทธ์กับ 49

n = 49 = 72
φ(49) =
8.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ยาก
533c = me​ mod n?m = cd​ mod nm(n, e) = (703, 13)d

เข้ารหัสข้อความ m = 533 ด้วยกุญแจสาธารณะ RSA (n, e) = (703, 13) จงหาข้อความเข้ารหัส c

n = 703e = 13m = 533
c =

3สารละลาย

1.ตรรกศาสตร์ประพจน์และการพิสูจน์

คำตอบ: ขัดแย้ง (contradiction)

ความสมมูลเชิงตรรกะ: สูตรสองสูตรสมมูลกัน (≡) เมื่อมีค่าเท่ากันทุกแถวของตารางค่าความจริง ซ้ำซ้อน (tautology) เป็น 1 ทุกแถว ขัดแย้ง (contradiction) เป็น 0 ทุกแถว และ contingency ไม่ใช่ทั้งสองอย่าง กฎที่มีประโยชน์: กฎของเดอมอร์แกน ¬(a ∧ b) ≡ ¬a ∨ ¬b และ ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (การแย้งสลับที่); ¬(a → b) ≡ a ∧ ¬b; และกฎการแจกแจง a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c)

ตารางค่าความจริงทีละแถว

p = 1, r = 1: p ∨ r = 1, ¬p = 0, ¬r = 0, ¬p ∧ ¬r = 0, (p ∨ r) ∧ (¬p ∧ ¬r) = 0
p = 1, r = 0: p ∨ r = 1, ¬p = 0, ¬r = 1, ¬p ∧ ¬r = 0, (p ∨ r) ∧ (¬p ∧ ¬r) = 0
p = 0, r = 1: p ∨ r = 1, ¬p = 1, ¬r = 0, ¬p ∧ ¬r = 0, (p ∨ r) ∧ (¬p ∧ ¬r) = 0
p = 0, r = 0: p ∨ r = 0, ¬p = 1, ¬r = 1, ¬p ∧ ¬r = 1, (p ∨ r) ∧ (¬p ∧ ¬r) = 0

จัดประเภท

(p ∨ r) ∧ (¬p ∧ ¬r): 0, 0, 0, 0
เป็น 0 ทุกแถว: contradiction

คำตอบ

ขัดแย้ง (contradiction)
2.ตรรกศาสตร์ประพจน์และการพิสูจน์

คำตอบ: a = 0, b = 1

ตัวบ่งปริมาณและการอ้างเหตุผล: ¬∀x P(x) ≡ ∃x ¬P(x) และ ¬∃x P(x) ≡ ∀x ¬P(x) ย้ายนิเสธเข้าด้านใน สลับทุกตัวบ่งปริมาณที่นิเสธผ่าน และใส่นิเสธให้สูตรด้านในด้วยกฎของประพจน์ เช่น ¬(a → b) ≡ a ∧ ¬b การอ้างเหตุผลสมเหตุสมผลเมื่อบทสรุปเป็น 1 ในทุกแถวที่สมมติฐานทั้งหมดเป็น 1 แถวเดียวที่สมมติฐานเป็นจริงแต่บทสรุปเป็นเท็จคือตัวอย่างค้านและแสดงว่าการอ้างเหตุผลนั้นไม่สมเหตุสมผล

สมมติฐานและบทสรุปทีละแถว

a = 1, b = 1: 1 0 | 0
a = 1, b = 0: 0 0 | 1
a = 0, b = 1: 1 1 | 0
a = 0, b = 0: 1 1 | 1

ตัวอย่างค้าน

a = 0, b = 1

คำตอบ

a = 0, b = 1

การอ้างเหตุผลรูปแบบนี้ดูเหมือนกฎที่สมเหตุสมผล แต่แถวเดียวก็เพียงพอที่จะแสดงว่าไม่ใช่

3.เซต ความสัมพันธ์ และฟังก์ชัน

คำตอบ: k = 2

ความสัมพันธ์: ความสัมพันธ์ R บนเซต X คือเซตของคู่อันดับ (x, y) R สะท้อนเมื่อ (x, x) ∈ R สำหรับทุก x ใน X; สมมาตรเมื่อ (x, y) ∈ R มี (y, x) ∈ R มาด้วยเสมอ; ปฏิสมมาตรเมื่อ (x, y) และ (y, x) อยู่ใน R ทั้งคู่เฉพาะเมื่อ x = y; และแพร่ผ่านเมื่อ (x, y) และ (y, z) ใน R บังคับให้ (x, z) ∈ R ความสัมพันธ์สมมูลคือความสัมพันธ์ที่สะท้อน สมมาตร และแพร่ผ่าน และแบ่ง X เป็นคลาสที่ไม่ซ้อนกัน

คู่ที่ต้องเพิ่ม

{(1, 1), (4, 4)}

นับ

k = 2

คำตอบ

k = 2
4.เซต ความสัมพันธ์ และฟังก์ชัน

คำตอบ: ไม่ใช่ทั้งสองอย่าง

ฟังก์ชันและการนับ: ฟังก์ชัน f: A → B ให้สมาชิกทุกตัวของ A มีภาพใน B เพียงหนึ่งตัวพอดี f เป็นหนึ่งต่อหนึ่ง (injective) เมื่อสมาชิกต่างกันมีภาพต่างกัน ทั่วถึง (surjective) เมื่อสมาชิกทุกตัวของ B เป็นภาพ และหนึ่งต่อหนึ่งทั่วถึง (bijective) เมื่อเป็นจริงทั้งสองอย่าง เมื่อ |A| = m และ |B| = n มี nᵐ ฟังก์ชัน ฟังก์ชันหนึ่งต่อหนึ่ง n!/(n − m)! ฟังก์ชัน (m ≤ n) และฟังก์ชันทั่วถึง Σ (−1)ᵏ·C(n, k)·(n − k)ᵐ ฟังก์ชันโดยหลักการเพิ่มเข้า–ตัดออก |𝒫(A)| = 2ᵐ และ |A × B| = m·n

หนึ่งต่อหนึ่งหรือไม่

f(1) = f(2) = a → ไม่เป็นหนึ่งต่อหนึ่ง

ทั่วถึงหรือไม่

b ไม่มีลูกศรชี้เข้า → ไม่ทั่วถึง

คำตอบ

ไม่ใช่ทั้งสองอย่าง

คำตอบ

ไม่ใช่ทั้งสองอย่าง
5.ทฤษฎีกราฟ

คำตอบ: L = 6

ออยเลอร์ แฮมิลตัน และต้นไม้: กราฟเชื่อมโยงมีวงจรออยเลอร์ (ผ่านทุกเส้นเชื่อมครั้งเดียวและกลับจุดเริ่มต้น) เมื่อทุกจุดยอดมีดีกรีคู่ และมีทางเดินออยเลอร์ที่ไม่ใช่วงจรเมื่อมีจุดยอดดีกรีคี่พอดีสองจุด ทางเดินนั้นไปจากจุดยอดคี่จุดหนึ่งถึงอีกจุดหนึ่ง วงจรแฮมิลตันผ่านทุกจุดยอดครั้งเดียว Kn มีวงจรแบบนี้ (n − 1)!/2 วงจร ต้นไม้ที่มี n จุดยอดมี n − 1 เส้นเชื่อม และกราฟเชื่อมโยงที่มี m เส้นเชื่อมจะเหลือต้นไม้ทอดข้ามหลังเอาเส้นเชื่อมออก m − n + 1 เส้น

เล็มมาการจับมือสำหรับต้นไม้

L + 16 = 2(L + 6) − 2
L = 6

คำตอบ

L = 6

ทางลัด: L = 2 + Σ (d − 2) ของจุดยอดที่มีดีกรี d ≥ 3

6.ทฤษฎีกราฟ

คำตอบ: d(F) = 9

เส้นทางที่สั้นที่สุดและต้นไม้ทอดข้าม: ขั้นตอนวิธีของไดก์สตรายืนยันหนึ่งจุดยอดต่อรอบ: จุดยอดที่ยังไม่ยืนยันซึ่งมีระยะทางชั่วคราวน้อยที่สุด ระยะทางของมันเป็นค่าสุดท้ายแล้ว และเพื่อนบ้าน v ทุกจุดได้ d(v) = min(d(v), d(u) + w(u, v)) ขั้นตอนวิธีของครัสคัลสร้างต้นไม้ทอดข้ามค่าน้อยที่สุดโดยเลือกเส้นเชื่อมจากเบาไปหนักและข้ามเส้นที่ทำให้เกิดวัฏจักร ขั้นตอนวิธีของพริมขยายต้นไม้หนึ่งต้นจากจุดยอดเริ่มต้นโดยเพิ่มเส้นเชื่อมที่เบาที่สุดที่ออกจากต้นไม้เสมอ ต้นไม้ทอดข้ามที่มี n จุดยอดมี n − 1 เส้นเชื่อม

ไดก์สตราทีละรอบ

แต่ละบรรทัด: จุดยอดที่ยืนยัน ระยะทางสุดท้ายของมัน และเพื่อนบ้านที่ระยะทางดีขึ้น

A (0): B: 3, C: 6
B (3): D: 5, E: 14
D (5): E: 10, F: 9
C (6)
F (9)
E (10)

เส้นทางที่สั้นที่สุด

A → B → D → F
d(F) = 9

คำตอบ

d(F) = 9
7.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์

คำตอบ: φ(49) = 42

ตัวผกผันและความสอดคล้อง: a มีตัวผกผันมอดูโล n เมื่อ gcd(a, n) = 1 เท่านั้น ขั้นตอนวิธีของยูคลิดแบบขยายเขียน 1 = s·n + t·a แล้ว a⁻¹ ≡ t (mod n) ความสอดคล้อง a·x ≡ b (mod n) ที่ gcd(a, n) = 1 มีคำตอบ x ≡ a⁻¹·b ความสอดคล้องสองข้อ x ≡ r₁ (mod m₁) และ x ≡ r₂ (mod m₂) ที่มอดูลัสเป็นจำนวนเฉพาะสัมพัทธ์กันมีคำตอบเดียวมอดูโล m₁·m₂ (ทฤษฎีบทเศษเหลือของจีน) φ(n) ของออยเลอร์นับจำนวนตั้งแต่ 1 ถึง n ที่เป็นจำนวนเฉพาะสัมพัทธ์กับ n: φ(n) = n·∏(1 − 1/p)

ตัวประกอบเฉพาะ

49 = 72

โทเทียนต์

φ(49) = 49 − 7 = 42

คำตอบ

φ(49) = 42
8.ทฤษฎีจำนวนและเลขคณิตมอดูลาร์

คำตอบ: c = 20

เลขยกกำลังมอดูลาร์และ RSA: คำนวณ aᵏ mod n ด้วยการยกกำลังสองซ้ำ: เขียน k เป็นเลขฐานสอง ยกกำลังสอง ลดค่าหลังทุกขั้นตอน และคูณเลขยกกำลังที่บิตเป็น 1 แฟร์มา: aᵖ⁻¹ ≡ 1 (mod p) สำหรับจำนวนเฉพาะ p ที่หาร a ไม่ลงตัว ดังนั้นลดเลขชี้กำลังมอดูโล p − 1 ได้ RSA: เลือกจำนวนเฉพาะ p และ q, n = p·q และ φ(n) = (p − 1)(q − 1) เลขชี้กำลังสาธารณะ e เป็นจำนวนเฉพาะสัมพัทธ์กับ φ(n) และเลขชี้กำลังส่วนตัวคือ d = e⁻¹ mod φ(n) เข้ารหัสด้วย c = mᵉ mod n และถอดรหัสด้วย m = cᵈ mod n

การยกกำลังสองซ้ำ

13 = 8 + 4 + 1
5331 ≡ 533 (mod 703)
5332 ≡ 77 (mod 703)
5334 ≡ 305 (mod 703)
5338 ≡ 229 (mod 703)
53313 ≡ 533·305·229 ≡ 20 (mod 703)

ข้อความเข้ารหัส

c = 20

คำตอบ

c = 20

ExamProblems · examproblems.com/courses/discrete-mathematics