免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 7519 | 回复: 52

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

论坛徽章:
0
发表于 2012-09-30 19:14 |显示全部楼层
本帖最后由 ethantsien 于 2012-09-30 19:18 编辑

证明:假设p成立,则q成立

数理逻辑:

描述一

因为p为真,要使p->q为真,只能q为真

我们假设p->q为假,因为p为真,所以q只能为假

总可以找到一个命题x和q是等价的,即x<->q

但是我们能证明p->x成立,即x为真

因为x和q等价所以q为真。

根据矛盾律,q不能同时为真和假

所以我们假设的p->q为假不成立

所以p->q为真

证明完毕。

描述二

我们假设q为假,总可以找到一个命题x和q是等价的,即x<->q

但是我们能证明p->x成立,即x为真

因为x和q等价所以q为真。

根据矛盾律,q不能同时为真和假

所以我们假设的q为假不成立

所以q为真,所以p->q成立

================================================
用哪个描述呢?

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11数据库技术版块每日发帖之星
日期:2016-08-03 06:20:00数据库技术版块每日发帖之星
日期:2016-08-04 06:20:00
发表于 2012-09-30 19:25 |显示全部楼层
论述2中
"但是我们能证明p->x成立,即x为真"
这句还得加一个前提,p为真

论坛徽章:
0
发表于 2012-09-30 19:29 |显示全部楼层
本帖最后由 ethantsien 于 2012-09-30 19:30 编辑
cjaizss 发表于 2012-09-30 19:25
论述2中
"但是我们能证明p->x成立,即x为真"
这句还得加一个前提,p为真


嗯,反证法是假设p->q为假呢,还是假设q为假为前提,虽然根据真值表,在p为真的情况下,两者是相等的

论坛徽章:
0
发表于 2012-09-30 20:03 |显示全部楼层
那个排中律没有问题么?
q 要么为真,要么为假,没有别的可能?薛定谔家养的猫表示强烈不满。

论坛徽章:
0
发表于 2012-09-30 20:33 |显示全部楼层
fallening_cu 发表于 2012-09-30 20:03
那个排中律没有问题么?
q 要么为真,要么为假,没有别的可能?薛定谔家养的猫表示强烈不满。


因为这是个命题,命题要符合排中律,矛盾律和同一律

论坛徽章:
0
发表于 2012-09-30 21:06 |显示全部楼层
ethantsien 发表于 2012-09-30 20:33
因为这是个命题,命题要符合排中律,矛盾律和同一律

你是在说命题演算(Propositional calculus)而不是在说命题吧?

论坛徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11数据库技术版块每日发帖之星
日期:2016-08-03 06:20:00数据库技术版块每日发帖之星
日期:2016-08-04 06:20:00
发表于 2012-09-30 21:18 |显示全部楼层
ethantsien 发表于 2012-09-30 19:29
嗯,反证法是假设p->q为假呢,还是假设q为假为前提,虽然根据真值表,在p为真的情况下,两者是相等的

既然是互推的,那就一致了

论坛徽章:
2
CU大牛徽章
日期:2013-04-17 11:46:28CU大牛徽章
日期:2013-04-17 11:46:39
发表于 2012-09-30 22:03 |显示全部楼层
这是什么命题....

论坛徽章:
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 11:31 |显示全部楼层
这不是反证法吧?

假设p为真,证明q也为真。

如果找到了一个x,使x<->q,

那么,如果证明了p->x的话,因为p为真,那么x为真,而x<->q,则q为真,这就是正常的证明方法吧?

反证法不是应该是这样的么:

首先假设q为假,设这个命题为!q,推导出!q->!p,即如果q为假,则p也为假,但p为真,所以q不可能为假,即q为真。

因为一个命题的逆反命题肯定成立,如果p->q为真,那么我们总能找到!q->!p的证明方法,这是反证法成立的原理。

论坛徽章:
0
发表于 2012-10-01 17:36 |显示全部楼层
本帖最后由 ethantsien 于 2012-10-02 15:32 编辑
starwing83 发表于 2012-10-01 11:31
这不是反证法吧?

假设p为真,证明q也为真。


恩,我后来想想是有问题,但是,你的也不是反证法,你的是利用了原命题和它的逆否命题相等的原理
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

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

限时8.5折扣期:2019年9月30日前


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

大会官网>>
  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP