离散数学习题课PPT课件.ppt

习题课,1,2,容易观察到000和010是A的成假赋值，而他们是B的成真赋值。,3,2、用等值演算法判断下列公式的类型,4,解：,所以（1）为重言式,5,所以2为矛盾式。,6,3、用等值演算法求公式的主析取范式或主和取范式1）求公式,的主析取范式,2）求公式,的主合取范式,3）求公式,的主析取范式，再由主析取范式求出主合取范式。,7,8,9,4、用等值演算方法求解实际问题讨论派遣方案：某公司派小李或小张去上海出差。若派小李去，则小赵要加班。若派小张去，小王也得去。小赵没加班。问公司是如何派遣的？解答与分析解此类问题的步骤如下：1）先将简单命题（或语句）符号化；2）写出复合命题（或公式）；3）求成真赋值；4）求解方法很多：观察法，等值演算法，主析取范式法或吸取范式法等。,10,在本题中，具体步骤如下。1）令p：派小李去上海出差；q：派小张去上海出差；r：小赵要加班；s：小王也去上海；2）,11,3）用等值演算法讲A化简后，就能找出成真赋值了。,本式的成真赋值为0101，所以派遣方案为：派小张和小王去上海出差，只有这一种方案。,12,5、判断下列公式的类型,13,解：记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也为非永真式的可满足式。,14,6、构造下面推理的证明，个体域为中国人组成的集合。1）东北人都不怕冷。王国端怕冷。所以王国端不是东北人。2）偶数能被2整除。8是偶数。所以8能被2整除。,15,16,7、化简下列集合(1)(B-(AC)(ABC)(2)(AB)-(C-(AB)(3)(AB)B）-(AB),17,解：r(R)=，s(R)=，R2=R5=，R3=，R4=，t(R)=，,8、设R=，求r(R)、s(R)和t(R).,18,9、已知A、B、C是三个集合，证明A-(BC)=(A-B)(A-C).,证明：xA-（BC）xAx（BC）xA（xBxC）（xAxB）（xAxC）x（A-B）x（A-C）x（A-B）（A-C）A-（BC）=（A-B）（A-C）,19,10、证明整数集I上的模m同余关系R=|xy(modm)是等价关系。其中，xy(modm)的含义是x-y可以被m整除.,证明：1）xI，因为（x-x）/m=0，所以xx(modm)，即xRx。2）x，yI，若xRy，则xy(modm)，即（x-y）/m=kI，所以（y-x）/m=-kI，所以yx(modm)，即yRx。3）x，y，zI，若xRy，yRz，则（x-y）/m=uI，（y-z）/m=vI,于是（x-z）/m=（x-y+y-z）/m=u+vI，因此xRz。,20,11、设集合，上的二元关系,，是否上的等价关系?,解：从的表达式可知，对任意xA，（x，x）R，即具有自反性。由的表达式，对任意x，yA,(x,y)R,则(y,x)，具有对称性。又有对任意x，y，z，(x，y)R且（y，），则（x，），于是具有传递性。故是上的等价关系。,21,12、在1到10000之间既不是某个整数的平方,也不是某个整数的立方的数有多少?,解:设E=xN|1x10000,|E|=10000A=xE|x=k2kZ,|A|=100B=xE|x=k3kZ,|B|=21则|(AB)|=|E|-|AB|=|E|-(|A|+|B|-|AB|)=10000-100-21+4=9883注意AB=xE|x=k6kZ,|AB|=4.#,22,13、G是一个群，BG非空，如果|B|有限，那么只要*在B上封闭，必定是的子群。,证：bB，由*在B上封闭，则b2=b*b，b3=b2*b,.,B，由B有限，必存在i1，则由bj-i=b*bj-i-1可知bj-i-1为b的逆元，若j-i=1，则由bi=bi*b可知b为幺元，以自身为逆，总之b均在B中有逆元，因此，B为G的子群。,23,14、在群中，除幺元e外，不可能有任何别的等幂元(即a*a=a),证：e*e=e，e为等幂元现设aA，ae且a*a=a则有a=e*a=(a-1*a)*a=a-1*(a*a)=a-1*a=e,24,15、给出是环的代数结构的例子,数环Z,Q,R,C关于普通数的加法与乘法,25,16、设n是正整数，Sn是n的正因子的集合.D为整除关系，则偏序集构成格.x,ySn，xy是lcm(x,y)，即x与y的最小公倍数.xy是gcd(x,y)，即x与y的最大公约