Hi, from course algorithm. Question 34.4-5, I cant understand the conception of

Question

Hi, from course algorithm. Question 34.4-5, I cant understand the conception of the question clearly and also the answer which was given in the solution of the text book: question: show that the problem of determining the satisfiablity of boolean formulas in disjunctive normal form is polynomial-time solvable? I cant understand the conception of satisfiability very well, and also teh answer of the solution which is given. I would be glad if you explain first clearly the question and also teh conception of satisfibility for me before answering this question

Explanation / Answer

Proof. A boolean formula in disjunctive normal form(DNF) is composed of OR of clauses of
ANDs. It is satis able if any of its clause can be evaluated 1. If there is some variable x
such that one clause contains x ^ :x, the clause will evaluate 0 whatever boolean value x
is assigned; else there is some assignment of values 0 and 1 to its variable that causes it to
evaluate 1. Therefore the determining algorithm simply checks every clause and will return
false there is some variable x such that x and :x exist in the same clause. Else the algorithm
will return true.
Assume that there are m clauses and each clause has at most k literals. Therefore each
clause can be evaluated in O(k2) time and the whole algorithm runs in O(mk2). Hence the
problem of determining the satis ability of boolean formulas in disjunctive normal form is
polynomial-time solvable.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.