Boolean Expression

Question

How can you express X of Y are true, in boolean logic? a rule like 2 of the following must be true (A, B, C, D, E, F) is it a form of multiplcation or set operations?
the end result is all the permutations like AB OR AC OR AD, if you said 3 of following it is like ABC, ABD, ABE, etc.. so it is like (A,B,C)^2?

thanks!

Answer 1

You've got the idea there. To express "k of n holds" you're going to need to enumerate all cases for which k holds. So, if we have variables A B C D E, and you want 3 of 5, you'll need

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

where & is "and", | is "or" and ~ is "not".

Answer 2

Assuming "A or more"

you can do a bit better by building a tree

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

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

better yet

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

Answer 3

In boolean logic (v is OR, ' following the predicate is 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

With permutations, there's a great many subexpressions you need to write.

Of course, if this is a programming question, you could just convert the booleans to 0 or 1, add them all up and ensure the result is 2.

Answer 4

Assuming C# or some other language where bool != int:

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

Answer 5

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 6

I would count them. However if you must produce a predicate using boolean operations only then you could treat the inputs as bits into a system of adders.

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;

You can find more examples and links at [Wikipedia][http://en.wikipedia.org/wiki/Half_adder (Half-Adder)]

Then you can group up the six variables into 3 pairs, then figure out how to use those outputs to get closer to the answer and solve the rest yourself.

Another option would be to use a circuit to find pop count (sideways add) and check to see if the only bit matches for 2. Famous example in assembly not logic gates is [Hakmem 169][http://home.pipeline.com/~hbaker1/hakmem/hacks.html#item169 (popcount)].

Answer 7

It makes a difference whether you mean "exactly two must be true" versus "at least two must be true".

For the set of variables {A..F}, the responses by Pax and Charlie Martin covered the "exactly two" situation (two are true and the rest are false), while the expression in your question seemed to deal with the "at least two" case:

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

is an expression that is true when, for example, A and B are true and the remaining variables are anything (true or false).

If what you're asking for is a set-theory-like expression to describe the situation(s) above, you might express it something like this:

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

where the notation works this way:

#{...}

represents the size of the enclosed set, and the set itself:

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

reads "the set of x, where x is one of A through F, and x is true". In other words given the set of variables A through F, the subset made up of the variables with true values has exactly two elements. (Use <= instead of '=' to express the other interpretation of your question.)