patternMinor
In SAT, do we require an assignment for arbitrary variables?
Viewed 0 times
satarbitraryassignmentforrequirevariables
Problem
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 ?
$(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 ?
Solution
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.
Context
StackExchange Computer Science Q#100498, answer score: 9
Revisions (0)
No revisions yet.