概念：-在3CNF SAT中, 你至少有3个子句, 而在子句中, 你将有几乎3个文字或常量
如（X + Y + Z）（X + Y + Z）（X + Y + Z）你可以定义为（XvYvZ）?（XvYvZ）?（XvYvZ）V = OR运算符^ = AND运算符
以下所有这些点都需要在3CNF SAT中加以考虑。
证明： –
- 3CNF SAT的概念
- SAT≤ρ3CNF SAT
- 3CNF≤ρSAT
- 3CNF ? NPC
- 概念：-在3CNF SAT中, 你至少有3个子句, 在3个子句中, 你将有几乎3个文字或常量。
- SAT≤ρ3CNF SAT：-首先, 你需要在多项式时间内F = X + YZ =（X + Y）（X + Z）=（ X + Y + ZZ’ ）（X + YY’ + Z）=（X + Y + Z）（X + Y + Z’ ）（X + Y + Z）（X + Y’ + Z）=（X + Y + Z）（X + Y + Z’ ）（X + Y’ + Z）
- 3CNF≤pSAT：-从具有三个文字的布尔函数中, 我们可以将整个函数简化为较短的一个。 F =（X + Y + Z）（X + Y + Z’ ）（X + Y’ + Z）=（X + Y + Z）（X + Y + Z’ ）（X + Y + Z）（X + Y’ + Z）=（X + Y + ZZ’ ）（X + YY’ + Z）=（X + Y）（X + Z）= X + YZ
- 3CNF ? NPC：-众所周知, 你可以通过SAT获得3CNF, 并且可以通过来自NP的CIRCUIT SAT获得SAT。
- 它表明你可以轻松地将SAT的布尔函数转换为3CNF SAT, 并且还可以在多项式时间内通过归约概念满足3CNF SAT的概念。
- 如果要验证3CNF SAT中的输出, 请执行精简并将其转换为SAT和CIRCUIT来检查输出
