3

ブール論理で、X of Y が true であることをどのように表現できますか? 次の 2 つのような規則 (A、B、C、D、E、F) は真でなければなりません。それは乗算または集合操作の形式ですか?
最終結果は、AB OR AC OR AD のようなすべての順列です。次の 3 つが ABC、ABD、ABE などのようなものだと言うと、(A,B,C)^2 のようになりますか?

ありがとう！

4

7 に答える 7

3

bool != int である C# またはその他の言語を想定すると、次のようになります。

bool nOf(int n, bool[] bs)
{
    foreach(bool b in bs)
    {
      if((n -= b ? 1 : 0) <= 0) break;
    }
    return n == 0;
}
于 2008-11-12T01:39:59.427 に答える
3

ブール論理 ( 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 になるようにすることもできます。

于 2008-11-12T01:34:21.137 に答える
3

パイソン:

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));
于 2008-11-12T02:27:56.180 に答える
2

あなたはそこにアイデアを持っています。「n 中の k が成立する」と表現するには、k が成立するすべてのケースを列挙する必要があります。したがって、変数 ABCDE があり、3/5 が必要な場合は、

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

& は "and" です。は「または」であり、〜は「ない」です。

于 2008-11-12T01:32:24.823 に答える
0

「正確に 2 つが真でなければならない」という意味と「少なくとも 2 つが真でなければならない」という意味では違いがあります。

変数 {A..F} のセットについて、Pax と Charlie Martin による応答は「正確に 2 つの」状況 (2 つが真で残りが偽) をカバーしていましたが、質問の式は「で」を扱っているように見えました。少なくとも 2 つのケース:

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

たとえば、A と B が true で、残りの変数が何でも (true または false) の場合に true となる式です。

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

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

表記法は次のように機能します。

#{...}

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

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

「 のセットx、ここでxはAから までのいずれかでありF、x真である」と表示されます。言い換えると、 から変数のセットが与えられたA場合F、真の値を持つ変数で構成されるサブセットには、ちょうど 2 つの要素があります。( <=「=」の代わりに使用して、質問の別の解釈を表現してください。)

于 2008-12-13T20:29:17.697 に答える
0

「A以上」前提

ツリーを構築することで、もう少しうまくいくことができます

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;
}
于 2008-11-12T01:33:25.447 に答える
0

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

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 (Half-Adder)]で、より多くの例とリンクを見つけることができます。

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

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

于 2008-11-14T21:14:40.827 に答える