CODEWITHSUNDEEP
javaboolean-expression
user140161
user140161

Reputation: 125

How to think when solving boolean expressions?

I have the following question:

Let a and b be boolean variables. Is it possible to set values for a and b to have the following expression evaluate as false? b or (((not a) or (not a)) or (a or (not b)))

What would be the best way to go about this? I know that working out all four possibilities on a piece of paper would give me the answer but is there in an effective strategy to deal with this kind of problem?

Upvotes: 1

Views: 132

Answers (3)

GhostCat
GhostCat

Reputation: 140457

An answer to the second part: in the real world you would be using a so call SAT solver (for satisfiability). Meaning: you can simplify small equations manually, but in the real world, you might have equations with millions of variables - and then you turn to SAT solvers.

Diving in how such tools work is an excellent entry point to fundamental topics of computer science. See resp. listen to this podcast for example. It discusses the differences between P and NP - and then spents a lot of time explaining why we are able to solve large SAT problems (which are in NP) efficiently nowadays.

Upvotes: 1

Naxos84
Naxos84

Reputation: 2038

You could write a small program or unit test.

  @Test
  public void testSomeThing() {
    System.out.println(check(true, true));
    System.out.println(check(true, false));
    System.out.println(check(false, true));
    System.out.println(check(false, false));

  }

  private boolean check(final boolean a, final boolean b) {
    return b || (((!a) || (!a)) || (a || (!b)));
  }

I preserved the brackets even though some of them could be removed.

The result is:

true
true
true
true


So the answer to your question :

Is it possible to set values for a and b to have the following expression evaluate as false?

is "No you can't".

Upvotes: 1

Sweeper
Sweeper

Reputation: 271660

We can get the answer by deduction.

b or (((not a) or (not a)) or (a or (not b)))

As we can see here, b must be false for the whole expression to be false, because it is an operand of the OR operator:

b or ...

However, on the right side, if b is false, then not b would be true, making this:

(a or (not b))

true.

Now our expression has become:

false or (((not a) or (not a)) or true)

As you can see pretty clearly here, the right side must evaluate to true ad the whole thing evaluates to true. Therefore, the answer is no.

Upvotes: 2

Related Questions