《离散数学课后习题》由会员分享，可在线阅读，更多相关《离散数学课后习题（41页珍藏版）》请在金锄头文库上搜索。
1、如果您需要使用本文档，请点击下载按钮下载!一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？()(1)Q=QP (2)Q=PQ (3)P=PQ (4)P(PQ)=P 答：（1），（4）2、下列公式中哪些是永真式？( )(1)(PQ)(QR) (2)P(QQ) (3)(PQ)P (4)P(PQ)答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=PQ (2) PQ=P (3) PQ=PQ (4)P(PQ)=Q (5) (PQ)=P (6) P(PQ)=P答：（2），（3），（4），（5），（6）4、公式x(A(x)B(y，x) $z C(y，z)D(x)
2、中，自由变元是( )，约束变元是( )。答：x,y, x,z5、判断下列语句是不是命题。若是，给出命题的真值。( )(1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。(3) 你喜欢唱歌吗？ (4) 若7+818，则三角形有4条边。(5) 前进！ (6) 给我一杯水吧！ 答：（1） 是，T （2） 是，F （3） 不是（4） 是，T （5） 不是 （6） 不是6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。答：所有人都不是大学生，有些人不会死7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。(1)只有在生病时，我才不去学校 (2
3、) 若我生病，则我不去学校(3)当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1） （2） （3） （4）1 / 41如果您需要使用本文档，请点击下载按钮下载!8、设个体域为整数集，则下列公式的意义是( )。(1) x$y(x+y=0) (2) $yx(x+y=0)答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=09、设全体域D是正整数集合，确定下列命题的真值：(1) x$y (xy=y)()(2) $xy(x+y=y)()(3) $xy(x+y=x) ()(4) x$y(y=2x) ()答：（1） F （2） F （3）F （4
4、）T11、命题“2是偶数或-3是负数”的否定是（ ）。答：2不是偶数且-3不是负数。12、永真式的否定是（ ）(1) 永真式(2) 永假式(3) 可满足式(4) (1)-(3)均有可能答：（2）13、公式(PQ)(PQ)化简为（ ），公式 Q(P(PQ)可化简为（ ）。答：P ，QP15、令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=, (2) R=,29、举出集合A上的既是等价关系
5、又是偏序关系的一个例子。()答：A上的恒等关系30、集合A上的等价关系的三个性质是什么？( )答：自反性、对称性和传递性31、集合A上的偏序关系的三个性质是什么？( )答：自反性、反对称性和传递性2 / 41如果您需要使用本文档，请点击下载按钮下载!32、设S=,，上的关系1,2，2,1，2,3，3,4求(1)RR (2) R-1 。答：RR =1,1，1,3，2,2，2,4R-1 =2,1，1,2，3,2，4,333、设1，2，3，4，5，6，是A上的整除关系，求R= ()。答：R=,34、设1,2,3,4,5,6，B=1,2,3，从到B的关系x,y|x=2y，求(1)R (2) R-1 。
6、答：（1）R=, (2) R=,(3，635、设1,2,3,4,5,6，B=1,2,3，从到B的关系x,y|x=y2，求R和R-1的关系矩阵。答：R的关系矩阵= R的关系矩阵=36、集合A=1,2,10上的关系R=|x+y=10,x,yA，则R 的性质为（ ）。(1) 自反的(2) 对称的 (3) 传递的，对称的 (4) 传递的答：（2）（代数结构部分）37、设A=2,4,6，A上的二元运算*定义为：a*b=maxa,b，则在独异点中，单位元是( )，零元是( )。答：2，638、设A=3,6,9，A上的二元运算*定义为：a*b=mina,b，则在独异点中，单位元是( )，零元是( )；答：9
7、，3（半群与群部分）3 / 41如果您需要使用本文档，请点击下载按钮下载!39、设G,*是一个群，则(1) 若a,b,xG，ax=b，则x=( )；(2) 若a,b,xG，ax=ab，则x=( )。答： （1） ab （2） b40、设a是12阶群的生成元， 则a2是( )阶元素，a3是( )阶元素。答： 6,441、代数系统是一个群，则G的等幂元是()。答：单位元42、设a是10阶群的生成元， 则a4是( )阶元素，a3是( )阶元素。答：5，1043、群的等幂元是()，有()个。答：单位元，144、素数阶群一定是( )群, 它的生成元是( )。答：循环群，任一非单位元45、设G,*是一个群
8、，a,b,cG，则(1) 若ca=b，则c=( )；(2) 若ca=ba，则c=( )。答：（1） b (2) b46、是的子群的充分必要条件是( )。答：是群 或 a，b G， abH，a-1H 或 a,b G，ab-1H 47、群A,*的等幂元有()个，是()，零元有()个。答：1，单位元，048、在一个群G,*中，若G中的元素a的阶是k，则a-1的阶是( )。答：k49、在自然数集N上，下列哪种运算是可结合的？（ ） (1) a*b=a-b(2) a*b=maxa,b(3) a*b=a+2b(4) a*b=|a-b|答：(2)50、任意一个具有2个或以上元的半群，它（ ）。(1) 不可能
9、是群(2) 不一定是群(3) 一定是群 (4) 是交换群4 / 41如果您需要使用本文档，请点击下载按钮下载!答：(1)51、6阶有限群的任何子群一定不是（ ）。(1) 2阶(2) 3 阶 (3) 4 阶 (4) 6 阶答：(3)（数理逻辑部分）二、求下列各公式的主析取范式和主合取范式： 1、(PQ)R 解：(PQ)R(PQ )R(PR)(QR) （析取范式）(P(QQ)R)(PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)（主析取范式）(PQ)R)(PQR)(PQR)(PQR) (PQR)( PQR)（原公式否定的主析取范式）(PQ)R(PQR)(PQR)(
10、PQR)(PQR)(PQR)（主合取范式）2、(PR)(QR)P 解： (PR)(QR)P（析取范式）(P(QQ)R)(PP)QR)(P(QQ)(RR)(PQR)(PQR)(PQR)(PQR)( PQR)( PQR)(PQR)(PQR) (PQR)(PQR)(PQR)(PQR) (PQR)(PQR) (主析取范式)（(PR)(QR)P）(PQR)(PQR）（原公式否定的主析取范式）(PR)(QR)P (PQR)(PQR)（主合取范式）3、(PQ)(RP)解：(PQ)(RP)(PQ)(RP)（合取范式）(PQ(RR)(P(QQ)R)5 / 41如果您需要使用本文档，请点击下载按钮下载!(PQR)
11、(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)（主合取范式） (PQ)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)（原公式否定的主合取范式）(PQ)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)（主析取范式）4、Q(PR) 解：Q(PR)QPR（主合取范式）（Q(PR)）(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR）（原公式否定的主合取范式）Q(PR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR）（主析取范式）5、P(P(QP) 解：P(P(QP)P(P(QP)PP T (主合取范式)(PQ)(PQ)(P
12、Q)(PQ)（主析取范式）6、(PQ)(RP)解： (PQ)(RP)(PQ)(RP)(PQ)(RP)（析取范式）(PQ(RR)(P(QQ)R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)（主析取范式）(PQ)(RP)(PQR)(PQR)(PQR)6 / 41如果您需要使用本文档，请点击下载按钮下载!(PQR)(PQR)（原公式否定的主析取范式）(PQ)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)（主合取范式）7、P(PQ) 解：P(PQ)P(PQ)(PP)QT(主合取范式)(PQ)(PQ)(PQ)(PQ)（主析取范式）8、(RQ)P解：(RQ)P(RQ )P(RP)(QP) （析取范式）(R(QQ)P)(RR)QP)(RQP)(RQP)(RQP)(RQP)(PQR)(PQR)(PQR)（主析取范式）(RQ)P)(PQR)(PQR）(PQR) (PQR)(PQR)（原公式否定的主析取范式）(RQ)P(PQR)(PQR)(PQR)(PQR)(PQR)（主合取范式）9、PQ 解：PQPQ（主合取范式）(P(QQ)(PP)Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)（主析取范式）10、PQ 解： PQ （主合取范式）(P(QQ)(PP)Q）(
