•  08-07-2019
  •  | 
  •  

質問

ブール論理で、YのXが真であることをどのように表現できますか？次の2つのようなルールが真でなければなりません（A、B、C、D、E、F） 乗算または集合演算の形式ですか？
最終結果は、AB OR AC OR ADなどのすべての順列です。次の3つがABC、ABD、ABEなどのようなものである場合、（A、B、C）^ 2？

のようになります。

ありがとう！

役に立ちましたか？

解決

ブール論理（ v はOR、述語の後の 'はNOT）：

A B C'D'E'F' v
A B'C'D'E'F  v
A'B C'D'E'F' v
: : : : : :
<absolute bucketload of boolean expressions>
: : : : : :
A'B'C'D'E F

順列では、記述する必要がある非常に多くの部分式があります。

もちろん、これがプログラミングの質問であれば、ブール値を0または1に変換するだけで、それらをすべて加算して、結果が2になることを確認できます。

他のヒント

bool！= intであるC＃または他の言語を想定：

bool nOf(int n, bool[] bs)
{
    foreach(bool b in bs)
    {
      if((n -= b ? 1 : 0) <= 0) break;
    }
    return n == 0;
}

Python：

expressions = [A, B, C, D, E, F, G ]
numTrue = len(filter(None, expressions)

PHP：

$expressions = array(A, B, C, D, E, F, G);
$numTrue = count(array_filter($expressions));

そこにアイデアがあります。 <！> quot; n個のホールドの<！> quotを表現するには; kが成り立つすべてのケースを列挙する必要があります。したがって、変数A B C D Eがあり、5のうち3つが必要な場合は、

(A  &  B &  C & ~D & ~E) |
(A  &  B & ~C &  D & ~E) |
(A  &  B & ~C & ~D &  E) | ...
(~A & ~B &  C &  D &  E)

where <！> amp; <！> quot;および<！> quot;、| <！> quot;または<！> quot; 〜は<！> quot; not <！> quot;です。

<！> quot; A以上<！> quot;と仮定して

ツリーを構築することで少し改善できます

2 : a&(b|c|d|e|f) | b&(c|d|e|f) | c&(d|e|f) | d&(e|f) | e*f
3 : a&(b&(c|d|e|f) | c&(d|e|f) | d&(e|f) | e*f) | b&(c&(d|e|f) | d&(e|f) | e*f) | c&(d&(e|f) | e*f) | d&e&f

またはコードとして

bool AofB(int n, bool[] bs)
{
   if(bs.length == 0) return false;
   if(n == 0) return true;

   foreach(int i, bool b; b[0..$-n])
      if(b && AofB(n-1,b[i+1..$]) return true;

   return false;
}

さらに良い

bool AofB(int n, bool[] bs)
{
   foreach(bool b; bs) if(b && --n == 0) return true;
   return false;
}

それらを数えます。 ただし、ブール演算のみを使用して述語を作成する必要がある場合は、入力を加算器システムへのビットとして扱うことができます。

Basic Half-Adder

A, B : 1st 2nd bits
O, C : unit output and carry to next unit

O := A xor B;
C := A and B;

[Wikipedia] [ http://en.wikipedia.orgで他の例とリンクを見つけることができます。 / wiki / Half_adder （半加算器）]

次に、6つの変数を3つのペアにグループ化し、それらの出力を使用して答えに近づき、残りを自分で解決する方法を見つけます。

もう1つのオプションは、回路を使用してポップカウント（横方向に追加）を検索し、2にのみビットが一致するかどうかを確認することです。 論理ゲートではなくアセンブリの有名な例は、[Hakmem 169] [ http：// home.pipeline.com/~hbaker1/hakmem/hacks.html#item169 （popcount）]。

<！> quot;正確に2つがtrue <！> quotでなければならないかどうかに違いがあります。対<！> quot;少なくとも2つはtrue <！> quot;でなければなりません。

変数のセット{A..F}について、PaxとCharlie Martinの回答は<！> quot; exactly two <！> quot;あなたの質問の表現は<！> quot;少なくとも2 <！> quot;を扱っているように見えますが、ケース：

(A && B) || (A && C) || ... || (D && E) || (D && F) || (E && F)

は、たとえば、AとBが真で、残りの変数がすべて（真または偽）である場合に真になる式です。

求めているのが、上記の状況を説明するための集合論的な表現である場合、次のように表現できます：

#{x | x <- {A, B, C, D, E, F} | x} = 2

表記がこのように機能する場所：

#{...}

囲まれたセットのサイズとセット自体を表します：

{x | x <- {A, B, C, D, E, F} | x}

は<！> quot; xのセットを読み取ります。ここで、AはFから<=のいずれかであり、<=>はtrue <！> quot;です。つまり、変数のセット<=>から<=>が与えられた場合、真の値を持つ変数で構成されたサブセットには、正確に2つの要素があります。 （質問の他の解釈を表すには、「=」の代わりに<=>を使用します。）

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top