มาเรียน Logic for Computer Science (4 -- Propositional Logic vs First-Order Logic)

สำหรับใครที่เพิ่งเข้ามาหน้านี้ แนะนำว่าให้อ่าน ที่นี่ ก่อนนะคะ เอาล่ะที่นี้เราจะมาคุยกันต่อเรื่องว่า ทำอย่างไรเราถึงจะนำเสนอรูปแบบข้อมูลให้อยู่ในรูปที่สามารถนำไปทำ reasoning ได้ ซึ่งก็มีทฤษฎี 2 อย่างที่เราจะพูดถึงคือ Propositional logic และ First-Order logic ซึ่งมีความแตกต่างกันอยู่

เพื่อให้เข้าใจได้ง่ายและกระชับ เราจะไม่อธิบายนิยามแต่ละอันไปทีละนิดนะคะ แต่จะชี้ให้เห็นลอจิกทั้งสองรูปแบบ และตอนต่อไปจึงจะเน้นอธิบาย First-Order logic เลยทีเดียว

ก่อนอื่นเรามารู้จักกับคำว่า Formal language กันก่อน ซึ่งก็คือ ภาษาที่ถูกออกแบบมาเพื่อใช้นำเสนอข้อเท็จจริงต่างๆ(arguments) ซึ่งการออกแบบ formal language นี้จำเป็นต้องประกอบไปด้วย 3 ส่วน คือ
1. Lexicon คือ กลุ่มคำศัพท์ที่ใช้ในภาษา
2. Syntax คือ ไวยากรณ์ หรือจะเรียกว่า grammar นั่นเอง
3. Semantic คือการเชื่อมโยงกันระหว่างคำศัพท์กับความหมาย

ดังนั้น ภาษาลอจิก ทั้ง Propositional logic และ First-Order logic ก็จำเป็นที่จะต้องมีทั้งสามส่วนนี้

สมมติว่า เรามีประโยค P= นกแก้วเป็นนก  Q=นกทุกตัวสามารถบินได้
ด้วย Propositional logic เราสามารถนำเสนอประโยค P ได้ แต่ไม่สามารถนำเสนอประโยคQ
ในขณะที่ First-Order logic สามารถที่จะนำเสนอได้ทั้ง P และQ
ดังนั้นจะเห็นว่า ปัญหาคือ propositional logic ไม่มีโครงสร้างที่ใช้บ่งบอกปริมาณของนามในประโยค

เรามาพิจารณาโครงสร้างของลอจิกทั้งสองแบบในแต่องค์ประกอบของการออกแบบกันเลยนะคะ
1. Lexicon ไม่มีอะไรแตกต่างกัน ทั้ง Propositional และ First-order จะสนใจแค่ กลุ่มของ symbols ที่ถูกใช้เป็นสัญลักษณ์ในการนำเสนอ statements เท่านั้น
2. Syntax มีความแตกต่าง โดยเฉพาะ First-Order logic มีนิยามขององค์ประกอบมากกว่า ดังสรุปในแผนภาพ

Atom คือ statement (ข้อมูลหรือข้อเท็จจริง)
Formula (Well-formed formula) สามารถที่จะสร้างขึ้นมาได้จากเงื่อนไข 4 ข้อต่อไปนี้
- Atom อันนึงก็ถือเป็น formula
- ถ้าเรามี formula G ใดๆ แล้ว (~G) ก็เป็น formula เหมือนกัน
- ถ้าเรามี formula สองอันใดๆ แล้ว การนำ formula 2 อันนั้นมาเชื่อมกันด้วย logical connectives (and , or , if, iff ) ก็ถือเป็น formula เช่นกัน
-  เราจะสร้าง formula ทั้งหมดได้จากการใช้กฎทั้ง 3 ข้างต้นเท่านั้น

จะเห็นว่า สิ่งที่เพิ่มขึ้นมาคือ Quantifier ซึ่งจะมีได้สองแบบ คือ for all กับ for some ใช้นำหน้าตัวแปรใดๆ
และ Atom เอง ก็ไม่ใช่แค่ statement เฉยๆ แต่ว่ามีโครงสร้างที่ซับซ้อนขึ้นเมื่อ
Atom ต้องเป็น Predicate ซึ่ง Predicate นั้นเป็นสัญลักษณ์ที่รับค่า n จำนวนใดๆ และ Predicate เองก็จะทำการ map ค่าไปเป็นคำตอบแค่ จริงหรือเท็จเท่านั้น

ค่าที่จะใส่ลงไปใน Predicate เราเรียกว่า Term ซึ่ง term นั้นสามารถเป็น ค่าคงที่ หรือ ตัวแปร หรือฟังก์ชัน ก็ได้

3. Semantic ในลอจิกส่วนนี้ก็คือ Interpretation นั่นเอง ซึ่งมีความแตกต่างระหว่างลอจิกทั้งสองแบบ เนื่องจากว่าโครงสร้างไวยากรณ์ก็ไม่เหมือนกัน

Propositional Logic มี formula ที่ถูกสร้างมาจาก Atom ซึ่งเป็นแค่ statement เพราะฉะนั้น เราก็เพียงแค่ใส่ค่า ความจริงให้กับแต่ละ atom ว่า Atom/ Statement นั้นเป็นจริงหรือเท็จ แล้วก็ทำการประมวลผลตามหลักตรรกศาสตร์ธรรมดา
ตัวอย่างเช่น
เรากำหนดให้ มี Atom คือ P , Q โดยที่ P และ Q แทนค่า statement ดังนี้
P= นกแก้วเป็นนก   ( A parrot is a bird)
Q=นกบินได้ (A bird can fly)
กำหนดให้ formula G = P ∧ P->Q
และตารางกำหนดค่าความจริงของ Propositional Interpretation คือ

ดังนั้น Interpretation ของ G เมื่อเราให้ค่า P,Q = {T,T} จะได้ผลลัพธ์เป็น T ก็แสดงว่า formula G นี้เป็นจริงสำหรับ interpretation นี้ แต่ถ้าเราให้ค่า P,Q ={F,T} ก็จะได้ว่า G เป็นเท็จ สำหรับ interpretation นี้ (คือให้ว่า นกแก้วไม่เป็นนก , นกบินได้)

First-Order Logic นั้น formula ถูกสร้างมาจาก Atom ที่ซับซ้อน ดังนั้นการทำ interpretation ต้องมีการกำหนดค่า Domain ให้กับตัวแปร(variable) , ค่าคงที่ (constant), ผลลัพธ์ของ function และค่าความจริงของ predicate ร่วมด้วย
จากตัวอย่างข้างต้น
เรากำหนดให้  formula G = (∀x) (P(x) -> Q(x))
ให้ predicate P(x) =  x เป็นนก (x is a bird)  และให้ Q(x) = x บินได้  (x can fly)
ถ้าเรามี domain D = {นกแก้ว (parrot) , เพนกวิน (penguin)}
และมีตารางค่าความจริงของ predicate ของ First-Order Interpretation คือ

ดังนั้น Interpretation ของ G เมื่อเราให้ค่า x เป็น parrot ผลลัพธ์คือ T->T = T ถ้า x เป็น penguin ผลลัพธ์คือ T-> F = F  จะเห็นว่า มีตัวแปร x ตัวนึงใน domain D ให้ผลลัพธ์ interpretation เป็น   F ดังนั้นเราจะถือว่า formula  G เป็นเท็จสำหรับ interpretation

ทีนี้ก็พอจะเห็นความเหมือนและความแตกต่างของลอจิกทั้งสองแบบอย่างคร่าวๆแล้วนะคะ แนะนำว่าให้อ่านเพิ่มเติมอย่างละเอียดจะดีกว่า หนังสือแนะนำ ที่นี่ นะคะ