ตรรกศาสตร์: รูปแบบปกติสโกเล็ม

ต่อจากที่ค้างไว้คราวที่แล้ว เราได้รูปแบบประพจน์ที่ เครื่องหมายนิเสธอยู่ในสุดแล้ว (บางคนเรียกรูปแบบนี้ว่า Negation Normal Form หรือ รูปแบบปกตินิเสธ) หน้าตาแบบนี้...

∀x[(∃y[P(x, y) ∧ ∀z[¬Q(x, y, z)]] ∨ R(x)) ∧
(∀y[¬P(x, y) ∨ ∃z[Q(x, y, z)] ∨ ¬R(x))]

เดี๋ยวเราจะหาทางทำให้อยู่ในรูปแบบปกติประพจน์รวมให้ได้ ซึ่งมีขั้นตอนหลัก 2 ขั้น คือ

1. กำจัด ∃
2. ขยับ ∀ ไปไว้นอกสุด

เริ่มต้น เราจะ กำจัด ∃ โดยใช้หลักการดังนี้

∀x[∃y[P(x, y)]] เป็นจริง
ก็ต่อเมื่อ
มีฟังก์ชัน f(x) ที่ทำให้ ∀x[P(x, f(x))] เป็นจริง

เราเรียก f ว่าเป็น "ฟังก์ชันสโกเล็ม (Skolem Function)" จากรูปประพจน์เดิมคือ

∀x[(∃y[P(x, y) ∧ ∀z[¬Q(x, y, z)]] ∨ R(x)) ∧
(∀y[¬P(x, y) ∨ ∃z[Q(x, y, z)] ∨ ¬R(x))]

พอกำจัด ∃ โดยการแทนฟังก์ชันสโกเล็มลงไป ก็จะเป็น

∀x[((P(x, f(x)) ∧ ∀z[¬Q(x, f(x), z)]) ∨ R(x)) ∧
(∀y[¬P(x, y) ∨ Q(x, y, g(x, y)) ∨ ¬R(x))]

หมายเหตุ: g(x, y) มีพารามิเตอร์ 2 ตัว ก็เพราะว่า มันแทน ∃z ที่อยู่ใน scope ของ ∀x∀y

ในกรณีที่มี ∃ มากกว่า 1 ตัวซ้อนกัน ก็ไม่ต้องเอาไปเพิ่มเป็นพารามิเตอร์นะ เช่น

∀a∃b∀c∃d[P(a, b, c, d)]
จะกลายเป็น
∀a∀c[P(a, f(a), c, g(a, c)]

ตอนนี้ เราได้ประพจน์ใน รูปแบบปกติสโกเล็ม (Skolem Normal Form) แล้ว กลับมาที่ประพจน์เดิมของเราอีกที

∀x[((P(x, f(x)) ∧ ∀z[¬Q(x, f(x), z)]) ∨ R(x)) ∧
(∀y[¬P(x, y) ∨ Q(x, y, g(x, y)) ∨ ¬R(x))]

คราวนี้จะ ผลัก ∀ ไปไว้นอกสุดด้วยกัน หมดเลย มันจะหน้าตาแบบนี้

∀x∀z∀y[((P(x, f(x)) ∧ ¬Q(x, f(x), z)) ∨ R(x)) ∧
(¬P(x, y) ∨ Q(x, y, g(x, y)) ∨ ¬R(x))]

โชคดี ที่ไม่มีตัวแปรหน้าตาซ้ำกัน แต่ถ้ามันซ้ำกัน (อยู่ที่ ∀ หรือ ∃ คนละตัว) เราจะใช้หลักการนี้...

∀x[P(x)] ∧ ∀x[Q(x)]
จะเทียบเท่ากับ
∀x∀y[P(x) ∧ Q(y)]

และ

∀x[P(x)] ∨ ∀x[Q(x)]
จะเทียบเท่ากับ
∀x∀y[P(x) ∨ Q(y)]

จะเห็นว่า เราแก้ปัญหาได้ง่าย ๆ โดย กำหนดตัวแปรใหม่ (ให้ชื่อไม่ซ้ำกับตัวที่มีอยู่แล้ว) ... กลับมาที่ประพจน์ของเราอีกที คราวนี้ ∀ อยู่นอกสุดหมดแล้ว เราก็เอามันออกไปเลย แล้วคิดซะว่า ตัวแปรทุกตัวมี ∀ อยู่ หน้าตาของประพจน์เราจะกลายเป็น

((P(x, f(x)) ∧ ¬Q(x, f(x), z)) ∨ R(x)) ∧
(¬P(x, y) ∨ Q(x, y, g(x, y)) ∨ ¬R(x))

คราวนี้ก็สามารถทำเป็น รูปแบบปกติประพจน์รวม (Conjunctive Normal Form) ได้แล้ว ผลคือ จะได้วรรค 3 วรรค คือ

P(x, f(x)) ∨ R(x)
¬Q(x, f(x), z) ∨ R(x)
¬P(x, y) ∨ Q(x, y, g(x, y)) ∨ ¬R(x)

บางที เราก็เรียกการเขียนเป็นวรรค ๆ ว่า รูปแบบวรรค (Clause Form)

วันนี้จบเรื่องละ