Question

(a) Show how to use (the Boolean formula satisfiability program) satisfiable num (and substitute) to find a satisfying assignment that minimizes the number of variables set to TRUE. Write the pseudo-code. HINT: eurtottesebtsumselbairavynamwohenimretedtsrif. HINT for hint: sdrawkcabtidaer. (b) How fast is your algorithm? Justify.

Answer 1

Check the explanation

Step-by-step explanation:

(a)

# We need to try all options(TRUE/FALSE) of all the Variables

# to find the correct arrangement.

permutations <- permutate(0,1,n) [Find all permutions O(2^n)]

for permutation in permutations:

for X in variables:

if(permutation[i] == 1)

substitute(H,X,true)

else

substitute(H,X,false)

if(satisfiable(H)) return permutation

increment i