Chapter 2, Problem 13E

Program Plan Intro

Satisfiability Problem:

The problem to determine if there exists an interpretation that would satify a given boolean formula is known a satisfiability problem.

• In a given Boolean formula it is asked whether it’s variables could be replaced by values “TRUE” or “FALSE” such that formula evaluates to “TRUE”.
• In such a case, the boolean formula is called satisfiable.
• Otherwise, if there is no such assignment possible and the function becomes “FALSE” for all variable assignments possible, then the formula is unsatisfiable.

3-Satisfiablity:

The satisfiability of a formula stated in a conjunctive normal (CNF) form is been determined where each clause is been limited to atmost three literals, such a problem is termed as 3-satisfiability problem.

Explanation of Solution

Boolean expression with one variables:

Consider an instance when an alternative in a Boolean expression has two variables.

$A=q_1$

Convert the above satisfiablity problem into 3-satisfiability problem by generating the below expression. Transform each clause into a conjunction of “n-2” clauses, where “n” denotes the total count of literals in all clauses.

$A\text{'}=\left(q_1\vee x\vee y\right)(\left(q_1\vee \neg x\vee y\right)\wedge ($