众所周知，SAT（可满足性）问题是由斯蒂芬-库克（Stephen Cook）在其 1971 年发表的题为 "The Complexity of Theorem-Proving Procedures »的论文中提出的，SAT 问题涉及判定合取范式公式的可满足性，合取范式公式由变量、逻辑运算符和子句组成。这些公式使用布尔代数的原理来表达。所以，SAT问题又与乔治-布尔（George Boole，1815—1864）相关。

布尔是 19 世纪的数学家和逻辑学家，是深度学习大家杰弗里·辛顿（Geoffrey Everest Hinton，1947—）的曾祖父。布尔33岁出版《逻辑的数学分析》，搭起逻辑与代数的桥梁；7年后出版的《思维的规则》提出了现在以他的名字命名的 布尔代数，这一代数系统使用代数符号将逻辑形式化，为表达和处理逻辑语句提供了数学框架，构成了理解和解决 SAT 问题的基础。

转载本文请联系原作者获取授权，同时请注明本文来自柳渝科学网博客。

链接地址：https://wap.sciencenet.cn/blog-2322490-1403521.html?mobile=1

收藏

分享