离散数学课后习题

一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？()(1)Q=Q→P(2)Q=P→Q(3)P=P→Q(4)P(PQ)=P答：（1），（4）2、下列公式中哪些是永真式？()(1)(┐PQ)→(Q→R)(2)P→(Q→Q)(3)(PQ)→P(4)P→(PQ)答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式?()(1)P=PQ(2)PQ=P(3)PQ=PQ(4)P(P→Q)=Q(5)(P→Q)=P(6)P(PQ)=P答：（2），（3），（4），（5），（6）4、公式x((A(x)B(y，x))zC(y，z))D(x)中，自由变元是()，约束变元是()。答：x,y,x,z5、判断下列语句是不是命题。若是，给出命题的真值。()(1)北京是中华人民共和国的首都。(2)陕西师大是一座工厂。(3)你喜欢唱歌吗？(4)若7+8＞18，则三角形有4条边。(5)前进！(6)给我一杯水吧！答：（1）是，T（2）是，F（3）不是（4）是，T（5）不是（6）不是6、命题“存在一些人是大学生”的否定是()，而命题“所有的人都是要死的”的否定是()。答：所有人都不是大学生，有些人不会死7、设P：我生病，Q：我去学校，则下列命题可符号化为()。(1)只有在生病时，我才不去学校(2)若我生病，则我不去学校(3)当且仅当我生病时，我才不去学校(4)若我不生病，则我一定去学校答：（1）PQ（2）QP（3）QP（4）QP8、设个体域为整数集，则下列公式的意义是()。(1)xy(x+y=0)(2)yx(x+y=0)答：（1）对任一整数x存在整数y满足x+y=0（2）存在整数y对任一整数x满足x+y=09、设全体域D是正整数集合，确定下列命题的真值：(1)xy(xy=y)()(2)xy(x+y=y)()(3)xy(x+y=x)()(4)xy(y=2x)()答：（1）F（2）F（3）F（4）T11、命题“2是偶数或-3是负数”的否定是（）。答：2不是偶数且-3不是负数。12、永真式的否定是（）(1)永真式(2)永假式(3)可满足式(4)(1)--(3)均有可能答：（2）13、公式(PQ)(PQ)化简为（），公式Q(P(PQ))可化简为（）。答：P，QP15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（）。答：x(R(x)Q(x))（二元关系部分）28、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2｝，求(1)R(2)R-1。答：（1）R={1,1,4,2}(2)R1={1,1,2,4}29、举出集合A上的既是等价关系又是偏序关系的一个例子。()答：A上的恒等关系30、集合A上的等价关系的三个性质是什么？()答：自反性、对称性和传递性31、集合A上的偏序关系的三个性质是什么？()答：自反性、反对称性和传递性32、设S={１,２,３,４}，Ａ上的关系Ｒ＝｛〈1,2〉，〈2,1〉，〈2,3〉，〈3,4〉｝求(1)RR(2)R-1。答：RR={〈1,1〉，〈1,3〉，〈2,2〉，〈2,4〉}R-1=｛〈2,1〉，〈1,2〉，〈3,2〉，〈4,3〉｝33、设Ａ＝｛1，2，3，4，5，6｝，Ｒ是A上的整除关系，求R={()}。答：R={1,1,2,2,3,3,4,4,5,5,6,6,1,2,1,3,1,4,1,5,1,6,2,4,2,6,3,6}34、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=2y｝，求(1)R(2)R-1。答：（1）R={1,1,4,2,6,3}(2)R1={1,1,2,4,(3，6}35、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2｝，求R和R-1的关系矩阵。答：R的关系矩阵=000000001000000001R1的关系矩阵=00000001000000000136、集合A={1,2,…,10}上的关系R={x,y|x+y=10,x,yA}，则R的性质为（）。(1)自反的(2)对称的(3)传递的，对称的(4)传递的答：（2）（代数结构部分）37、设A={2,4,6}，A上的二元运算*定义为：a*b=max{a,b}，则在独异点A,*中，单位元是()，零元是()。答：2，638、设A={3,6,9}，A上的二元运算*定义为：a*b=min{a,b}，则在独异点A,*中，单位元是()，零元是()；答：9，3（半群与群部分）39、设〈G,*〉是一个群，则(1)若a,b,x∈G，ax=b，则x=()；(2)若a,b,x∈G，ax=ab，则x=()。答：（1）a1b（2）b40、设a是12阶群的生成元，则a2是()阶元素，a3是()阶元素。答：6,441、代数系统G,*是一个群，则G的等幂元是()。答：单位元42、设a是10阶群的生成元，则a4是()阶元素，a3是()阶元素。答：5，1043、群G,*的等幂元是()，有()个。答：单位元，144、素数阶群一定是()群,它的生成元是()。答：循环群，任一非单位元45、设〈G,*〉是一个群，a,b,c∈G，则(1)若ca=b，则c=()；(2)若ca=ba，则c=()。答：（1）b1a(2)b46、H,,是G,,的子群的充分必要条件是()。答：H,,是群或a，bG，abH，a-1H或a,bG，ab-1H47、群＜A,*＞的等幂元有()个，是()，零元有()个。答：1，单位元，048、在一个群〈G,*〉中，若G中的元素a的阶是k，则a-1的阶是()。答：k49、在自然数集N上，下列哪种运算是可结合的？（）(1)a*b=a-b(2)a*b=max{a,b}(3)a*b=a+2b(4)a*b=|a-b|答：(2)50、任意一个具有2个或以上元的半群，它（）。(1)不可能是群(2)不一定是群(3)一定是群(4)是交换群答：(1)51、6阶有限群的任何子群一定不是（）。(1)2阶(2)3阶(3)4阶(4)6阶答：(3)（数理逻辑部分）二、求下列各公式的主析取范式和主合取范式：1、(P→Q)R解：(P→Q)R(PQ)R(PR)(QR)（析取范式）(P(QQ)R)((PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)（主析取范式）((P→Q)R)(PQR)(PQR)(PQR)(PQR)(PQR)（原公式否定的主析取范式）(P→Q)R(PQR)(PQR)(PQR)(PQR)(PQR)（主合取范式）2、(PR)(QR)P解：(PR)(QR)P（析取范式）(P(QQ)R)((PP)QR)(P(QQ)(RR))(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)（(PR)(QR)P）(PQR)(PQR）（原公式否定的主析取范式）(PR)(QR)P(PQR)(PQR)（主合取范式）3、(P→Q)(RP)解：(P→Q)(RP)(PQ)(RP)（合取范式）(PQ(RR))(P(QQ))R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)（主合取范式）((P→Q)(RP))(PQR)(PQR)(PQR)(PQR)(PQR)（原公式否定的主合取范式）(P→Q)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)（主析取范式）4、Q→(PR)解：Q→(PR)QPR（主合取范式）（Q→(PR)）(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR）（原公式否定的主合取范式）Q→(PR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR）（主析取范式）5、P→(P(Q→P))解：P→(P(Q→P))P(P(QP))PPT(主合取范式)(PQ)(PQ)(PQ)(PQ)（主析取范式）6、(P→Q)(RP)解：(P→Q)(RP)(PQ)(RP)(PQ)(RP)（析取范式）(PQ(RR))(P(QQ)R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)（主析取范式）((P→Q)(RP))(PQR)(PQR)(PQR)(PQR)(PQR)（原公式否定的主析取范式）(P→Q)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)（主合取范式）7、P(P→Q)解：P(P→Q)P(PQ)(PP)QT(主合取范式)(PQ)(PQ)(PQ)(PQ)（主析取范式）8、(R→Q)P解：(R→Q)P(RQ)P(RP)(QP)（析取范式）(R(QQ)P)((RR)QP)(RQP)(RQP)(RQP)(RQP)(PQR)(PQR)(PQR)（主析取范式）((R→Q)P)(PQR)(PQR）(PQR)(PQR)(PQR)（原公式否定的主析取范式）(R→Q)P(PQR)(PQR)(PQR)(PQR)(PQR)（主合取范式）9、P→Q解：P→QPQ（主合取范式）(P(QQ))((PP)Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)（主析取范式）10、PQ解：PQ（主合取范式）(P(QQ))((PP)Q）(PQ)(PQ)(PQ)(PQ）(PQ)(PQ)(PQ)（主析取范式）11、PQ解：PQ（主析取范式）(P(QQ))((PP)Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)（主合取范式）12、（PR）Q解：（PR）Q(PR)Q(PR)Q(PQ)(RQ)（合取范式）(PQ(RR))((PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)