ตรรกศาสตร์: ภาษาอันดับหนึ่ง

ถ้าว่ากันสั้น ๆ ว่า ภาษาอันดับหนึ่ง (First-Order Language) คืออะไร? มันก็คือ ภาษาที่ไม่มีความคลุมเครือ และง่ายกับคอมพิวเตอร์ครับ

โครงสร้างของภาษาอันดับหนึ่ง มีส่วนประกอบ 5 กลุ่มหลัก ๆ คือ

1. สัญลักษณ์ประพจน์ภาคแสดง (Predicate Symbol)
2. สัญลักษณ์ฟังก์ชัน (Function Symbol)
   
3. สัญลักษณ์ค่าคงที่ (Constant Symbol)
4. สัญลักษณ์ตัวแปร (Variable Symbol)
   
5. กลุ่มของประพจน์ภาคแสดง (Predicate Set)

ซึ่งประพจน์ภาคแสดงใน 4 จะต้องประกอบด้วยเครื่องหมายใน 3 กลุ่มแรก รวมกับกลุ่มของตัวเชื่อม และตัวบ่งปริมาณ ได้แก่

1. ¬ ∧ ∨ → ↔
2. ∃ ∀ ที่ตามหลังด้วยสัญลักษณ์ตัวแปร
   
3. , ( ) [ ] { } ตามแต่สะดวกใช้
   

จริง ๆ กฎเกณฑ์มันมากกว่านี้ แต่ขอไม่พูดถึงละกัน เพราะคิดว่าใช้สามัญสำนึกจะง่ายกว่า ส่วนความหมายของเครื่องหมายพวกนี้ คงไม่ต้องอธิบายนะ

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

Predicate Symbol: Even, Odd
Function Symbol: NextOf
Constant Symbol: 0
Variable Symbol: x
Predicate Set:
1. Even(0)
2. ∀x [ Even(x) ↔ ¬Odd(x) ]
3. ∀x [ Even(x) → Odd(NextOf(x)) ]
4. ∀x [ Odd(x) → Even(NextOf(x)) ]

สมมติว่า เรามีระบบของภาษาอันดับแล้วอันนึง เราอยากรู้ว่า ประพจน์ภาคแสดงอีกอันนึง เป็นจริงในระบบนั้นรึเปล่า เช่นในตัวอย่างนี้ เราอยากรู้ว่า Odd(NextOf(0)) เป็นจริงรึเปล่า วิธีที่นิยมใช้กันก็คือ เพิ่มนิเสธของประพจน์ดังกล่าวเข้าไป ซึ่งก็คือ

5. ¬Odd(NextOf(0))

คราวนี้ ถ้าเราสามารถแสดงให้เห็นว่าเกิด ความไม่สมเหตุสมผล (Inconsistency) ของระบบขึ้นมาได้ เราก็จะรู้ว่าประพจน์ที่เราต้องการตรวจสอบเป็นจริง แต่ถ้าไม่ได้ เราก็จะยังสรุปไม่ได้

ในตัวอย่างที่ยกมานี่ ถ้าเราเอา 1 กับ 3 รวมกัน จะได้ประพจน์ใหม่คือ

Odd(NextOf(0))

ซึ่ง ขัดแย้งกับประพจน์ที่ 5 เราก็เลยสรุปได้ว่า Odd(NextOf(0)) เป็นจริง

คำว่า "รวมกัน" เนี่ย ตอนนี้ก็ขอให้เข้าใจไปตาม "สามัญสำนึก" ก่อนละกัน วิธีตายตัวที่เรียกได้ว่าเป็น "Algorithm" เนี่ย จะต้องพูดถึงแน่ ๆ แต่รอก่อนนะ

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