SAT问题的定义设X=x为一个有限布尔变量集，文=(-。设是文的非空子集，定义vX"=V.x。对于给定的x"X,x."cx，要求判定是否存在某个对X中的每个变量赋值的方案，使得(VXI)A(VX,)A...A(VX.)=1。对于给定的(X，若x_X=k，则将该问题称为k-SAT问题。举个例子：(=1V=1V=1)(=0V=)=1
SAT问题的定义
K-SATk=2时存在确定性算法k>3时，考虑语句xxV.x增加k-3个变量yJ2Jr-3则原语句可转化为(VX Vy)A(-yiVxVy2)A(-VX, Vy)A...A(-y3 VX-I Vx)故k>2时均可以转化为3-SAT问题
k-SAT
3-SAT·完备性算法·非完备性算法一些拓展u
3-SAT • 完备性算法 • 非完备性算法 • 一些拓展
完备性算法·根本思想：回潮法·优化：(1)优先确定短的子句中包含的变量的值(2)优先确定在较多子句中出现的变量的值
完备性算法 • 根本思想:回溯法 • 优化: (1)优先确定短的子句中包含的变量的值 (2)优先确定在较多子句中出现的变量的值
问题模型的转化对于文的非空子集X，定义一X，使其满足以下条件：（1）-E-X当且仅当xEX(2）xEX当且仅当-x,EX定义A(-X)=Amx(VX)A(VX,)A... A(VX)=1(N(-XI))V(N(-X,))V...V(N(-X.)=0举个例子：(=1Vx=1Vx =1)A(xg=0Vx=1)=1(=0AX=0AX=0)V(=1AX4=0)= 0
问题模型的转化