离散数学第一章-(精选·公开·课件).ppt

* * 为了方便，用Mδ1δ2...δr来表示最小集 例如：A1?A2 ? A3 ? A4 表示为M1001 我们知道?运算的成员表中只有一行取1，其余各行均为0，且只有A、B均取1的行，A?B才取1。 * * 命题： Mδ1δ2...δr的成员表中， M δ1δ2...δr所对应的列中只有一行为1，其余的均为0。并且M δ1δ2...δr取1的行， 恰好为δ1δ2...δr。 证明： ∵x∈ Mδ1δ2...δr＝ 当且仅当 ∴在Mδ1δ2...δr取1的行，一定有 (j=1,2,...,r) 若 ＝Ai 此时δi＝1 x∈Ai，即xi ? Ai，于是在Ai所标记的列中，Ai在该行取值δi＝0。 由x∈ ＝Ai ，知在Ai所标记的列中，该行取值δi＝1； 若 ＝Ai，此时δi＝0 ∴M δ1δ2...δr取1的行恰好为δ1δ2...δr。 * * 例：M000、M110、M100、M111及S＝M000?M110?M001?M111的成员表。 A1 A2 A3 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 M000 1 0 0 0 0 0 0 0 M110 0 0 0 0 0 0 1 0 M100 0 0 0 0 1 0 0 0 M111 0 0 0 0 0 0 0 1 S 1 0 0 0 1 0 1 1 A1? A2? A3? 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 M000＝A1?A2 ?A3 M110=A1?A2 ? A3 M100=A1? A2 ?A3 M111=A1? A2 ?A3 * * 从上页的成员表可以看出： M000恰好在000行取1，其余取0 M110恰好在110行取1，其余取0 M100恰好在100行取1，其余取0 M111恰好在111行取1，其余取0 现在我们把这些最小集并起来，得另一个由A1、A2、A3产生的集合S，即S＝ M000?M110?M100?M111。那么S构成的成员表就不必要重新构造，可根据前4列得到。(这可根据并运算的成员表知，它为0，仅当前面的4列均为0。) 由最小集和最小集的并集的成员表的上述特点，我们有下面的定理。 * * 定理：由A1,...,A r产生的每个非空集合S恒可表示为由A1,...,Ar产生的不同最小集的并集。 分析：根据S的成员表，构造一个由A1，....，A r产生的不同最小集的并集T，然后说明S＝T即可。 证明： ∵S≠? ∴S的成员表中S所标记的列不全为0 (否则S＝?，因为成员表中一列全为0，表示该列所标记的集合为空集。) 不妨设m个1(1≤m≤2r，∵由A1，...，Ar生成的成员表有2r行)。 * * 如在上例，S列中 δ11δ12δ13＝000 δ21δ22δ23＝100 δ31δ32δ33＝110 δ41δ42δ43＝111 于是我们可以作最小集Mδj1....δj r＝ (i=1,2,...,r) 设这m个1分别在δ11δ12...δ1r，δ21δ22...δ2r，...， δm1δm2...δm3处为1。(其中δj1δj2...δjr表示在成员表中，A1，...，Ar各列取值分别为δj1...δjr的行。) 这里第一个坐标j，标志S列中，第j个取1的行。 * * T仅在δ11δ12...δ1r，δ21δ22...δ2r，....，δm1δm2...δm3行处为1，其余行为0。 因此T与S所标记的列完全一样。∴S＝T 从而 S＝M δ11....δ1r?M δ21....δ2r?... ∪M δm1....δm r 于是，原定理得证。 这样根据并集成员表的定义知： 于是作最小集的并集 T＝M δ11....δ1r?M δ21....δ2r?.... ?M δm1....δm r 由命题知M δj1....δj r仅在δj1....δj r行处为1，其余全为0。 * * 每一