离散数学:构造性二难推理和破坏性二难定理的解释

二难推理是由两个假言判断和一个有两个选言支持的选言判断做前提构成的推理。假言选言推理的主要形式。其结论可以是直言判断,也可以是选言判断。因为这种推理有时反映左右为难的困境,故称。

构造性二难推理:(A→B)∧(C→D)∧(A∨C)⇒(B∨D)
破坏性二难推理:(A → B)∧(C→D)∧(┐B∨┐D)⇒ (┐A ∨┐C)

举个栗子~:
父亲对他那喜欢到处游说的儿子说,“你不要到处游说。如果你说真话,那么富人恨你;如果你说假话,那么穷人恨你。既然游说只会招致大家恨你,你又何苦为之呢?”在这里,父亲劝儿子就使用了一个二难推理,形式是:
如果你说真话,那么富人恨你;
如果你说假话,那么穷人恨你;
或者你说真话,或者你说假话;
总之,有人恨你。

构造性二难推理的意思就是,构造出一个二难的境地,比如:
A 能推出 B,C 能推出 D,【(A→B)∧(C→D)
但是 B 和 D 这两个结论都令你很难受,(所以叫二难推理)可是
A 和 C 至少要有一个是成立的,【A∨C
所以 B 和 D 至少有一个是成立的。【B∨D

破坏性二难推理的意思是,
A 能推出 B,C 能推出 D,【(A→B)∧(C→D)
但是 B 和 D 这两个结论都令你很难受,可是
至少你想让其中一个不成立【(┐B∨┐D)】
这样就能说明 A 和 C 至少有一个是不成立的【(┐A ∨┐C)】

还有一个栗子~:
《红楼梦》第六十四回载:贾宝玉从林黛玉的丫环雪雁处得知林黛玉在私室内用瓜果私祭时想:“大约必是七月,因为瓜果之节,家家都上秋季的坟,林妹妹有感于心,所以在私室自己奠宗……”,怎么呢?贾宝玉又想:“但我此刻走去,见她伤感,必极力劝解,又怕她烦恼郁结于心;若不去,又恐她过于伤感,无人劝止,两件皆足致疾……”如果我们将贾宝玉的后一段想法稍加简化,那么,就可构成如下一个简单构成式的二难推理
如果我去林妹妹处,足以致疾;如果我不去林妹妹处,也足以致疾,
或者我去林妹妹处,或者我不去林妹妹处,
总之,皆足以致疾。

离散数学中输出律的证明:(P∧Q→R)恒等于(P→(Q→R))

证明(P∧Q→R)恒等于(P→(Q→R)):
因为: 蕴含式 A->B 的一条性质是:当且仅当 A 真 B 假时,(A->B) 为假

①:所以: (P∧Q→R)可以表述为:当且仅当 (P∧Q) 真 R 假时,(P∧Q→R)为假
//(P∧Q) 真等价于 P 真 且 Q 真
所以当且仅当(P真,Q真,R假)时,(P∧Q→R)为假

②:所以:(P→(Q→R))可以表述为:当且仅当 P 真 Q->R 假时,(P→(Q→R))为假
//Q->R 假等价于 Q 真 且 R 假(根据第一句蕴含式的性质)
所以当且仅当(P真,Q真,R假)时,(P→(Q→R))为假

所以 (P∧Q→R)恒等于(P→(Q→R)).