How to write the following boolean expression?

Question

I've got three boolean values A, B and C. I need to write an IF statement which will execute if and only if no more than one of these values is True. In other words, here is the truth table:

 A | B | C | Result
---+---+---+--------
 0 | 0 | 0 |   1
 0 | 0 | 1 |   1
 0 | 1 | 0 |   1
 0 | 1 | 1 |   0
 1 | 0 | 0 |   1
 1 | 0 | 1 |   0
 1 | 1 | 0 |   0
 1 | 1 | 1 |   0

What is the best way to write this? I know I can enumerate all possibilities, but that seems... too verbose. :P

Added: Just had one idea:

!(A && B) && !(B && C) && !(A && C)

This checks that no two values are set. The suggestion about sums is OK as well. Even more readable maybe...

(A?1:0) + (B?1:0) + (C?1:0) <= 1

P.S. This is for production code, so I'm going more for code readability than performance.

Added 2: Already accepted answer, but for the curious ones - it's C#. :) The question is pretty much language-agnostic though.

Answer 1

how about treating them as integer 1's and 0's, and checking that their sum equals 1?

EDIT:

now that we know that it's c#.net, i think the most readable solution would look somewhat like

public static class Extensions
{
    public static int ToInt(this bool b)
    {
        return b ? 1 : 0;
    }
}

the above tucked away in a class library (appcode?) where we don't have to see it, yet can easily access it (ctrl+click in r#, for instance) and then the implementation will simply be:

public bool noMoreThanOne(params bool[] bools) 
{ 
    return bools.ToList().Sum(b => b.ToInt()) <= 1; 
}

...

bool check = noMoreThanOne(true, true, false, any, amount, of, bools);

Answer 2

(A XOR B XOR C) OR NOT (A OR B OR C)

Edit: As pointed out by Vilx, this isn't right.

If A and B are both 1, and C is 0, A XOR B will be 0, the overall result will be 0.

How about: NOT (A AND B) AND NOT (A AND C) AND NOT (B AND C)

Answer 3

You shold familiarize yourself with Karnaugh maps. Concept is most often applied to electronics but is very useful here too. It's very easy (thought Wikipedia explanation does look long -- it's thorough).

Answer 4

Good ol' logic:

+ = OR
. = AND

R = Abar.Bbar.Cbar + Abar.Bbar.C + Abar.B.Cbar + A.Bbar.Cbar
  = Abar.Bbar.(Cbar + C) + Abar.B.Cbar + A.Bbar.Cbar
  = Abar.Bbar + Abar.B.Cbar + A.Bbar.Cbar
  = Abar.Bbar + CBar(A XOR B)
  = NOT(A OR B) OR (NOT C AND (A XOR B))

Take the hint and simplify further if you want.

And yeah, get your self familiar with Karnaugh Maps

Answer 5

A general way of finding a minimal boolean expression for a given truth table is to use a Karnaugh map:

http://babbage.cs.qc.edu/courses/Minimize/

There are several online minimizers on the web. The one here (linked to from the article, it's in German, though) finds the following expression:

(!A && !B) || (!A && !C) || (!B && !C)

If you're going for code readability, though, I would probably go with the idea of "sum<=1". Take care that not all languages guarantee that false==0 and true==1 -- but you're probably aware of this since you've taken care of it in your own solution.

Answer 6

Depends whether you want something where it's easy to understand what you're trying to do, or something that's as logically simple as can be. Other people are posting logically simple answers, so here's one where it's more clear what's going on (and what the outcome will be for different inputs):

  def only1st(a, b, c):
    return a and not b and not c

  if only1st(a, b, c) or only1st(b, a, c) or only1st(c, a, b):
    print "Yes"
  else:
    print "No"

Answer 7

If you turn the logic around, you want the condition to be false if you have any pair of booleans that are both true:

if (! ((a && b) || (a && c) || (b && c))) { ... }

For something completely different, you can put the booleans in an array and count how many true values there are:

if ((new bool[] { a, b, c }).Where(x => x).Count() <= 1) { ... }

Answer 8

I'd go for maximum maintainability and readability.

static bool ZeroOrOneAreTrue(params bool[] bools)
{
    return NumThatAreTrue(bools) <= 1;
}

static int NumThatAreTrue(params bool[] bools)
{
    return bools.Where(b => b).Count();
}

Answer 9

I like the addition solution, but here's a hack to do that with bit fields as well.

inline bool OnlyOneBitSet(int x)
{
    // removes the leftmost bit, if zero, there was only one set.
    return x & (x-1) == 0;
}

// macro for int conversion
#define BOOLASINT(x) ((x)?1:0)

// turn bools a, b, c into the bit field cba
int i = (BOOLASINT(a) << 0) | BOOLASINT(b) << 1 | BOOLASINT(c) << 2;

if (OnlyOneBitSet(i)) { /* tada */ }

Answer 10

Code demonstration of d's solution:

int total=0;
if (A) total++;
if (B) total++;
if (C) total++;

if (total<=1) // iff no more than one is true.
{
    // execute

}