3
$\begingroup$

I am reading about the Satisfiability Problem, in page (5) the author gives the following example :

$(P \lor Q \lor R) \wedge (\bar{P} \lor Q \lor \bar{R}) \wedge (P \lor \bar{Q} \lor S) \wedge (\bar{P} \lor \bar{R} \lor \bar{S})$

A satisfying assignement is $: P,Q,\bar{R},\bar{S}$.

A different assignments is $P,\bar{R}$ to satisfy the four caluses. This means that $Q,S$ can be set arbitrarily to $True$ or $False$.

Do we require an assignment for all variables or we only reqiure to set variables that satisfy the input (i.e. $P,\bar{R}$ discluding $Q,S$) ?

Does that mean that the satisfying assignment of $P,\bar{R}$ is more efficient than $P,Q,\bar{R},\bar{S}$ given that it uses less variables ? Is there any resources to read about it ?

Also, given that $P,\bar{R}$ satisfy the input, does that mean that we can disclude $Q,S$ from the original Boolean Formula ?

$\endgroup$
1
  • 2
    $\begingroup$ A truth assignment assigns values to all variables. $\endgroup$ Nov 24, 2018 at 19:07

1 Answer 1

9
$\begingroup$

If the truth value of a formula is determined by setting only a subset of the variables, an author might skip describing the remaining truth values. However, by definition, a truth assignment gives a value to every variable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.