So now that you know about Boolean formulas,
so what is the SAT problem?
The SAT problem has as an input a Boolean formula with N variables,
and I'm usually going to write them as X1, X2, and so on until you get to Xn,
and the output or question since SAT is a decision problem is the following:
And the question is, can you set the variables
X1 to Xn to a combination of true or false so
that the whole formula that you're given in the input becomes true?
And the answer to that can, of course, only be yes or no,
so again, SAT is a decision problem.
So for example, if we're given a very simple Boolean formula such X1 and X2,
and then the answer to SAT would be yes
because you could set X1 to true and X2 to true,
and then the whole formula would also evaluate to true
because you have 1 and 1,
which is true or 1.
Let's do a little bit more challenging example.
If you had a Boolean formula such as this,
x1 and X2 or 1 and not X1 or X2,
and what you can also see here is that
you do not always have to put brackets around each or to
signify in which order you evaluate the individual ones,
so it's okay to write 2 or 3 or 4 or's
or 2 or 3 or 4 and's
or even more if you want to
without doing those brackets.
It really doesn't make a difference in the way that the formula evaluates.
But let's come back to SAT.
So does this Boolean formula here have a satisfying assignment,
meaning can you set the variables to a combination of true and false
so that the whole formula becomes true, and here the answer is again yes.
X1, unfortunately, doesn't really help here.
So if you set X1 to true for example, this would also be true.
And here you have not X1, so X1 and not X1, that would evaluate to 0.
If you set X1 to 0, then you have it the other way around,
and then let's set X2 to 1 because then this whole thing here is 1,
this stays at 0 no matter what we do,
and this one also goes to 1,
and then you have 1 or 0 or 1 so there's at least one 1 in here,
and so the whole thing evaluates to 1,
and the formula can be satisfied.
So now let's see if you can figure out an even more challenging example yourself.
So here's our Boolean formula,
X1 or X3 and X1 and X2 or not X3,
and the formula continues here,
not X2 or not X3 and not X1 or not X2,
and I'm going reveal to you that this
formula indeed has an assignment of true and false
to the variables X1, X2, and X3
so that the whole formula is satisfied,
meaning it evaluates to true.
What I want to know from you is
how I have to set the variables to do this.
So if I should set X1 to false, please check here.
If I should set it to 2, please check here,
and the same thing for the variables X2 and X3, please.
