多値論理を効率的な論理論理に変換するにはどうすればよいですか？

Question

Sが{0₁, ¯1₂, 0₂, 1₂, ¯2₃, ¯1₃, 0₃, 1₃, 2₃, ¯3₄, ¯2₄, ¯1₄, 0₄, 1₄, 2₄, 3₄}であるとします。私はS上で、次の操作を定義したい：と場合のみSが負の場合は1を返し

• S < 0。
• ¯SSの否定を返します。
• S + 0Sに0を加えたものです。Sは変更されていません。
• S + 1Sの絶対値+1に添字を法とする1を返します。たとえば：
  • ¯1₃ + 1と1₃ + 1の両方が2₃に評価されます。
  • ¯2₃ + 1および2₃ + 1は、0₃と評価されます。
  • 0₃ + 1は、1₃と評価されます。
• S ¢ 0carry（S + 0）を返します。これはゼロです。
• S ¢ 1S + 1のキャリーを返します。これはがn > 1の場合にのみ1になります。

この情報は、真理値表の形式でキャプチャすることができます：私は何をしたいか

S S<0 ¯S S+0 S+1 S¢0 S¢1 
┌───┬───┬───┬───┬───┬───┬───┐ 
│ 0₁│ 0 │ 0₁│ 0₁│ 0₁│ 0 │ 0 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│¯1₂│ 1 │ 1₂│¯1₂│ 0₂│ 0 │ 1 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│ 0₂│ 0 │ 0₂│ 0₂│ 1₂│ 0 │ 0 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│ 1₂│ 0 │¯1₂│ 1₂│ 0₂│ 0 │ 1 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│¯2₃│ 1 │ 2₃│¯2₃│ 0₃│ 0 │ 1 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│¯1₃│ 1 │ 1₃│¯1₃│ 2₃│ 0 │ 0 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│ 0₃│ 0 │ 0₃│ 0₃│ 1₃│ 0 │ 0 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│ 1₃│ 0 │¯1₃│ 1₃│ 2₃│ 0 │ 0 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│ 2₃│ 0 │¯2₃│ 2₃│ 0₃│ 0 │ 1 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│¯3₄│ 1 │ 3₄│¯3₄│ 0₄│ 0 │ 1 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│¯2₄│ 1 │ 2₄│¯2₄│ 3₄│ 0 │ 0 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│¯1₄│ 1 │ 1₄│¯1₄│ 2₄│ 0 │ 0 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│ 0₄│ 0 │ 0₄│ 0₄│ 1₄│ 0 │ 0 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│ 1₄│ 0 │¯1₄│ 1₄│ 2₄│ 0 │ 0 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│ 2₄│ 0 │¯2₄│ 2₄│ 3₄│ 0 │ 0 │ 
├───┼───┼───┼───┼───┼───┼───┤ 
│ 3₄│ 0 │¯3₄│ 3₄│ 0₄│ 0 │ 1 │ 
└───┴───┴───┴───┴───┴───┴───┘ 

は、私が実装できるように、この複数の値を持つ真理値表は、ブール真理値表に変換され並列演算のためのビット演算子を使用した演算。十分に簡単です。 0000を0₁,0001から¯1₂、...、1111から3₄に割り当てます。結果として得られるKarnaugh mapを解いてCNFまたはDNFという式を取得し、それを1日と呼びます。

残念なことに、結果のCNFまたはDNF式は、ブール値にSのこの素朴なマッピングでは効率的でない場合があります。私はブール値の真理値表としてこの多値真理値表を表現する最も効率的な方法を見つけたいと思っています。ここで、効率的とは、少数の演算子を用いて、加算、否定、キャリー、およびその順序での比較が優先されて、様々な演算を実現することを意味する。しかし、問題は、または20922789888000の方法でブール値にSをマッピングすることです。強引な力よりも解決策を見つける良い方法はありますか？

Answer 1

私はこの問題の一般的な解決策は考えられませんが、ここでは私の問題に対する具体的な解決方法があります。 Sのセットを2つの互いに素なセット、すなわちS₁とS₂にダイビングすることから始めます。セットS₁は、0₁と添え字₄要素を含むでしょう。今、私たちはS₁とS₂で別々にこの問題を解決することができます

S₁ = {0₁, ¯3₄, ¯2₄, ¯1₄, 0₄, 1₄, 2₄, 3₄} 
S₂ = {¯1₂, 0₂, 1₂, ¯2₃, ¯1₃, 0₃, 1₃, 2₃} 
S = S₁ ∪ S₂ 

：セットS₂は添字₂と添字₃の要素が含まれます。しかし、我々は解決策が似ているようにしたい。したがって、それらを組み合わせると、類似性を利用して関連する操作の数を減らすことができます。ここで私が思いついた解決策があります：

1. すべてゼロ要素がC'D'列に属している：

   

   私の解決策について、注意すべき2つのものがあります。したがって、C+Dを使用して残りの要素を選択するのは簡単です。これは後で便利になるでしょう。

2. 負の要素は常にBの行にあり、対応する正の要素と同じ列にあります。これは否定的であり否定的なものかどうかをチェックする。

がとにかく、ここでの操作はビット演算子(A, B, C, D) ∈ S使用して実装されている：運ぶ、またために必要な操作の数

(A, B, C, D) < 0 = B (C + D) 

¯(A, B, C, D) = (A, B^(C + D), C, D) 

(A, B, C, D) + M = 
    E = C D 
    N = M' 
    (A, B N + M E, 
     C N + M (A^C^D^A E), 
     D N + M D' (B + C)) 

(A, B, C, D) ¢ M = M D (A + C) 

を、否定比較は、それぞれ18、3、2、2です。否定の場合はBを変更する必要があり、追加の場合はAを変更する必要はありません。 Common subexpression eliminationおよびxor操作はreduce操作で使用されます。

これよりも優れているかどうかはわかりません。これは私が思いついた最善の解決策です。