资源描述
2 0 2 1 -6 -1 6 1 例 3 给 出 下 列 公 式 的 真 值 表PRQP )(RQP QP RQP A000 100 010 110 001 101 011 111 00000011 11111110 11110000成 真 指 派 ： 1 0 0 ， 1 0 1 ， 1 1 0 ， 1 1 1 2 0 2 1 -6 -1 6 2 例 4 试 求 下 面 公 式 的 主 析 取 （ 主 合 取 ） 范 式 ， 并 写出 成 真 指 派 和 成 假 指 派 。( ) ( )P Q Q P ( ) ( )P Q Q P ( )P Q Q P ( ) ( ( ) ( ( )P Q Q P P P Q Q ( ) ( ) ( )P Q P Q P Q 0,2,3 1( )P Q 成 真 指 派 ： 00， 10， 11成 假 指 派 ： 01 2 0 2 1 -6 -1 6 3 例 5 试 证 PQQPPQ )( ) ( )Q P P P Q 证明)( QPPQ )()( QQPPQ )( QPPQ PQ PQ ( ( )Q P P Q 2 0 2 1 -6 -1 6 4 例 1 符 号 化 下 列 命 题a)不 是 所 有 的 男 人 都 比 女 人 高 。 M(x):x是 男 人 ， W(x):x是 女 人 ， H(x,y):x比 y高 。),()()( yxHyWyxMx 2 0 2 1 -6 -1 6 5 例 2 证 明) ( ( ) ( ), ( ) ( )a x A x B x x B x xA x 1) ( ( ) ( ) 2) ( ) ( ) 1)3) ( ) 4) ( ) 3)5) ( ) 2)4) 6) ( ) 5)x A x B x PA u B u USx B x PB u USA u TxA x EG 证 明 2 0 2 1 -6 -1 6 6 例 1 求 集 合 的 幂 集 )( xxP )(P ),( P , , 2 0 2 1 -6 -1 6 7 例 2 n 个 元 素 的 集 合 上 ， 可 以 定 义 多 少 个 关 系 ？ 设 集 合 X,Y, |X|=m, |Y|=n， 可 以 定 义 多 少 个从 X到 Y的 函 数 ？)2( 2n nm (|Y|X| ) 2 0 2 1 -6 -1 6 8 例 3 对 任 意 两 个 集 合 A, B,试 证 BABAA )(证明对于任意的x )( BAAx )( BxAxAxxx )( BAxAxxx )( BAxAxxx )( BxAxAxxx BxAxxx BAx 因为 x 是任意的,所以有)()( BAxBAAxx 的真值为T,BABAA )(因此 2 0 2 1 -6 -1 6 9 例 4 判 断 关 系 的 性 质 100 010 011 1RM abc 1RR1 是自反的、反对称、传递的。 ,1 ccbbbaaaR 2 0 2 1 -6 -1 6 1 0 例 5 求 关 系 的 闭 包 , cbaX , ccbbaaR XIRRr )( , cbbaR, cbba , ccbbaa CRRRs )( , bcabcbba 解 ： 2 0 2 1 -6 -1 6 1 1 例 5 （ 续 ）, cbaX , cbbaR )3()2()( RRRRt , cacbba , cacbba ,)2( caR )3(R 2 0 2 1 -6 -1 6 1 2 例 7 设 A=1 ,2 ,3 , 求 出 A上 所 有 的 等 价 关 系解 ： 先 求 A的 各 种 划 分 ： 12 3512 32 12 33 12 3412 31设 对 应 于 i 的 等 价 关 系 为 Ri ,则 ：R 1=, = IAR2=, IAR3=, IAR4=, IAR5=, , IA 2 0 2 1 -6 -1 6 1 3 例 8 画 出 哈 斯 图 RcbaP , a b c, ca , cb , cba, ba 2 0 2 1 -6 -1 6 1 4 例 9 求 极 大 （ 小 ） 元 ， 最 大 （ 小 ） 元 、 上 （ 下 ）界 ， 上 （ 下 ） 确 界 ab c d ef gh ij k 极 大 元 ： j,k极 小 元 :a,b,e最 大 元 ： 无最 小 元 ： 无B=a,b,c,d,e,f,g上 界 ： h,i,j,k下 界 ： 无无 上 （ 下 ） 确 界 2 0 2 1 -6 -1 6 1 5 例 1 0 判 断 函 数 的 类 型 1x 1y2y3y2x3x2x3x1x 3y2y1y4x 入 射 映 射 函 数 双 (入 、 满 )射满 射 4y 1y2x3x1x 2y3y4y1x2x3x 1y2y3y 2 0 2 1 -6 -1 6 1 6 例 1 1 求 复 合 函 数,3,2,1 qpYX , baZ ,3,2,1 qppf fg 求, bqbpg ,3,2,1 bbbfg 2 0 2 1 -6 -1 6 1 7 例 1 2 求 复 合 函 数,3,2,1 qpYX , baZ ,3,2,1 qppf fg 求, bqbpg ,3,2,1 bbbfg 2 0 2 1 -6 -1 6 1 8 例 : 求 幺 元 、 零 元 、 逆 元 N, I, Q, R上 的 普 通 加 法 + 和 乘 法 *+： 幺 元 0 ， a-1 = -a；*： 幺 元 1 ， 零 元 0 ， a-1 = 1 /a； 命 题 公 式 集 合 上 的 和 ： 幺 元 F， 零 元 T ： 幺 元 T， 零 元 F 幂 集 P(S)上 的 和 ： 幺 元 ， 零 元 S： 幺 元 S， 零 元 2 0 2 1 -6 -1 6 1 9 例 1G 是一个有 15 条边的简单图， 有 13 条边，请问 G 中有多少个结点? G解：共有 15 + 13 = 28 条边，GG 是一个完全图，它的结点数与 G 相同，设为 n，根据定理4，GG n(n-1)/2 = 28n = 8 2 0 2 1 -6 -1 6 2 0 例 3请画出 4 个顶点 3 条边的所有可能不同构的无向简单图？ 2 0 2 1 -6 -1 6 2 1 例 4若无向图 G 中恰有两个奇数度结点，则这两个结点必是连通的。设 G 中 两 个 奇 数 度 结 点 分 别 为 u ,v。 若 u 与 v 不 连 通 ,则 至 少 有 两 个 连 通分 支 G1 和 G2， u G1,v G2。 于 是 G1 和 G2 各 含 一 个 奇 数 度 结 点 ，这 与 握 手 原 理 的 推 论 矛 盾 ，因 此 u 与 v 必 是 连 通 的 。证明试证 2 0 2 1 -6 -1 6 2 2 例 6 判 断 下 列 图 哪 些 是 E 图 、 H图 ？EE非 H H非 2 0 2 1 -6 -1 6 2 3 例 7 证 明设 G 有 r 个面，当v = 3, e = 2时， 3v-6 显然成立。若 e 3, 则每一个面至少由 3 条边围成，所以re 32 er 32 eevrev 322 32 ev ev 36 63 ve 设 G 是 一 个 有 v 个 结 点 , e 条 边 的 连 通 简 单 平 面图 ， 若 v 3， 则 有 v 。证明 2 0 2 1 -6 -1 6 2 4 例 1 0 求 图 的 最 小 生 成 树ACB D E1 234 5 67 ABC DE1 24 6 2 0 2 1 -6 -1 6 2 5 例 1 1 无 向 树 T有 7 片 树 叶 , 3 个 3 度 顶 点 ,其 余 的都 是 4 度 顶 点 ， 则 T有 几 个 4 度 顶 点 ？ 解 :设 T有 x个 4 度 顶 点 顶 点 度 数 之 和 ： 7 +3 *3 +4 x 由 树 的 性 质 可 得 总 边 数 ： 7 +3 +x-1 由 握 手 原 理 可 得 ： 7 +3 *3 +4 x=2 (7 +3 +x-1 ) x=1
展开阅读全文