COMING SOON! PQDT Open is getting a new home!

ProQuest Open Access Dissertations & Theses will remain freely available as part of a new and enhanced search experience at

Questions? Please refer to this FAQ.

Dissertation/Thesis Abstract

Boolean Satisfiability, Graph Problems, and Zeons
by Strotheide, Amanda, M.S., Southern Illinois University at Edwardsville, 2018, 30; 10844331
Abstract (Summary)

It has been previously shown that given a finite set of clauses a corresponding graph can be constructed to help determine if a SAT problem in CNF is satisfiable by looking for cliques in the associated graph. This paper uses a similar method to convert the SAT problem to a finite graph. Differing from the traditional approach, in this case, the vertex incidence representation on a given Clifford algebra can be utilized on complement graphs to find independent sets. This approach gives a concrete method to determine not only if a SAT problem is satisfiable, but also yields all satisfying truth assignments.

Indexing (document details)
Advisor: Staples, G. S.
Commitee: Loreaux, Jireh, Parish, James
School: Southern Illinois University at Edwardsville
Department: Math
School Location: United States -- Illinois
Source: MAI 58/03M(E), Masters Abstracts International
Subjects: Mathematics
Keywords: Boolean satisfiability, Graph theory, Zeons
Publication Number: 10844331
ISBN: 978-0-438-76908-3
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy