4 Replies Latest reply on Apr 5, 2008 8:21 PM by 807591

    Negating boolean expressions

    807591
      I need a method that takes a simple boolean expression as the input and returns an arraylist containing possible negations of the input. The input can contain relational operators ( ==, !=, <, >, <=, and >=) and boolean operators (&& and ||).

      For "b+amt<0", it would return ["b+amt>=0"].

      The most complex input I would need to evaluate and negate would be something like "b-amt<0&&b-amt>-1000". For this, it would return (not entirely sure about this) ["b-amt>=0&&b-amt>-1000","b-amt<0&&b-amt<=-1000","b-amt>=0&&b-amt<=-1000"].

      Any thoughts on how to go about doing this?
        • 1. Re: Negating boolean expressions
          807591
          Currenty my negate function just returns "!("+input+")", but that's too crude. I need something better.
          • 2. Re: Negating boolean expressions
            807591
            My original post didn't format as I intended, so here it is again:

            I need a method that takes a simple boolean expression as the input and returns an arraylist containing possible negations of the input. The input can contain relational operators ( ==, !=, <, >, <=, and >=) and boolean operators (&& and ||).

            For "b+amt<0", it would return
            ["b+amt>=0"]
            .

            The most complex input I would need to evaluate and negate would be something like "b-amt<0&&b-amt>-1000". For this, it would return (not entirely sure about this)
            ["b-amt>=0&&b-amt>-1000","b-amt<0&&b-amt<=-1000","b-amt>=0&&b-amt<=-1000"]
            .

            Currenty my negate function just returns
            "!("+input+")"
            , but that's too crude. I need something better.

            Any thoughts on how to go about doing this?
            • 3. Re: Negating boolean expressions
              807591
              Using the logical negation operator isn't really crude. So I'm assuming that you need to do something else because your homework assignment requires it.

              You already know how to negate relational operators. That's a pretty straightforward mapping. How about just applying those mappings to relational operators, and DeMorgan's Rule for logical operators?

              After that you could perhaps try doing arithmetic simplification with relational operators (e.g., "!(a < 5)" => "a >= 5" => "a > 4" for integers).
              • 4. Re: Negating boolean expressions
                807591
                Thanks for the tip, paulcw.

                Still welcoming other suggestions.