离散数学重要公式定理汇总.ppt

本节要求：1.准确掌握这五个性质的定义。2.熟练掌握五个性质的判断和证明。R是A中自反的??x(x?A?xRx)R是A中反自反的??x(x?A?x,x?R)R是A上对称的??x?y((x?A?y?A?xRy)?yRx)R是A上反对称的??x?y((x?A?y?A?xRy?yRx)?x=y)??x?y((x?A?y?A?x?y?xRy)?yx)R在A上传递??x?y?z((x?A?y?A?z?A?xRy?yRz)?xRz)注意性质表达式的前件为F时此表达式为T，即R是满足此性质的。(自反和反自反性除外)从关系的有向图自反性反自反性对称性传递性反对称性每个结点都有环主对角线全是1每个结点都无环主对角线全是0不同结点间如果有边,则有方向相反的两条边.是以对角线为对称的矩阵不同结点间,最多有一条边.以主对角线为对称的位置不会同时为1如果有边a,b,b,c,则也有边a,c.或前件为假如果aij=1,且ajk=1,则aik=1性质判定从关系的矩阵若R?A×BS?B×CT?B×C则有证明⑴任取a,c∈R○(S∪T)1??b(b∈B∧a,b∈R∧b,c∈S∪T)2??b(b∈B∧a,b∈R∧(b,c∈S∨b,c∈T)）3??b((b∈B∧a,b∈R∧b,c∈S)∨4(b∈B∧a,b∈R∧b,c∈T))5??b(b∈B∧a,b∈R∧b,c∈S)∨6?b(b∈B∧a,b∈R∧b,c∈T)7?a,c∈R?S∨a,c∈R?T8?a,c∈(R?S)∪(R?T)9所以R○(S∪T)=(R?S)∪(R?T)10R是从A到B的关系，则2.RC的有向图：是将R的有向图的所有边的方向颠倒一下即可。3.RC的矩阵M=(MR)T即为R矩阵的转置。如101000011011MR=3×40001010114×3101=MRc性质令R、S都是从X到Y的关系，则(RC)C=R(R∪S)C=RC∪SC。(R∩S)C=RC∩SC。(R－S)C=RC－SC。R?S?RC?SC。(~R)C=~RC(R?S)C=SC?RC。(注意≠RC?SC)7.令R是从X到Y的关系，S是Y到Z的关系，则R是对称的，当且仅当RC=RR是反对称的，当且仅当R∩RC?IA。8.R是A上关系，则大一上离散数学重要公式定理汇总Formula**基本的等价公式⑴对合律??P?P⑵幂等律P∨P?PP∧P?P⑶结合律P∨(Q∨R)?(P∨Q)∨RP∧(Q∧R)?(P∧Q)∧R⑷交换律P∨Q?Q∨PP∧Q?Q∧P⑸分配律P∨(Q∧R)?(P∨Q)∧(P∨R)P∧(Q∨R)?(P∧Q)∨(P∧R)⑹吸收律P∨(P∧Q)?PP∧(P∨Q)?P⑺德．摩根定律?(P∨Q)??P∧?Q?(P∧Q)??P∨?QFormula**同一律P∨F?PP∧T?P1零律P∨T?TP∧F?F2互补律P∨?P?TP∧?P?F3附加：4P?Q??P∨Q5P?Q??Q??P6P?Q?(P?Q)∧(Q?P)7P?Q?(?P∨Q)∧(P∨?Q)8P?Q?(P∧Q)∨(?P∧?Q)9Formula**等价公式(前10个)与集合论的公式比较：对合律~~A?A~A表示A的绝对补集幂等律A∪A?AA∩A?A结合律A∪(B∪C)?(A∪B)∪C；A∩(B∩C)?(A∩B)∩C交换律A∪B?B∪AA∩B?B∩A分配律A∪(B∩C)?(A∪B)∩(A∪C)A∩(B∪C)?(A∩B)∪(A∩C)吸收律A∪(A∩B)?AA∩(A∪B)?AFormula**德．摩根定律~(A∪B)?~A∩~B1~(A∩B)?~A∪~B2同一律A∪Φ?A;