用多项式来表示布尔逻辑
原文作者，Jeremy Kun，伊利诺伊大学数学博士，谷歌工程师。
翻译作者，donkeycn，哆嗒数学网翻译组成员。
校对，Math001。
关注微信：哆嗒数学网 每天获得更多数学趣文
新浪微博：http://weibo.com/duodaa
问题：用一些多项式来表示布尔逻辑表达式。即：若每个输入变量x取值为0（对应于假）或1（对应于真）。则一般地，对应的多项式的输出值应根据表达式的真假而分别为1或0。
解答：只需一个多项式。
举例说明：表达式┐[(a∨b)∧(┐c∨d)]，即：非((a或b)且(非c或d))。
诀窍是：碰到“且”就用乘法，碰到“非”就用1去减。于是，“a且b”就对应于“x1 x2”；“非z” 就对应于“1-z”。事实上，如果你有两个二值变量x、y，那么xy为1，当x、y都是1时；为0，当x、y有一个为0时。类似地，1-x为1，如果x为0；为0，如果x为1。
再结合德·摩根律就可以得到任意表达式了。a∨b=┐(┐a∧┐b)对应为1-(1-a)(1-b)。对于我们上面的例子：
f(a , b, c, d) = 1-(1-(1-a)(1-b))(1-c(1-d)).
展开，得：
1-a-b+ab+(1-d)(ac+bc-abc)
如果你代入a=1,b=0,c=1,d=0，你就可以得到原来的表达式的值为“真”（因为“非c或d”为“假”）。同样地，对应的多项式的运算结果为
1-1-0+0+(1-0)(1+0-0)=1.
你可以用下面的列表作为参考，来验证其余的工作：
0, 0, 0, 0 -> 1
0, 0, 0, 1 -> 1
0, 0, 1, 0 -> 1
0, 0, 1, 1 -> 1
0, 1, 0, 0 -> 0
0, 1, 0, 1 -> 0
0, 1, 1, 0 -> 1
0, 1, 1, 1 -> 0
1, 0, 0, 0 -> 0
1, 0, 0, 1 -> 0
1, 0, 1, 0 -> 1
1, 0, 1, 1 -> 0
1, 1, 0, 0 -> 0
1, 1, 0, 1 -> 0
1, 1, 1, 0 -> 1
1, 1, 1, 1 -> 0
讨论：这一技巧被广泛应用于计算机科学理论中，将布尔逻辑嵌入到多项式中。显然，之所以称之为“布尔代数”，是因为它的确是代数的一个子集。
此外，由于布尔可满足性问题：“用算法来确定布尔表达式是否可满足（选择一组变量的值使表达式的值为真）”是NP难(NP-hard)的，这可以用来表明与多元多项式有关的某些问题也是非常困难的。例如，求多元多项式的根（这里甚至可以假设你对代数几何一无所知）是很困难的，因为：即使你只是简单地考虑来自布尔表达式的那些多项式也将是NP难的。
这里有一个更有趣的例子，涉及到在现代机器学习中出现的优化问题。现在设想一下你要优化一个在一组二次等式约束下的多项式f(x)。这也是NP难的。而下面简单解释一下原因。
设φ是一个布尔表达式，f_φ是对应的多项式。首先，多项式中使用的每个变量xi可以通过约束x_i(x_i - 1)=0被限制为只能取0、1二个值。
你甚至可以证明：哪怕需优化的目标函数仅仅是二次的，它依然是一个NP难的问题。作为练习，可以将子集和的问题表示为使用类似选择作为约束条件的二次规划问题。据此，你甚至把子集和表示成具有线性约束的二次规划问题。
最后话说回来，这篇文章的重点很简单，多元多项式可以编码任意的布尔逻辑表达式。
关注微信：哆嗒数学网 每天获得更多数学趣文
新浪微博：http://weibo.com/duodaa
评论已关闭