2

正の命題式を選言標準形 (DNF)に圧縮したいと思います。

今のところ、否定されたリテラルのない単純な DNF のみを想定しています。逆のプロセス、解凍は簡単に定義できます。論理積と論理和のみから構築された数式の場合、次の書き換え規則によって DNF が生成されます。

A & (B v C) --> (A & B) v (A & C)
(A v B) & C --> (A & C) v (B & C)

解凍の例を次に示します。

Example: Decompression
Input:
  (p & (q v r) & s & (t v u)) v
  w.

Output:
  (p & q & s & t) v
  (p & r & s & t) v
  (p & q & s & u) v
  (p & r & s & u) v
  w.

ここで、DNF から単一の数式を生成できるアルゴリズムがいくつかあるのではないかと考えています。私はすでに二分決定図を調べました。私がこれらの問題を抱えているのは、途中ですべての選言を組み合わせることができないということです。

たとえば、共有を使用する二分決定図のアルゴリズムは、印刷中に同様の分岐を表示したり、新しい前置詞変数を導入したりしますが、どちらも望ましくありません。

Example: Compression (Bad)
Input:
  (p & q & s & t) v
  (p & r & s & t) v
  (p & q & s & u) v
  (p & r & s & u) v 
  w.

Output:
  (p & ((q & s & (t v u)) v (r & s & (t v u)))) v
  w.

- or -

Output:
  (p & ((q & h) v (r & h))) & (h <-> s & (t v u))) v
  w.

結果は、もはや DNF ではなく、単一の式になるはずです。これは、元の DNF に既にある前置詞変数と、選言と接続詞のみを使用する二分決定図アルゴリズムよりもコンパクトです。必要な圧縮の例を次に示します。

Example: Compression (Good)
Input:
  (p & q & s & t) v
  (p & r & s & t) v
  (p & q & s & u) v
  (p & r & s & u) v
  w.

Output:
  (p & (q v r) & s & (t v u)) v
  w.

あなたはどう思いますか？Prolog の実装が優先されます。

さよなら

4

1 に答える 1

1

必要なのは、2 つのレイヤーでブール式の最小値を計算するための体系的なアルゴリズムだと思います (入力変数の論理和の論理和、または入力変数の論理和の論理和)。

これを行うために使用される通常のアルゴリズムは、Karnaugh マップとQuine-McCluskeyアルゴリズムです。

これらのアルゴリズムは、否定された変数で機能します。いずれにせよ、少なくとも入力が選言正規形 (DNF) であり、否定された変数が表示されない場合、入力変数の論理積の選言として表される出力にも否定された変数は含まれません)。

于 2012-09-05T15:42:46.470 に答える