【离散数学】偏序关系与全序关系的区别、解释(偏序集合、全序集合)

偏序关系全序关系都是公理集合论中的一种二元关系。
偏序集合:配备了偏序关系的集合。
全序集合:配备了全序关系的集合。

偏序:集合内只有部分元素之间在这个关系下是可以比较的。
比如比如复数集中并不是所有的数都可以比较大小,那么“大小”就是复数集的一个偏序关系。

全序:集合内任何一对元素在在这个关系下都是相互可比较的。
比如有限长度的序列按字典序是全序的。最常见的是单词在字典中是全序的。

偏序的定义
设R是集合A上的一个二元关系,若R满足:
Ⅰ 自反性:对任意x∈A,有xRx;
Ⅱ 反对称性(即反对称关系):对任意x,y∈A,若xRy,且yRx,则x=y;
Ⅲ 传递性:对任意x, y,z∈A,若xRy,且yRz,则xRz。
则称R为A上的偏序关系。

全序的定义
设集合X上有一全序关系,如果我们把这种关系用 ≤ 表述,则下列陈述对于 X 中的所有 a, b 和 c 成立:
如果 a ≤ b 且 b ≤ a 则 a = b (反对称性)
如果 a ≤ b 且 b ≤ c 则 a ≤ c (传递性)
a ≤ b 或 b ≤ a (完全性)

注意:完全性本身也包括了自反性。
所以,全序关系必是偏序关系。

【离散数学】单射、满射和双射的定义、区别

满射:对任意b,存在a满足f(a) = b。
Snip20160613_129
即:值域y是满的。每个y都有x对应。不存在某个y没有x对应的情况。

单射:(one-to-one function) 一对一函数。x不同则y不同。
Snip20160613_128
即:没有一个x对应两个y,也没有一个y有对应两个x。

双射:既是满射,也是单射。
Snip20160613_130
即:每个y都有x对应。而且都是一一对应。

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

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

构造性二难推理:(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)).