不変条件
論理問題での不変条件の特定が便利であることを示すため、MUパズルを例に用いる。このパズルは次の規則からなる。
ある文字列が I で終わっている場合、U をそれにつなげることができる(xI → xIU)
Mの後の文字列は全体を複製できる(Mx → Mxx)
3つの I が連続している場合(III)、それらを1つの U に置換できる(xIIIy → xUy)
2つの U が連続している場合、それらを削除できる(xUUy → xy)
この4つの規則だけで MI から MU に変換できるか、というのがダグラス・ホフスタッターの考案したMUパズルである。
このパズルをやってみると何時間でもつぶすことができるかもしれない。しかし、全ての規則に対して不変である述語を探し、MU を作ることができないと示す方が早い。論理的に見てみると、I を取り除くには I が3つ連続していなければならない。このことから、次のように興味深い不変条件が導かれる。
文字列内の I の個数は 3 の倍数ではない
この条件が不変条件と言えるのは、この条件が事前に成り立っている場合に、どの変換規則を適用した後も常に同じ条件が成り立っていると言える場合である。各変換規則が I と U の個数に与える効果を見てみると、この条件が不変条件だとわかる。

上の表を見れば明らかなように、この不変条件はどの変換規則を適用した後も成り立つ。したがって、最初に I の個数が3の倍数でないなら、どの規則をどういう順序で適用しても I の個数は3の倍数にはならない。
MI という文字列には I が1つしかなく、3の倍数ではない。MU には I が 0 個あり、0は3の倍数である。したがって、MI から MU への変換は不可能である。