1

For a boolean formule like a ⋁ b ⋁ c the truth table would look something like:

a   b   c   a ⋁ b ⋁ c
0   0   0   0
0   0   1   1
0   1   0   1
0   1   1   1
1   0   0   1
1   0   1   1
1   1   0   1
1   1   1   1

Now I am supposed to remove the redundant values. We see that the formule is always true if a is true despite of the other variables. The same goes for all other variables in this example.

The expected result would like like:

a   b   c   (a ⋁ b) ⋁ c
0   0   0   0
*   *   1   1
*   1   *   1
1   *   *   1

I thought of a solution, but I think it is way too inefficient:

for every variable v in formule f {

  substitute v for true in f as g

  if g is a tautology or a contradiction {
     remove all rows where v is true
     add a row where v is true and all other variables are redundant
  }

  substitute v for false in f as h

  if h is a tautology or a contradiction {
     remove all rows where v is false
     add a row where v is false and all other variables are redundant
  }
}

I'm not sure if it even works as it is supposed to do, since it will only check if all other variables except just one are redundant.

Question: Is there a better method to achieve this? If so, I would really appreciate a hint.

Tim
  • 211

0 Answers0