ตัวอย่างโจทย์ตรรกศาสตร์เชิงประพจน์
บทความนี้แสดงรูปแบบของประพจน์หลายรูปแบบ และค่าความจริงที่เป็นไปได้ของรูปแบบเหล่านั้นด้วยวิธีตาราง
ตัวอย่างที่ 1
ลองหาว่ารูปแบบต่อไปนี้เป็นจริงเมื่อใด: ϕ = (p ∧ q) ∨ ¬q เริ่มจากเขียนตัวแปรแทนประพจน์ p และ q ลงในตาราง:
จากนั้นเพิ่มส่วนแรกของรูปแบบ (p ∧ q) นิเสธ ¬q และรูปแบบทั้งหมดลงในตาราง:
ต่อไปหาค่าในหลักที่สาม ซึ่งเป็นตัวเชื่อม และ ธรรมดา พร้อมกับหาค่านิเสธ ซึ่งเพียงเขียนค่าตรงข้ามกับค่าในหลักที่สอง:
สุดท้ายหาค่าในหลักสุดท้าย ซึ่งเป็นรูปแบบทั้งหมด เมื่อดูจากตาราง สิ่งที่ต้องหาคือตัวเชื่อม หรือ “ระหว่างหลักที่สามกับหลักที่สี่” ผลลัพธ์:
ตัวอย่างที่ 2
โจทย์เหมือนเดิม แต่เป็นรูปแบบใหม่: ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ q) จะเห็นว่าในรูปแบบมีตัวแปรแทนประพจน์ p และ q รวมทั้งนิเสธของทั้งสองตัว จึงเริ่มจากสร้างตารางที่มีตัวแปรสองตัวและนิเสธของตัวแปรเหล่านั้น:
ต่อไปเพิ่มรูปแบบ p ∧ ¬q และ ¬p ⇒ q ซึ่งหาค่าได้ง่าย เพราะในตารางมีทั้งค่าความจริงของประพจน์แต่ละตัวและของนิเสธแล้ว ตารางเป็นดังนี้:
สุดท้ายเหลือหาค่าของรูปแบบทั้งหมด ซึ่งเป็นตัวเชื่อม ก็ต่อเมื่อ ระหว่างสองหลักสุดท้าย:
ตัวอย่างที่ 3
ตัวอย่างที่สามยากขึ้นอีกนิด เพราะมีตัวแปรแทนประพจน์สามตัว ตารางจึงยาวขึ้น รูปแบบเป็นดังนี้: ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q))
เนื่องจากมีตัวแปรแทนประพจน์สามตัว จำนวนกรณีของการกำหนดค่าความจริงทั้งหมดจึงเท่ากับแปด:
จากนั้นทำแบบเดียวกับตัวอย่างก่อนหน้า คือหาค่าของแต่ละหลักครบทั้งแปดแถว ตารางทั้งหมดเป็นดังนี้:
ตัวอย่างที่ 4
ตัวอย่างนี้ไม่ได้ให้มาเป็นรูปแบบของประพจน์ธรรมดา แต่เป็นโจทย์ปัญหา เพื่อนสามคนอยากไปงานวันเกิดสุดสนุกของเพื่อนร่วมห้อง แต่ทั้งสามคนไม่ค่อยถูกกันนัก จึงตั้งเงื่อนไขกันว่าจะไปงานในกรณีใดบ้าง ทั้งสามคนชื่อมานพ จักรพันธ์ และปกรณ์ กติกามีดังนี้:
- ถ้ามานพไป แล้วจักรพันธ์ก็ไปด้วย
- ปกรณ์ไปงาน หรือถ้ามานพไป แล้วจักรพันธ์ไม่ไป
- ปกรณ์ไปก็ต่อเมื่อมานพไม่ไปหรือจักรพันธ์ไม่ไป
คำถามคือ ทุกคนไปงานพร้อมกันได้หรือไม่ ถ้าไม่ได้ ใครบ้างที่ไปงานได้โดยไม่ผิดกติกาข้อใดเลย
ก่อนอื่นต้องเขียนประพจน์ที่เป็นคำพูดข้างต้นให้เป็นตัวแปรแทนประพจน์และรูปแบบของประพจน์ ให้ตัวแปรแทนประพจน์ M J และ P (มานพ จักรพันธ์ ปกรณ์) แทนประพจน์ทำนอง “มานพไปงาน” กติกาข้อแรกเขียนได้เป็น M ⇒ J คือ “ถ้า M แล้ว J” หรือ “ถ้ามานพไปงาน แล้วจักรพันธ์ไปงาน”
กติกาข้อที่สองเขียนได้ดังนี้ กติกาขึ้นต้นด้วย “ปกรณ์ไปงาน หรือ…” จึงต้องใช้ตัวเชื่อม หรือ แน่นอน ตอนนี้เขียนไว้ก่อนว่า P ∨ … ส่วนที่เหลือของประโยคบอกว่า “ถ้ามานพไป แล้วจักรพันธ์ไม่ไป” ซึ่งเป็นตัวเชื่อม ถ้า…แล้ว และข้างขวายังต้องใช้นิเสธด้วย “จักรพันธ์ไม่ไป” = ¬J ประพจน์ ถ้า…แล้ว ทั้งหมดเป็นดังนี้: M ⇒ ¬J นำไปเชื่อมกับตัวเชื่อม หรือ ข้างต้น: P ∨ (M ⇒ ¬J)
กติกาข้อที่สามเขียนได้ดังนี้ เริ่มจาก “ปกรณ์ไปก็ต่อเมื่อ” ซึ่งหมายถึงตัวเชื่อม ก็ต่อเมื่อ: P ⇔ … ต่อมาคือ “มานพไม่ไปหรือจักรพันธ์ไม่ไป” เขียนได้เป็น ¬M ∨ ¬J รวมกันได้: (P ⇔ (¬M ∨ ¬J))
ตอนนี้ใส่รูปแบบทั้งหมดลงในตารางแล้วหาค่า:
คำถามคือ เพื่อนทั้งสามคนไปงานวันเกิดพร้อมกันได้หรือไม่ คำตอบอยู่ในแถวแรก แถวนี้เป็นกรณีที่ทุกคนไป ซึ่งดูได้จาก T สามตัวในสามหลักแรก เป็นไปตามเงื่อนไขทุกข้อหรือไม่ ข้อแรกเป็นไปตามเงื่อนไข (หลักที่สี่) ข้อที่สองก็เช่นกัน (หลักที่ห้า) แต่ข้อสุดท้ายไม่เป็นไปตามเงื่อนไข (หลักสุดท้าย) ตรงนั้นเป็น F แสดงว่าถ้าทั้งสามคนไป เงื่อนไขข้อที่สามจะไม่เป็นจริง
จึงต้องหาแถวที่ตำแหน่งของเงื่อนไข (คือสามหลักสุดท้าย) เป็น T ทั้งหมด T หมายความว่าเงื่อนไขนั้นเป็นจริง จะเห็นว่ามีสองกรณี คือเมื่อจักรพันธ์กับปกรณ์ไปแต่มานพไม่ไป และเมื่อปกรณ์ไปคนเดียว
อีกวิธีหนึ่งคือเพิ่มรูปแบบ ϕ ลงในตาราง ซึ่งเป็นตัวเชื่อม และ ของเงื่อนไขทั้งสามข้อ ซึ่งเป็นดังนี้: ϕ = ((M ⇒ J) ∧ (P ∨ (M ⇒ ¬J)) ∧ (P ⇔ (¬M ∨ ¬J))) รูปแบบนี้แสดงสิ่งที่ต้องการ คือให้รูปแบบทั้งหมด (เงื่อนไขทุกข้อ) เป็นจริง ตารางจะเป็นดังนี้:
ตัวอย่างวิธีตารางเพิ่มเติม
ผู้เขียนเขียนโปรแกรมที่สร้างตารางทั้งหมดจากรูปแบบที่กำหนดได้โดยอัตโนมัติ จึงขอใช้ให้คุ้ม ต่อไปนี้เป็นรูปแบบอีกหลายรูปแบบพร้อมคำตอบ:
รูปแบบ: ((a ∧ ¬b) ∨ (b ∧ (b ⇒ a))) ตาราง:
รูปแบบ: (a ∨ ¬a) ⇔ (b ∧ ¬b) ตาราง:
รูปแบบ: ¬(a ∨ b) ⇔ (¬b ∧ ¬a) ตาราง:
รูปแบบ: ϕ = (¬p ⇔ (q ∧ r)) ⇒ (p ∨ ¬(p ∧ q)) ตาราง:
รูปแบบ: ϕ = ¬(p ⇔ ¬q) ∧ (r ⇒ ¬p) ∧ (p ∨ r) ตาราง:
สารบัญ: ตรรกศาสตร์เชิงประพจน์, ค่าความจริงของรูปแบบของประพจน์, ตัวอย่างโจทย์ตรรกศาสตร์เชิงประพจน์