CODEWITHSUNDEEP
algorithmbooleanboolean-expression
Naruto
Naruto

Reputation: 53

Evaluate whether an expression is tautology or not

I am looking for an algorithm to find whether an expression is a tautology or not ? I tried using truth table (brute force) but this is not feasible in my case.

Upvotes: 0

Views: 675

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65468

A formula is a tautology if and only if its negation is satisfiable. Satisfiability is an NP-hard problem, but there are many solvers that do better than brute force.

Upvotes: 1

Related Questions