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.