2013年秋离散数学作业题

2013年秋离散数学作业题

离散数学作业题

第一章 命题逻辑

p38 习题一 1、2（1）（3）、3（1）（4）、4（2）（3）、6（2）、7（4）（6）、8（1）（3）（5）

补充题：将P Q化成与之等价的并仅含联结词 的公式。

第二章 谓词逻辑

P70 习题二 2（2）（4）、3（1）（3）、4（3）（4）、10（4）

补充题：

1. 谓词符号化：

1) 所有的鱼都生活在水中。

2) 没有大于2的偶素数。

3) 并不是每个人都聪明。

2. 设个体域D={a,b}，将一阶公式( x)(F(x)→( y)G(y))中的量词消除

3. 设个体域为整数集，令P(x,y)：x+y=1；Q(x,y)：xy>0，试求解下列命题的真假。

1) ( x) ( y)P(x,y).

2) ( x) ( y)Q(x,y).

4. 求前束范式：

1) ( x)F(x) ( x)R(x).

2) (( x)P(x)∨( y)Q(y)) ( x)R(x).

5. 证明：

前提：( x)(A(x) B(x)∧C(x))，( x)(A(x)∧D(x))

结论：( x)(C(x)∧D(x))

6. 所有的整数均为有理数并且为实数，存在是整数又是奇数的数，因而存在是奇数又是实数的数。

写出上面推理的证明。(用谓词逻辑，写出用谓词表示的前提、结论和证明过程)

第三章 集合、关系与映射

P133 习题三：7、9、11、17

补充题

1. A B，A∈B能否同时成立，说明原因

求集合A＝{a，{a}}的幂集

2. 证明：若B C，则P(B) P(C)

3. 如果A∪B=A∪C，是否有B=C？

如果A⊕B=A⊕C，是否有B=C？

4. 试求1到10000之间不能被4，5或6整除的整数个数.

5. 列出所有从A={a,b,c}到B={s}的关系，并指出集合A上的恒等关系和从A到B的全域关系.

5. 给出A上的关系及其关系图和矩阵表示.{<x,y>|0≤x-y＜3} A={0，1，2，3，4}

6. 已知S={a,b}. R ={〈x,y〉|x,y∈A∧x y∧A为集合族ρ(S)}.试写出关系R .

7. 已知： A={a,b,c}, R={〈a,b〉,〈a,c〉,〈b,c〉}该关系具有什么性质？

(自反，反自反，对称，反对称，传递性)

8. 设A={a,b,c},R={〈a,b〉,〈a,c〉} 计算：r(R)，sr(R)，tr(R)，str(R).

9. 设A是含有4个元素的集合，试求：

(1)在A上可以定义多少种对称关系？

(2)在A上可以定义多少种既是自反的，又是对称的关系？

(3)在A上可以定义多少种既不是自反的，也不是反自反的二元关系？

10. 设集合A={0，1，2，3，4}. R={<x,y>|x+y=4,x,y∈A} ，S={<x,y>|y-x=1,x,y∈A}.

试求：R S，R R，(R S) R，R (S R).

11. 证明：R是A上的传递关系 R R R.

12. A={1,2,3,4,5},R={<x,y>|x,y∈A∧x-y可被2整除}，试问R是否是A上的等价关系？如果是，求出R的各等价类.

第1页下一页