一、填空
1．不能再分解的命题称为____________，至少包含一个联结词的命题称为____________。2．一个命题公式A(P, Q, R)为真的所有真值指派是000, 001, 010, 100，则其主析取范式是__________________，其主合取范式是_________________。
3．设A={a,b,c}，B={b,c,d,e}，C={b,c}，则( A ⋃ ⊕＝____________。4．幂集P(P(∅)) ＝________________。
5．设A为任意集合，请填入适当运算符，使式子A________A=∅；A________A’=∅成立。6．设A={0，1，2，3，6}，R={〈x,y〉|x≠y∧(x,y∈A)∧y≡x(mod 3)}，则D(R)=____________，R(R)=____________。
7．称集合S是给定非空集合A的覆盖：若S={S1，S2，…，S n}，其中S i⊆A，S i≠Ø，i=1，2，…，n，且______ _____；进一步若_____ _______，则S是集合A的划分。8．两个重言式的析取是____ ____式，一个重言式和一个永假式的合取式是式。9．公式┐(P∨Q) ←→(P∧Q)的主析取范式是。
10. 已知Π={{a}{b,c}}是A={a,b,c}的一个划分，由Π决定的A上的一个等价关系
是。
二、证明及求解
1．求命题公式（P→Q）→（Q∨P）的主析取范式。
2．推理证明题
1）⌝P∨Q，⌝Q∨R，R→S⇒P→S。
2) (∀x)(P(x)→Q(y)∧R(x))，(∃x)P(x)⇒Q(y)∧(∃x)(P(x)∧R(x))
x)}，S={〈x,y〉|x,y∈A∧（x=y+2）}。3．设A={0，1，2，3}，R={〈x,y〉|x,y∈A∧(y=x+1∨y=
2
试求R S R。
4．证明：R是传递的⇔R*R⊆R。
5．设R是A上的二元关系，S={| 存在c∈A，使∈R，且∈R}。证明：若R是等价关系，则S也是等价关系。
6．若f:A→B和g:B→C是双射，则（g f）-1=f-1 g-1。
7．符号化下列命题，并证明结论的有效性。
只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好。
8．画出集合S={1,2,3,4,5,6}在偏序关系“整除”下的哈斯图，并讨论：
1）写出{1,2,3,4,5,6}的最大(小)元和极大(小)元；
2）分别写出{2,3,6}和{2,3,5}的上(下)界、上(下)确界。
9. 设R是A={1,2,3,4,5}上的二元关系，R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>}，求r(R)、s(R)和t(R)，并作出它们及R的关系图。
参考答案
一、填空
1．原子命题；复合命题
2．0m ∨1m ∨2m ∨4m ；3M ∧5M ∧6M ∧7M
3．{a,d,e}
4．{∅,{∅}}
5．⊕；∩
6．{0，3，6}；{0，3，6}
7．S 1∪S 2∪…∪S n ＝S ； S i ∩S j ＝∅,1≤i8．重言；永假
9．0m ∨1m
10. {,,,,}
二、证明及求解
1．解：(⌝p →q)→( ⌝q ∨p)⇔⌝(⌝p →q)∨(p ∨⌝q)
⇔⌝(p ∨q)∨(p ∨⌝q)
⇔(⌝p ∧⌝q)∨(p ∨⌝q)
⇔(⌝p ∨p ∨⌝q)∧(⌝q ∨p ∨⌝q)
⇔(p ∨⌝q)
⇔M1
⇔m0∨m2∨m3
2．1）证明：
(1)P 附加前提
(2)⌝P ∨Q P
(3)Q T(1)(2)，I
(4)⌝Q ∨R P
(5)R T(3)(4)，I
(6)R →S P
(7)S T(5)(6)，I
(8)P →S CP
2) 证明
(1)∃xP(x)
P (2)P(a) ES(1)
(3)∀x(P(x)→Q(y)∧R(x)) P
(4)P(a)→Q(y)∧R(a) US(3)
(5)Q(y)∧R(a) T(2)(4),I
(6)Q(y) T(5),I
(7)R(a) T(5),I
(8)P(a)∧R(a) T(2)(7),I
(9)∃x(P(x)∧R(x)) EG(8)
(10)Q(y)∧∃x(P(x)∧R(x)) T(6)(9),I
3．解：
R={<0,1>,<1,2>,<2,3>,<0,0>,<2,1>},S={<2,0>,<3,1>}，
R S={<1,0>,<2,1>},
R S R={<1,1>,<1,0>,<2,2>}
4．证明若R是传递的，则∈R*R⇒∃z(xRz∧zSy)⇒xRc∧cSy，由R是传递的得xRy，即有∈R，所以R*R⊆R。
反之，若R*R⊆R，则对任意的x、y、z∈A，如果xRz且zRy，则∈R*R，于是有∈R，即有xRy，所以R是传递的。
5．证明由R是A上的等价关系，知∈R，故存在a∈A，使∈R，且
∈R，故∈S。若∈S，则存在c∈A，使∈R，且∈R，由R的对称性，∈R，且∈R，故∈S。若∈S，∈S，存在d∈A，使∈R，且∈R，存在e∈A，使∈R，且∈R，由R的传递性，故存在e∈A，使∈R，且∈R，所以∈S。故S
是等价关系。
6．证明：1)因为f:A→B和g:B→C均是双射，故f-1和g-1均存在，且f-1：B→A，g-1：C→B，所以f-1 g-1：C→A。
由f和g是双射，可知g f也是双射，故（g f）-1存在且（g f）-1：C→A。
D(f-1 g-1)=D(g f)-1=C
2) 对任意c∈C⇒存在唯一b∈B，使得g(b)=c⇒存在唯一a∈A，使得f(a)=b，故
(f-1 g-1)(c)= (f-1(g-1(c))=f-1(b)=a
但（g f）(a)=g(f(a))=g(b)=c
故（g f）-1(c)=a
因此对任意c∈C有：(g f)-1(c)= (f-1 g-1)(c)
