《离散数学及其应用》的一道逻辑题

Quasimodo_lory

不知道这样的帖子该不该发到这里来，但是我自己自学实在找不人来帮我解答。
还望各位不吝赐教，谢谢了！
题目：
在一个100条语句的列表中，第n条语句是“在这个列表中，恰有n个语句为假”
a）从这些语句中你可以得出什么结论？
b）若第n条语句是“在这个列表中，至少有n个语句为假”，回答问题a
c）假设这个列表包含99条语句，回答问题b

问题a我很快知道答案了，问题b看了答案也想不明白。

kangtian

我怎么觉得这有点“子非鱼，安知鱼之乐也”思辨味道。

[ 本帖最后由 kangtian 于 2009-10-14 09:46 编辑 ]

Quasimodo_lory

没人会吗？
自己顶一下吧～

naihe2010

首先得从这个第N条语句为真或假进行分析吧？

kangtian

另外我觉得这个题目的表述不严谨，语句应该改为命题。真命题，假命题。
还有，题面是完整的吗？还是大致意思？

epegasus

编程序验证啊.

b,推理也很简单啊,如果至少有n个语句为假,则对于m<n来说,"至少有m个语句为假"是真的.
也就是当第n句对的,那么他前面的都是对的.而他后面的都是错的.这样一共n句是对的.
一共n句是对的 和 至少n句为假, 怎么样才不矛盾呢?
只有n<=50

c,根据上面的n < 50

kouu

a)
"恰有n个语句为假"(n=1~100)这100句话是互斥的，所以，其中至多有一句是真（即有0句或1句是真）。
第一种情况，有1句是真，则有99句是假。正好，第99句说"恰有99个语句为假"。所以，第99句是真，其余是假；
第二种情况，有0句是真，则有100句是假。但是，第100句说"恰有100个语句为假"，这句话是真，矛盾了。所以不存在这种情况。
所以，第99句是真，其余是假。


b)
如果"至少有n个语句为假"这句话是真的，则"至少有n-1个语句为假"、"至少有n-2个语句为假"、...、"至少有1个语句为假"这些都是真的。
即从第1句到第n句都是真的。
且第n句到第100句都是假的（否则，如果第n+x句是真的，那么第n+1、n+2、...n+x都是真的了）。

现在假设第n句是真，那么第1~n句是真的，第N+1~100句是假的，真的语句数目为n，假的语句数目为100-n。
第n句说"至少有n个语句为假"，这是真的，则100-n>=n；
第n+1句说"至少有n个语句为假"，这是假的，则100-(n+1)<n；
于是99-n < n <= 100-n，99<2n<=100，n=50。
所以，前50句是真的，后50句是假的。


c)
同b，假设第n句是真，那么第1~n句是真的，第N+1~99句是假的，真的语句数目为n，假的语句数目为99-n。
有99-n>=n，99-(n+1)<n，
于是98-n < n <= 99-n，98<2n<=99，n无解(49 < n <= 49.5)。
所以，前49句是真的，后49句是假的。
第50句无解： 如果为真，则"至少有50个语句为假"，实际上只有后面的49句为假，矛盾；如果为假，则"至少没有50个语句为假"，实际上只有前面的49句不为假，矛盾。

Quasimodo_lory

太谢谢各位了！我明白了！
尤其要感谢epegasus 和kouu
谢谢！

epegasus

这事还没完呢...

我昨天看了kouu 的回复,想了很久..

首先要指出kouu 的几个错误.
在b的证明中,
>>第n+1句说"至少有n个语句为假"，这是假的，则100-(n+1)<n；
这句话是明显错误.应该是
第n+1句说"至少有n+1个语句为假"，这是假的，则100-(n+1)<n+1；[1]

在C中同时也也存在类似错误.
当然kouu 分析方法很好.

不过
我在仔细查看我自己的错误后发现了些东西.
我的证明没给出确定的n,为什么呢?
相比kouu 的证明,我漏掉了上面那段红色标记的话.
但是我查看了我的证明,如同kouu 的证明,我通过假设第n句是对的,推论出 大于n的都是错的.kouu 也这样做了推论.
如此我就在第n 句对的中已经包含了第n+1句是错的这个事实,
那为什么我还有必要在得出100-(n+1)<n+1这个结论呢?
这明显是可疑的.

我发现错误在于:原先的假设第n句是对的,推论出 大于n的都是错的.[2]

因为基于以下可以说明它是自相矛盾的.
假设第n句是对的,那么小于n都是对的,这是肯定的.
但如果这时大于n都是错的:
那么n-1是对的可以得出n是错的
这和假设相矛盾.

所以[2]不成立.
为什么会得出[2]这个错误结论呢?
我想是因为人在做逻辑推理这种机械思维时容易犯糊涂.
我们只能得出:当n是错误的时候,大于n都为错.

还没完....

我们假设b中所有语句都是非对即错,那么我们能确定的得出n=50.
我们同样引到C中来证明,通过修正kouu的C的证明,我们能确定得出n=49,而不是kouu的无解.
由于我们原先假设c中的语句非对即错,那么我们就能得出50句是假的,但c给出了50句无法判断到出人意料.

哪里错了?
对于C中50句的判断,那不就是一个悖论呢?

我又想起了说谎者悖论来.
其本质是做了自指的判断.而再在a,b,c中所有的句子,他们不正是3套隐含自指的命题么?
也就是这里面可能隐含悖论!
我们原先的假设并没引入悖论.
那什么是悖论?我功力不够,只能联想到数字逻辑里面的RS触发器的不稳定态,RS触发器就是时序逻辑电路,输出的状态又返回为输入.
这个不正是我们上面的命题的形式吗?

就拿b来说,每个命题的真假就是一个一位的逻辑变量,而每条语句就是把这些逻辑变量作为输入的一个逻辑函数,也就是等价为一个组合逻辑电路,而这个逻辑函数的输出就是一个命题的值.
那么就等价于n个输入,n个输出的组合逻辑,或者组合电路,但这里还要求n输入 衡等于n输出.
问题本身等价于:对于上述给的情况,求n个输出的,确定逻辑值.

首先问题是存在这样一组逻辑值吗?
通过b和c的例子我们知道可能存在,可能不存在,并且有进一步问题,如:
是否存在一个或多个稳定值(不存在悖论),如果存在不稳定(悖论),那么是否存在多种情况.
说谎者悖论,命题只有1个,所以只有2个态的悖论:0->1->0->1........
对于多命题是否存在多种;比如A->B->C->A......

[ 本帖最后由 epegasus 于 2009-10-15 10:22 编辑 ]

kouu

原帖由 epegasus 于 2009-10-15 10:18 发表
第n+1句说"至少有n+1个语句为假"，这是假的，则100-(n+1)<n+1；[1]
我发现错误在于:原先的假设第n句是对的,推论出 大于n的都是错的.[2]

多谢指正~
第一个问题的确是个错误；
第二个问题确实也是错了，其实我的本意是假设n是最后一句为真的。呵呵，表述不当。

其实我很想知道LZ看到的标准答案是什么