Tri-State Boolean Satisfiability with Commit: An Efficient Partial Solution Using Hyperlogic

<p>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.</p>

Name thesis:degree_name

Master of Science (MS)

Level thesis:degree_level

Masters Thesis

Discipline thesis:degree_discipline

Computing

Year dc:date.available

2011

Author dc:creator

• Byrd, Kevin Michael

Contributors dc:contributor

• Louise Perkins

Repository record dc:identifier

https://aquila.usm.edu/masters_theses/421

OAI identifier oai:identifier

oai:aquila.usm.edu:masters_theses-1499