离散数学习题解答

《离散数学习题解答》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、离散数学习题解答数理逻辑习题1.将下列命题符号化：（1）要是明天不下雨且我有时间，那么我去步行街购物。设p：明天下雨q：我有时间r：我去步行街购物（2）如果小王和小张是一个组，那么这次英语竞赛一定取胜。设p：小王和小张是一个组q：这次英语竞赛一定取胜（3）除非天下雨，否则他不乘出租车上班。设p：天下雨q：他乘出租车上班（4）我反悔，仅当太阳从西边出来。设p：我反悔q：太阳从西边出来（5）如果在点处可导，则在点处可微。反之亦然。设p：在点处可导q：在点处可微（6）明天既不是晴天也不是下雨天。设p：明天是晴天q：明天是雨天4、用真值表判断下列公式的类型。（2）000

2、00011010101111001101111001111公式是可满足式。115、证明下列等值式方法：等值演算、主范式、真值表（2）6、使用恒等式证明下列各式，并写出它们的对偶公式。（3）的对偶公式：7、证明下列蕴涵式（1）118、（1）（2）（3）（4）可满足式9、求下列公式的主析取范式和主合取范式。（1）真值表法也很简单：00，10，11时是1，01时是0。10、将下列公式化成与之等值且仅含中联结词的公式。（1）14、构造下面推理的证明。（1）如果今天是星期六，我们就要到独秀峰或象鼻山去玩，如果独秀峰人太多，我们就不去独秀峰。今天是星期六。独秀峰游人太多，所

3、以我们去象鼻山玩。解：设p：今天是星期六。q：我们到独秀峰玩。r：我们到象鼻山玩。s：独秀峰游人多。前提：，，。结论：证明：11①前提引入②前提引入③①②假言推理④附加前提引入⑤前提引入⑥④⑤假言推理⑦③⑥析取三段论（2）如果马会飞或羊吃草，则母鸡就会是飞鸟。如果母鸡是飞鸟，那么烤熟的鸭子还会跑。烤熟的鸭子不会跑。所以，羊不吃草。设p：马会飞。q：羊吃草。r：母鸡是飞鸟。s：烤熟的鸭子会跑。前提：，，结论：证明：①前提引入②前提引入③①②拒取式④前提引入⑤③④拒取式⑥⑤等值演算⑦⑥化简规则17、符号化下列语句。（1）有会说话的机器人。设：：x是机器人。：x会说话

4、。符号化为：（2）尽管有人很聪明，但未必一切人都聪明。设：：x是人。：x很聪明。11符号化为：（3）并不是所有的汽车都比火车快。设：：x是汽车。：y是火车。：x比y快。符号化为：（4）有的人不吃萝卜，但人都要喝水。设：：x是人。：x吃萝卜。：x要喝水。符号化为：（5）男人一定比女人高，是不对的。设：：x是男人。：y是女人。：x比y高。符号化为：（6）某些汽车慢于所有的火车，但至少有一火车快于每一汽车。设：：x是汽车。：y是火车。：x比y慢。符号化为：（7）两个不相等的实数间，必存在第三个实数。设：：x是实数。：x和y相等。：z在x和y之间。符号化为：19、（1）

5、x是任意自然数，2x=x。真值为假。（2）x和y是任意自然数，若x+2=y，那么y+2=x。真值为假。（3）x和y是任意自然数，存在自然数z，使得x+y=z。真值为真。20、（1）命题公式的代换实例。永真式（3）个体域：自然数。：x=y。真命题。：x>y。假命题。可满足式。1124、（1）（2）25、设：x是无理数。：x是有理数。：x能表示成分数。前提：，结论：证明：①前提引入②①量词等值式③②等值式④③等值式⑤④全称量词消去规则⑥前提引入⑦⑥全称量词消去规则⑧⑤⑦假言三段论⑨⑧全称量词引入规则11集合论与关系习题2、集合应用题文氏图求解，答案是5人。5、已知，

6、求。解：7、解：R的关系矩阵为R的关系图为：9、dom(A)={1,2,3}，dom(B)={1,2,4}，ran(A)={2,3,4}，ran(B)={2,3,4}。11、，，，1112、（1）自反（2）反对称、传递（3）自反、对称、传递（4）自反（5）对称（6）对称13、14、[a]=[b]={a,b}，[c]=[d]={c,d}。15、（1）证明：1），，所以R自反。2），，所以R对称。3），，，，11由和可得。。所以R传递。由1），2），3）可证R是A×A上的等价关系。（2）具有R关系，具有R关系，具有R关系，具有R关系，具有R关系，由R确定的划分为{{

7、},{},{},{},{},{},{}}19、（1）必要性R循环，由则，所以R对称，由则，因为R对称，由，可得，所以R传递，因R自反，所以综上所述，R是等价关系。（2）充分性R是等价关系，所以R自反；11R是等价关系，则，因为R对称，所以可得，故R是循环的。22、哈斯图：极大元：7，8，9，10，11，12；极小元：1最小元：1最大元：无24、上界：12，下界：1，最小上界：12，最大下界：1。27、（1）单射，不是满射（2）不是满射，也不是单射（3）不是满射，也不是单射（4）是满射，不是单射（5）是单射，不是满射（6）不是单射，也不是满射29、（1）计算。（2

8、）确定商集。1111