免费注册 查看新帖 |

Chinaunix

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

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

论坛徽章:
0
发表于 2012-10-02 15:29 |显示全部楼层
证明:若p成立,则q成立

反证法:

我们假设q为假,所以!q为真

在!q为真的情况下,我们假设某一命题r成立

但是我们能够证明!q->!r

能证明命题为假的话,前提只能是假,也就是!q为假,q为真,与我们的假设q为假之间矛盾,所以假设不成立,所以q为真

论坛徽章:
0
发表于 2012-10-02 15:31 |显示全部楼层
cjaizss说的对,说白了,反证法还是用了逆否原理

论坛徽章:
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-02 15:40 |显示全部楼层
回复 31# ethantsien


    并不是假设r成立,你得先证明r是成立的,然后根据!q证明!r成立。

论坛徽章:
0
发表于 2012-10-02 15:41 |显示全部楼层
starwing83 发表于 2012-10-02 15:40
回复 31# ethantsien


你错了,一个命题的真假,都是相对于人的认知的,我现在认知r是对的,所以我只要能推导出!r,就说明前提一定是假的

再讨论下去,要往哲学范畴跑了

论坛徽章:
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-02 16:42 |显示全部楼层
回复 34# ethantsien


    ………………你清楚啥叫自然推理系统么?一个系统里面,有公理集合,推理规则,如果一个命题能由公理集合开始,经由推理规则产生,才能说这个命题是真的,否则就是假的,不是你认为是真的就是真的,你认为是假的就是假的。

比如说,煤炭是白的,雪是白的,白的东西都是煤炭是你的公理,而古典三段论是你的推理规则,那么“雪是煤炭“就是你的系统的定理,而不是你说他真他就真的,那是唯心主义。

明白了么?所以谈论r是否为真,必须证明,至少从公理角度上证明。就比如证明质数有无穷个,就用到了集合论公理,证明出的结论和公理直接矛盾(这里的公理就是你说的r),所以才能得证。因为r是公理所以r不用证明,但是如果你用到的r不是公理,那就是必须证明的。

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11数据库技术版块每日发帖之星
日期:2016-08-03 06:20:00数据库技术版块每日发帖之星
日期:2016-08-04 06:20:00
发表于 2012-10-02 18:50 |显示全部楼层
ethantsien 发表于 2012-10-02 15:41
你错了,一个命题的真假,都是相对于人的认知的,我现在认知r是对的,所以我只要能推导出!r,就说明前提 ...

no

论坛徽章:
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-02 19:32 |显示全部楼层
本帖最后由 captivated 于 2012-10-02 21:31 编辑

晕倒. 又歪楼了。


“逆否原理”,是说一个蕴涵命题(这个蕴涵命题是p->q, 而不是p, 或者q)和其逆否命题是等价命题。这只是属于命题演算的一种等价演绎规则,它只是说:
如果令命题 r <=> p->q, 那么, 如下演绎成立:
r <=> p->q <=> !p<-!q <=> ...
反证法的前提是 r 不成立,
也就是 !r <=> !(p->q) <=> ... 如此演绎下去, 然后...

反证法的依据是, 命题r不能既成立又不成立,反证法的最终依据是矛盾律。

判断一个命题究竟是否成立,和命题演算一点关系都没有。
也就是说,判断命题是否成立是对命题赋值
通过对 p 或者 q 赋值, 就得到了命题 r 的值。而对命题赋值是由证明人所使用的附加步骤只不过一般来说证明人从公理系统出发来为命题赋值。就是说赋值和命题等价无关,赋值也和命题演绎无关,因为无论怎么赋值,命题等价关系都成立。更进一步说,公理系统是赋值的依据,而不是命题等价的依据。命题等价是"The Law of Thought."

把某个命题等价规则说成是反证法的依据,是绝对错误的。它只是可能的演绎步骤。

发证法的出发点是,假设 r 不成立, 然后开始通过命题等价演绎, 直到演绎到某一步, 这时证明人能够比较容易地对命题表达式中的命题赋值了(也就是证明人能够一眼明确表达式中的所有命题成立与否了),然后得出的结果却是 r 成立。于是,根据矛盾律,这个原来的假设前提 r 不成立矛盾,由此 r 成立得证。

论坛徽章:
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-02 19:33 |显示全部楼层
本帖最后由 captivated 于 2012-10-02 20:23 编辑

回复 30# cjaizss


    呃. 之前说是一定是矛盾律而不是排中律。

    这里对斑竹的说法表示下,是我错了。对于这个(反证法)来说,应该排中律和矛盾律都对。

    排中律是说,不能同假,必有一真。矛盾律是说,不能同真,必有一假。

   

论坛徽章:
0
发表于 2012-10-02 20:15 |显示全部楼层
starwing83 发表于 2012-10-02 16:42
回复 34# ethantsien


你误解我的意思了,我认知r为对,并不是说它有悖于公理系统,我的认知基于人类的认知,我不可能假设一个有悖于公理系统的r成立,我意思是r不用证明,针对你说的“我假设r成立,我一定要先证明r成立”,

比如我假设r为偶数成立,但是我通过!q推出了r为奇数,所以!q为假,q为正

论坛徽章:
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-02 21:56 |显示全部楼层
回复 39# ethantsien


    啊,我懂了。你说的对,这的确是反证法的一种很重要的方式,也是通常的方式。

本质上就是添加一个新的前提进行推理,然后推理出这个前提的反面。的确这是一种方法。

所谓反证,说白了就是假设结论为假,推理出矛盾的地方,所谓矛盾,和公理系统矛盾、和定理矛盾以及和前提矛盾都是可行的。是这样。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

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




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

大会官网>>
  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP