免费注册 查看新帖 |

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 19:48 |显示全部楼层
本帖最后由 captivated 于 2012-10-01 20:02 编辑

回复 10# ethantsien


    见楼下说明.
   

    其实要, 令命题 r == p->q (没办法打等价符号, 用==代替命题等价吧), 就是实际要判断的是r是否成立.
    接下来, r == p->q 可以有很多种演化/演绎的, 只要用逻辑等价的式子不断替换就行了, 比如:
    r == p->q == !p V q ... 然后 p, q又可以不断被命题等价的式子(假设题目前提下有另外的条件, 那么命题还可以被别的命题替换, 只要等价)替换.
    所以我认为LZ你的想法是没什么意义的事情.

论坛徽章:
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 20:00 |显示全部楼层
回复 9# starwing83

回复 1# ethantsien


    那么我也给一种描述好了.

    令 r == p->q

    (你们大意了反证法其实是假设命题 r 为假, 而不是假设 p, q 中任意一个命题为假.
=================================================================

    由 r == F 这个假设, 去重重演绎(演绎过程可以有很多很多的..., 只要确保演绎过程正确), 最终得到 r == T 这个结论.
    那么命题 r ^ !r 是矛盾, 根据这个得出 r == F 的前提不成立. 这才是反证法咯.

=================================================================

论坛徽章:
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 20:17 |显示全部楼层

你们给的都是一种演绎过程,而不是反证法。演绎过程可以有很多种。你们的演绎过程都是对的(我没仔细看),但是它不是反证法本身。

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

其实我倒想出个问题。
一个岛上的村民, 要么总是说真话,要么总说谎. 对旅游者的问题, 村民要么回答“是”,要么回答“不是”。假设你去这个岛上旅游,走到一个岔路口,一条岔路通往你想去的神庙,一条岔路通往毒蛇遍布的丛林深处。此时恰好有一个村民站在岔路口,你要问村民一个什么样的问题就能决定走哪条路?

当然,上述问题的答案想必大家都知道。

我的问题是:请问,你需要假设什么样的命题,并根据你假设的命题,通过什么样的逻辑演绎,就能够知道答案?

@OwnWaterloo
@starwing83
@幻の上帝
@zylthinking
@tempname2
@xxw19840406
@mr_sev
@cdtits
@koolcoy

论坛徽章:
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 20:48 |显示全部楼层
回复 14# captivated


    比如说吧,假设我要证明一个命题:质数有无数个。

设这个命题为q,p是公理系统。即p->q表述为“如果在现有公理下,那么质数有无数个”。

我们先假设!q(注意,不是假设!(p->q),这句话的意思是,“在现有公理下,质数有无数个”是假的,有两个含义:1.现有公理是假的,2.质数有无数个是假的,后者就是!q,但是前者明星不可能成立,因此这里直接假设!q),即,质数有无数个是错的,即质数有有限个。

然后,我们利用!q,证明!p(即证明公理系统是错误的),即假设这有限个质数是P = {p1, p2, ... , pn},那么我们给定一个数字PM = p1*p2*...*pn + 1,显然它和p1...pn互质,根据定义它是质数,但是它又不属于我们的质数集合。这属于制造矛盾,我们并没有直接制造!p,而是采用了制造矛盾间接证明!p的办法。意思是假设{p, x}->y正确,但是y和x矛盾,要满足这个式子唯一的办法就是p为假,这样我们就证明了!p。

但是p是真的(公里系统肯定是成立的),而我们是在!q的前提下证明了!p,唯一的一个可能就是这个前提是假的。那么!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-01 21:03 |显示全部楼层
本帖最后由 starwing83 于 2012-10-01 21:04 编辑

回复 14# captivated


    这个问题跟反证没关系。一个村民要么是p要么是!p(p为公理系统),那么很简单,问他一个属于p的内容,设q,如果p->q他回答为真则他为p,否则他为!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:04 |显示全部楼层
本帖最后由 captivated 于 2012-10-01 21:08 编辑

回复 15# starwing83


    反证法的说明我12L给的那个应该就是的, 我个人觉得关于反证法本身, 应该不会再有争议了, 呵呵.

    我想要14L我提出的那个问题的答案, 而且就按照我14L原来的问题来假设命题.

    比如可以假设, 命题P1: 右边的岔路是通往神庙的.
                 命题P2: 村民说的是真话.
    当然, 你可以用别的方式来假设命题, 并不一定就是我说的这两个.

    我的意思是, 根据假设命题, 推导出某种确定模式, 根据这个模式, 你能知道那个问题的答案. 而那个问题的答案本身并不是命题, 而是一个问句.

    那个问题的答案是如下问句:
    "如果我说右边的岔路是否通往神庙,请问你会说'是'吗?"

    所以我的问题是, 你要怎样假设命题, 要怎么样得到一个模式(或者相对等的真值表), 从而引出上面那个问句(嗯, 那个问句不是命题)。

论坛徽章:
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:05 |显示全部楼层
回复 16# starwing83


    问句的答案我17给了。 题目的意思是只能问一个问题。

    我的问题是,怎么引导出这个问句。

论坛徽章:
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:06 |显示全部楼层
回复 17# captivated


    参见我的回答,比你的更加广泛。

另外,你的定义是不对的,仔细看看我对质数的论证,已经告诉你为什么不对了。

论坛徽章:
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:12 |显示全部楼层
回复 17# captivated


你是你的答案只是让说谎者两次取反了,这是一个“元问题”,说谎者会告诉你“如果你让我回答的问题包含了我的反应自身,那我有权不回答”,这其实可以算作“停机问题”的一个特殊形式了。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

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




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

大会官网>>
  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP