Maximal falsifiability

Alexey Ignatiev, Antonio Morgado, Jordi Planes, Joao Marques-Silva

Research output: Contribution to journalArticleResearchpeer-review

10 Citations (Scopus)


Similarly to Maximum Satisfiability (MaxSAT), Minimum Satisfiability (MinSAT) is an optimization extension of the Boolean Satisfiability (SAT) decision problem. In recent years, both problems have been studied in terms of exact and approximation algorithms. In addition, the MaxSAT problem has been characterized in terms of Maximal Satisfiable Subsets (MSSes) and Minimal Correction Subsets (MCSes), as well as Minimal Unsatisfiable Subsets (MUSes) and minimal hitting set dualization. However, and in contrast with MaxSAT, no such characterizations exist for MinSAT. This paper addresses this issue by casting the MinSAT problem in a more general framework. The paper studies Maximal Falsifiability, the problem of computing a subset-maximal set of clauses that can be simultaneously falsified, and shows that MinSAT corresponds to the complement of a largest subset-maximal set of simultaneously falsifiable clauses, i.e. the solution of the Maximum Falsifiability (MaxFalse) problem. Additional contributions of the paper include novel algorithms for Maximum and Maximal Falsifiability, as well as minimal hitting set dualization results for the MaxFalse problem. Moreover, the proposed algorithms are validated on practical instances.

Original languageEnglish
Pages (from-to)351-370
Number of pages20
JournalAI Communications
Issue number2
Publication statusPublished - 2016
Externally publishedYes


  • Boolean optimization
  • Maximum falsifiability
  • minimal hitting set duality
  • minimum satisfiability
  • Maximal Falsifiability: definitions, algorithms, and applications

    Ignatiev, A., Morgado, A., Planes, J. & Marques-Silva, J., 2013, Logic for Programming, Artificial Intelligence, and Reasoning - 19th International Conference, LPAR 2013, Proceedings. Springer, Vol. 8312. p. 439-456 18 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8312 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference PaperOtherpeer-review

    11 Citations (Scopus)

Cite this