How does 3-sat work in laymen's terms?

Question

I know only basic math like so: (+,-,x,\,). And I studied a little bit of programming up to the point of knowing a little bit about Boolean values.I desperately want to understand the 3-sat question fully so I can solve it, but no one ever gives examples I can understand. Please give me a few example problems with full explanations on what they want, then give one example question that If solved will also solve 3-sat. I know they want someone to assign values to variables in a certain way to where the expression is always true,but I can't wrap my head around what that actually means? Other people have asked the same question as me and got a complicated explanation. Please explain to me as simple as possible how does 3-sat work? I know there was an example once that went something like this: A or B , C and D but not A. so the answer is obviously B ,C and D. They are asking about puting values in variables in a way were the expression always evaluates true, but I can't comprehend that concept to even try and solve. Please help. I've seen this example before x1∧x2∨x3 and I did a little research and I keep getting this symbol ^ with an explanation that says A and B are true if A and B are true. I get the logic of that statement but U don't get how those symbols make since in an example. Please clarify so that I can finally be able to try and solve it.I don't know much about c++ so please be sure to give an example problem fully explaining how it works. Thanks please don't tell that I shouldn't study this problem just because I don't know a lot of math. I'm sure I don't need to be a math or computer expert to figure out the basics and understanding of this problem so I can TRY and solve it.

Answer 1

THE SHORT VERSION

3-SAT is basically a bunch of questions separated into groups of threes. If at least one in each group is true, we say it is satisfiable. If not, we say it's unsatisfiable.

---

THE LONG VERSION

AN EXAMPLE

For example, we can think of things in the kitchen. We can look at 4 things; an oven, a microwave, a toaster, and a refrigerator. Now we take groups of three of them. For example, we can take the oven, the microwave, and the toaster as one group. We can take the oven, the toaster, and the refrigerator as another group.

Now, we can ask if one in each group is on? Returning to our example, we ask

(is the oven on?) OR (is the microwave on?) OR (is the toaster on?)

...and for the other group

(is the oven on?) OR (is the toaster on?) OR (is the refrigerator on?)

That's how we get groups of 3 for 3-SAT. We combine them together to ask:

((is the oven on?) OR (is the microwave on?) OR (is the toaster on?))

AND

((is the oven on?) OR (is the toaster on?) OR (is the refrigerator on?))

That's the essence of 3-SAT. We use variables to represent the questions. So, for example, we could say that

$O$ means Is the oven on?

$M$ means Is the microwave on?

$T$ means Is the toaster on?

$R$ means Is the refrigerator on?

Then our example can be phrased like an equation:

((is the oven on?) OR (is the microwave on?) OR (is the toaster on?)) becomes ($O$ OR $M$ OR $T$)

((is the oven on?) OR (is the toaster on?) OR (is the refrigerator on?)) becomes ($O$ OR $T$ OR $R$)

COMBINING THINGS

So putting everything together, we have:

($O$ OR $M$ OR $T$) AND ($O$ OR $T$ OR $R$)

That's how we get the equation form of 3-SAT.

THE COMPLETE PROBLEM

There's one more thing we can do. We can ask the opposite. So instead of asking, "is the oven on?", we can ask "is the oven off?". We call "Is the oven on?" $O$, and we call "Is the oven off?" NOT $O$. So now we can say NOT $O$, NOT $M$, NOT $T$, NOT $R$ if we want.

Here's a sample equation of this:

($O$ OR $M$ OR (NOT $T$)) AND ($O$ OR (NOT $T$) OR $R$)

This is:

((is the oven on?) OR (is the microwave on?) OR (is the toaster OFF?)) becomes

($O$ OR $M$ OR (NOT $T$))

AND

((is the oven on?) OR (is the toaster OFF?) OR (is the refrigerator on?)) becomes

($O$ OR (NOT $T$) OR $R$)

That's the gist of it. It's really just making sure that at least one thing in each group of three is true. In other words, one thing in each group has a yes answer. If this is true, then we say the whole thing is true, or SATISFIABLE. If not, then we say the whole thing is false, or UNSATISFIABLE.