Linking Łukasiewicz Logic and Boolean Maximum Satisfiability
Sandro Márcio da Silva Preto, Felip Manyà, Marcelo Finger · 2023
We define a new reduction from the Boolean Maximum Satisfiability problem (MaxSAT) to the Satisfiability problem (SAT) of Łukasiewicz logic. This reduction is particularly interesting from a problem solving perspective because it shows how to encode cardinality constraints using Łukasiewicz logic. Moreover, we describe how to implement a MaxSAT solver using the proposed reduction.