มาเรียน Logic for Computer Science (2 -- Natural Deduction ภาคต่อ)

วันนี้เราจะมาต่อจากเมื่อวานนะคะ จาก Natural Deduction ทั้ง 10 ข้อ เราก็ได้รู้จักไปแล้ว 3 กฎ สำหรับใครที่เพิ่งเข้ามาหน้านี้ แนะนำว่าให้อ่าน ที่นี่ ก่อนจะเข้าใจได้มากกว่าค่ะ
4. Implication Introduction Rule อันนี้เป็นกฎที่เรากำลังจะสร้างเงื่อนไข ถ้า...แล้ว.... ดังนั้น ถ้าเรามี statement (ข้อสันนิษฐาน)นึง และก็มีข้อพิสูจน์อันนึงว่าเกิดอะไรขึ้น เราก็จะสามารถสร้างข้อสรุปได้ว่า ถ้า statement นั้นแล้ว...

ตัวอย่างเช่น

statement = ฝนตก
derivation =                      ท้องฟ้าวันนี้มีเมฆครึ้มและพื้นถนนเปียก

_____________________________________(and E)

    พื้นถนนเปียก

เราก็จะพิสูจน์ข้อสรุปได้คือ conclusion = ถ้า ฝนตก แล้ว พื้นถนนเปียก
ซึ่ง statement = ฝนตก จะเรียกว่า discharged assumption คือมันไม่จำเป็นต้องใช้อีกแล้วสำหรับข้อสรุปบทพิสูจน์ เนื่องจากว่าถ้าดู ข้อสรุปหรือ conclusion ดีๆ จะเห็นว่า statement มันถูกรวมไปใน if ของ conclusion เรียบร้อยแล้ว
สามารถเขียน derivation ได้แบบนี้ค่ะ
                                                             ฝนตก
                                              __________________________

      ท้องฟ้าวันนี้มีเมฆครึ้มและพื้นถนนเปียก

_____________________________________(and E)

    พื้นถนนเปียก

                                      _________________________________(If I)
                                                  (ฝนตก -> พื้นถนนเปียก)

5. Implication Elimination Rule กฎ ข้อนี้บอกว่า ถ้าเรามีข้อพิสูจน์ (derivation) อันแรกที่อยู่ในรูปแบบของถ้าแล้ว(implication) และเรามีข้อพิสูจน์อีกอันที่ตรงกับ statement ใน implication เราก็สามารถที่จะสรุปบทพิสูจน์ออกมาเป็น ข้อสรุปของ implication ได้
พูดง่ายๆก็คือ ถ้าเรามีข้อมูลตรง if ว่าจริง ข้อมูลหลัง then ก็จะเป็นข้อสรุป

ตัวอย่างเช่น
derivation 1 =      ฝนตก
                        ________
                          ฝนตก
derivation 2=                                  ฝนตก -> พื้นถนนเปียก

_____________________________________

     ฝนตก -> พื้นถนนเปียก

เราก็จะพิสูจน์ข้อสรุปได้คือ conclusion =  พื้นถนนเปียก

สามารถเขียน derivation ได้แบบนี้ค่ะ
                                                 ฝนตก         (ฝนตก -> พื้นถนนเปียก)
                                      _______________________________________(If E)
                                                   พื้นถนนเปียก

6. Negation Elimination Rule  เป็นกฎที่บอกเราว่า ถ้ามีข้อพิสูจน์สองข้อใดๆที่มันขัดแย้งกันเอง ข้อสรุปก็คือ contradiction ซึ่งใช้สัญลักษณ์ เหมือนตัว T กลับด้านนะคะ

ตัวอย่างเช่น

derivation 1 =      ฝนตก
                        ________
                          ฝนตก
derivation 2=                                        ฝนไม่ตก

_______________________

  ฝนไม่ตก

เราก็จะพิสูจน์ข้อสรุปได้คือ conclusion =  contradiction เพราะมันขัดแย้งกัน

สามารถเขียน derivation ได้แบบนี้ค่ะ
                                                     ฝนตก            ฝนไม่ตก
                                      _______________________________________(~ E)
                                                                 contradiction

7. Negation Introduction Rule กฎ ข้อนี้บอกว่า ถ้าเรามี statement(ข้อสันนิษฐาน) นึง แล้วพิสูจน์ (derivation) ที่ได้ผลลัพธ์ว่า contradiction ดังนั้นเราจะสรุปข้อพิสูจน์เราได้เป็น ตรงกันข้ามกับ statement (ข้อสันนิษฐาน) ที่คิดไว้

ตัวอย่างเช่น
statement =      ฝนตก
derivation 1 =  พื้นถนนไม่เปียก

derivation 2 =                   ฝนตก               ฝนตก -> พื้นถนนเปียก

_____________________________________

   พื้นถนนเปียก

เราก็จะพิสูจน์ข้อสรุปได้คือ conclusion =  ฝนไม่ตก

สามารถเขียน derivation ได้แบบนี้ค่ะ
                                                 ฝนตก         (ฝนตก -> พื้นถนนเปียก)
                                         _______________________________________(If E)
             พื้นถนนไม่เปียก                             พื้นถนนเปียก
______________________________________________(~ E)
                                contradiction
___________________________________________(~ I)
                              ฝนไม่ตก

ซึ่ง statement = ฝนตก จะเรียกว่า discharged assumption คือมันไม่จำเป็นต้องใช้อีกแล้วสำหรับข้อสรุปบทพิสูจน์ เนื่องจากว่าถ้าดู ข้อสรุปมันตรงกันข้ามกับข้อสันนิษฐานที่เราคิดไว้

8. Reduction Ad Absurdum Rule กฎข้อนี้ตรงกันข้ามกับ ~I เพราะถ้าเรามี negation of statement(ข้อสันนิษฐาน) นึง แล้วพิสูจน์ (derivation) ที่ได้ผลลัพธ์ว่า contradiction ดังนั้นเราจะสรุปข้อพิสูจน์เราได้เป็น ตรงกันข้าม คือได้ statement (ข้อสันนิษฐาน)

ตัวอย่างเช่น
statement =      ฝนไม่ตก
derivation 1 =  พื้นถนนไม่เปียก

derivation 2 =                   ฝนไม่ตก               ฝนไม่ตก -> พื้นถนนไม่เปียก

_____________________________________

   พื้นถนนไม่เปียก

เราก็จะพิสูจน์ข้อสรุปได้คือ conclusion =  ฝนตก

สามารถเขียน derivation ได้แบบนี้ค่ะ
                                                 ฝนไม่ตก         (ฝนไม่ตก -> พื้นถนนไม่เปียก)
                                         _______________________________________(If E)
             พื้นถนนเปียก                             พื้นถนนไม่เปียก
______________________________________________(~ E)
                                contradiction
___________________________________________(RAA)
                              ฝนตก

 ซึ่ง statement = ฝนไม่ตก จะเรียกว่า discharged assumption คือมันไม่จำเป็นต้องใช้อีกแล้วสำหรับข้อสรุปบทพิสูจน์ เนื่องจากว่าถ้าดู ข้อสรุปมันตรงกันข้ามกับข้อสันนิษฐานที่เราคิดไว้

9. Disjunction Introduction Rule กฎ ข้อนี้บอกว่า ถ้าเรามีข้อพิสูจน์ได้ข้อสรุปอันนึง เราก็สามารถที่จะบอกได้ว่ามันเป็นข้อสรุปนั้นหรือข้อสรุปอื่นก็ได้ เพราะการใช้ "หรือ" จะเป็นจริงเมื่ออย่างใดอย่างหนึ่งเป็นจริง

ตัวอย่างเช่น

derivation 1 =  ท้องฟ้าวันนี้มีเมฆครึ้ม (ใช้ axiom rule ดังนั้นขอละไว้ในฐานที่เข้าใจนะคะ)
เราก็จะพิสูจน์ข้อสรุปได้คือ conclusion =  ท้องฟ้าวันนี้มีเมฆครึ้ม หรือ ฝนตก

สามารถเขียน derivation ได้แบบนี้ค่ะ
                                                
                                ท้องฟ้าวันนี้มีเมฆครึ้ม
___________________________________________(or I)
                     ท้องฟ้าวันนี้มีเมฆครึ้ม หรือ ฝนตก
 
10. Disjunction Elimination Rule กฎข้อนี้บอกว่า ถ้าเรามีข้อพิสูจน์ได้ข้อสรุปที่สามารถเป็นอย่างใดอย่างหนึ่ง  เราก็ตั้งข้อสันนิษฐาน(statement) ขึ้นมา แล้วถ้าข้อสันนิษฐานทั้งสองอันนั้นสามารถพิสูจน์ได้ข้อสรุปตรงกัน เราก็สามารถพิสูจน์ได้ข้อสรุปนั้นเช่นกัน

ตัวอย่างเช่น
derivation 1 =  ฝนตก หรือ สปริงเกอร์ถูกเปิดอยู่
derivation 2 =               ฝนตก      (ฝนตก -> พื้นถนนเปียก)
                    ___________________________________________(if E)
                                     พื้นถนนเปียก
derivation 3 =     สปริงเกอร์ถูกเปิดอยู่     (สปริงเกอร์ถูกเปิดอยู่  -> พื้นถนนเปียก)
                    __________________________________________________(if E)
                                                   พื้นถนนเปียก

เราก็จะพิสูจน์ข้อสรุปได้คือ conclusion =  พื้นถนนเปียก

สามารถเขียน derivation ได้แบบนี้ค่ะ

 ซึ่ง statement = it's raining กับ statement = the sprinkler is on จะเรียกว่า discharged assumption คือมันไม่จำเป็นต้องใช้อีกแล้วสำหรับข้อสรุปบทพิสูจน์

 เราพยายามพิมพ์ใหม่ให้เป็นภาษาไทยแล้วแต่มันยาวมากล้นหน้า ทำให้ดูแล้วงง ก็เลยขอตัดแปะเวอร์ชันภาษาอังกฤษจากเอกสารมาแทนแล้วกันนะคะ

ตอนนี้ก็รู้จัก Natural Deduction ทั้ง 10 แบบครบแล้วนะคะ ก็จะเห็นว่าจริงๆมันคือวิธีการคิดหาเหตุผลที่มนุษย์เราใช้กันอยู่แล้ว คราวหน้าจะนำวิธีกฎทั้ง 10 แบบนี้มาเขียนเป็นบทพิสูจน์ที่ยาวๆและตรงกับสถานการณ์จริงดู เพื่อที่ว่าจะได้เข้าใจมากขึ้นว่าถูกเอาไปใช้อย่างไรนะคะ

มาเรียน Logic for Computer Science (1 -- Natural Deduction)

เราเคยโพสความรู้เกี่ยวกับลอจิกไปสองบทความ ซึ่งตอนนั้นที่เขียนก็อาศัยศึกษาเองบ้างอะไรบ้าง แต่ก็ยังเรียบเรียงได้ไม่ดีเท่าไหร่ 

หลังจากบ่มเพาะเก็บความรู้จากอาจารย์ อ่านหนังสือมาสักพัก เราก็คิดว่าคราวนี้จะตั้งใจเขียนให้ดีๆแล้วล่ะ เผื่อว่ามีใครสนใจศาสตร์ด้านนี้ จะได้เป็นแหล่งแลกเปลี่ยนความรู้พูดคุยกัน
ขอออกตัวก่อนเลยนะคะ ว่าเราไม่ใช่ผู้เชี่ยวชาญหรือเก่งกาจอะไร เป็นแค่นักศึกษา ถ้ามีข้อมูลตรงไหนผิดพลาดหรือไม่ชัดเจนก็ต้องขออภัยไว้ ณ ที่นี้ และยินดีที่จะถกเถียงกันเพื่อการพัฒนาความรู้ความเข้าใจร่วมกันนะคะ :)

เนื่องจากเราศึกษาแบบ Computer Science ดังนั้นเนื้อหาจะไม่ใช่แบบนักคณิตศาสตร์ แต่จะเป็นการเอาคณิตศาสตร์ตรรกศาสตร์ หรือ Mathematical Logic มาใช้ร่วมกับหลักการทางคอมพิวเตอร์ค่ะ

เอาล่ะ เรามาเริ่มทำความรู้จักกันก่อนว่า เราจะเรียนลอจิกกันไปทำไม

Mathematical Logic เนี่ยจริงๆแล้ว เป็นการศึกษาเกี่ยวกับการตรวจสอบว่า  argument ที่เรามีเนี่ยมัน valid หรือเปล่า พูดง่ายๆก็คือ เวลาที่เราได้รับข้อมูลมา จะเป็นข้อเท็จจริงความคิดเห็น หรืออะไรก็แล้วแต่ เราต้องตัดสินใจว่า เอ๊ะ ข้อมูลนี้มันถูกต้องสมบูรณ์มีเหตุมีผลจริงหรือเปล่า

โดยปกติมนุษย์เรา พอได้ข้อมูลแล้วก็จะเอาไปคิดต่อใช่มั้ยคะ โดยการคิดของมนุษย์เนี่ยมักจะมีหลักการมีเหตุมีผลอยู่ พอคิดแล้วก็จะหาข้อสรุปออกมา

ซึ่งกระบวนการเหล่านี้ของมนุษนี่ล่ะค่ะ ที่เราอยากเอามามันมาจำลองให้กับคอมพิวเตอร์ ดังนั้น Logic for Computer Science ก็เลยเป็นการผสมผสานทฤษฎีคณิตตรรกศาสตร์เข้ากับทฤษฎีการคำนวณของคอมพิวเตอร์ โดยจุดประสงค์คือ เราต้องการทำให้คอมพิวเตอร์สามารถที่จะเอาปัญหาต่างๆมาคำนวณในรูปการหาเหตุผลแบบนี้ได้

ไม่ใช่เรื่องง่ายเลยใช่มั้ยคะ ลองคิดๆดูว่า เราจะจัดเก็บข้อมูลเข้าไปในรูปแบบไหน แล้วจะหาวิธีการอะไรให้คอมพิวเตอร์คิดแบบมีเหตุผลอย่างมนุษย์ได้

ก่อนที่จะไปพูดถึงทฤษฎีของคณิตตรรกศาสตร์ ที่ถูกเอามาใช้ ซึ่งเราจะอธิบายแค่สองอย่างคือ Propositional Logic กับ First-Order Logic เท่านั้น เราจะพูดถึง  Natural Deduction  ภาษาไทยคำว่า deduction แปลว่า นิรนัย แต่เราขอเรียกว่า deduction ละกันนะ คุ้นเคยกว่า

Natural Deduction คืออะไร   มนุษย์โดยปกติแล้วมีกระบวนการคิดหาเหตุผลโดยอ้างอิงจากพื้นฐานหลักฐาน (deduction) ซึ่งจากแหล่งอ้างอิงได้แบ่งออกเป็น 10 แบบด้วยกันค่ะ


จากนี้ไป เราจะยกตัวอย่างเหตุการณ์ที่พบเจอได้ในชีวิตจริง เพื่อให้เห็นภาพกว้างๆ พร้อมกับแสดงรูปแบบทางคณิตศาสตร์พร้อมกันด้วย เพราะถ้าเรียนกันจริงๆ เราจะต้องฝึกพิสูจน์ด้วยนะคะ ว่าจะได้ข้อสรุปตรงตามทฤษฎีหรือเปล่า

ก่อนจะไปพูดถึงกฎของ deduction ทั้ง 10 แบบนั้น เราต้องรู้จักคำศัพท์ 3 คำก่อนค่ะ คือ
statement  derivation แล้วก็ discharged assumption

statement คือ ประโยคบอกเล่าธรรมดาๆ แต่จะต้องเป็นประโยคที่เราสามารถให้ความหมายมันได้ว่า เป็นจริงหรือเท็จ
เช่น "เลข 2.9 เป็นเลขทศนิยม" อย่างนี้เราบอกได้ว่า เป็นจริง
แต่  "3+6 " เป็นประโยคที่ไม่สมบูรณ์ เราให้ค่า จริงหรือเท็จกับมันไม่ได้

derivation คือ การเขียนบทพิสูจน์ โดยที่รูปแบบการเขียนที่เราอ้างอิงอยู่นี้ จะนิยมเขียนเป็นบรรทัดไล่กันมา แล้วบรรทัดสุดท้ายก็คือ conclusion หรือผลลัพธ์ของการพิสูจน์ค่ะ

assumption คือข้อสันนิษฐาน ดังนั้น discharged assumption คือข้อสันนิษฐานที่เราไม่ต้องใช้มันอีกแล้วกับ conclusion ที่ได้ (เดี๋ยวอ่านวิธีการ deduction ไปเรื่อยๆจะเข้าใจมากขึ้นนะคะ)

ทีนี้เราก็เริ่มทำการศึกษา Natural Deduction ทั้ง 10 ข้อได้เลยค่ะ
1. Axiom Rule อันนี้เป็นกฎที่ตายตัวอยู่แล้ว พูดง่ายๆก็คือ ถ้าเรามี statement ใดๆ เราก็จะสามารถพิสูจน์ได้ว่าข้อสรุปก็คือตัวมันเอง


ตัวอย่างเช่น

statement = ท้องฟ้าวันนี้มีเมฆครึ้ม
เราก็จะพิสูจน์ข้อสรุปได้ตัวมันเองก็คือ conclusion = ท้องฟ้าวันนี้มีเมฆครึ้ม
สามารถเขียน derivation ได้แบบนี้ค่ะ

    ท้องฟ้าวันนี้มีเมฆครึ้ม

______________________

    ท้องฟ้าวันนี้มีเมฆครึ้ม

2. Conjunction Introduction Rule กฎข้อนี้บอกว่า ถ้าเรามีข้อพิสูจน์ (derivation) อันแรกที่ได้ข้อสรุปมาอย่างนึง แล้วมีข้อพิสูจน์อีกอันที่ได้ข้อสรุปมาอีกอย่างนึง เราก็สามารถที่จะเอาข้อสรุปสองอันนั้นมาเชื่อมกันด้วย "และ" ได้



ตัวอย่างเช่น

derivation 1 =  ท้องฟ้าวันนี้มีเมฆครึ้ม
                     _________________
                      ท้องฟ้าวันนี้มีเมฆครึ้ม

derivation 2 =  พื้นถนนเปียก
                     _________________
                      พื้นถนนเปียก

เราก็จะพิสูจน์ข้อสรุปได้ด้วยการเชื่อมข้อสรุปจากทั้งสอง derivation ก็คือ conclusion = ท้องฟ้าวันนี้มีเมฆครึ้มและพื้นถนนเปียก
สามารถเขียน derivation ได้แบบนี้ค่ะ

ท้องฟ้าวันนี้มีเมฆครึ้ม                  พื้นถนนเปียก

______________________        _________________

ท้องฟ้าวันนี้มีเมฆครึ้ม                พื้นถนนเปียก

_________________________________________________________(and I)

                                                      ท้องฟ้าวันนี้มีเมฆครึ้มและพื้นถนนเปียก

 ตัวอย่างนี้ จะเห็นว่าเราพิสูจน์โดยใช้กฎสองข้อคือ axiom rule ก่อน แล้วก็ and introduction ทีหลัง ซึ่งจริงๆแล้ว เราสามารถที่จะละ axiom rule ออกไปได้นะคะ เพราะมันรู้ๆกันอยู่แล้วไม่ได้มีผลกระทบอะไร

3. Conjunction Elimination Rule กฎ ข้อนี้บอกว่า ถ้าเรามีข้อพิสูจน์ (derivation) ที่เป็นสองประโยคเชื่อมกัน เราสามารถที่จะแยกออกเป็นข้อสรุปอันใดอันหนึ่งก็ได้



ตัวอย่างเช่น
เรามี derivation = ท้องฟ้าวันนี้มีเมฆครึ้มและพื้นถนนเปียก
ก็สามารถที่จะพิสูจน์ข้อสรุปได้ 2 แบบ คือ

                      ท้องฟ้าวันนี้มีเมฆครึ้มและพื้นถนนเปียก

                     ___________________________________(and E)

                      ท้องฟ้าวันนี้มีเมฆครึ้ม

 หรือ

                       ท้องฟ้าวันนี้มีเมฆครึ้มและพื้นถนนเปียก

                     ___________________________________(and E)

                      พื้นถนนเปียก

   ตัวอย่างนี้ เราละ axiom rule ออกนะคะ

สรุปสั้นๆเพื่อความเข้าใจก่อน จากกฎ 3 ข้อที่ยกมาให้เห็น จะพบว่ามันก็คือความจริงของมนุษย์ เป็นหลักการธรรมดาๆที่เราใช้ในการโต้เถียงหาเหตุผลกัน
อย่างเวลาเราได้ข้อมูลมาว่า "นกตัวนั้นบินได้และว่ายน้ำได้"  เวลาเราเอาไปพูดต่อกับเพื่อน เราก็อาจจะพูดแค่ว่า "นกตัวนั้นว่ายน้ำได้"  ซึ่งการที่เราพูดด้วยข้อสรุปแบบนี้ ก็ไม่ได้ทำให้ประโยคเดิมหรือข้อมูลเดิมเปลี่ยนไป เราเพียงแต่ตัดเอาส่วนที่เราอยากใช้นำไปใช้เท่านั้นเอง

กฎที่เหลืออีก 7 ข้อจะเริ่มซับซ้อนมากขึ้นและหลังจากศึกษาครบทั้ง 10 ข้อแล้ว ทีนี้เราจะเข้าใจกระบวนการคิดของมนุษย์มากขึ้นว่า ทุกครั้งที่เราคิดทำอะไรมันจะมีกระบวนการเหตุผลซ่อนอยู่เบื้องหลัง เพียงแต่ว่ามันเร็วมากจนเราไม่รู้ตัวเท่านั้นเองค่ะ

สำหรับท่านที่สนใจศึกษาจริงจัง เราแนะนำว่าให้อ่านหนังสือ Mathematical Logic จริงๆเลยดีกว่า เพราะต้องอ่านตัวบทพิสูจน์ให้ละเอียด ที่เราแปะมานี้เป็นแค่คร่าวๆเท่านั้นเอง  ลิงก์หนังสือแนะนำ ดูได้ที่นี่ ค่ะ

หวังว่าที่เราเขียนมาคงจะพออ่านเข้าใจนะคะ  สำหรับ 7 ข้อที่เหลือเราจะแบ่งไปโพสหน้านะคะ เพราะว่าบล็อกนี้มันยาวมากแล้ว  ;)