永假式的是

Ap→p∨q∨r
Bp→┐p→┐p
C┐q→q∧p
D┐q∨┐p→p∧┐p
二、填空题每空1分，共20分
16在一棵根树中，仅有一个结点的入度为______，称为树根，其余结点的入度均为______。
17A1234上二元关系R〈2，4〉，〈3，3〉，〈4，2〉，R的关系矩阵MR中m24______m34______。
18设〈s〉是群，则那么s中除______外，不可能有别的幂等元；若〈s〉有零元，则s______。
19设A为集合，PA为A的幂集，则〈PA，〉是格，若xy∈PA则xy最大下界是______，
最小上界是______。
20设函数fX→Y如果对X中的任意两个不同的x1和x2，它们的象y1和y2也不同，我们说f是______函数，如果ra
fY，则称f是______函数。
21设R为非空集合A上的等价关系，其等价类记为〔x〕R。xy∈A，若〈xy〉∈R，则
〔x〕R与〔y〕R的关系是______，而若〈xy〉R，则〔x〕R∩〔y〕R______。22使公式xyAx∧ByxAx∧yBy成立的条件是______不含有y，
______不含有x。
23设Mxx是人，Dsx是要死的，则命题“所有的人都是要死的”可符号化为x______
其中量词x的辖域是______。
24若H1∧H2∧…∧H
是______，则称H1H2…H
是相容的，若H1∧H2∧…∧H
是______，
则称H1H2…H
是不相容的。
25判断一个语句是否为命题，首先要看它是否为
，然后再看它是否具有唯一
的
。
三、计算题共30分
264分设有向图GVE如下图所示，试用邻接矩阵方法求长度为2的路的总数和回路总数。
275设AabPA是A的幂集，是对称差运算，可以验证PA，是群。设
是正整数，求a1ba
a
b
a
286分设A12345A上偏序关系R〈1，2〉，〈3，2〉，〈4，1〉，〈4，2〉，〈4，3〉，〈3，5〉，〈4，5〉∪IA
精品文档
f精品文档
1作出偏序关系R的哈斯图2令B1235，求B的最大，最小元，极大、极小元，上界，下确界，下界，下确界。296分求┐P→QP→┐Q的主合取范式并给出所有使命题为真的赋值。305分设带权无向图G如下，求G的最小生成树T及T的权总和，要求写出解的过程。
314分求公式┐xFxy→yGxy∨xHx的前束范式。四、证明题共20分326分设T是非平凡的无向树，T中度数最大的顶点有2个，它们的度数为kk≥2证明T
中至少有2k2片树叶。338分设A是非空集合，F是所有从A到A的双射函数的集合，是函数复合运算。
证明：〈F〉是群。346分在个体域Da1a2…，a
中证明等价式：
xAx→Bxr