,x,z)中的x和z是约束变元,y是自由变元R(y,x)中的x是自由变元,y是约束变元9.设个体域为D={a1,a2},求谓词公式("y)($x)P(x,y)消去量词后的等值式;解:"y$xP(x,y)=$xP(x,a1)Ù$xP(x,a2)=(P(a1,a1)ÚP(a2,a1))Ù(P(a1,a2)ÚP(a1,a2))三、证明题1.对任意三个集合A,B和C,试证明:若A´B=A´C,且A¹,则B=C.证明:设xÎA,yÎB,则<x,y>ÎA´B,因为A´B=A´C,故<x,y>ÎA´C,则有yÎC,所以BÍC.设xÎA,zÎC,则<x,z>ÎA´C,因为A´B=A´C,故<x,z>ÎA´B,则有zÎB,所以CÍB.故得A=B.2.试证明:若R与S是集合A上的自反关系,则R∩S也是集合A上的自反关系.证明:R1和R2是自反的,"xÎA,<x,x>ÎR1,<x,x>ÎR2,则<x,x>ÎR1∩R2,所以R1∩R2是自反的.3.设连通图G有k个奇数度的结点,证明在图G中至少要添加条边才能使其成为欧拉图.证明:由定理推论知:在任何图中,度数为奇数的结点必是偶数个,则k是偶数。又由欧拉图的充要条件是图G中不含奇数度结点。因此,只要在每对奇数度结点间各加一条边,使图G的所有结点的度数变为偶数,成为欧拉图。故最少要加条边才能使其成为欧拉图。4.试证明(P®(QÚØR))ÙØPÙQ与Ø(PÚØQ)等价.证:(P®(QÚØR))ÙØPÙQÛ(ØPÚ(QÚØR))ÙØPÙQÛ(ØPÚQÚØR)ÙØPÙQÛ(ØPÙØPÙQ)Ú(QÙØPÙQ)Ú(ØRÙØPÙQ)Û(ØPÙQ)Ú(ØPÙQ)Ú(ØPÙQÙØR)ÛØPÙQ(吸收律)ÛØ(PÚØQ)(摩根律)5.试证明:Ø(A∧ØB)∧(ØB∨C)∧ØCÞØA.证明:①前提引入;②前提引入;③①②析取三段论;④前提引入;⑤置换;④⑥③⑤析取三段论。
全文预览
