SAT and 3-SAT

【SAT Questions】
Call the Boolean satisfiability problem SAT:
Given a set of clauses C_1,C_2,…,C_n on the set of variables X={{x_1,x_2,…,x_n}}, is there a satisfactory truth value assignment?
For example, there are 3 clauses: (x_1 \vee \overline {x_2} ),(\overline {x_1} \vee \overline {x_3} ),(x_2 \vee \overline {x_3} ), then if you let If all variables are 1, then all clauses cannot be satisfied, because the value of the second clause is 0.
【3-SAT Question】
The 3-SAT problem is also called the ternary satisfiability problem. Because each clause contains exactly three items.
The 3-SAT problem can be described as:
Given the set of variables X={{x_1,x_2,…,x_n}} on a set of clauses C_1,C_2,…,C_n, the length of each clause is 3, Is there a true value assignment that satisfies?

0

Leave a Reply

Your email address will not be published.