Hi Chris and others, Certainly there are betters ways to do that.
For this and similar problems in propositional logic, I would suggest to wrap a SAT solver. (see the article on wikipedia) http://en.wikipedia.org/wiki/SAT_solver##Algorithms_for_solving_SAT and the ticket #418 "Wrap minisat" http://sagetrac.org/sage_trac/ticket/418 (and my comment there) Then the problem "decide if a is equivalent to b" is equivalent to decide if "not (a if and oly if b)" is sasfacible. I think that this is better since (even though in general the SAT problem is know to be NP-hard) in practice a SAT solver is usually more efficient than checking one truth table against the other. [There are some real-world applications of SAT solvers. For example, one that I've found very impresive is the use of a SAT Solver to check the dependencies among packages in a Debian distribution to decide if a package can be installed, developed as part of the Edos Project See the paper by Dicosmo et al. http://gallium.inria.fr/~xleroy/publi/edos-frcss06.pdf You can see it in action at http://edos.debian.net/] best regards Pablo El Monday 14 July 2008 19:59:06 Chris Gorecki escribió: > Hi All, > > I'm currently trying to implement a function for the propositional > calculus package that would determine if two statements are logically > equivalent. The usage would be something along the lines of: > > sage: a = propcalc.formula('a | (b&c)') > sage: b = propcalc.formula('(x&y) | z') > sage: a.equivlant(b) > True > > One way to do this would be to examine the truth tables of each for > every possible mapping of the variable, but the run time would be > exponential plus some. Does anyone know of a better way to implement > this? > > Thank you. > > -Chris Gorecki --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
