Question

The maximum satisfiability problem asks for an assignment of truth values to the variables in a compound proposition in conjunctive normal form (which expresses a compound proposition as the conjunction of clauses where each clause is the disjunction of two or more variables or their negations) that makes as many of these clauses true as possible. For example, three but not four of the clauses in (p V q)Λ(p V ~q)Λ(~p V r)Λ(~p V ~r) can be made true by an assignment of truth values to p, q, and r. we will show that probabilistic methods can provide a lower bound for the number of clauses that can be made true by an assignment of truth values to the variables.

a) Suppose that there are n variables in a compound proposition in conjunctive normal form. If we pick a truth value for each variable randomly by flipping a coin and assigning true to the variable if the coin comes up heads and false if it
comes up tails, what is the probability of each possible assignment of truth values to the n variables?
(b) Assuming that each clause is the disjunction of exactly two distinct variables or their negations, what is the probability that a given clause is true, given the random assignment of truth values from part (a)?

Answer 1

a. 1/(2^n)

b. ¾

Step-by-step explanation:

a. Given that there are n variables in a compound proposition.

Each of the n variables have exactly two possible equally likely truth values that can be assigned.

The values are true or false.

And the value can only be either true or false at any given time

True(1) + False (1) = 2 truth values

So, the probability of each possible assignment of truth values to the n variables is 1/(2^n)

b. Given that a clause is in disjunctive form of exactly two distinct variables

n = 2 distinct variables; n = 2

1/(2^n) becomes

1/2²

= ¼

This means that there's exactly 1 combination out of possible 2² that will lead to the clause being false.

The probability that a given clause is true, given the random assignment of truth values from part (a) is calculated as 1 - ¼

= ¾