Date of Award

Spring 5-2011

Degree Type

Masters Thesis

Degree Name

Master of Science (MS)

Department

Computing

Committee Chair

Louise Perkins

Committee Chair Department

Computing

Abstract

We present two implementation enhancements for the Boolean satisfiability problem and one visualization technique. The first is an expansion to a tri-nary logic system with a commit phase. The three states are (1) true, (2) false, and (3) don't care. We abstracted the operations of AND and OR to this hyperlogic system in a novel way. The commit phase works on one variable at a time and transitions values from temporary to permanent whenever possible. We viewed tri-state logic as a hyperspace above the binary (Boolean) logic. The second improvement is algorithmic. We modified the semantics of the classic 3 Conjunctive Normal Form Problem in order to develop a polynomial time algorithm for a simplified normal form - avoiding the need to examine all combinatoric limitations. In particular, we abandoned 3 CNF and used an unstructured left to right associativity. We do not claim that this new semantic is comprehensive. We do claim that it is simpler. Lastly, we introduced a node analogy to help us understand the algorithm itself.

Download

Share

COinS