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

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

ระบบตรรกะจะถือว่าสามารถตัดสินได้ หากมีวิธีการที่มีประสิทธิภาพในการตรวจสอบว่าสูตรใดๆ เป็นทฤษฎีบทของระบบตรรกะนั้นหรือไม่ ตัวอย่างเช่นตรรกะเชิงประพจน์สามารถตัดสินได้ เพราะสามารถใช้วิธีตารางความจริง ในการตรวจสอบว่า สูตรเชิงประพจน์ ใดๆ มีความถูกต้องทางตรรกะ หรือไม่

ตรรกะลำดับที่หนึ่งไม่สามารถตัดสินได้โดยทั่วไป โดยเฉพาะอย่างยิ่ง เซตของความถูกต้องเชิงตรรกะในลายเซ็น ใดๆ ที่รวมถึงความเท่าเทียมกันและ สัญลักษณ์ภาคแสดงอื่นๆ อย่างน้อยหนึ่งตัวที่มีอาร์กิวเมนต์สองตัวขึ้นไปนั้นไม่สามารถตัดสินได้^{[ 1 ]}ระบบตรรกะที่ขยายตรรกะลำดับที่หนึ่ง เช่นตรรกะลำดับที่สองและทฤษฎีประเภทก็ไม่สามารถตัดสินได้เช่นกัน

อย่างไรก็ตาม ความถูกต้องของแคลคูลัสภาคแสดงเอกนามที่มีเอกลักษณ์นั้นสามารถตัดสินได้ ระบบนี้เป็นตรรกะลำดับที่หนึ่งที่จำกัดเฉพาะลายเซ็นที่ไม่มีสัญลักษณ์ฟังก์ชัน และสัญลักษณ์ภาคแสดงอื่นนอกเหนือจากความเท่าเทียมกันจะไม่รับอาร์กิวเมนต์มากกว่าหนึ่งตัว

ระบบตรรกะบางระบบไม่สามารถแสดงได้อย่างเพียงพอด้วยชุดทฤษฎีบทเพียงอย่างเดียว (ตัวอย่างเช่นตรรกะของคลีนไม่มีทฤษฎีบทเลย) ในกรณีเช่นนี้ มักมีการใช้คำจำกัดความทางเลือกของความสามารถในการตัดสินของระบบตรรกะ ซึ่งต้องการวิธีการที่มีประสิทธิภาพในการพิจารณาสิ่งที่ทั่วไปกว่าความถูกต้องของสูตรเพียงอย่างเดียว เช่น ความถูกต้องของลำดับหรือความสัมพันธ์ของผลลัพธ์ {(Г, A ) | Г ⊧ A } ของตรรกะ

ทฤษฎีคือเซตของสูตร ซึ่งมักถือว่าปิดภายใต้ผลลัพธ์เชิงตรรกะ ความสามารถในการตัดสินใจสำหรับทฤษฎี นั้นเกี่ยวข้องกับว่ามีกระบวนการที่มีประสิทธิภาพในการตัดสินว่าสูตรนั้นเป็นสมาชิกของทฤษฎีหรือไม่ โดยกำหนดสูตรใดๆ ก็ตามในลายเซ็นของทฤษฎี ปัญหาเรื่องความสามารถในการตัดสินใจเกิดขึ้นโดยธรรมชาติเมื่อทฤษฎีถูกนิยามว่าเป็นเซตของผลลัพธ์เชิงตรรกะของเซตของสัจพจน์ ที่กำหนด ไว้

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

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

ตัวอย่างของทฤษฎีอันดับหนึ่งที่ตัดสินได้ ได้แก่ ทฤษฎีฟิลด์ปิดจริงและพีชคณิตของเพรสเบอร์เกอร์ในขณะที่ทฤษฎีกลุ่มและพีชคณิตของโรบินสันเป็นตัวอย่างของทฤษฎีที่ตัดสินไม่ได้

ทฤษฎีที่ตัดสินได้บางส่วนได้แก่ (Monk 1976, หน้า 234): ^{[ 2 ]}

• ชุดความถูกต้องเชิงตรรกะลำดับแรกในลายเซ็นที่มีเพียงความเท่าเทียมกันเท่านั้น ซึ่งกำหนดโดยเลโอโปลด์ โลเวนไฮม์ในปี 1915
• ชุดของความถูกต้องเชิงตรรกะลำดับแรกในลายเซ็นที่มีความเท่าเทียมกันและฟังก์ชันเอกภาคหนึ่งฟังก์ชัน ซึ่งกำหนดโดยEhrenfeuchtในปี 1959
• ทฤษฎีลำดับที่หนึ่งของจำนวนธรรมชาติในรูปแบบความเท่าเทียมและการบวก หรือที่เรียกว่าเลขคณิตเพรสเบอร์เกอร์ความสมบูรณ์ของทฤษฎีนี้ได้รับการพิสูจน์โดยโมเจส เพรสเบอร์เกอร์ในปี ค.ศ. 1929
• ทฤษฎีลำดับที่หนึ่งของจำนวนธรรมชาติในรูปแบบที่มีความเท่าเทียมและการคูณ หรือที่เรียกว่าเลขคณิต สโกเล็ม (Skolem arithmetic )
• ทฤษฎีลำดับที่หนึ่งของพีชคณิตบูลีนซึ่งก่อตั้งโดยอัลเฟรด ทาร์สกีในปี 1940 (ค้นพบในปี 1940 แต่ประกาศอย่างเป็นทางการในปี 1949)
• ทฤษฎีอันดับแรกของฟิลด์ปิดเชิงพีชคณิตที่มีลักษณะเฉพาะ ที่กำหนดให้ ซึ่งตั้งขึ้นโดยทาร์สกีในปี 1949
• ทฤษฎีอันดับแรกของฟิลด์เรียงลำดับแบบปิดจริงซึ่งตั้งขึ้นโดย Tarski ในปี 1949 (ดูเพิ่มเติมที่ปัญหาฟังก์ชันเลขชี้กำลังของ Tarski )
• ทฤษฎีลำดับที่หนึ่งของเรขาคณิตแบบยุคลิดซึ่งตั้งขึ้นโดยทาร์สกีในปี 1949
• ทฤษฎีลำดับที่หนึ่งของกลุ่มอาเบเลียนซึ่งตั้งขึ้นโดยSzmielewในปี 1955
• ทฤษฎีลำดับที่หนึ่งของเรขาคณิตไฮเปอร์โบลิกซึ่งคิดค้นโดยชวาบเฮาเซอร์ในปี 1959
• ภาษาย่อยที่สามารถตัดสิน ได้เฉพาะของทฤษฎีเซตซึ่งได้รับการศึกษาค้นคว้าตั้งแต่ทศวรรษ 1980 จนถึงปัจจุบัน (Cantone et al. , 2001)
• ทฤษฎีลำดับที่สองแบบเอกภาคของต้นไม้ (ดูS2S )

วิธีการที่ใช้ในการพิสูจน์ความสามารถในการตัดสินใจ ได้แก่การกำจัดตัวบ่งปริมาณ ความสมบูรณ์ของแบบจำลองและการทดสอบ Łoś– Vaught

ทฤษฎีที่ไม่สามารถตัดสินได้บางส่วนได้แก่: ^{[ 2 ]}

• เซตของความถูกต้องเชิงตรรกะในลายเซ็นลำดับที่หนึ่งใดๆ ที่มีความเท่าเทียมกันและมีอย่างใดอย่างหนึ่งดังต่อไปนี้: สัญลักษณ์ภาคแสดงที่มีจำนวนสมาชิกไม่น้อยกว่า 2 หรือสัญลักษณ์ฟังก์ชันเอกภาคสองตัว หรือสัญลักษณ์ฟังก์ชันหนึ่งตัวที่มีจำนวนสมาชิกไม่น้อยกว่า 2 ซึ่งกำหนดโดยTrakhtenbrotในปี 1953
• ทฤษฎีลำดับที่หนึ่งของจำนวนธรรมชาติที่มีการบวก การคูณ และความเท่าเทียมกัน ซึ่งตั้งขึ้นโดยทาร์สกีและอันเดรย์ โมสโตว์สกีในปี 1949
• ทฤษฎีลำดับที่หนึ่งของจำนวนตรรกยะที่มีการบวก การคูณ และความเท่ากัน ซึ่งตั้งขึ้นโดยจูเลีย โรบินสันในปี 1949
• ทฤษฎีลำดับแรกของกลุ่มซึ่งก่อตั้งโดยAlfred Tarskiในปี 1953 ^{[ 3 ]} ที่น่าสังเกตคือ ไม่เพียงแต่ทฤษฎีทั่วไปของกลุ่มเท่านั้นที่ไม่สามารถตัดสินได้ แต่ยังมีทฤษฎีเฉพาะเจาะจงอีกหลายทฤษฎี เช่น (ตามที่Mal'cev ก่อตั้งใน ปี 1961) ทฤษฎีของกลุ่มจำกัด Mal'cev ยังก่อตั้งทฤษฎีของเซมิกรุปและทฤษฎีของวงแหวนที่ไม่สามารถตัดสินได้อีกด้วย Robinson ก่อตั้งในปี 1949 ว่าทฤษฎีของฟิลด์นั้นไม่สามารถตัดสินได้
• เลขคณิตของโรบินสัน (และส่วนขยายที่สอดคล้องกันใดๆ เช่นเลขคณิตของพีอาโน ) นั้นโดยพื้นฐานแล้วไม่สามารถตัดสินได้ ดังที่ ราฟาเอล โรบินสันได้พิสูจน์ไว้ในปี 1950
• ทฤษฎีลำดับแรกที่มีความเท่าเทียมกันและสัญลักษณ์ฟังก์ชันสองตัว^{[ 4 ]}

วิธีการตีความได้มักถูกนำมาใช้เพื่อพิสูจน์ว่าทฤษฎีนั้นไม่สามารถตัดสินได้ หากทฤษฎีT ซึ่งโดยพื้นฐานแล้วไม่สามารถตัดสินได้ นั้น สามารถตีความได้ในทฤษฎีS ที่สอดคล้องกัน แล้วSก็ไม่สามารถตัดสินได้โดยพื้นฐานเช่นกัน แนวคิดนี้มีความเกี่ยวข้องอย่างใกล้ชิดกับแนวคิดของการลดรูปหลายต่อหนึ่งในทฤษฎีความสามารถในการคำนวณ

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

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

ความสามารถในการตัดสินใจไม่ควรสับสนกับความสมบูรณ์ตัวอย่างเช่น ทฤษฎีของฟิลด์ปิดเชิงพีชคณิตสามารถตัดสินใจได้แต่ไม่สมบูรณ์ ในขณะที่เซตของข้อความอันดับหนึ่งที่เป็นจริงทั้งหมดเกี่ยวกับจำนวนธรรมชาติในภาษาที่มีเครื่องหมาย + และ × นั้นสมบูรณ์แต่ไม่สามารถตัดสินใจได้ น่าเสียดายที่เนื่องจากความกำกวมทางศัพท์ คำว่า "ข้อความที่ตัดสินใจไม่ได้" บางครั้งถูกใช้เป็นคำพ้องความหมายกับ " ข้อความที่เป็นอิสระ "

เช่นเดียวกับแนวคิดของเซตที่ตัดสินได้นิยามของทฤษฎีหรือระบบตรรกะที่ตัดสินได้นั้น สามารถให้ได้ทั้งในแง่ของวิธีการที่มีประสิทธิภาพหรือในแง่ของฟังก์ชันที่คำนวณได้โดยทั่วไปแล้วถือว่าทั้งสองอย่างนี้เทียบเท่ากันตามทฤษฎีบทของเชิร์ชอันที่จริง การพิสูจน์ว่าระบบตรรกะหรือทฤษฎีนั้นตัดสินไม่ได้ จะใช้นิยามอย่างเป็นทางการของความสามารถในการคำนวณเพื่อแสดงว่าเซตที่เหมาะสมนั้นไม่ใช่เซตที่ตัดสินได้ จากนั้นจึงอ้างถึงทฤษฎีบทของเชิร์ชเพื่อแสดงว่าทฤษฎีหรือระบบตรรกะนั้นไม่สามารถตัดสินได้ด้วยวิธีการที่มีประสิทธิภาพใดๆ (Enderton 2001, หน้า 206 เป็นต้นไป )

เกมบาง เกม ได้รับการจัดประเภทตามความสามารถในการตัดสินใจ:

• การรุกฆาตในnในหมากรุกอนันต์ (โดยมีข้อจำกัดเกี่ยวกับกฎและตัวหมาก) สามารถตัดสินได้^{[ 5 ] [ 6 ]} อย่างไรก็ตาม มีตำแหน่ง (ที่มีตัวหมากจำนวนจำกัด) ที่เป็นการชนะแบบบังคับ แต่ไม่ใช่การรุกฆาตในnสำหรับnที่ จำกัดใดๆ ^{[ 7 ]}
• เกมทีมบางเกมที่มีข้อมูลไม่สมบูรณ์บนกระดานที่มีขอบเขตจำกัด (แต่มีเวลาไม่จำกัด) ไม่สามารถตัดสินได้^{[ 8 ]}

• Entscheidungsproblem
• การวัดเชิงอัตถิภาวะ