AN ALGORITHM FOR SATISFIABILITY DEGREE COMPUTATION

Jian Luo, Guiming Luo, Mo Xia

2011

Abstract

Satisfiability degree describes the satisfiable extent of a proposition based on the truth table by finding out the proportion of interpretations that make the proposition true. This paper considers an algorithm for computing satisfiability degree. The proposed algorithm divides a large formula into two smaller formulas that can be further simplified by using unit clauses; once the smaller formulas contains only a clause or unit clauses, their satisfiability degrees can be directly computed. The satisfiability degree of the large formula is the difference of the two smaller ones. The correctness of the algorithm is proved and it has lower time complexity and space complexity than all the existing algorithms, such as the enumeration algorithm, the backtracking algorithm, the propositional matrix algorithm and so on. That conclusion is further verified by experimental results.

Download


Paper Citation


in Harvard Style

Luo J., Luo G. and Xia M. (2011). AN ALGORITHM FOR SATISFIABILITY DEGREE COMPUTATION . In Proceedings of the International Conference on Evolutionary Computation Theory and Applications - Volume 1: FCTA, (IJCCI 2011) ISBN 978-989-8425-83-6, pages 501-504. DOI: 10.5220/0003673205010504

in Bibtex Style

@conference{fcta11,
author={Jian Luo and Guiming Luo and Mo Xia},
title={AN ALGORITHM FOR SATISFIABILITY DEGREE COMPUTATION},
booktitle={Proceedings of the International Conference on Evolutionary Computation Theory and Applications - Volume 1: FCTA, (IJCCI 2011)},
year={2011},
pages={501-504},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003673205010504},
isbn={978-989-8425-83-6},
}


in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Evolutionary Computation Theory and Applications - Volume 1: FCTA, (IJCCI 2011)
TI - AN ALGORITHM FOR SATISFIABILITY DEGREE COMPUTATION
SN - 978-989-8425-83-6
AU - Luo J.
AU - Luo G.
AU - Xia M.
PY - 2011
SP - 501
EP - 504
DO - 10.5220/0003673205010504