五、证明题
1．设G 是一个n 阶无向简单图，n 是大于等于3的奇数．证明图G 与它的补图G 中的奇数度顶点个数相等． 证明：设,G V E =<>，,G V E '=<>．则E '是由n 阶无向完全图n K 的边删去E 所得到的．所以对于任
意结点u V ∈，u 在G 和G 中的度数之和等于u 在n K 中的度数．由于n 是大于等于3的奇数，从而n K 的每个结点都是偶数度的（ 1 (2)n -≥度），于是若u V ∈在G 中是奇数度结点，则它在G 中也是奇数度结点．故图G 与它的补图G 中的奇数度结点个数相等．
2．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加
2
k 条边才能使其成为欧拉图． 证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k 是偶数．
又根据定理，图G 是欧拉图的充分必要条件是图G 不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G 的所有结点的度数变为偶数，成为欧拉图． 故最少要加2
k 条边到图G 才能使其成为欧拉图． 五、证明题
1．试证明集合等式：A ⋃ (B ⋂C )=(A ⋃B ) ⋂ (A ⋃C )．
证：若x ∈A ⋃ (B ⋂C )，则x ∈A 或x ∈B ⋂C ，
即 x ∈A 或x ∈B 且 x ∈A 或x ∈C ．
即x ∈A ⋃B 且 x ∈A ⋃C ，
即 x ∈T =(A ⋃B ) ⋂ (A ⋃C )，
所以A ⋃ (B ⋂C )⊆ (A ⋃B ) ⋂ (A ⋃C )．
反之，若x ∈(A ⋃B ) ⋂ (A ⋃C )，则x ∈A ⋃B 且 x ∈A ⋃C ，
即x ∈A 或x ∈B 且 x ∈A 或x ∈C ，
即x ∈A 或x ∈B ⋂C ，
即x ∈A ⋃ (B ⋂C )，
所以(A ⋃B ) ⋂ (A ⋃C )⊆ A ⋃ (B ⋂C )．
因此．A ⋃ (B ⋂C )=(A ⋃B ) ⋂ (A ⋃C )．
2．对任意三个集合A , B 和C ，试证明：若A ⨯B = A ⨯C ，且A ≠∅，则B = C ．
证明：设x ∈A ，y ∈B ，则∈A ⨯B ，
因为A ⨯B = A ⨯C ，故∈ A ⨯C ，则有y ∈C ，
所以B ⊆ C ．
设x ∈A ，z ∈C ，则∈ A ⨯C ，
因为A ⨯B = A ⨯C ，故∈A ⨯B ，则有z ∈B ，所以C ⊆B ．
故得B = C ．
3、设A ，B 是任意集合，试证明：若A ⨯A=B ⨯B ，则A=B ．
许多同学不会做，是不应该的．我们看一看
证明：设x ∈A ，则∈A ⨯A ，
因为A ⨯A=B ⨯B ，故∈B ⨯B ，则有x ∈B ，所以A ⊆B ．
设x ∈B ，则∈B ⨯B ，
因为A ⨯A=B ⨯B ，故∈A ⨯A ，则有x ∈A ，所以B ⊆A ．
故得A=B ．
1．试证明命题公式(P→(Q∨⌝R))∧⌝P∧Q与⌝（P∨⌝Q）等价．
证：(P→(Q∨⌝R))∧⌝P∧Q⇔(⌝P∨(Q∨⌝R))∧⌝P∧Q
⇔((⌝P∨Q∨⌝R)∧⌝P)∧Q
⇔⌝P∧Q（吸收律）
⇔⌝(P∨⌝Q) （摩根律）
2．试证明(∃x)(P(x)∧R(x))⇒(∃x)P(x)∧(∃x)R(x)．
分析：前提：(∃x)(P(x)∧R(x))，
结论：(∃x)P(x)∧(∃x)R(x) ．
证明(1) (∃x)(P(x)∧R(x)) P
(2) P(a)∧R(a) ES(1) (存在指定规则)
(3) P(a) T(2) （化简）
(4) (∃x)P(x) EG(3) (存在推广规则)
(5) R(a) T(2) （化简）
(6) (∃x)R(x) EG(5) (存在推广规则)
(7) (∃x)P(x)∧(∃x)R(x) T(4)(6) （合取引入）
2．设集合A={1, 2, 3, 4}，B={2, 4, 6, 8}，判断下列关系f：A→B是否构成函数，并说明理由．
(1) f ={<1, 4>, <2, 2,>, <4, 6>, <1, 8>}；(2) f ={<1, 6>, <3, 4>, <2, 2>}；
(3) f ={<1, 8>, <2, 6>, <3, 4>, <4, 2,>}．
解：(1) f不能构成函数．
因为A中的元素3在f中没有出现．
(2) f不能构成函数．
因为A中的元素4在f中没有出现．
(3) f可以构成函数．
因为f的定义域就是A，且A中的每一个元素都有B中的唯一一个元素与其对应，满足函数定义的条件．三、公式翻译题
1．请将语句“今天是天晴”翻译成命题公式．
解：设P：今天是天晴；
则命题公式为：P．
问：“今天不是天晴”的命题公式是什么？
2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式．
解：设P：小王去旅游，Q：小李去旅游，
则命题公式为：P∧Q．
注：语句中包含“也”、“且”、“但”等连接词，命题公式要用合取“∧”．
3．请将语句“他去旅游，仅当他有时间．”翻译成命题公式．
解：设P：他去旅游，Q：他有时间，
则命题公式为：P→Q．
注意：命题公式的翻译还要注意“不可兼或”的表示．
例如，教材第164页的例6 “T2次列车5点或6点钟开．”怎么翻译成命题公式？这里的“或”为不可兼或．
4．请将语句“所有人都努力工作．”翻译成谓词公式．
解：设P(x)：x是人，Q(x)：x努力工作．
谓词公式为：(∀x)(P(x)→ Q(x))．
