离散数学知识点.doc

第一章 1. 将下列命题符号化: 解:令 p :天下雨, q :我骑自行车上班,则(1) 只要不下雨, 我就骑自行车上班?p是q 的充分条件, 所以符号化为:?p→q (2) 只有不下雨, 我才骑自行车上班?p是q 的必要条件, 所以符号化为:q →? p (3) 除非下雨, 否则我就骑自行车上班?p 仍然是 q 的充分条件, 所以符号化为:?p→q (4) 如果下雨, 我就不骑自行车上班 p是?q 的充分条件, 所以符号化为:p →? q 2. 命题: 判断结果惟一的陈述句(注意: 感叹句、祈使句、疑问句都不是命题陈述句中的悖论以及判断结果不惟一确定的也不是命题) ?q 为假当且仅当 p 为真 q 为假 ?q(q为p 的必要条件) “如果 p ,则 q”的不同表述法很多: 若p ,就 q 只要 p ,就 qp 仅当 q 只有 q才p 除非 q,才p或除非 q, 否则非 p 因为…. 所以 ?q 为真当且仅当 p与q 同真或同假 ?p1层?p ?q2层?(p ?q) ?r3层(( ?p ?q) ?r) ?( ?r ?s)4层 7. 双重否定律??A ?A 等幂律: A ?A ?A,A ?A ?A 交换律:A ?B ?B ?A,A ?B ?B ?A 结合律:(A ?B) ?C ?A ?(B ?C)(A ?B) ?C ?A ?(B ?C) 分配律:A ?(B ?C) ?(A ?B) ?(A ?C)A ?(B ?C) ?(A ?B) ?(A ?C) 德· 摩根律: ?(A ?B) ??A ??B ?(A ?B) ??A ??B 吸收律:A ?(A ?B) ?A,A ?(A ?B) ?A 零律:A ?1 ? 1,A ?0 ?0 同一律:A ?0 ? A,A ?1 ?A 排中律:A ??A ?1 矛盾律:A ??A ?0 蕴涵等值式:A ?B ??A ?B 等价等值式:A ?B ?(A ?B) ?(B ?A) 假言易位:A ?B ??B ??A 等价否定等值式:A ?B ??A ??B 归谬论:(A ?B) ?(A ??B) ??A 8. 对偶原理设A,B 为两个命题公式,若 A ?B ,则 A* ? B* . 9. 求公式 A 的范式的步骤: (1) 消去 A 中的?, ?(若存在) (2) 否定联结词?的内移或消去(3) 使用分配律?对?分配(析取范式) ?对?分配(合取范式) (公式的范式存在,但不惟一) 10. 设A含n 个命题变项,则 A 为重言式?A 的主析取范式含 2n 个极小项?A 的主合取范式为 1. A 为矛盾式?A 的主析取范式为 0?A 的主合取范式含 2n 个极大项 A 为非重言式的可满足式?A 的主析取范式中至少含一个且不含全部极小项?A 的主合取范式中至少含一个且不含全部极大项第二章第三章 1. 相对补 A ?B={x|x ?A ?x ?B} =A -(A ?B) 对称差 A ?B=(A ?B) ?(B ?A )=(A ?B) ?(A ?B) 绝对补?A=E ?A 第四章 1. R=M1 S=M2 R°S= M2 * M1 2. (1) (F ?1) ?1 =F (2) dom F ? 1=ran F, ran F ? 1=dom F (1) (F°G)°H=F°(G°H) (2) (F°G) ?