Editing Knuth–Bendix completion algorithm (section)

==Introduction==

For a set ''E'' of equations, its '''deductive closure''' ({{Overunderset|⟷|⁎|''E''}})  is the set of all equations that can be derived by applying equations from ''E'' in any order.
Formally, ''E'' is considered a [[binary relation]], ({{underset|''E''|⟶}}) is its [[rewrite closure]], and ({{Overunderset|⟷|⁎|''E''}}) is the [[equivalence closure]] of ({{underset|''E''|⟶}}).
For a set ''R'' of rewrite rules, its '''deductive closure''' ({{Overunderset|⟶|⁎|''R''}} ∘ {{Overunderset|⟵|⁎|''R''}}) is the set of all equations that can be confirmed by applying rules from ''R'' left-to-right to both sides until they are literally equal.
Formally, ''R'' is again viewed as a binary relation, ({{underset|''R''|⟶}}) is its rewrite closure, ({{underset|''R''|⟵}}) is its [[converse relation|converse]], and ({{Overunderset|⟶|⁎|''R''}} ∘ {{Overunderset|⟵|⁎|''R''}}) is the [[relation composition]] of their [[reflexive transitive closure]]s ({{Overunderset|⟶|⁎|''R''}} and {{Overunderset|⟵|⁎|''R''}}).

For example, if {{math|1=''E'' = {{mset|1= 1⋅''x'' = ''x'', ''x''<sup>−1</sup>⋅''x'' = 1, (''x''⋅''y'')⋅''z'' = ''x''⋅(''y''⋅''z'') }}}} are the [[Group (mathematics)|group]] axioms, the derivation chain
:{{math|''a''<sup>−1</sup>⋅(''a''⋅''b'') &nbsp; {{Overunderset|⟷|⁎|''E''}} &nbsp; (''a''<sup>−1</sup>⋅''a'')⋅''b'' &nbsp; {{Overunderset|⟷|⁎|''E''}} &nbsp; 1⋅''b'' &nbsp; {{Overunderset|⟷|⁎|''E''}} &nbsp; ''b''}}
demonstrates that ''a''<sup>−1</sup>⋅(''a''⋅''b'')  {{Overunderset|⟷|⁎|''E''}} ''b'' is a member of ''E'''s deductive closure.
If {{math|1=''R'' = {{mset| 1⋅''x'' → ''x'', ''x''<sup>−1</sup>⋅''x'' → 1, (''x''⋅''y'')⋅''z'' → ''x''⋅(''y''⋅''z'') }}}} is a "rewrite rule" version of ''E'', the derivation chains
:{{math|(''a''<sup>−1</sup>⋅''a'')⋅''b'' &nbsp; {{Overunderset|⟶|⁎|''R''}} &nbsp;  1⋅''b'' &nbsp; {{Overunderset|⟶|⁎|''R''}} &nbsp; ''b''  &nbsp;  &nbsp;  &nbsp; and &nbsp;  &nbsp;  &nbsp; ''b'' &nbsp; {{Overunderset|⟵|⁎|''R''}} &nbsp; ''b''}}
demonstrate that (''a''<sup>−1</sup>⋅''a'')⋅''b'' {{Overunderset|⟶|⁎|''R''}}∘{{Overunderset|⟵|⁎|''R''}} ''b'' is a member of ''R'''s deductive closure.
However, there is no way to derive ''a''<sup>−1</sup>⋅(''a''⋅''b'') {{Overunderset|⟶|⁎|''R''}}∘{{Overunderset|⟵|⁎|''R''}} ''b'' similar to above, since a right-to-left application of the rule {{math|(''x''⋅''y'')⋅''z'' → ''x''⋅(''y''⋅''z'')}} is not allowed.

The Knuth–Bendix algorithm takes a set ''E'' of equations between [[term (logic)|terms]], and a [[reduction ordering]] (>) on the set of all terms, and attempts to construct a confluent and terminating term rewriting system ''R'' that has the same deductive closure as ''E''.
While proving consequences from ''E'' often requires human intuition, proving consequences from ''R'' does not.
For more details, see [[Confluence (abstract rewriting)#Motivating examples]], which gives an example proof from group theory, performed both using ''E'' and using ''R''.