Set Theory and Logic

Tautology Problem and Two Dimensional Formulas

Authors: Deniz Uyar
Comments: 39 Pages.

Finding whether a boolean formula is a tautology or not in a feasible time is an important problem of computer science. Many algorithms have been developed to solve this problem but none of them is a polynomial time algorithm. Our aim is to develop an algorithm that achieve this in polynomial time. In this article, we convert boolean functions to some graph forms in polynomial time. They are called two dimensional formulas and similar to AND-OR graphs except arches on them are bidirectional. Then these graphs are investigated to find properties which can be used to differentiate tautological formulas from non tautological ones.
Category: Set Theory and Logic