离散数学

离散数学复习题二一、简要回答下列问题：1．请给出P，PQ，PQ的真值表。2．请给出公式蕴涵的定义。举一个例子。3.请给出命题xG(x)的真值规定。4.什么是谓词逻辑公式的解释？5.叙述谓词逻辑公式G与它的Skolem范式之间的区别与联系。6.什么是图的关联矩阵？7.什么是简单路？举一例。8.什么是有向树？举一例9.设G为整数加群，H为5的所有倍数组成的加法群，给出H的所有陪集。10．设Z7={0，1，2，3，4，5，6}，为其上的模7加运算，请给出每个元素的周期。11．什么是交换环？请举一例二、判断下列公式是恒真？恒假？可满足？a)(P(QR))(P(QR))；b)P(P(QP))；c)(QP)(PQ)；d)(PQ)(PQ)。二、R，S是集合A上的两个关系。试证明下列等式：（1）(R•S)-1=S-1•R-1（2）(R-1)-1=R（20分）给P和Q指派真值1，给R和S指派真值0，求出下面命题的真值：a)(P(QR))((PQ)(RS))b)((PQ)R)(((PQ)R)S)c)((PQ)R)((QP)(RS))d)(P(Q(RP)))(QS)四、（18分）设下面所有谓词的定义域都是{a，b，c}。试将下面谓词公式中的量词消除，写成与之等价的命题公式。(1)xR(x)xS(x)(2)x(P(x)Q(x))（3）xP(x)xP(x)五、证明：连通图中任意两条最长的简单路必有公共点。六、设S={G1，…，Gn}是命题公式集合。试求出在不增加新原子的情况下从S出发演绎出的所有命题公式。提示：考虑G1…Gn的主合取范式。离散数学复习题二答案一、简要回答下列问题：1．请给出P，PQ，PQ的真值表。PQPPQPQ011011000111011001002．请给出公式蕴涵的定义。举一个例子。答：设G，H是两个公式，如果解释I满足G，I也满足S，称G蕴涵H。例如：PQ蕴涵P。3．请给出命题xG(x)的真值规定。答：xG(x)取1值对任意xD，G(x)都取1值；xG(x)取0值有一个x0D，使G(x0)取0值。4．什么是谓词逻辑公式的解释？答：词逻辑中公式G的一个解释I，是由非空区域D和对G中常量符号，函数符号，谓词符号以下列规则进行的一组指定组成：1.对每个常量符号，指定D中一个元素；2.对每个n元函数符号，指定一个函数，即指定Dn到D的一个映射；3.对每个n元谓词符号，指定一个谓词，即指定Dn到{0，1}的一个映射。5叙述谓词逻辑公式G与它的Skolem范式之间的区别与联系。答：区别：二者之间不一定等价；联系：二者之间恒假性是等价的。6．什么是图的关联矩阵？答：设G＝（P，L）是有限图，集合P的元数为m，集合L的元数为n，不妨设P（G）＝v1，…，vm，L（G）＝l1，…，ln。矩阵M（G）＝aij称为G的关联矩阵，其中0，当vi不是lj的端点；aij=1，当vi是lj的端点。显然，M（G）是m×n阶矩阵。7．什么是简单路？举一例。答：设G＝（P，L）是图，（v0,v1,…,vn）是G中从v0到vn的路，称此路为简单路，如果1）v0,…,vn－1互不相同；2）v1,…,vn互不相同。8．什么是有向树？举一例。答：有向图G称为有向树（或有根树），如果G中有一点r，并且满足：1）G中每一点v(vr)都恰是一条弧e的起点。2）r不是任一条弧的起点。3）r是根。9．设G为整数加群，H为5的所有倍数组成的加法群，给出H的所有陪集。答：5G+1；5G+2；5G+3；5G+4；5G10.设Z7={0，1，2，3，4，5，6}，为其上的模7加运算，请给出每个元素的周期。答：0的周期是1，其他元素周期是7.11．什么是交换环？请举一例。答：乘法满足交换律的环是交换环，如整数环。二、判断下列公式是恒真？恒假？可满足？a)(P(QR))(P(QR))；b)P(P(QP))；c)(QP)(PQ)；d)(PQ)(PQ)。解：（1）设G=(P(QR))(P(QR))=(P(QR))(P(QR))=(((P(QR))P)((P(QR))QR)=((PP)(PQR))((P(QR))QR)=((PP)(PQR))((PQ)(PR)QR)=((PP)(PQR))(((PQ)Q)((PR)R))=(PQR)(PQR)，其真值表如下：PQRGPQRG00011000001010100100110001101111因此G是可满足的。（2）设G=P(P(QP))=P(P(QP))=PP=T其真值表如下：PQG001011101111因此G是恒真的。G=(QP)(PQ)=(QP)(PQ)=(PQ)(PQ)=F其真值表如下：PQG000010100110因此G是恒假的。G=(PQ)(PQ)=(PQ)((PQ)(QP))=(PQ)((PQ)(QP))=(PQ)(PQ)(PQ)其真值表如下：PQG000011101111因此G是可满足的。三、给P和Q指派真值1，给R和S指派真值0，求出下面命题的真值：a)(P(QR))((PQ)(RS))b)((PQ)R)(((PQ)R)S)c)((PQ)R)((QP)(RS))d)(P(Q(RP)))(QS)解：a)令G=(P(QR))((PQ)(RS))则：TI(G)=(1(10))((11)(00))=00=1b)令G=((PQ)R)(((PQ)R)S)则：TI(G)=((11)0)(((11)0)0)=10=1c)令G=((PQ)R)((QP)(RS))=((PQ)R)(((QP)(PQ))(RS))=(PQR)((QP)(PQ)(RS))则：TI(G)=(110)((11)(11)(00))=11=1d)令G=(P(Q(RP)))(QS)=(P(Q(RP)))(QS)=(P(Q(RP)))(QS)=((P(Q(RP)))(QS))((QS)(P(Q(RP))))=(P(Q(RP)))(QS))((QS)(P(Q(RP))))TI(G)=(1(1(01)))(10))((10)(1(1(01))))=11=1四、设下面所有谓词的定义域都是{a，b，c}。试将下面谓词公式中的量词消除，写成与之等价的命题公式。(1)xR(x)xS(x)(2)x(P(x)Q(x))(3)xP(x)xP(x)解：（1）xR(x)xS(x)等价的命题公式为：R(a)R(b)R(c)(S(a)S(b)S(c))（2）x(P(x)Q(x))等价的命题公式为：(P(a)Q(a))(P(b)Q(b))(P(c)Q(c))（3）xP(x)xP(x)等价的命题公式为：(P(a)P(b)P(b))(P(a)P(b)P(b))五、证明：连通图中任意两条最长的简单路必有公共点。证明：设有限图G=(P，L)是连通的，且有两条最长的简单路：l1：(v1,v2,……vn)l2：(v1’,v2’,……vm’)假设l1和l2无公共点，取l1中一点v1，l2中一点v1’，则由于G连通知必然有一条简单路l3:(x1,x2,……,xk)，其中x1=v1，xk=v1’。设xj是l3中从左往右看第一个l2中的点vh’，得一简单路l4：(x1,x2,……,xj)，设xi是l4中从右往左看第一个l1中的点vg，则又得到一个简单路l5：(xi,xi+1,……,xj)，|l5|1，且l5中除了xi和xj外，没有l1，l2中的点，不妨设|(v1,v2,……xi)||(xi,vg+1,……vn)|,|(v1’,v2’,……xj)||(xj,vh+1’,……vm’)|,则可以取到简单路l6：(v1,v2,……xi,xi+1,……,xj,vh-1’,……v1’),因为|l5|1，所以|l6|min{|l1|,|l2|},这样我们就可以得到一条更长的路，矛盾。因此，命题得证。六、提示：考虑G1…Gn的主合取范式。解：任设一公式G’为从S出发演绎出来的公式。则可知G’为G=G1…Gn的一个逻辑结果。而G有唯一一个与其等价的主合取范式，设为G’’。可设G’’共有m个极大项，则可以知道令G’’取1的解释使这m个极大项也取1。则从S出发的演绎出来的的所有命题公式正是从这m个极大项中任取n(0≤n≤m)个合取组成，共有2m个，其中包括恒真公式这里用1表示。设H为由若干极大项构成的合取公式。现在证明：1)S=H，即G=H。从定义出发，设有一解释I使G=G1…Gn取1值，必使G的主合取范式也取1值。即使每一个极大项都取1值。从而使由若干极大项合取组成的公式H也取1值，则有S=H。2)任意设公式H是S的一个逻辑结果，H是一些极大项的合取。现在要证组成H的极大项都在G的主合取范式G”中。反证法：若不然，假设H中有一个极大项mk不在G的主合取范式中。则取使mk为0的解释I，可有解释I使H取0值。而I使所有不等于mk的极大项都为1，则可有G的主合取范式G’’在I下取1值，即G在I下取1值，这与G=H矛盾。离散数学复习题三一、简要回答下列问题：1．Skolem范式中的母式有什么特点2．设A={1，2，3}，请给出A上的相等关系和全域关系。3．设A={1，2，3，4}，R=IA{（1，2），（2，1），（1，3），（3，1），（2，3），（3，2）}，请给出在等价关系R下的所有等价类。4．请给出PQ，PQ的真值表。5．什么是谓词逻辑公式的解释？6．给出有向树的定义，请举一例7．设R*为非零实数乘法群，请给出R*的单位元及每个元素的逆元。8．设G是3次对称群，H是{I，（12）}做成的子群，求H的三个右陪集。9．设R={0，1，2，3，4，5}是模6环，请给出R中两个不同的零因子10．什么是半序格？请举一例。二、R，S是集合A上的两个关系。试证明下列等式：（1）(R•S)-1=S-1•R-1（2）(R-1)-1=R三、给P和Q指派真值1，给R和S指派真值0，求出下面命题的真值：a)(P(QR))((PQ)(RS))b)((PQ)R)(((PQ)R)S)c)((PQ)R)((QP)(RS))d)(P(Q(RP)))(QS)四、设下面所有谓词的定义域都是{a，b，c}。试将下面谓词公式中的量词消除，写成与之等价的命题公式。(1)xR(x)xS(x)(2)x(P(x)Q(x))(3)xP(x)xP(x)五、若G=(P，L)是有限图，设P(G)，L(G)的元数分别为m，n。证明：n2mC，其中2mC表示m中取2的组合数。六、试证明n个元素的所有置换作成一个群（通常叫做n次对称群）。证明n个元素的所有偶置换作成群（叫做n次交代群）。写出四次交代群中的元素。n次交代群的元数为何？离散数学复习题三答案一、简要回答下列问题：1．Skolem范式中的母式有什么特点？答：母式是合取范式。2．设A={1，2，3}，请给出A上的相等关系和全域关系。答：IA={(1,1),(2,2),(3,3)};