8、既不含________________也不含____________________的无向图称为简单图。三、计算题本大题共3小题，每小题10分，共30分
1、用等值演算法求公式Apqpr的主析取范式。
2、求公式xQxGx，syPyzHy，z的前束范式。
3、设集合A1，2，3，4，5，关系Rx，yx，yA且x整除y，要求：
（1）列出R的所有元素；（2）写出R的关系矩阵MR；
（3）求偏序集A，R的极大元、极小元和最小元。
四、应用题本大题共2小题，每小题5分，共10分1、用命题公式将下列命题符号化：2和5是偶数，当且仅当52。2、用谓词公式将下列命题符号化：每个计算机专业的学生都要学《编译原理》，但有些计算机专业的学生不学《经济学》。五、证明题（本大题共2小题，每小题10分，共20分）1、在命题逻辑系统中用归结法证明下列推理是有效的：
前提：sq，pq，s结论：p
2、在谓词逻辑系统中写出下列推理的（形式）证明：
前提：xMxPx，xMxGx，xGx
结论：xPx
计算题6设命题公式GP→Q∨Q∧P→R求G的主析取范式。79分设一阶逻辑公式：GxPx∨yQy→xRx，把G化成前束范式
9设R是集合AabcdR是A上的二元关系Rabbabccd
1求出rRsRtR；
2画出rRsRtR的关系图
11通过求主析取范式判断下列命题公式是否等价：1GP∧Q∨P∧Q∧R2HP∨Q∧R∧Q∨P∧R
13设R和S是集合A＝abcd上的关系，其中R＝aaacbccd
S＝
fabbcbddd1试写出R和S的关系矩阵；2计算RSR∪SR－1S－1R－1
证明题1利用形式演绎法证明：P→QR→SP∨R蕴涵Q∨S。2设AB为任意集合，证明：ABCAB∪C3本题10分利用形式演绎法证明：A∨BC→BC→D蕴涵A→D。
4本题10分AB为两个任意集合，求证：
A－A∩BA∪B－B
答案：15BADBB610BBABB11，a，1，2，b，220，23164
15零元6半群7弱连通8平行边环三．
pqpr1pqpr
pqrpqrpqrpqrm011m010m111m101
xQxGxsyzPyHyz
2
yzxQxGxsPyHyz
31R11223344551213141524
12345
111111
2010102MR300100
400010


500001
（3）最小元1极小元1
四
1令p表示2是偶数；令q表示5是偶数；r表示52；
极大元5
pqr
2S（x）：x是计算机专业的学生；G（x）：x要学《编译原理》；F（x）：x学经济学；
xSxGxxSxFr