帮我看下这个反证法的数理逻辑是正确的吗？

captivated

回复 10# ethantsien


    见楼下说明.
   

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

captivated

回复 9# starwing83

回复 1# ethantsien


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

    令 r == p->q

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

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

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

captivated

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

captivated

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

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

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

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

starwing83

回复 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为真。落实到证明上，如果质数有有限个，那么我们就推导出一个不属于质数集合的质数，这和公理“一个元素不能既属于又不属于某个集合”矛盾，这证明前提是错误的，既有有限个质数是错误的，即质数有无限个。

starwing83

回复 14# captivated


    这个问题跟反证没关系。一个村民要么是p要么是!p（p为公理系统），那么很简单，问他一个属于p的内容，设q，如果p->q他回答为真则他为p，否则他为!p。那么我问他：天是什么颜色的，然后再问他那条路到神庙即可。

好吧，只能问一个问题，那就把上述两个问题总结成一个问题，或者让这一个问题具备两者的特性即可——另外，你遇到一个人，会只问一个问题么？？？

captivated

回复 15# starwing83


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

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

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

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

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

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

captivated

回复 16# starwing83


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

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

starwing83

回复 17# captivated


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

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

starwing83

回复 17# captivated


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