《离散数学》试题及答案(6)

所以A=(A-B)?(A-C)。

12、(A-B)?(A-C)=??A?B?C

证明：

? 因为(A-B)?(A-C) =(A?B)?(A?C) =A?(B?C)

=A?B?C= A-(B?C)，且(A-B)?(A-C)=?，

所以?= A-(B?C)，故A?B?C。

? 因为A?B?C，所以A-(B?C)=A。而A-(B?C)= (A-B)?(A-C)， 所以A=(A-B)?(A-C)。

13、(A-B)?(B-A)=A ? B=?

证明：

? 因为(A-B)?(B-A)=A，所以B-A?A。但(B-A)?A=?，故B-A=?。 即B?A，从而B=?（否则A-B?A，从而与(A-B)?(B-A)=A矛盾）。

? 因为B=?，所以A-B=A且B-A=?。从而(A-B)?(B-A)=A。

14、(A-B)-C?A-(B-C)

证明：

?x?(A-B)-C，有x?A-B且x?C，即x?A，x?B且x?C。 从而x?A，x?B-C，故x?A-(B-C)。从而(A-B)-C?A-(B-C)

15、P(A)?P(B)?P(A?B) （P(S)表示S的幂集）

证明：

?S?P(A)?P(B)，有S?P(A)或S?P(B)，所以S?A或S?B。 从而S?A?B，故S?P(A?B)。即P(A)?P(B)?P(A?B)

16、P(A)?P(B)=P(A?B) （P(S)表示S的幂集）

证明：

?S?P(A)?P(B)，有S?P(A)且S?P(B)，所以S?A且S?B。 从而S?A?B，故S?P(A?B)。即P(A)?P(B)?P(A?B)。

?S?P(A?B)，有S?A?B，所以S?A且S?B。

从而S?P(A)且S?P(B)，故S?P(A)?P(B)。即P(A?B)?P(A)?P(B)。 故P(A?B)=P(A)?P(B)

第 26 页 共 33 页

17、（A-B）?B=（A?B）-B当且仅当B=?。

证明：

（A?B）-B=（A??）-? =A，?当B=?时，因为（A-B）?B=（A-?）??=A，所以（A-B）?B=（A?B）-B。

假设B??，则存在b?B。因为b?B且b? A?B，所以b?（A?B）?用反证法证明。

-B。而显然b?（A-B）?B。故这与已知（A-B）?B=（A?B）-B矛盾。

五、证明或解答：

（数理逻辑、集合论与二元关系部分）

1、设个体域是自然数，将下列各式翻译成自然语言：

(1) ?x?y（xy=1）; (2) ?x?y(xy=1); (3) ?x?y (xy=0); (4) ?x?y（xy=0）; (5) ?x?y (xy=x); (6) ?x?y（xy=x）; (7) ?x?y?z (x-y=z)

答：

（1）存在自然数x，对任意自然数y满足xy=1; （2）对每个自然数x，存在自然数y满足xy=1; （3）对每个自然数x，存在自然数y满足xy=0; （4）存在自然数x，对任意自然数y满足xy=1; （5）对每个自然数x，存在自然数y满足xy=x; （6）存在自然数x，对任意自然数y满足xy=x; （7）对任意自然数x,y，存在自然数z满足x-y=z。

2、设A(x,y,z): x+y=z, M（x,y,z）: xy=z, L(x,y): xy体域为自然数。将下列命题符号化： （1）没有小于0的自然数; （2）xyz;

， 个第 27 页 共 33 页

（4）存在x，对任意y 使得xy=y; （5）对任意x，存在y使x+y=x。

答：

（1）?x（G(x,0)?M（0,0,x）） 或??x L(x,0) （2）?x?y?z ((L(x,y)?L(y,z))?L(x,z)) （3）?x?y ((L(x,y)??z(L(z,0)?G(xz,yz))) （4）?x?yM（x,y,y） （5）?x?yA(x,y,x)

3、列出下列二元关系的所有元素：

（1）A={0,1,2}，B={0,2,4}，R={|x,y?A?B};

（2）A={1,2,3,4,5}，B={1,2}，R={|2?x+y?4且x?A且y?B}; （3）A={1,2,3}，B={-3,-2,-1,0,1}，R={||x|=|y|且x?A且y?B};

解：

(1) R={<0,0>,<0,2>,<2,0>,<2,2>} (2) R={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>}; (3) R={<1,1>,<1,-1>,<2,-2>,<3,-3>}。

4、对任意集合A,B，证明：若A?A=B?B，则B=B。

证明：

若B=?，则B?B=?。从而A?A =?。故A=?。从而B=A。

若B??，则B?B??。从而A?A??。

对?x?B, ?B?B。因为A?A=B?B，则?A?A。从而x?A。故B?A。 同理可证，A?B。 故B=A。

5、对任意集合A,B，证明：若A??，A?B=A?C，则B=C。

证明：

若B=?，则A?B=?。从而A?C =?。因为A??，所以C=?。即B=C。

若B??，则A?B??。从而A?C??。

对?x?B,因为A??，所以存在y?A, 使?A?B。因为A?B=A?C，则

第 28 页 共 33 页

?A?C。从而x?C。故B?C。

同理可证，C?B。 故B=C。

6、设A={a,b}, B={c}。求下列集合：

(1) A?{0,1}?B； (2) B2?A； (3) (A?B)2; (4) P(A)?A。

解：

（1） A?{0,1}?B={,,,}; （2） B2?A={,};

（3） (A?B)2={,,,}; （4） P(A)?A={,,<{a},a>,<{a},b>,<{b},a>,<{b},b>

,,}。

7、设全集U={a,b,c,d,e}, A={a,d}, B={a,b,c}, C={b,d}。求下列各集合： （1）A?B?C； （2）A?B?C；（3）(A?B)?C; （4）P(A)-P(B); （5）(A-B)?(B-C); （6）(A?B)?C;

解 ：

(1) A?B?C={a}; (2) A?B?C={a,b,c,d,e}; (3) （A?B）?C={b,d}; (4) P(A)-P(B)={{d},{a,d}}; (5) (A-B)?(B-C)={d,c,a}; (6) (A?B) ?C={b,d}。

8、设A,B,C是任意集合，证明或否定下列断言： （1）若A?B，且B?C，则A?C； （2）若A?B，且B?C，则A?C; （3）若A?B，且B?C，则A?C； （4）若A?B，且B?C，则A?C；

证明：

(1) 成立。

对?x?A, 因为A?B，所以x?B。又因为B?C，所以x?C。即A?C。

(2) 不成立。反例如下：A={a}, B={a,b},C={a,b,c}。虽然A?B，且B?C，但A?C。

第 29 页 共 33 页

(3) 不成立。反例如下：A={a}, B={{a},b},C={{{a},b},c}。虽然A?B，且B?C，但A?C。

(4) 成立。因为A?B, 且B?C，所以A?C。

9、A上的任一良序关系一定是A上的全序关系。

证明：

?a，b∈A，则{a,b}是A的一个非空子集。?≤是A上的良序关系，?{a,b}有最小元。若最小元为a，则a≤b；否则b≤a。从而≤为A上的的全序关系。

10、若R和S都是非空集A上的等价关系，则R?S是A上的等价关系。

证明：

?a∈A，因为R和S都是A上的等价关系，所以xRx且xSx。故xR?Sx。从而R?S是自反的。

?a,b∈A，aR?Sb，即aRb且aSb。因为R和S都是A上的等价关系，所以bRa且bSa。故bR?Sa。从而R?S是对称的。

?a,b,c∈A，aR?Sb且bR?Sc，即aRb，aSb,bRc且bSc。因为R和S都是A上的等价关系，所以aRc且aSc。故aR?Sc。从而R?S是传递的。

故R?S是A上的等价关系。

11、设R?A×A，则R自反 ?IA?R。

证明：

??x?A，?R是自反的，?xRx。即?R，故IA?R。 ??x?A，?IA?R，??R。即xRx，故R是自反的。

12、设A是集合，R?A×A，则R是对称的?R＝R－1。

证明：

_1-1

???R ，?R是对称的，?yRx。即?R，故?R 。从而R?R。

反之??R-1,即?R 。?R是对称的，?yRx。即?R， R_1?R。 故R=R-1。

-1-1

??x，y?A，若?R ，即?R。? R=R，??R。即yRx，故R是对

称的。

13、设A,B,C和D均是集合，R?A×B，S?B×C，T?C×D，则 (1) R?(S?T)=(R?S)?(R?T)；

第 30 页 共 33 页

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《离散数学》试题及答案(6)在线全文阅读。