โพสนี้อยู่ในหมวด เรียนรู้ logic programming + argumentation นะคะ
ก่อนอื่น เรามารู้จักคำว่า order กันก่อน ซึ่ง order ก็คือการที่เราสามารถเปรียบเทียบสิ่งของสิ่งได้
เช่น 0 น้อยกว่า 1 หรือ ดาวอังคารอยู่ห่างจากดวงอาทิตย์ มากกว่าที่อยู่ห่างจากโลก
ก่อนอื่น เรามารู้จักคำว่า order กันก่อน ซึ่ง order ก็คือการที่เราสามารถเปรียบเทียบสิ่งของสิ่งได้
เช่น 0 น้อยกว่า 1 หรือ ดาวอังคารอยู่ห่างจากดวงอาทิตย์ มากกว่าที่อยู่ห่างจากโลก
คิดว่าทุกคนคงทราบความหมายของ set กับ relation กันดีอยู่แล้ว ซึ่ง order เองก็คือ relation ประเภทหนึ่ง
ทีนี้เรามาดูนิยามของคำว่า partial order ซึ่งคือ relation ที่จะต้องมีคุณสมบัติ
- reflexive (มีการเปรียบเทียบตัวเองกับตัวเอง)
- antisymmetric (ถ้าลำดับ X น้อยกว่า Y แล้วลำดับ Y ต้องไม่น้อยกว่า X แต่ถ้าเกิดพบกว่าลำดับของ X น้อยกว่า Y และลำดับของ Y ก็น้อยกว่า X แสดงว่า Xและ Y นั้นคือค่าเดียวกัน)
-transitive (ถ้าลำดับของ X น้อยกว่า Y, ลำดับของ Y น้อยกว่า Z แล้วลำดับของ X ต้องน้อยกว่าลำดับของ Z)
ทีนี้เรามาดูนิยามของคำว่า partial order ซึ่งคือ relation ที่จะต้องมีคุณสมบัติ
- reflexive (มีการเปรียบเทียบตัวเองกับตัวเอง)
- antisymmetric (ถ้าลำดับ X น้อยกว่า Y แล้วลำดับ Y ต้องไม่น้อยกว่า X แต่ถ้าเกิดพบกว่าลำดับของ X น้อยกว่า Y และลำดับของ Y ก็น้อยกว่า X แสดงว่า Xและ Y นั้นคือค่าเดียวกัน)
-transitive (ถ้าลำดับของ X น้อยกว่า Y, ลำดับของ Y น้อยกว่า Z แล้วลำดับของ X ต้องน้อยกว่าลำดับของ Z)
ตัวอย่างของ partial order ก็อย่าง ความสัมพันธ์ของ subset
หรือการเปรียบเทียบ น้อยกว่าหรือเท่ากับของตัวเลขจำนวนเต็ม
เช่น {(1,1),(1,2),(2,2),(2,3)} ก็จะเห็นว่า 1 ≤ 1 , 1 ≤ 2, 2 ≤ 2 , 2 ≤ 3
เช่น {(1,1),(1,2),(2,2),(2,3)} ก็จะเห็นว่า 1 ≤ 1 , 1 ≤ 2, 2 ≤ 2 , 2 ≤ 3
ทีนี้เรามาทำความรู้จัก
upper bound กันดีกว่านะคะ
ถ้าเรามี partial order สมมติชื่อว่า S เราดึงแค่ subset ของเซต S นี้ออกมา สมมติให้ชื่อ subset นี้ว่า X แล้วพบว่า สมาชิกทุกตัวใน X นี้มีค่าน้อยกว่าหรือเท่ากับ ค่าๆหนึ่งซึ่งเป็นสมาชิกของ S เช่นกัน เราจะเรียกค่านั้นว่า upper bound
ยกตัวอย่าง เช่นถ้าเรามีค่า A,B,C ซึ่ง A ≤ B≤ C
แล้วเรามี {A , B, C} ถ้าถามว่า upper bound ของ { A } คือค่าอะไร ก็สามารถตอบได้ว่าคือ A, B , C
และในบรรดา upper bound ทั้งหมด upper bound ที่มีค่าน้อยที่สุด คือ least upper bound
ดังนั้นจากตัวอย่างนี้ least upper bound คือ A
ถ้าเรามี partial order สมมติชื่อว่า S เราดึงแค่ subset ของเซต S นี้ออกมา สมมติให้ชื่อ subset นี้ว่า X แล้วพบว่า สมาชิกทุกตัวใน X นี้มีค่าน้อยกว่าหรือเท่ากับ ค่าๆหนึ่งซึ่งเป็นสมาชิกของ S เช่นกัน เราจะเรียกค่านั้นว่า upper bound
ยกตัวอย่าง เช่นถ้าเรามีค่า A,B,C ซึ่ง A ≤ B
แล้วเรามี {A , B, C} ถ้าถามว่า upper bound ของ { A } คือค่าอะไร ก็สามารถตอบได้ว่าคือ A, B , C
และในบรรดา upper bound ทั้งหมด upper bound ที่มีค่าน้อยที่สุด คือ least upper bound
ดังนั้นจากตัวอย่างนี้ least upper bound คือ A
ถ้าเราต้องการหา
lower bound ก็คล้ายๆกันเปลี่ยนแค่จากน้อยกว่าเป็นมากกว่า จะได้ว่าถ้าพบว่า สมาชิกทุกตัวใน X นี้มีค่ามากกว่าหรือเท่ากับ
ค่าๆหนึ่งซึ่งเป็นสมาชิกของ S เราจะเรียกค่านั้นว่า lower bound และในบรรดา lower bound ทั้งหมด lower bound
ที่มีค่ามากที่สุด จะเรียกว่า greatest lower bound
จากตัวอย่างนี้ ถ้าถามว่าlower bound ของ{ A} คือค่าอะไร lower bound คือ A และ greatest lower bound ก็คือ A
ในขณะที่ lower bound ของ {B} = A, B และ greatest lower bound ก็คือ B
จากตัวอย่างนี้ ถ้าถามว่าlower bound ของ{ A} คือค่าอะไร lower bound คือ A และ greatest lower bound ก็คือ A
ในขณะที่ lower bound ของ {B} = A, B และ greatest lower bound ก็คือ B
ทีนี้ถ้าเรามีเซต
S ใดๆ แล้วเราหา power set of S ( 2S) ก็จะเห็นว่า 2S
มีคุณสมบัติเป็น
partial order
ยกตัวอย่างเช่น S = {A,B} ดังนั้น
= {∅, A, B, {A,B} } เป็น partial order เพราะ
∅ ⊆ {A}⊆ {B} ⊆ {A,B}
ยกตัวอย่างเช่น S = {A,B} ดังนั้น
ก่อนจะไปหา lower bound, upper bound ของ 2S ขอยกตัวอย่างอีกสักตัวอย่าง
ถ้าเรามีเซต A , B สมมติว่า A ⊆C , B ⊆C
จะเห็นว่า C is upper bound of A , C is upper bound of B
ถ้าเราจับ A ∪ B
แล้ว จะพบว่า upper
bound = A ∪ B , C
และมี least upper bound =
เช่นกันค่ะ เราจะได้ว่า ∅ is lower bound of A และ ∅ is lower bound of B
ถ้าเรามีเซต A , B สมมติว่า A ⊆C , B ⊆C
จะเห็นว่า C is upper bound of A , C is upper bound of B
ถ้าเราจับ A ∪ B
และมี least upper bound =
เช่นกันค่ะ เราจะได้ว่า ∅ is lower bound of A และ ∅ is lower bound of B
ถ้าเราจับ A ∩ B แล้ว lower bound of
= ∅, A ∩ B
และมี greatest lower bound = A ∩ B
และมี greatest lower bound = A ∩ B
จากแค่ทำกับสองเซต
A,B ใช้หลักการเดียวกันไม่ว่าจะมีกี่เซต ซึ่งเราสามารถที่จะหาค่า least upper bound และ greatest lower bound ของทุกๆ subset of 2S ได้
ซึ่งถ้าเรา หา intersection ของสมาชิกทุกตัวใน 2S เราก็จะได้
greatest lower bound = ∅ และถ้าหา
union ของสมาชิกทุกตัวใน 2S ก็จะได้ least
upper bound = S นั่นเอง
ซึ่งถ้าเรามี
partial order L ใดๆ ที่สามารถหา least upper bound และ greatest lower bound ของทุกๆ subset ของ ของ order L นั้นได้
เราเรียกว่าคุณสมบัตินี้ว่า complete
lattice
จากตัวอย่างข้างต้น
เราก็เห็นกันแล้วนะคะว่า 2S มีคุณสมบัติ complete lattice ทีนี้เราจะพูดถึง fix point theory กันบ้าง
fix point theory นิยามไว้ว่า
ถ้าเรามี complete lattice ใดๆสมมติชื่อ L และมี mapping ให้ชื่อว่า T จากโดเมนคือ Lไปยังเรนจ์ คือ L (T: L ->
ทีนี้ fix point เนี่ย ก็มีได้หลายค่า เราก็จะเรียกค่า fix point ที่น้อยที่สุดในบรรดาค่า fix point ทั้งหมดว่า least fix point และเช่นกัน เราจะเรียกค่า fix point ที่มากที่สุดในบรรดาค่า fix point ทั้งหมดว่า greatest fix point
ทีนี้ fix point เนี่ย ก็มีได้หลายค่า เราก็จะเรียกค่า fix point ที่น้อยที่สุดในบรรดาค่า fix point ทั้งหมดว่า least fix point และเช่นกัน เราจะเรียกค่า fix point ที่มากที่สุดในบรรดาค่า fix point ทั้งหมดว่า greatest fix point
ทีนี้ เรากลับมาที่คำอธิบายเรื่อง complete lattice ของเรากันนะคะ
เรารู้แล้วว่า 2S มีคุณสมบัติ
complete lattice แล้วถ้าเรามี mapping T: 2S -> 2S ก็แสดงว่า ทั้ง input และ output (หรือโดเมนและเรนจ์) ของการ mapping นี้
จะมีคุณสมบัติ complete lattice แน่นอน เพราะว่ามันเป็น subset ของเซต ซึ่งก็จะทำให้เราสามารถหา greatest lower bound, least upper bound ได้เสมอ ซึ่งคุณสมบัติตรงนี้จะใช้อธิบายในหลายๆเรื่องของทฤษฎีในหนังสือ
logic programming
ขอเล่าแถมอีกหน่อย เรื่อง fix point theory ว่าสำคัญไฉน
fix point เนี่ยมีความสำคัญในหลายๆแขนงของคณิตศาสตร์
เรารู้แล้วใช่ไหมคะว่า partial order คืออะไร และ complete lattice คืออะไรและเกี่ยวข้องกับ fix point ยังไง
ทีนี้เราลองมาดู fix point ในงานด้านอื่นบ้าง ถ้าเรามีจุด สองจุด บนแกน x,y อยากจะเทียบว่าจุดไหนใหญ่กว่า(ไม่แน่ใจว่าใช้คำว่าใหญ่กว่าจะดีไหม) วิธีการเทียบคือ ถ้า ค่าบนแกน x ของจุดแรกมากกว่าเท่ากับจุดสอง และ ค่าบนแกน y ของจุดแรกมากกว่าเท่ากับจุดสอง เราก็จะถือว่าจุดแรกใหญ่กว่า
อย่างเช่น จุด (2,2) ใหญ่กว่า จุด (1,1)
ทีนี้เราเทียบสองจุดได้แล้ว
เราก็จะสามารถเทียบหลายๆจุดได้ใช่ไหมคะ เมื่อเราเทียบจุดหลายๆจุดได้
เราก็จัดลำดับเซตของจุดเหล่านี้ได้
และเราก็จะได้ partial
order ใช่ไหมคะ
เมื่อเราได้ partial order ของความสัมพันธ์ของจุดบนระนาบ x,y (ซึ่ง ณ
จุดนี้ก็คล้ายกับความสัมพันธ์ subset
ของเซตแล้ว) ต่อไปเราก็จะพบว่ามันมีคุณสมบัติ complete lattice แล้วเราก็จะหา
fix point ได้
คำถามคือเราจะหา
fix point ของจุดไปทำไม ?
ถ้ายังจำได้ คณิตศาสตร์ที่เราเคยเรียนสมัยมัธยม เราจะหาจุดตัด (0,0) ซึ่งเราสามารถจะมองว่าคือ fix point ได้ นี่ก็คือ application นึงของ fix point ค่ะ และไม่ใช่แค่จุดบนระนาบ x,y เราสามารถจะเทียบบน สามมิติ x,y,z หรือ n-dimension ก็ได้
ถ้ายังจำได้ คณิตศาสตร์ที่เราเคยเรียนสมัยมัธยม เราจะหาจุดตัด (0,0) ซึ่งเราสามารถจะมองว่าคือ fix point ได้ นี่ก็คือ application นึงของ fix point ค่ะ และไม่ใช่แค่จุดบนระนาบ x,y เราสามารถจะเทียบบน สามมิติ x,y,z หรือ n-dimension ก็ได้
ซึ่งในระบบ
dynamic ต่างๆ
เราย่อมจะอยากหาเงื่อนไขที่ทำให้มัน stable
เราก็นำเอา fix point theory เข้าไปใช้
ไม่ว่าจะเป็น งานด้าน machine
vision , computer graphic ก็จะเห็นว่ามีทฤษฎี fix point ค่ะ
รวมถึง สมการ
หรือ equation ที่เรารู้จักกันดี
นั่นก็คือรูปแบบนึงของ fix
point เช่นกัน
เช่น
เรารู้จักกันในรูปแบบของสมการ
ที่เราจะต้องการหาค่าตัวแปร X ว่ามีค่าเท่าไหร่
ซึ่งถ้าเรามองสมการเป็น
ใช่ไหมคะ
เช่น
ซึ่งถ้าเรามองสมการเป็น
ใช่ไหมคะถ้าเรากำหนดให้
หวังว่าคงจะเห็นความสำคัญและเข้าใจทฤษฎี
fixpoint มากขึ้นและอ่านหนังสือ logic programming ได้เข้าใจยิ่งขึ้นนะคะ :)
