SAT和3 SAT

【SAT问题】 将布尔可满足性问题(Boolean satisfiability problem)叫做SAT: 给定变量集 X=X=X={x1,x2,...,xn{x_1,x_2,...,x_n}x1​,x2​,...,xn​} 上的一组子句 C1,C2,...,CnC_1,C_2,...,C_nC1​,C2​,...,Cn​ ,问存在满足的真值赋值吗? 例如,设有3个子句:(x1∨x2 ̅),(x1 ̅∨x3 ̅),(x2∨x3 ̅)(x_1 \vee \overline {x_2} ),(\overline {x_1} \vee \overline {x_3} ),(x_2 \vee \overline {x_3} )(