![Author ORCID: We display the ORCID iD icon alongside authors names on our website to acknowledge that the ORCiD has been authenticated when entered by the user. To view the users ORCiD record click the icon. [opens in a new tab]](https://www.cambridge.org/engage/assets/public/coe/logo/orcid.png){kind=logo}
Abstract
This paper introduces a novel normal form, the Prime Normal Form, to decide the satisfiability of a 3CNF formula. The PNF of a formula contains its prime truth assignments. A 3CNF formula is satisfiable iff its PNF is reducible.
Incorporating Semantics into Syntax for Deciding Reducibility of 3CNF Formulas
15 September 2026, Version 2
Working Paper
Authors
This content is an early or alternative research output and has not been peer-reviewed by Cambridge University Press at the time of posting.
Comments
Comments are not moderated before they are posted, but they can be removed
by the site moderators if they are found to be in contravention of our
Commenting and Discussion Policy
[opens in a new tab]
- please read this policy before you post. Comments should be used for
scholarly discussion of the content in question. You can
find more information about how to use the commenting feature here
[opens in a new tab]
.
This site is protected by reCAPTCHA and the Google
Privacy Policy
[opens in a new tab]
and
Terms of Service
[opens in a new tab]
apply.
Version History
Sep 15, 2026 Version 2
Version Notes
I have completely re-written the abstract. The proof of the satisfiability/reducibility theorem is more rigorous in the revised paper. I have re-written the reducibility procedure. In general, the revised paper is better-written.
Metrics
284
123
0
Views
Downloads
Citations
Author’s competing interest statement
The author(s) have declared they have no conflict of interest with regard
to this content
Ethics
The author(s) have declared ethics committee/IRB approval is not relevant
to this content