ค่าความจริงและปัญหาความสอดคล้องแบบบูล

ทางลัด: ความแตกต่างความคล้ายคลึงกันค่าสัมประสิทธิ์การเปรียบเทียบ Jaccardการอ้างอิง

ความแตกต่างระหว่าง ค่าความจริงและปัญหาความสอดคล้องแบบบูล

ค่าความจริง vs. ปัญหาความสอดคล้องแบบบูล

ค่าความจริง (Truth value) ในทางตรรกศาสตร์และคณิตศาสตร์ หมายถึง ค่าที่ใช้บ่งบอกว่าประพจน์ใดเป็นความจริง ในเรื่องของตรรกศาสตร์แบบฉบับ (classical logic) ค่าความจริงมีเพียงสองอย่างเท่านั้นคือ ค่าจริง (true) และค่าเท็จ (false) แต่สำหรับตรรกศาสตร์คลุมเครือ (fuzzy logic) หรือตรรกศาสตร์หลายค่า (multi-valued logic) ค่าความจริงอาจจะมีค่าอย่างอื่นที่นอกเหนือจากนั้นก็ได้ เซตของค่าความจริง ทำให้เกิดพีชคณิตแบบบูล (Boolean algebra) ซึ่งคำนวณด้วยวิธีที่คล้ายพีชคณิตแล้วให้ผลเฉพาะในเซตเท่านั้น ส่วนพีชคณิตแบบอื่นอาจมีการใช้เซตของค่าความจริงในตรรกศาสตร์ที่ไม่ได้เป็นแบบฉบับ ตัวอย่างเช่น ตรรกศาสตร์สหัชญาณนิยม (intuitionistic logic) หรือพีชคณิตเฮย์ทิง (Heyting algebra) เป็นต้น ในการเขียนโปรแกรม คอมพิวเตอร์จะให้ความหมายของค่า 0 เป็นค่าเท็จ และค่าอื่นที่ไม่ใช่ 0 (รวมทั้ง 1) หมายถึงค่าจริง และภาษาโปรแกรมบางภาษาอาจมีค่าว่าง (null) อยู่ด้วย ซึ่งไม่ใช่ทั้งค่าจริงและค่าเท็จ หมวดหมู่:ตรรกศาสตร์. ปัญหาความสอดคล้องแบบบูล หรือ SAT (Boolean satisfiability) เป็นปัญหาการตัดสินใจอย่างหนึ่งที่ถูกกล่าวถึงบ่อย ๆ ในศาสตร์ทางด้านทฤษฎีความซับซ้อนในการคำนวณ ตัวอย่างของปัญหา (instance) สำหรับปัญหานี้ก็คือ นิพจน์บูลีน (boolean expression) ที่ประกอบด้วยตัวแปร ตัวเชื่อมต่าง ๆ และวงเล็บ ปัญหานี้ถามคำถามที่ว่า สำหรับนิพจน์บูลีนที่กำหนด เราสามารถทำให้นิพจน์เป็นจริงโดยการกำหนดค่าให้กับตัวแปรได้หรือไม่ ในกรณีที่เราสามารถกำหนดค่าความจริงให้กับตัวแปรแล้วทำให้นิพจน์เป็นจริงได้ เราจะกล่าวว่านิพจน์นั้น สามารถทำให้เป็นจริงได้ (satisfiable) ปัญหา SAT จัดอยู่ในกลุ่มของปัญหาเอ็นพีบริบูรณ์ (NP-complete) ในบางครั้งเราอาจจะสนใจศึกษาความซับซ้อนของรูปแบบที่ต่างกันออกไปของปัญหา SAT ยกตัวอย่างเช่นปัญหา SAT แบบที่นิพจน์บูลีนอยู่ในรูปมาตรฐานแบบเชื่อม (หรือ Conjunctive Normal Form---CNF) ในกรณีนี้ถ้าแต่ละประพจน์เลือก (disjunct) ประกอบด้วยตัวแปรไม่เกิน 3 ตัวแปรเราจะเรียกปัญหาว่า 3-SAT ซึ่งเป็นปัญหาเอ็นพีบริบูรณ์เช่นเดียวกัน อย่างไรก็ตาม ในกรณีที่ตัวแปรในแต่ละประพจน์เลือกมีไม่เกิน 2 ตัวแปร (เรียกว่าปัญหา 2-SAT) นั้น เรามีอัลกอริธึมที่มีประสิทธิภาพในการแก้ปัญหาได้ นั่นก็คือ 2SAT \in P หรือหากจะพูดให้ชัดเจนกว่านั้น 2SAT \in NL \subseteq P (ทั้งนี้เนื่องจากขั้นตอนวิธีที่ใช้แก้ปัญหา 2-SAT เป็นขั้นตอนวิธีที่ทำงานโดยใช้เนื้อที่เป็นลอการิธึมบนเครื่องจักรทัวริงเชิงไม่กำหนดเท่านั้น).