秋离散数学作业题.docVIP

离散数学作业题 命题逻辑 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） 补充题： 谓词符号化： 所有的鱼都生活在水中。 没有大于2的偶素数。 并不是每个人都聪明。 设个体域D={a,b}，将一阶公式(x)(F(x)→($y)G(y))中的量词消除 设个体域为整数集，令P(x,y)：x+y=1；Q(x,y)：xy0，试求解下列命题的真假。 (x) ($y)P(x,y). ($x) (y)Q(x,y). 求前束范式： ($x)F(x)?(x)R(x). ((x)P(x)∨($y)Q(y))?(x)R(x). 证明： 前提：(x)(A(x) ?B(x)∧C(x))，($x)(A(x)∧D(x)) 结论：($x)(C(x)∧D(x)) 6. 所有的整数均为有理数并且为实数，存在是整数又是奇数的数，因而存在是奇数又是实数的数。 写出上面推理的证明。(用谓词逻辑，写出用谓词表示的前提、结论和证明过程) 集合、关系与映射 P133 习题三：7、9、11、17 补充题 AíB，A∈B能否同时成立，说明原因 求集合A＝{a，{a}}的幂集 证明：若BíC，则P(B)í P(C) 如果A∪B=A∪C，是否有B=C？ 如果A⊕B=A⊕C，是否有B=C？ 试求1到10000之间不能被4，5或6整除的整数个数. 5. 列出所有从A={a,b,c}到B={s}的关系，并指出集合A上的恒等关系和从A到B的全域关系. 给出A上的关系及其关系图和矩阵表示.{x,y|0≤x-y＜3} A={0，1，2，3，4} 已知S={a,b}. Rí ={〈x,y〉|x,y∈A∧xíy∧A为集合族ρ(S)}.试写出关系Rí. 已知： A={a,b,c}, R={〈a,b〉,〈a,c〉,〈b,c〉}该关系具有什么性质？ (自反，反自反，对称，反对称，传递性) 设A={a,b,c},R={〈a,b〉,〈a,c〉} 计算：r(R)，sr(R)，tr(R)，str(R). 设A是含有4个元素的集合，试求： (1)在A上可以定义多少种对称关系？ (2)在A上可以定义多少种既是自反的，又是对称的关系？ (3)在A上可以定义多少种既不是自反的，也不是反自反的二元关系？ 设集合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). 证明：R是A上的传递关系?R?RíR. A={1,2,3,4,5},R={x,y|x,y∈A∧x-y可被2整除}，试问R是否是A上的等价关系？如果是，求出R的各等价类. A={1,2,3,4,5},A上的划分∏={{1,2},{3,4},{5}}，给出由∏所诱导出的A上的等价关系R的集合表达式. 试给出一个单射但非满射的函数.(对某一集合而言) 设f：N→N×N，f(n)=n,n+1,则： (1)说明f是否为单射和满射，并说明理由. (2) f的反函数是否存在？并说明理由. (3)求ranf. 已知如果从无限集合A到集合B存在单射f，则B也是无限集合。 设X是无限集合，集合Y≠φ，证明：X与Y的笛卡儿积X×Y是无限集合。 代数结构 P247 习题六：4（1）（3）、6、16、21 补充题： 以下集合和运算是否构成代数系统？如果构成，说明该系统是否满足结合律、交换律？求出该运算的幺元、零元和所有可逆元素的逆元. P(B)关于对称差运算⊕，其中P(B)为幂集. A={a,b,c}，*运算如下表所示： 设集合A={a,b}，那么（1）在A上可以定义多少不同的二元运算？（2）在A上可以定义多少不同的具有交换律的二元运算？ 设A={1,2},B是A上的等价关系的集合. 列出B的元素. 给出代数系统V=B,∩的运算表. 求出V的幺元、零元和所有可逆元素的逆元. 说明V是否为半群、独异点和群？ 设A={a,b,c}，构造A上的二元运算*，使得a*b=c,c*b=b，且*运算满足幂等律、交换律. 给出关于*运算的一个运算表. 其中表中？位置可以是a、b、c。 *运算是否满足结合律，为什么？ 设R，*是一个代数系统。 *是R上的一个二元运算，使得对于R(实数集合)中的任意元素a,b都有a*b=a+b+a·b(·和+为数集上的乘法和加法). 证明：:R，* 是独异