Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Decidability (logic)
open-in-new
<p>In <a href="/facts/Logic/8JnpJLtt">logic</a>, a true/false <a href="/facts/Decision_problem/cQNWjbdE">decision problem</a> is decidable if there exists an <a href="/facts/Effective_method/4kC9c5hE">effective method</a> for deriving the correct answer. <a href="/facts/Zeroth-order_logic/NI8T4gNG">Zeroth-order logic</a> (propositional logic) is decidable, whereas <a href="/facts/First-order_logic/lcISqWIg">first-order</a> and <a href="/facts/Higher-order_logic/hdUhry6m">higher-order</a> logic are not. <a href="/facts/Formal_system/KaeDAjK7">Logical systems</a> are decidable if membership in their set of <a href="/facts/Validity_(logic)/oMGkywGC">logically valid</a> formulas (or theorems) can be effectively determined. A <a href="/facts/Theory_(mathematical_logic)/mYe5gQpI">theory</a> (set of sentences <a href="/facts/Deductive_closure/mSIIFmlE">closed</a> under <a href="/facts/Logical_consequence/AyDXp4dn">logical consequence</a>) in a fixed logical system is decidable if there is an effective method for determining whether arbitrary formulas are included in the theory. Many important problems are <a href="/facts/Undecidable_problem/QBxmXBbY">undecidable</a>, that is, it has been proven that no effective method for determining membership (returning a correct answer after finite, though possibly very long, time in all cases) can exist for them. </p>