多项式举例10个(本原多项式举例)

作者Jeremy Kun，伊利诺伊大学数学博士，谷歌工程师。

译者，donkeycn，多多数学网翻译组成员。

校对，Math001。

关注微信:多多数学网每天获取更多有趣的数学文章。

新浪:http://weibo.com/duodaa,微博

问题:用一些多项式表示布尔逻辑表达式。也就是说，如果每个输入变量x取值为0(对应于false)或1(对应于true)。一般情况下，对应多项式的输出值应根据表达式的真值分别为1或0。

答:只需要一个多项式。

例子:表达式┐[(a∨b)∧(┐c∨d)]，即not ((a或b) and (not 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 ->一个

0，0，0，1 ->一个

0，0，1，0 ->一个

0，0，1，1 ->一个

0，1，0，0 ->0

0，1，0，1 ->0

0，1，1，0 ->一个

0，1，1，1 ->0

1，0，0，0 ->0

1，0，0，1 ->0

1，0，1，0 ->一个

1，0，1，1 ->0

1，1，0，0 ->0

1，1，0，1 ->0

1，1，1，0 ->一个

1，1，1，1 ->0

讨论:该技术广泛应用于计算机科学理论中，将布尔逻辑嵌入到多项式中。显然，它被称为“布尔代数”，因为它确实是代数的子集。

此外，由于布尔可满足性问题:“确定一个布尔表达式能否被一个算法满足(选择一组变量使表达式的值为真)是NP-hard”，这可以用来说明与多元多项式相关的一些问题也是非常困难的。比如多元多项式的求根很难(这里甚至可以假设你对代数几何一无所知)是因为:即使单纯从布尔表达式考虑那些多项式，也会是NP难的。

还有一个更有趣的例子，涉及到现代机器学习中的优化问题。现在，假设您想要优化一个受一组二次方程约束的多项式f(x)。这也是NP难的。下面简单解释一下原因。

设φ为布尔表达式，f_φ为相应的多项式。首先，通过限制x_i(x_i-1)=0，可以将多项式中使用的每个变量xi限制为仅取0和1两个值。

你甚至可以证明，即使要优化的目标函数只是二次的，它仍然是一个NP难问题。作为练习，子集和的问题可以表示为一个二次规划问题，以相似的选择作为约束。据此，你甚至把子集的和表示成一个线性约束的二次规划问题。

最后，这篇文章的观点很简单。多元多项式可以编码任意布尔逻辑表达式。

关注微信:多多数学网每天获取更多有趣的数学文章。

新浪:http://weibo.com/duodaa,微博