找回密码
 欢迎注册
查看: 1689|回复: 5

[分享] 数学家最新重大突破:发现了第九个戴德金数

[复制链接]
发表于 2023-7-11 15:41:42 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
“含有n个变量的单调布尔函数有多少种?”

数学家们把这个问题的答案称为“第n个戴德金数”

前9个戴德金数如下图所示:

1.png

其中,第8个戴德金数,是在1991年使用当时最强大的超级计算机Cray 2算出来的

而最新的第9个戴德金数,是在可编程门阵列(Field Programmable Gate Arrays,FPGA)的硬件上,经过几年的时间开发软件(程序),然后在超级计算机上运行了大约5个月,最终在2023年3月8日算出来的

新闻链接:
https://www.huxiu.com/article/1732768.html
https://baijiahao.baidu.com/s?id=1769861253645924163

OEIS链接:
https://oeis.org/A000372
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-7-11 16:08:41 | 显示全部楼层
第一次听说戴德金数,不知道能干嘛
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-7-11 20:01:11 | 显示全部楼层
我也不知道能干什么,继续查阅了一些资料,发现:

新闻里的“戴德金数”是“含有n个变量的单调布尔函数有多少种”

百度百科上面的“戴德金数”是“数论中的一种著名函数s(p,q)=∑((k/q))((pk/q))”:
https://baike.baidu.com/item/%E6%88%B4%E5%BE%B7%E9%87%91%E6%95%B0

关于“第n个戴德金数”,百度百科里压根就没提到。

不知道百度百科里讲的“戴德金数”为什么完全不一样呢?

它和“第n个戴德金数”有联系吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-7-12 10:52:48 | 显示全部楼层
不知道戴德金数能干嘛,我孤陋寡闻第一次听说
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-7-12 12:54:54 | 显示全部楼层
KeyTo9_Fans 发表于 2023-7-11 20:01
我也不知道能干什么,继续查阅了一些资料,发现:

新闻里的“戴德金数”是“含有n个变量的单调布尔函数 ...

数学没啥用,还是学计算机实在,郭先强去码代码了,最后还创业当老板了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-11-3 20:41:35 | 显示全部楼层
这个概念有点难理解,看了大半天才明白。
原来所谓n个变量的布尔函数就是n个元素集合{1,2,3,...,n}的所有子集到{0,1}集合的映射。
比如n=2,那么就是{{}, {1},{2},{1,2}}到{0,1}的所有映射,比如f({})=f({1})=0, f({2})=f({1,2})=1就是一个n=2的布尔函数。
而单调递增的布尔函数要求,如果一个集合被映射到0,那么它的所有子集也都映射为0,比如上面我给出的例子就是单调递增的。
而函数f({})=f({1,2})=0,f({1})=f({2})=1就不单调递增。

oeis链接里面还给出了一个antichain的概念,但是没有给出解释,这个比较费解。
由于如果一个集合被映射到0,那么它的所有子集也都会被映射到0,所以我们只需要找到所有那些被映射到0的极大集合(也就是所有包含它的集合都被映射到1),这些极大集合就构成了antichain。然后,我们就可以用antichain来表示这个函数映射了。
比如n=0有两个antichain,也就是有两个不同的单调增函数:
{}:,代表所有集合被映射为1,也就是函数f({})=1
{{}}: 代表空集被映射为0,也就是函数f({})=0

n=2有6个antichain
{}: 代表所有集合被映射为1,也就是函数f({})=f({1})=f({2})=f({1,2})=1
{{}}: 代表仅空集被映射为0, 也就是函数f({})=0, f({1})=f({2})=f({1,2})=1
{{1}}: 代表{1}和它子集被映射为0, 也就是函数f({})=f({1})=0,f({2})=f({1,2})=1
{{2}} : 代表{2}和它子集被映射为0, 也就是函数f({})=f({2})=0,f({1})=f({1,2})=1
{{12}}: 代表{12}和它子集被映射为0, 也就是函数f({})=f({1})=f({2})=f({1,2})=0
{{1}{2}}: 代表{1},{2}和它们的子集被映射为0,也就是函数f({})=f({1})=f({2})=0,f({1,2})=1

另外我们可以看出对于一个antichain, 它的任意两个元素(都是集合)相互不包含。而对于任何一个符合这个条件的子集集合,它也是一个antichain.
所以可以通过计数所有任意两个元素都互相不包含的集合的数目就可以。

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-4-19 14:18 , Processed in 0.050298 second(s), 19 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表