免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: ethantsien

[算法] 帮我看下这个反证法的数理逻辑是正确的吗? [复制链接]

论坛徽章:
3
15-16赛季CBA联赛之山东
日期:2016-10-30 08:47:3015-16赛季CBA联赛之佛山
日期:2016-12-17 00:06:31CU十四周年纪念徽章
日期:2017-12-03 01:04:02
发表于 2012-10-01 21:24 |显示全部楼层
本帖最后由 captivated 于 2012-10-01 22:44 编辑

(!r成立表述有误, 再编辑下)

如果在现有公理下,那么质数有无数个
p: 现有公理成立.
q: 质数有无数个.

命题 r <=> p->q,
命题r: 如果现有公理成立, 那么质数有无限个.

所以你的假设就是 !r 成立. 因为假设 !r 成立的表述就是: p成立并且q不成立.
也就是说, 我们的假设就是r不成立.

命题演算(v析取, ^合取, !否定, <=>命题等价):  
            r <=> p->q <=> !p v q
            !r <=> !(p->q) <=> !(!p v q) <=> p ^ !q

你最初的假设是!r成立, 后面的谁真谁假及其关系是根据 !r 通过命题等价演绎演绎出来的. 你可以演绎出无数个版本的,而最终的实质假设前提就是!r成立.

而反正法本身, 就是我12L说的那个.
=====================================

看14L的问题吧~

论坛徽章:
4
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:11
发表于 2012-10-01 21:33 |显示全部楼层
回复 21# captivated


    你这么说也对,我之前也解释过了,说明!r就是在说明!q,因为p肯定成立。

论坛徽章:
3
15-16赛季CBA联赛之山东
日期:2016-10-30 08:47:3015-16赛季CBA联赛之佛山
日期:2016-12-17 00:06:31CU十四周年纪念徽章
日期:2017-12-03 01:04:02
发表于 2012-10-01 21:36 |显示全部楼层
回复 20# starwing83


    所以我其实是常被这个问题折磨到宕机的。我试图通过某种命题演算来引导出那个问题的答案(在我已经知道答案的前提下),却发现有些困难(所以我需要,有人证明无法通过命题演算引导出答案,或者,有人用命题演算引导出了答案)。

论坛徽章:
4
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:11
发表于 2012-10-01 21:46 |显示全部楼层
回复 23# captivated


    这是完全不同的问题了。这个实际上是属于“可证性”的范畴,参见哥德尔不完备原理。

命题逻辑肯定可以证明的。命题逻辑本身不知道啥叫反证法。反证法是某种命题逻辑证明思路的代称,但是符号逻辑本身是不会用思路的,采用这种思路的是人类,就算最终证明出来,也是人类证明的。命题逻辑只是给出了这种证明的步骤,而不是思路。

论坛徽章:
3
15-16赛季CBA联赛之山东
日期:2016-10-30 08:47:3015-16赛季CBA联赛之佛山
日期:2016-12-17 00:06:31CU十四周年纪念徽章
日期:2017-12-03 01:04:02
发表于 2012-10-01 21:48 |显示全部楼层
回复 24# starwing83

        额, 我要被你引导到不知通往何方了
   

论坛徽章:
4
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:11
发表于 2012-10-01 21:49 |显示全部楼层
回复 25# captivated


    无所谓啦,十一在家无事刷坛,有人陪刷显然是好的~~嘿嘿。

论坛徽章:
3
15-16赛季CBA联赛之山东
日期:2016-10-30 08:47:3015-16赛季CBA联赛之佛山
日期:2016-12-17 00:06:31CU十四周年纪念徽章
日期:2017-12-03 01:04:02
发表于 2012-10-01 21:56 |显示全部楼层
回复 26# starwing83


    嗯, 彼此彼此

论坛徽章:
2
CU大牛徽章
日期:2013-04-17 11:46:28CU大牛徽章
日期:2013-04-17 11:46:39
发表于 2012-10-02 09:01 |显示全部楼层
无所谓啦,十一在家无事刷坛

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11数据库技术版块每日发帖之星
日期:2016-08-03 06:20:00数据库技术版块每日发帖之星
日期:2016-08-04 06:20:00
发表于 2012-10-02 10:22 |显示全部楼层
captivated 发表于 2012-10-01 21:24
(!r成立表述有误, 再编辑下)

如果在现有公理下,那么质数有无数个

命题r: 如果现有公理成立, 那么质数有无限个.
这个写法是很不靠谱的
首先"在现有公理下"的字样不应该出现
再者,对于潜无穷,以下说法比较靠谱
质数集无界(因为无界在之后的研究中已被定义)
或者完整的
对于任何一个质数a,存在一个质数b,使得b>a

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11数据库技术版块每日发帖之星
日期:2016-08-03 06:20:00数据库技术版块每日发帖之星
日期:2016-08-04 06:20:00
发表于 2012-10-02 10:25 |显示全部楼层
cjaizss 发表于 2012-10-02 10:22
命题r: 如果现有公理成立, 那么质数有无限个.
这个写法是很不靠谱的
首先"在现有公理下"的字样不应该出 ...

另外,反证用的不是人脑的思维,人脑的思维不靠谱.
用的是逆否命题,当然成立前提是排中律为公理.
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。




----------------------------------------

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP