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$
  • 2
    $\begingroup$ A truth assignment assigns values to all variables. $\endgroup$ – Yuval Filmus Nov 24 '18 at 19:07
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, privacy policy and cookie policy

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