項書き換え
項書き換え(こうかきかえ、英: term rewriting)とは、数学・計算機科学・論理学において、式(数式、論理式)の項を別の項に置換する手法を総称する用語である。項書き換え系(英: term rewriting system、TRS)とは、項の集合とその置換規則から構成される。
項書き換えは非決定的になることがありうる。ある規則で書き換え可能な項が他の規則でも書き換え可能な場合がありえて、その場合は複数の規則が適用可能と言うことになる。項書き換え系では、項書き換えのためのアルゴリズムは提供されず、書き換え規則の集合のみが提供される。しかし、適当なアルゴリズムと組み合わせれば、項書き換え系はプログラムのような働きをし、実際いくつかの宣言型プログラミング言語は項書き換えに基づいている。
項書き換え系は自動定理証明にとっても便利な手法である。いくつかの等式からなる仮説があったとき、それらが一種の項書き換え規則群として利用できる。簡単な代数学での項書き換え手法として「類似の項を一方の辺に集める」というやり方がある。その進め方は何通りもある。
P(x) = Q(x)
ここで、P と Q は多項式である。これに通常の規則を何度か適用すると次のような形の等式が得られる。
R(x) = 0.
これは一種の標準形であるが、書き換えの経路が違うと R の内容が異なることもある。R が正規形であると言った場合、R(x)は x の次数の大きい項から順に次数が小さくなるように項が並んでいる。