Booleschen Ausdruck [geschlossen

Question

Wie können Sie X von Y in Booleschen Logik ausdrücken? Eine Regel wie 2 der folgenden muss wahr sein (A, B, C, D, E, F) Ist es eine Form der Multiplkations- oder festgelegten Operationen?
Das Endergebnis ist alle Permutationen wie AB oder AC oder AD, wenn Sie gesagt haben, dass 3 von ABC, ABD, ABE usw. ist. Es ist also wie (a, b, c)^2?

Danke!

Answer 1

In Booleschen Logik (v ist oder, ' Das Prädikat folgt nicht):

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

Bei Permutationen müssen Sie viel Suberxpressionen schreiben.

Wenn dies eine Programmierfrage ist, können Sie natürlich die Booleschen auf 0 oder 1 umwandeln, sie alle hinzufügen und sicherstellen, dass das Ergebnis 2 ist.

Answer 2

Angenommen, C# oder eine andere Sprache, in der bool! = Int:

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

Answer 3

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));

Answer 4

Du hast die Idee dort. Um "k von n hält" auszudrücken, müssen Sie alle Fälle, für die K gilt, aufgezählt. Wenn wir also Variablen abcde haben und Sie 3 von 5 möchten, brauchen Sie

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

wo & ist "und", | ist "oder" und ~ ist "nicht".

Answer 5

Angenommen "a oder mehr"

Sie können ein bisschen besser abschneiden, indem Sie einen Baum bauen

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

oder als Code

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;
}

noch besser

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

Answer 6

Ich würde sie zählen. Wenn Sie jedoch nur ein Prädikat mit Booleschen Operationen erstellen müssen, können Sie die Eingaben als Bits in ein System von Addierern behandeln.

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;

Weitere Beispiele und Links finden Sie bei [Wikipedia] [http://en.wikipedia.org/wiki/half_adder (Halbadder)

Anschließend können Sie die sechs Variablen in 3 Paare gruppieren und dann herausfinden, wie Sie diese Ausgänge verwenden, um der Antwort näher zu kommen und den Rest selbst zu lösen.

Eine andere Option wäre die Verwendung einer Schaltung, um die Popzahl zu finden (seitlich hinzuzufügen) und zu prüfen, ob das einzige Bit für 2. berühmtes Beispiel in der Baugruppe NICHT LOGIC GATE ist [Hakmem 169] [http://home.pipeline.com/~hbaker1/hakmem/hacks.html#item169 (PopCount)].

Answer 7

Es macht einen Unterschied, ob Sie meinen "genau zwei müssen wahr sein" gegen "mindestens zwei müssen wahr sein".

Für den Satz von Variablen {a..f} deckten die Antworten von Pax und Charlie Martin die Situation "genau zwei" ab (zwei sind wahr und der Rest falsch), während der Ausdruck in Ihrer Frage mit dem "at" zu tun schien mindestens zwei "Fall:

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

ist ein Ausdruck, der wahr ist, wenn beispielsweise A und B wahr sind und die verbleibenden Variablen irgendetwas (wahr oder falsch) sind.

Wenn das, was Sie verlangen, ein set-theoryartiger Ausdruck ist beschreiben In den oben genannten Situationen können Sie es so ausdrücken:

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

wo die Notation auf diese Weise funktioniert:

#{...}

repräsentiert die Größe des geschlossenen Satzes und der Satz selbst:

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

liest "das Satz von x, wo x ist einer von A durch F, und x ist wahr ". Mit anderen Worten angesichts der Variablenmenge A durch F, Die Untergruppe der Variablen mit wahren Werten hat genau zwei Elemente. (Verwenden <= anstelle von '=' die andere Interpretation Ihrer Frage ausdrücken.)