Question

10 points (bonus) A propositional formula on n variables, P(ri,2,... ,Tn) is satisfiable if there exists an assignment of truth values (true or false) to its variables such that it evaluates to true. (a) Give an algorithm (pseudocode) that, given a formula P determines if it is satisfiable or not. Analyze your algorithm. b) Suppose that we are given a free" algorithm A that, given P and a partial assignment of truth values (that is, some variables are set to T, others to F, others remain variables) outputs true if the formula is still satisfiable and false if it is not. Further suppose that the cost of this algorithm is constant. Give an algorithm that, given a formula determines if it is satisfiable or not and returns a satisfying assignment. Make use of A as a subroutine and analyze your algorithm

Answer 1

Answer:-

Given :-

“ n variables” formula p(X1,X2.......Xn)

(a)

Pseudocode:-

Function bool CheckIfSatisfy(std::vector<int> v,int numberOfVariable):

. check using the array values as variable input to the function and check if it evalutes to true

. return true if it evalutes to true.

Function void RecursiveCheck(vector<int> v,int numberOfVariable):

. if sizeof(v)==numberOfVariable:

.if CheckIfSatisfy(v,numberOfVariable) == true:

. insert v into solution

.pop last value from vector

.return v

. else:

.push back true in v

.v=RecursiveCheck(v,numberOfVariable)

.push back false in v

.v=RecursiveCheck(v,numberOfVariable)

.return v

(b)

given free algorithm A,

P and a partial assignment of truth values,

if the output is truth then prove that the formula is still satisfiable are not.

code:-

Function int[] CheckIfSatisfy(int numberOfVariable):

. declare int[]solution(size=numberOfVariable)

. for int i=0 to numberOfVariable-1:

.assign i th variable to true, use all previous assignments (i.e 0 to i-1) along with this to pass as partial assignment in A

. if A returns true

. solution[i] = true

. else

. solution[i] = false

return solution

==>> the system shows the numbers of times of loops = no.of vaiables , so that the

no.of complexity is O(constant*numberOfVariable)~ O(numberOfVariable).