）
┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式，只要其中一项为真，则整个公式为真．可以看到，不论P的值为真或为假，┐P∧（P→┐Q）与P总有一个为真，所以┐P∧（P→┐Q）∨P是永真式．
（5分）（7分）
或用等价演算┐P∧（P→┐Q）∨PT
五．计算题（每小题12分，本题共36分）
15．设集合A1，2，3，4，RxyxyA；xy1或xy0，试（1）写出R的有序对表示；（2）画出R的关系图；（3）说明R满足自反性，不满足传递性．15．（1）R11223344122123323443（2）关系图如图二：
（3分）
图二
（6分）
（3）因为11223344均属于R，即A的每个元素构成的有序对均在R中，故R在A上是
自反的．
（9分）
因有23与34属于R，但24不属于R，所以R在A上不是传递的．
（12分）
f16．设图GV，E，Vv1，v2，v3，v4，v5，Ev1v2，v1v3，v2v4，v3v5，v4v5，试
1画出G的图形表示；
2写出其邻接矩阵；
3求出每个结点的度数；
4画出图G的补图的图形．
v1
16．（1）关系图如图三：v2v5
（2）邻接矩阵
01100
10010
10001
01001
00110
（3）degv12
degv22
degv32
degv42
degv52
（4）补图如图四
v1
v3
v4
图三
（3分）（6分）
（9分）
v2
v5
v3
v4
图四
（12分）
17．求PQ∧R的合取范式与主析取范式．
P→（R∧Q）
┐P∨R∧Q（┐P∨Q）∧（┐P∨R）（合取范式）
（4分）（6分）
P→（R∧Q）
┐P∨R∧Q
┐P∧┐Q∨Q∨R∧Q
（7分）
┐P∧┐Q∨┐P∧Q∨R∧Q
（8分）
┐P∧┐Q∧┐R∨R∨┐P∧Q∨R∧Q
（9分）
┐P∧┐Q∧┐R∨┐P∧┐Q∧R∨┐P∧Q∨R∧Q
（10分）
┐P∧┐Q∧┐R∨┐P∧┐Q∧R∨┐P∧Q∧┐R∨R∨R∧Q
┐P∧┐Q∧┐R∨┐P∧┐Q∧R∨┐P∧Q∧┐R∨┐P∧Q∧R∨R∧Q
┐P∧┐Q∧┐R∨┐P∧┐Q∧R∨┐P∧Q∧┐R∨
┐P∧Q∧R∨┐P∨P∧R∧Q
┐P∧┐Q∧┐R∨┐P∧┐Q∧R∨┐P∧Q∧┐R∨
f┐P∧Q∧R∨P∧R∧Q（主析取范式）说明：此题解法步骤多样，若能按正确步骤求得结果，均可给分．
（12分）
六、证明题（本题共8分）
18．设连通无向图G有14条边，3个4度顶点，4个3度顶点，其它顶点的度数均小于3，试说明G
中可能有的顶点数．
证明：可利用数列可图化及握手定理解答
顶点度数和为21428，
（2分）
28（3443）4，则知其他顶点度数和为4，
（4分）
对于有限图，若无零度顶点，则除4度及3度顶点外，可能的顶点情况有：
2个2度点；
1个2度点和2r