ในทฤษฎีความสามารถในการคำนวณการลดรูปตารางความจริงเป็นรูปแบบหนึ่งของการลดรูปจากปัญหาการตัดสินใจ ไปสู่ปัญหาการตัดสินใจอีก ปัญหาหนึ่ง ในการแก้ปัญหาในการลดรูปจะอธิบายคำตอบของปัญหาในรูปของสูตรบูลีนหรือตารางความจริงของการสอบถามจำนวนจำกัดไปยังปัญหา ${\displaystyle A}$${\displaystyle B}$${\displaystyle A}$${\displaystyle A}$${\displaystyle B}$

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

การลดตารางความจริงปรากฏในบทความของEmil Postที่ตีพิมพ์ในปี พ.ศ. 2487 ^{[ 1 ]}

การลดรูปตารางความจริงแบบอ่อนคือการลดรูปที่ใช้คำตอบจากออราเคิลเป็นพื้นฐานสำหรับการคำนวณเพิ่มเติม ซึ่งอาจขึ้นอยู่กับคำตอบที่ให้มา แต่ไม่จำเป็นต้องถามคำถามเพิ่มเติมจากออราเคิล ที่ได้ชื่อเช่นนี้เพราะมันลดข้อจำกัดที่กำหนดไว้ในการลดรูปตารางความจริง และให้การจำแนกความเท่าเทียมกันที่อ่อนกว่า ดังนั้น "การลดรูปตารางความจริงแบบอ่อน" จึงอาจมีประสิทธิภาพมากกว่าการลดรูปตารางความจริงในฐานะ "เครื่องมือ" และสามารถทำการลดรูปที่ไม่สามารถทำได้โดยใช้ตารางความจริง กล่าวอีกนัยหนึ่ง การลดรูปตารางความจริงแบบอ่อนคือการลดรูปทัวริงที่การใช้การลดรูปนั้นถูกจำกัดด้วยฟังก์ชันที่คำนวณได้ด้วยเหตุนี้ บางครั้งจึงเรียกว่า การลด รูปทัวริงแบบจำกัด (bT) แทนที่จะเรียกว่าการลดรูปตารางความจริงแบบอ่อน (wtt)

เนื่องจากการลดรูปตารางความจริงทุกรูปแบบเป็นการลดรูปทัวริง ดังนั้น ถ้าAสามารถลดรูปตารางความจริงไปเป็นB ได้ ( A ≤ _tt B ) แล้วAก็สามารถลดรูปทัวริงไปเป็นB ได้เช่นกัน ( A ≤ _T B ) นอกจากนี้ยังพิจารณาถึงการลดรูปแบบหนึ่งต่อหนึ่ง การลดรูปแบบหลายต่อหนึ่ง และการลดรูปตารางความจริงแบบอ่อนด้วย

${\displaystyle A\leq _{1}B\Rightarrow A\leq _{m}B\Rightarrow A\leq _{tt}B\Rightarrow A\leq _{wtt}B\Rightarrow A\leq _{T}B}$,

หรือกล่าวอีกนัยหนึ่ง ความสามารถในการลดรูปหนึ่งต่อหนึ่งหมายถึงความสามารถในการลดรูปหลายต่อหนึ่ง ซึ่งหมายถึงความสามารถในการลดรูปตารางความจริง ซึ่งในทางกลับกันหมายถึงความสามารถในการลดรูปตารางความจริงแบบอ่อน ซึ่งในทางกลับกันหมายถึงความสามารถในการลดรูปทัวริง

นอกจากนี้A สามารถลดรูปตารางความจริงไปเป็นBได้ก็ต่อเมื่อAสามารถลดรูปทัวริงไปเป็นB ได้ โดยใช้ฟังก์ชันรวมบนทิศทางไปข้างหน้าเป็นเรื่องง่าย สำหรับทิศทางย้อนกลับ สมมติว่าเป็นฟังก์ชันที่คำนวณได้ทั้งหมด ในการสร้างตารางความจริงสำหรับการคำนวณA ( n ) เพียงแค่ค้นหาจำนวนmเช่นนั้น สำหรับสตริงไบนารีทั้งหมดที่มีความยาวmจะ ลู่เข้า จำนวน mดังกล่าวต้องมีอยู่จริงตามทฤษฎีบทของ Kőnigเนื่องจากต้องเป็นฟังก์ชันรวมบนทุกเส้นทางผ่าน เมื่อกำหนด mดังกล่าวแล้ว การหาตารางความจริงที่ไม่ซ้ำกันซึ่งให้ เมื่อนำไปใช้กับ นั้นเป็นเรื่องง่ายทิศทางไปข้างหน้าล้มเหลวสำหรับการลดรูปตารางความจริงแบบอ่อน ${\displaystyle 2^{\omega }}$${\displaystyle \Gamma }$${\displaystyle \sigma }$${\displaystyle \Gamma ^{\sigma }(n)}$${\displaystyle \Gamma }$${\displaystyle 2^{<\omega }}$${\displaystyle \Gamma ^{\sigma }(n)}$${\displaystyle \sigma }$