How to check all possibilities of boolean expressions?

Question

I am currently trying to figure out how to check all the possibilities of the boolean expressions !b && (c || !d) and !(b || !c && d there are eight possible assignments to the booleans b c and d I need to figure out which combination results in (!b && (c || !d)) != (!(b || !c && d) The current code I have is:

public static void Main(String[] args)
{
    java.util.Random randy = new java.util.Random();
    boolean expression1 = false;
    boolean expression2 = false;
    boolean[] b = {true, false};
    boolean[] c = {true, false};
    boolean[] d = {true, false};
    int B = 0;
    int C = 0;
    int D = 0;

    while(expression1 == expression2)
    {
        B = randy.nextInt(2);
        C = randy.nextInt(2);
        D = randy.nextInt(2);
        expression1 = !b[B] && (c[C] || !d[D]);
        expression2 = !(b[B] || !c[C] && d[D]);
    }

    if(expression1 != expression2)
    {
        JOptionPane.showMessageDialog(null, "b: " + b + "c: " + c + "d: " + d);
    }
}

However it does not seem to do the trick. So my question is how can I figured out all of the possibilities of the boolean expressions and then compare them to each other to see whether they are not equal to each other.

Answer 1

Both expressions are the same, so they will always be equal to each other. Let's do some transformations to the second expression:

!(b || !c && d)   # original expression
!(b || (!c && d)) # && has precedence over ||
!b && !(!c && d)  # negate the whole expression
!b && (c || !d)   # negate the right most expression

We've just got the same expression as the first one so (!b && (c || !d)) != (!(b || !c && d)) will always evaluate to false.

Answer 2

There's only eight possibilities, so it's not too hard to just enumerate them all. Something a bit like this (not remotely tested):

static boolean toBoolean(int n) {
    if(n==0) {return false; }
    return true;
}
...
for(int b_int=0; b_int<2; b_int++) {
    for(int c_int=0; c_int<2; c_int++) {
        for(int d_int=0; d_int<2; d_int++) {
            boolean b = toBoolean(b_int);
            boolean c = toBoolean(c_int);
            boolean d = toBoolean(d_int);
            boolean expr1 = whatever;
            boolean expr2 = whatever else;
            if(expr1 != expr2) {
                // Eureka! signal success
            }
         }
     }
}

As long as you're brute-forcing a problem, think about enumeration rather than random testing, especially if the problem has a small space of possibilities. That said, you might try using de Morgan's laws on your expressions. If I did it right myself, you'll find something interesting.

Answer 3

The problem with your current approach is that you're using randomization to get all the combinations of the variables you have, but that is not assuring you'll get them all.

The other problem seems to be in the logic of your code snippet: if at any point expression1 != expression2 you'll be out of the while-loop and the if-statement will be true, it will print the message dialog and then the program will exit. Since you're using randoms you'll get either the same values each time o different ones, but you will always get ONE possibility.

One approach would be creating a truth table which has all the combinations of truth of the variables involved and test your expression each time. For example:

private static void compareExpressions() {
    final int NUMBER_OF_VARIABLES = 3;
    final int NUMBER_OF_ROWS = (int) Math.pow(2, NUMBER_OF_VARIABLES);

    boolean values[] = new boolean[NUMBER_OF_VARIABLES];
    boolean expression1, expression2;

    // Build a truth table

    for(int i = 0; i < NUMBER_OF_ROWS; i++) {
        for(int j = NUMBER_OF_VARIABLES - 1, k = 0; j >= 0; j--, k++) {
            values[k] = (i / (int) Math.pow(2, j)) % 2 == 0 ? false : true;
        }

        // Compare what you need and show results for each row in the truth table
        expression1 = !values[0] && (values[1] || !values[2]);
        expression2 = !(values[0] || !values[1] && values[2]);

        if(expression1 != expression2) {
            System.out.println("b: " + values[0] + " c: " + values[1] + " d: " + values[2]);
        }
    }   
}

You can create truth tables as big as you want with this approach but it will get tedious and more error prone as the number of variables increases because of the "unnamed" variables in the values[] array or if you have different expressions.

Unfortunately solving that would require a parser for the expressions and a better way to store the variables (say, for example, a Map<String, Boolean>).

Answer 4

You could check all the possible combinations using nested loops.

for(int i=0;i<2;i++){
    for(int j=0;j<2;j++){
        for(int k=0;k<2;k++){
            //Check b[i] c[j] d[k] for your condition and handle accordingly
        }
    }
}