离散数学习题课.pptVIP

习 题 课 2、用等值演算法判断下列公式的类型 解： 3、用等值演算法求公式的主析取范式或主和取范式 1）求公式 4、用等值演算方法求解实际问题 讨论派遣方案：某公司派小李或小张去上海出差。若派小李去，则小赵要加班。若派小张去，小王也得去。小赵没加班。问公司是如何派遣的？ 解答与分析 解此类问题的步骤如下： 1）先将简单命题（或语句）符号化； 2）写出复合命题（或公式）； 3）求成真赋值； 4）求解方法很多：观察法，等值演算法，主析取范式法或吸取范式法等。 在本题中，具体步骤如下。 1）令p：派小李去上海出差； q：派小张去上海出差； r：小赵要加班； s：小王也去上海； 2） 3）用等值演算法讲A化简后，就能找出成真赋值了。 5、判断下列公式的类型 解：记1) 2) 3)公式分别为A,B,C. 1)设I为任意的一个解释，个体域为D。若存在x1是D中的一个元素，使得F(x1)为假，则A的前件为假，故A为真。若对于D中任意的一个元素x，F(x)均为真，显然A为真。又由I的任意性可知A为永真式。 2)取解释I，个体域为自然数N，F(x，y)为x小于等于y。在I下B的前件与后件均为真，所以B为真，这说明B不是矛盾式。再取一个解释I1，个体域仍为N，F(x，y)为x=y，在I1下，B 的前件为真而后件为假，所以B为假，这又说明B不是永真式，故B是非永真式的可满足式。 3)C也为非永真式的可满足式。 6、构造下面推理的证明， 个体域为中国人组成的集合。 1）东北人都不怕冷。王国端怕冷。所以王国端不是东北人。 2）偶数能被2整除。8是偶数。所以8能被2整除。 7、化简下列集合 (1)(B-(A∩C))∪(A∩B∩C)  (2)(A∩B)-(C-(A∪B))  (3)((A∪B)∩B）-(A∪B) 解：r(R)={a，b，b，c，c，a，a，a，b，b，c，c}s(R)={a，b，b，c，c，a，b，a，c，b，a，c}R^2= R^5={a，c，b，a，c，b}R^3={a，a，b，b，c，b}R^4={a，b，b，c，c，c}t(R)={a，b，b，c，c，a，a，c，b，a，，a，a，b，b，c，b，c，c} 9、已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C) . 10、证明整数集I上的模m同余关系R={x，y|x?y(mod m)}是等价关系。其中，x?y(mod m)的含义是x-y可以被m整除. 11、设集合Ａ＝｛１，２，３，４｝，Ａ上的二元关系 Ｒ＝｛1,1, 1,4, 2,2, 2,3, 3,2, 3,3, 4,1, 4,4｝，Ｒ是否Ａ上的等价关系? 12、在1到10000之间既不是某个整数的平方,也不是某个整数的立方的数有多少? 解: 设 E={x?N|1?x?10000}, |E|=10000 A={x?E|x=k2?k?Z}, |A|=100 B={x?E|x=k3?k?Z}, |B|=21 则 |~(A?B)|=|E|-|A?B| =|E|-(|A|+|B|-|A?B|) =10000-100-21+4=9883 注意 A?B= {x?E|x=k6?k?Z}, |A?B|=4. # 13、G是一个群，B?G非空，如果|B|有限，那么只要*在B上封闭，B,*必定是a,*的子群。 14、在群A,*中，除幺元e外，不可能有任何别的等幂元(即a*a=a) 15、给出是环的代数结构的例子 数环Z,Q,R,C 关于普通数的加法与乘法 Zn, ⊕, ? Mn(R), +, ? P(B), ⊕, ∩ 16、设n是正整数，Sn是n的正因子的集合. D为整除关系，则偏序集Sn,D构成格. ?x,y∈Sn， x∨y 是lcm(x,y)，即x 与y 的最小公倍数. x∧y 是gcd(x,y)，即x 与y 的最大公约数. 17、下面三个图中哪些是汉密尔顿图,哪些是半汉密尔顿图,为什么? 18、设G是简单平面图,则?(G)?5. 证明: (反证) 设n?6并且??6, 则 2m=?d(v)?n??6n ? m?3n, 与 m?3n-6 矛盾. # LOGO * LOGO 1、证明 不成立 先将A,B通过等值演算化成容易观察真值的情况，再进行判断 方法二：观察法。易知010是前面表达式的成假赋值，而0