Question

Describe a polynomial time algorithm to solve following problem

Input: A boolean function in CNF such that each clause has exactly three literals.

Output: An assignment of the variables such that each clause has all TRUE literals or all FALSE literals.

Answer 1

We define 3-CNF-SAT satisfiability using the following terms. A literal in a boolean formula is an occurrence of a variable or its negation. A boolean formula is in conjunctive normal form, or CNF, if it is expressed as conjunctions (by AND) of clauses, each of which is the disjunction (by OR) of one or more literals. A boolean formula is in 3-conjunctive normal form, or 3-CNF-SAT, if each clause has exactly three distinct literals. For example, the boolean formula (?1 ∨ ?2 ∨ ?̅3 ) ∧ (?̅1 ∨ ?̅2 ∨ ?3 ) ∧ (?1 ∨ ?̅2 ∨ ?3 ) is in 3-CNF-SAT. The first clause is (?1 ∨ ?2 ∨ ?̅3 ), which contains the three literals ?1, ?2, and ?̅3. In 3-CNF-SAT, we are asked whether a given boolean formula the φ in 3-CNF-SAT is satisfiable. The following theorem shows that a polynomial-time algorithm that can determine the satisfiability of boolean formulas is unlikely to exist, even when they are expressed in this simple normal form. satisfiability of boolean formulas in 3-conjunctive normal form is NP-complete[3]. 2.2 The truth table According to the Boolean Algebra for any 3-CNF formula like φ with n variables [ x1, x2, ..., xn ], the truth table can be formed from Table 1 in order to initialize the variables in the given formula using values in one of the rows in truth table(Table 1).

2.3 Assumption The literals of each clause are sorted based on the positional index in the list of variables. ∀??????? ???ℎ ?? (??∨??∨?? ) ? < ? < ? and ?? ∈ {?? , ?̅? }, ?? ∈ {?? , ?̅? }, ?? ∈ {??, ?̅?} 2.4 Presumption The value of each clause is assumed as false. ∀??????? ???ℎ ?? (??∨??∨?? ) ????? ((?? ∨ ?? ∨ ?? )) = ????? ?? ?? = ?????, ?? = ?????, ?? = ?????, ?? ∈ {?? , ?̅? }, ?? ∈ {?? , ?̅? }, ?? ∈ {??, ?̅?}. 2.5 The table of strings The table of strings is generated from the truth table, which holds the rows and columns of the same size. For each row of the truth table, there is only one equivalent row in the table of strings and vice versa; in fact, the table of strings is a conversion of the truth table(Table 2). Table 2.

ALGORITHM 1: The method to generating Table 2 based on Table 1

??? ? ← 1 ?? 2 ? ?? // n is the number of variables

??? ? ← 1 ?? ? ??

?? ????? 1[?][?] = ????? ????

????? 2[?][?] ← ′?? ′ ;

?? ????? 1[?][?] = ????

???? ????? 2[?][?] ← ′?̅? ′ ;

end

end

Definition 1. Each row in the table of strings contains a string.

LEMMA 1. All strings are unique.

PROOF. The Lemma is correct due to the truth table (Table 1).

3 For example for ? = (?̅1 ∨ ?̅2 ∨ ?̅3 ) ∧ (?̅2 ∨ ?̅3 ∨ ?4 ) ∧ (?̅2 ∨ ?̅3 ∨ ?̅4 ) ∧ (?1 ∨ ?̅2 ∨ ?5 ) ∧ (?̅2 ∨ ?3 ∨ ?̅5 ) ∧ (?̅1 ∨ ?̅2 ∨ ?̅6 ), truth table and string table of problem φ are in Fig. 1.

Definition 2. Clause_Set (w) is said to the set of all clauses resulted from the literals of one string such as w.

ALGORITHM 2: The method to generating Clause_Set(w) //Suppose that w is a string like "?1?2?3 … . ??−1??" and the length of w is equal ?. ??????_???(?) ← ????

??? ? ← 1 ?? ? − 2 ?? ??? ? ← ? + 1 ?? ? − 1 ??

??? ? ← ? + 1 ?? ? ?? ??????_???(?) ← ??????_???(?) ∪ (?? ∨ ?? ∨ ??)

end

end

end

end