Разрешимость (логика)

• Разрешимость логической системы определяется как возможность эффективного определения, является ли произвольная формула логически корректной. 
• Логика первого порядка в целом неразрешима, включая логику Клини. 
• Разрешимость теории зависит от наличия эффективной процедуры определения, является ли формула частью теории. 
• Непротиворечивые теории, обладающие свойством, что каждое непротиворечивое расширение неразрешимо, называются по существу неразрешимыми. 
• Некоторые разрешимые теории включают набор логических значений первого порядка и различные теории первого порядка. 
• Полуразрешимость — свойство теории или логической системы, более слабое, чем разрешимость. 
• Связь разрешимости с полнотой и вычислимостью обычно считается эквивалентной. 
• Некоторые игры, такие как шахматы, разрешимы, в то время как другие командные игры с неполной информацией на конечной доске неразрешимы.