Name
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. |
Year | DOI | Venue |
|---|---|---|
2011 | null | ECTA 2011/FCTA 2011: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON EVOLUTIONARY COMPUTATION THEORY AND APPLICATIONS AND INTERNATIONAL CONFERENCE ON FUZZY COMPUTATION THEORY AND APPLICATIONS |
Keywords | Field | DocType |
Satisfiability degree,Propositional logic,Time complexity,Unit clause | Satisfiability,Theoretical computer science,Mathematics,Computation | Conference |
Volume | Issue | Citations |
null | null | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jian Luo | 1 | 5 | 2.83 |
| Guiming Luo | 2 | 69 | 28.79 |
| Mo Xia | 3 | 0 | 0.34 |