Выполнимость

• Выполнимость формулы в логике связана с ее истинностью при определенных значениях переменных. 
• Двойственным понятием выполнимости является валидность, формула считается валидной, если каждое присвоение значений делает ее истинной. 
• Задача о выполнимости теорий по модулю рассматривает выполнимость формулы относительно формальной теории. 
• Выполнимость и валидность определены для одной формулы, но могут быть обобщены на произвольную теорию или набор формул. 
• Проблема определения выполнимости формулы в логике высказываний разрешима и известна как проблема булевой выполнимости. 
• В классической логике выполнимость разрешима для пропозициональных формул, но неразрешима для логики первого порядка. 
• Проблема конечной выполнимости связана с определением того, допускает ли формула конечную модель, которая делает ее истинной.