离散数学总复习

离散数学 总复习 离散数学 总复习 1 12 23 34 43 14 14 24 3 1 2 3 4 ACovA p11 11 设设 是是 上上的的偏偏序序关关系系 则则 解解 知知识识点点 CovAx yyx p偏偏序序关关系系确确定定元元素素 盖盖住住元元素素 12 3 4 3 1 4 2 4 3 A AA 12 12 设设是是一一个个代代数数系系统统 为为定定义义在在 上上的的二二元元运运算算 若若 则则称称运运算算 为为可可交交换换的的 M若若 则则称称运运算算 为为可可结结合合的的 若若 则则称称运运算算 为为等等幂幂的的 x yA xyyx x y zA xyzxyz xA xxx QQ374289236 离散数学 总复习 离散数学 总复习 e若若 则则称称 为为幺幺元元 若若 则则称称 为为零零元元 xA exxex xAxx 1S 13 13 设设是是一一个个代代数数系系统统 若若满满足足 2 3 S 则则称称是是一一个个独独异异点点 运运算算封封闭闭 结结合合律律成成立立 有有幺幺元元 G S G S S 14 14 是是一一个个群群 是是的的平平凡凡子子群群 则则或或者者 e G G G 15 15 群群的的运运算算表表中中每每一一行行或或每每一一列列都都是是 中中元元素素的的 置置换换 n nKE 16 16 个个结结点点的的无无向向完完全全图图的的边边数数 1 1 2 nn 17 17 一一棵棵树树有有一一个个结结点点的的度度数数为为2 2 二二个个结结点点的的度度数数为为3 3 三三个个结结点点的的 度度数数为为4 4 则则有有个个结结点点的的度度数数为为1 1 解解 知知识识点点 树树的的基基本本概概念念及及图图的的基基本本定定理理 握握手手定定理理 x设设有有 个个结结点点的的度度数数为为1 1 1 1 22 33 42123 1 xx 则则有有 10 1Tevev 树树 的的边边数数 与与结结点点数数 的的关关系系 1 deg 2 v i i ve QQ374289236 离散数学 总复习 离散数学 总复习 QPQR 四四 求求合合式式公公式式的的主主析析取取 主主合合取取范范式式 解解 QPQR QPQR QPQR PQQR PQRPQRPQR 111011010 mmm 110101100001000 MMMMM PQRPQRPQR PQRPQR 1 2E 五五 已已知知论论域域 ab 1 f 1 1 P 1 TTF22 2 f 1 1 2 P 2 1 P 2 2 P F 1 P a f aP b f b求求 2 xy P x yP f xf y QQ374289236 离散数学 总复习 离散数学 总复习 1 P a f aP b f b 2 xy P x yP f xf y 解解 1 1 2 2 PfPf 1 2 2 1 PP TFF 1 1 2 2 xP xP f xfP xP f xf 1 1 1 1 1 2 1 2 PP ffPP ff 2 1 2 1 2 2 2 2 PP ffPP ff 1 1 2 2 1 2 2 1 PPPP 2 1 1 2 2 2 1 1 PPPP FFTT TTFF FTF QQ374289236 离散数学 总复习 离散数学 总复习 六六 用用推推理理规规则则证证明明以以下下论论证证 所所有有有有理理数数是是实实数数 某某些些有有理理数数 是是整整数数 因因此此某某些些实实数数是是整整数数 证证明明 Q xxxxxxRI设设为为有有理理数数 为为实实数数 为为整整数数 QRxxx xxQI x xxRI x 1 x QIxxP 2 Q aI a 1 ES 3 Q a 2 TI 4 I a 2 TI 5 x QRxxP 6 Q aR a 5 US 7 R a 8 R aI a 4 7 TI 3 6 TI 9 x RIxx 8 EG QQ374289236 离散数学 总复习 离散数学 总复习 Aa b c dA Ra bb ab cc dr R s R t R 七七 设设 上上的的二二元元关关系系为为 试试求求 解解 R M a b c d abcd 0100 1010 0001 0000 2 RR R MMM o 01000100 10101010 00010001 00000000 o A r RRI U a aa bb ab bb cc cc dd d C s RRR U a bb ab cc bc dd c 1010 0101 0001 0000 QQ374289236 离散数学 总复习 离散数学 总复习 32 R RR MMM o 10100100 01011010 00010001 00000000 o 0101 1010 0000 0000 43 R RR MMM o 01010100 10101010 00000001 00000000 o 1010 0101 0000 0000 2 Ra aa cb bb d 3 Ra ba db ab c 4 Ra aa cb bb d t Ra aa ba ca db ab bb cb dc d QQ374289236 离散数学 总复习 离散数学 总复习 2 3 4 5 7 10 12 13 16 17 19 20 21 22 25 29 30 mod3 ARA Rx yx yAxy RA 八八 已已知知 是是 上上的的 同同余余模模3 3关关系系 即即且且试试求求由由该该等等价价 关关系系 所所确确定定的的 的的一一个个划划分分 解解 mod3 Rx yx yAxyRA 且且是是 上上一一个个等等价价关关系系 22 mod3 R x xA x 23 0 1 2 x xA xk k L 2 5 17 20 29 33 mod3 R x xA x 33 0 1 2 x xA xk k L 3 12 21 30 44 mod3 R x xA x 43 0 1 2 x xA xk k L 4 7 10 13 16 19 22 25 234 RRR A R 2 5 17 20 29 3 12 21 30 4 7 10 13 16 19 22 25 QQ374289236 离散数学 总复习 离散数学 总复习 Aa bP A P A 九九 求求出出上上的的包包含含关关系系 证证明明包包含含关关系系是是偏偏序序关关系系 并并画画出出其其哈哈斯斯图图 问问是是否否为为全全序序集集 解解 P Aaba b aba baa aa bbbba ba ba b CovP A abaa bba b a b a b P A 由由哈哈斯斯图图可可以以看看出出 不不是是全全序序集集 QQ374289236 离散数学 总复习 离散数学 总复习 1 1 2 3 4 AA 十十 设设 上上的的偏偏序序关关系系如如图图 画画出出其其哈哈斯斯图图 说说明明此此 偏偏序序关关系系是是否否为为全全序序关关系系 12 3 4 2 AAp 已已知知偏偏序序集集哈哈斯斯图图如如图图所所示示 求求出出 上上的的偏偏序序关关系系 解解 1 2 3 4 4 1CovA 3 4 1 2 Ap 由由哈哈斯斯图图可可以以看看出出 是是全全序序集集 1 3 2 4 解解 1 3 1 4 3 2 CovA Q 1 1 2 2 3 3 4 4 1 3 1 4 3 2 1 2 p QQ374289236 离散数学 总复习 离散数学 总复习 十十一一 证证明明以以下下两两个个图图同同构构 证证明明 GG ab c d a b c d GV EGV E 给给图图和和的的结结点点标标上上记记1 1号号如如图图 1 1 2aa bb ccVgdVd 作作的的映映射射 ijij eevEggvEvv 且且满满足足若若 则则 GV EGV EGG 所所以以图图和和同同构构 即即 QQ374289236 离散数学 总复习 离散数学 总复习 GKruskal十十二二 对对于于图图利利用用算算法法求求出出一一棵棵最最小小生生成成树树 1 1 2 4 5 5 5 4 7 36 4 4 46 5 5 6 6 解解 1 1 2 3 3 4 4 4 5 6 0 11234 445630 C T QQ374289236 离散数学 总复习 离散数学 总复习 GaGHy yaay yG HG 十十三三 设设是是群群 对对任任一一 令令 试试 证证明明是是子子群群 证证明明HG显显然然 1x yHaGx aax y aay 有有使使得得 xyaxya xay axy xyH 2 HG运运算算 在在 中中显显然然满满足足结结合合律律 在在 中中结结合合律律成成立立 3 Gee aa eaeH 中中的的幺幺元元 使使 xH exx ex 并并使使 4 xH x aax 有有 11 xxax 11 xaxx 11 axxa 1 xH HG 因因此此 是是子子群群 QQ374289236 离散数学 总复习 离散数学 总复习 SSab aaa bbbababab 十十四四 如如果果是是半半群群 且且 是是可可交交换换的的 证证明明 若若 中中有有元元素素 使使得得 则则 证证明明 S 封封闭闭 结结合合律律成成立立的的半半群群代代数数系系统统是是 abSaaa b bb abab abab ab ab aabb aabb ab 4 10 CGx xxCG abi cdiCabicdi acbdadbc iG G gg g g 十十五五 设设 是是复复数数集集合合 上上的的二二元元运运算算 为为复复数数的的普普通通乘乘法法即即 试试构构造造 关关于于普普通通乘乘法法 运运算算表表 并并证证明明 代代数数系系统统是是一一个个群群 QQ374289236 离散数学 总复习 离散数学 总复习 4 10 Gx xxC 解解 11 ii g 11ii 1 1 i i 11ii 11ii i i 11 i i 11 1 g运运算算 封封闭闭 2 CG结结合合律律在在 上上成成立立 则则在在 上上自自然然成成立立 3 g运运算算的的幺幺元元为为1 1 11 xGxxx gg使使 4 G中中的的每每个个元元素素有有逆逆元元 1 11 1 11 1 ii 1 ii Gg因因此此是是一一个个群群 QQ374289236 离散数学 总复习 离散数学 总复习 1 GuGGaba ub G g十十六六 设设是是群群 在在 中中定定义义新新的的运运算算 证证明明 也也是是群群 证证明明 1 1 a bG aba ubG ggG关关于于运运算算封封闭闭 1 2 a b cG abca ubc gg 11 a ubuc gggg 11 a ub uc gg gg 1 ab cab uc gg 11 a ub uc gggg 11 a ub uc gg gg abcab c G关关于于运运算算 结结合合律律成成立立 1 3 GuaG uau uae aa ggg关关于于运运算算 的的幺幺元元为为 即即 1 aua uua ea ggg uaaua eGg 为为 关关于于运运算算 的的幺幺元元 11 4 C aG aau auaa gg g 关关于于运运算算 的的逆逆元元记记为为其其中中为为 关关于于 运运算算 的的逆逆元元 11 C a aa uu auu gg gg QQ374289236 离散数学 总复习 离散数学 总复习 ABC CA ABC 十十七七 有有 三三人人 这这三三人人中中 一一位位是是经经理理 一一位位是是会会计计 一一位位是是司司机机 已已知知 的的年年龄龄比比会会计计大大 和和司司机机的的年年龄龄不不相相同同 司司机机的的年年 龄龄 逻逻辑辑小小 比比B B小小 试试判判断断 三三人人确确切切 问问题题 的的身身份份 解解 ABC 经经理理 会会计计 司司机机 F FFT F B 的的年年龄龄司司机机的的年年龄龄会会计计的的年年龄龄 B是是经经理理 T T F F ABC因因此此 是是会会计计 是是经经理理 是是司司机机 QQ374289236 离散数学 总复习 离散数学 总复习 61 6十十八八 一一个个六六面面体体的的 个个面面 分分别别标标有有的的六六个个数数字字 它它放放置置的的状状态态不不同同 可可见见到到的的数数字字也也不不同同 请请判判断断出出每每个个相相对对面面 的的数数字字分分别别是是与与 逻逻辑辑小小问问题题 与与 与与 解解14与与26与与35与与 QQ374289236 离散数学 总复习 离散数学 总复习 十十九九 张张三三 李李四四 王王五五三三位位同同学学中中有有一一人人在在别别人人不不在在 时时为为集集体