Method of analytic tableaux

<p>In <a href="/facts/Proof_theory/kopBdQn9">proof theory</a>, the semantic tableau , also called an analytic tableau, truth tree, or simply tree, is a <a href="/facts/Decision_procedure/cQNWjbdE">decision procedure</a> for <a href="/facts/Sentential_logic/MNt5v31V">sentential</a> and related logics, and a <a href="/facts/Proof_procedure/DyMslchW">proof procedure</a> for formulae of <a href="/facts/First-order_logic/lcISqWIg">first-order logic</a>. An analytic tableau is a tree structure computed for a logical formula, having at each node a subformula of the original formula to be proved or refuted. Computation constructs this tree and uses it to prove or refute the whole formula. The tableau method can also determine the <a href="/facts/Satisfiability/NkmQFgHB">satisfiability</a> of finite sets of <a href="/facts/Formula/BosTcKnv">formulas</a> of various logics. It is the most popular <a href="/facts/Proof_procedure/DyMslchW">proof procedure</a> for <a href="/facts/Modal_logic/I7uXvYYT">modal logics</a>.
</p><p>A method of truth trees contains a fixed set of rules for producing trees from a given logical formula, or set of logical formulas. Those trees will have more formulas at each branch, and in some cases, a branch can come to contain both a formula and its negation, which is to say, a contradiction. In that case, the branch is said to close. If every branch in a tree closes, the tree itself is said to close. In virtue of the rules for construction of tableaux, a closed tree is a proof that the original formula, or set of formulas, used to construct it was itself self-contradictory, and therefore false. Conversely, a tableau can also prove that a logical formula is <a href="/facts/Tautology_(logic)/p82wWMaN">tautologous</a>: if a formula is tautologous, its negation is a contradiction, so a tableau built from its negation will close.
</p>

Method of analytic tableaux open-in-new

Method of analytic tableaux