1

回路充足可能性問題の OR ゲートの真理値表を書き留めています (これは、3 充足可能性問題の削減に関係しています)。

私は持っている：

a  b  c    c = (a OR b)
1  1  1    1
1  1  0    0
1  0  1    1
1  0  0    0
0  1  1    1
0  1  0    0
0  0  1    0
0  0  0    1

したがって、列 c = (a OR b) に 0 を含む行を取得し、a、b、c を否定すると、次の 4 つの句が得られます。

!a AND !b AND c
a AND !b AND !c
a AND !b and c
a AND b AND !c

これらの条項を最小限に抑えようとしています。正しい答えは次のとおりです。

c OR !a
c OR !b
c OR !a or !b

これらの 4 つの句を最小限に抑えるにはどうすればよいですか? オンラインのプログラムはありますか？私は wolfram を使用しましたが、正しい答えが出力されませんでした。

4

1 に答える 1

0

c最後の 2 つの行を除いて、最後の列が column とほぼ同じであることは簡単にわかります。最後の 2 つの行では、列の値がcスワップされています。したがって、次のように書くことができます。

if (a ∨ b) then c else ¬c

if c then t else fは CNF として表すことができる(c ∨ t) ∧ (¬c ∨ f)ため、上記の式は次のようになります。

(a ∨ b ∨ ¬c) ∧ (¬(a ∨ b) ∨ c)
= (a ∨ b ∨ ¬c) ∧ ((¬a ∧ ¬b) ∨ c)
= (a ∨ b ∨ ¬c) ∧ (¬a ∨ c) ∧ (¬b ∨ c)

そして最後のものはまさにあなたが望むものです。

于 2014-04-02T17:00:13.023 に答える