HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

In SAT, do we require an assignment for arbitrary variables?

Submitted by: @import:stackexchange-cs··
0
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 ?

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.