PLP のプログラムは形としてはPrologのプログラムで、実行順序のないものとします(以下で少しずつどういうことか説明していきます)。PLPのプログラムは論理的には
という論理式と考えることができます。ここで は
という形の式とします。 は述語、各 は項または変数です。この形の論理式を述語式と呼ぶことにします。 は
という形の論理式で、各 は
という形の論理式で、各 と各 は述語式です。
PLP のプログラムを論理式と考えて、それを証明することを考えます。証明は「シークエント計算」に基づいて行っていきますが、正確な説明にはなりませんが「シークエント計算」の全体を説明すると長くなるので必要な部分だけを書いていくことにします。
まず上記の
を証明するには、新しい項 を追加して に現れる を にそれぞれ置き換えたものを と書くとすると、
を証明すれば十分となります(「シークエント計算」の「 右」)。 が という述語、 が という述語とすると、 は となります。
次に を証明するには、 を証明すれば十分となります(「 右」)。
を証明するには を証明すれば十分となります(「簡約左」)。
を証明するには をどれかの に対して証明すれば十分となります(「左」の繰り返し)。ここで は に同様の変換を行ったものとします。Prolog ではこの についての実行順序は固定となりますが、PLP ではプログラムは並行に実行されるとしてすべての に対して実行されるものとします。
各 を
とおくと、
を証明するには、新しい変数 を追加して を でそれぞれ置き換えた
を証明すれば十分となります(「 左」)。
を証明するには
と
を証明すれば十分となります(「左」)。
は と が一致するときは公理となるので証明可能で一致しないときは証明できません。
を証明するには のときは公理となり証明可能で、 のときは
をすべての に対して証明すれば十分となります(「右」の繰り返し)。Prolog ではこの についての実行順序は固定となりますが、PLP ではプログラムは並行に実行されるとしてすべての に対して実行されるものとします。
を証明するには上記の
以下の議論を繰り返していきます(無限に実行するものを定義することも可能)。