ข้ามไปเนื้อหา

แคลคูลัสเชิงประพจน์

จากวิกิพีเดีย สารานุกรมเสรี
(เปลี่ยนทางจาก Propositional calculus)

แคลคูลัสเชิงประพจน์ (อังกฤษ: propositional calculus) คือระบบรูปนัยสำหรับการใช้เหตุผลแบบนิรนัย ที่มีหน่วยพื้นฐานคือตัวแปรเชิงประพจน์ (ซึ่งจะแตกต่างจากตรรกศาสตร์ภาคแสดงที่อาจมีการใช้ ตัวบ่งปริมาณ และมีหน่วยพื้นฐานคือฟังก์ชันเชิงประพจน์ และตรรกศาสตร์อัญรูปที่หน่วยพื้นฐานอาจไม่ใช่ประโยคระบุความจริง)

ในที่นี้ แคลคูลัส คือระบบทางตรรกศาสตร์ที่ใช้สำหรับพิสูจน์ทั้งสูตร (นั่นคือทฤษฎีบทที่ได้จากระบบนั้น) และการอ้างเหตุผลที่สมเหตุสมผล แคลคูลัสคือเซตของสัจพจน์ (ที่อาจเป็นเซตว่างหรืออาจเป็นเซตอนันต์นับได้) และกฎการอนุมานสำหรับการสร้างการอนุมานที่สมเหตุสมผล ไวยากรณ์รูปนัย (หรือ วากยสัมพันธ์) จะนิยามนิพจน์และสูตรที่จัดดีแล้ว (well-formed formular หรือ wff) ของภาษาแบบเวียนเกิด นอกจากนี้จะต้องมีการระบุความหมาย (อรรถศาสตร์) ที่นิยามความจริงและค่าต่าง ๆ (หรือการตีความ) ทั้งหมดนี้ทำให้เราสามารถตัดสินได้ว่าสูตรที่จัดดีแล้วสูตรใดสมเหตุสมผล

ในแคลคูลัสเชิงประพจน์นั้น ภาษาจะประกอบด้วยตัวแปรเชิงประพจน์ และตัวดำเนินการเชิงประโยค (หรือ ตัวเชื่อม) สูตรที่จัดดีแล้ว คือสูตรที่เป็นหน่วยพื้นฐาน หรือสูตรที่สร้างโดยใช้ตัวดำเนินการเชิงประโยค

ต่อไปเราจะได้แสดงรูปแบบมาตรฐานของแคลคูลัสเชิงประพจน์อย่างคร่าว ๆ รูปแบบอื่น ๆ ที่แตกต่างไปจากนี้ก็ยังมีใช้อยู่ ข้อแตกต่างที่พบจะมีในส่วนของ (1) ภาษา (ตัวดำเนินการและตัวแปรใดบ้างที่จัดว่าเป็นส่วนของภาษา) (2) สัจพจน์ใดที่ใช้ และ (3) กฎการอนุมานที่ใช้

ไวยากรณ์

[แก้]

ภาษาของแคลคูลัสเชิงประพจน์ประกอบด้วย:

  1. ตัวอักษรที่ใช้แทนตัวแปรเชิงประพจน์ ตัวอักษรเหล่านี้คือสูตรพื้นฐาน เรานิยมใช้ภาษาอังกฤษตัวใหญ่
  2. เครื่องหมายที่ใช้แทนตัวเชื่อมต่าง ๆ: ¬, , , , . (เราสามารถลดจำนวนตัวดำเนินการลงจากนี้ได้ เนื่องจากนิพจน์ที่ใช้ตัวดำเนินการบางตัวสมมูลกับนิพจน์ที่ใช้ตัวดำเนินการอื่น ๆ เช่น P → Q สมมูลกับ ¬ P ∨ Q.)
  3. เครื่องหมายวงเล็บเปิด และวงเล็บปิด: (, )

เซตของ wff ถูกนิยามแบบเวียนเกิด (เรียกซ้ำ) ด้วยกฎต่อไปนี้

  1. กรณีฐาน: ตัวอักษร (เช่น A, B, ฯลฯ) เป็น wff
  2. อนุพากย์อุปนัยที่ 1: ถ้า φ เป็น wff, แล้ว ¬ φ เป็น wff
  3. อนุพากย์อุปนัยที่ 2: ถ้า φ และ ψ ต่างเป็น wff, แล้ว (φ ∧ ψ) , (φ ∨ ψ) , (φ → ψ) , และ (φ ↔ ψ) ล้วนเป็น wff
  4. อนุพากย์แสดงการปิด: ไม่มีสิ่งอื่นที่เป็น wff

การใช้กฎเหล่านี้ทำให้เราสร้าง wff ที่ซับซ้อนได้ เช่น

  1. โดยกฎที่ 1, A เป็น wff
  2. โดยกฎที่ 2, ¬ A เป็น wff
  3. โดยกฎที่ 1, B เป็น wff
  4. โดยกฎที่ 3, ( ¬ AB ) เป็น wff

แคลคูลัส

[แก้]

สัจพจน์

[แก้]

กฎการอนุมาน

[แก้]

ตัวอย่าง

[แก้]

ความถูกต้องและความบริบูรณ์ของกฎ

[แก้]

แคลคูลัสอื่น ๆ

[แก้]

ตัวอย่างบทพิสูจน์

[แก้]

แคลคูลัสเชิงตรรกศาสตร์อื่น ๆ

[แก้]

ดูเพิ่ม

[แก้]