Simplest algorithm for computing the resultant of a boolean expression?

  • Thread starter spikenigma
  • Start date
  • #1
spikenigma
61
0
hi,

let's take something simple, for example:

(a>b) && ((b>c) && c>d) || (d > c)

Intuitively, it's easy to work out given the values of a, b, c and d and just evaluating the brackets in order of precedence.

i.e.

Is b > c?? then is c > d
Then in addition to the above answer being true is a > b?
Then despite the earlier answer is d > c?
If true return true, if false return false.

But surely there is an elegant, simple algorithm for working this out computationally?

Could you for example take each expression, number them in terms of their evaluation step then evaluate in n steps based on [some factor] to get the answer?

i.e.

1) b>c, and then because of [factor], compute &&
2) c>d, and then because of [factor], compute &&
3) a>b, and then because of [factor], compute ||
4) d > c
5) answer

I know the factor is sign-right or sign-left of the expression and it could be used to create an algorithm.

But has anybody got anything more elegant?
 

Answers and Replies

  • #2
fresh_42
Mentor
Insights Author
2021 Award
17,607
18,183
The problem itself is NP complete, i.e. no algorithm is known, which decides in polynomial time whether a general Boolean expression is satisfiable or not, see https://en.wikipedia.org/wiki/Boolean_satisfiability_problem. This means in return, that given a certain example, we can probably use specific properties to be faster, but not in general.
 

Suggested for: Simplest algorithm for computing the resultant of a boolean expression?

Replies
8
Views
661
Replies
1
Views
404
  • Last Post
Replies
18
Views
951
  • Last Post
Replies
34
Views
2K
  • Last Post
Replies
3
Views
396
  • Last Post
Replies
8
Views
273
Replies
25
Views
1K
  • Last Post
Replies
3
Views
3K
Top