昔論理学の授業で習ったタブロー法を Scheme と SLLGEN で実装してみました。 * 速習タブロー法 タブロー法とは論理式が充足可能か矛盾しているかを確かめるアルゴリズムの一つです。 充足可能というのはその論理式が真になるような場合がありうるかということです。例えば P&Q は P が 真で Q も真であれば真になるので充足可能です。一方で P&~P は P が真であっても偽であっても真になりえないので矛盾しています。 タブロー法は 1. 与えられた論理式が全て充足可能であると仮定する 2. 論理式を展開規則によって原子式まで分解して行く。例えば「A&B=真」という仮定からは「A=真」「B=真」という2つの仮定が生じます。 3. 分解していく過程でなんらかの原子式Pについて「P=真」と「P=偽」の両方が現れたら矛盾。最後まで矛盾しなかったら充足可能。 という手順を踏んでいきます。展