《离散数学》核心习题

您所在的位置：网站首页 › 如何卸载电脑壁纸桌面 › 《离散数学》核心习题

《离散数学》核心习题

2023-03-15 15:17| 来源: 网络整理| 查看: 265

内容来源：耿素云 & 屈婉玲的《离散数学》

目标人群：大学备考党、考研复试党、离散数学爱好者、计算机专业

理论知识：《离散数学》速成指南

本文内容包括四个板块：

数理逻辑（命题逻辑、一阶逻辑等）集合论（集合、关系、函数等）代数结构（代数系统、群、环、域等）图论（图、连通性、二部图等）命题逻辑

包括命题、联结词、公式、等值演算、析取范式相关概念的习题

1. 命题

Q：下面语句中，哪些是命题？哪些是简单命题？哪些是复合命题？

大熊猫是中国的国宝美国不位于南美洲15 是 2 的倍数，3 是素数5x + 7 > 6你下午有会吗？若无会，请到办公室来一下！2 和 3 是素数2 和 4 中有且仅有一个是素数李华和邓艾是同学这朵花真漂亮！圆的面积等于半径的平方乘以 π数 a 是偶数当且仅当它能被 2 整数只有 4 是偶数，3 才能被 2 整除除非 6 能被 4 整除，6 才能被 2 整除明年 10 月 1 号是晴天若 4 是素数，则 3 是偶数。4 是素数，所以 3 是偶数

A：逐个语句分析如下

简单命题：p复合命题：¬p复合命题：p ∧ q不是命题：真值不定不是命题：有疑问句复合命题：p ∧ q复合命题：(p ∧ ¬q) ∨ (¬p ∧ q)简单命题：p不是命题：感叹句简单命题：p复合命题：p↔q复合命题：q→p复合命题：q→p简单命题：p复合命题：((p→q)∧p)→q2. 等值演算

给定以下 8 个公式

(p∧q)→(p∨q)(¬p∨¬q)→(¬p∧¬q)(¬(q→p)∧p)∨(p∧q∧r)p∧q∧r(p→q)∧r(¬p∨q)∧r∧(p∧q→q)q→(p→r)(p→q)→r

Q1：用真值表法证明 1 与 2 不等值

Q2：用等值演算法证明 3 与 4 等值

Q3：用主析取范式法证明 5 与 6 等值

Q4：用主析取范式法证明 7 与 8 不等值

3. 真值

给定 3 个简单命题

p：北京比天津人口多q：2 大于 1r：15 是素数

Q：求下列各复合命题的真值

(q∨r)→(p→¬r)((p∧¬q)∨(¬p∧q))→r(¬q∨r)↔(p∧¬r)(q↔¬p)↔(p↔r)(q→p)→((p→¬r)→(¬r→¬q))

A：p, q, r 的真值分别是 1, 1, 0，所以 5 个公式的真值依次为 1, 1, 0, 1, 0

4. 构造证明

给出下面四个推理，对于正确的推理用构造证明的方法加以证明。对于不正确的推理要证明它不正确，方法不限

前提：¬p∨q, ¬(q∧¬r), ¬r. 结论：¬p前提：¬p, p∨q. 结论：p∧q若今天是星期日，则明天是星期一。今天是星期日，所以明天不是星期一。若今天是星期二，则明天是星期四。今天是星期二，所以明天是星期四。

Q：1 和 4 推理正确，2 和 3 推理不正确

5. 功能完备集

Q：将公式 (¬p∨q)↔r 化成下列各功能完备集中的公式

{¬, →}{¬, ∧, ∨}{¬, ∧}{¬, ∨}6. 附加前提证明

用附加前提证明法和不用附加前提证明法证明下面推理

前提：p∨q, p→r, q→s. 结论：¬s→r

7. 构造证明

如果小张守第一垒并且小李向 B 队投球，则 A 队取胜。或者 A 队未取胜，或者 A 队成为联察的第一名。小张守第一垒。A 队没有成为联赛的第一名。因此小李没有向 B 队投球。

8. 推理

一个公安人员审查一件盗窃案，已知下列事实

甲或乙盗窃了录像机若甲盗统了录像机，则作案时间不能发生在午夜前若乙的证词正确，则午夜时屋里灯光未灭若乙的证词不正确，则作案时间发生在午夜前午夜时屋里灯光灭了

Q：盗窃录像机的是甲还是乙

一阶逻辑

包括公式、等值式、前束范式等概念的习题

1. 真值

给定解释 I 如下

个体域为整数集合 ZZ 中特定元素 a = 0，b = 1Z 上的特定函数 f(x, y) = x - y，g(x, y) = x + yZ 上特定的谓词 F(x, y): x < y

Q：在 I 下讨论下列各公式的真值情况

F(f(x, b), g(x, b))∀x∀yF(f(x, y), g(x, y))∀x∃yF(f(x, y), g(x, y))∀y(F(y, a)→∀x(¬F(f(x, y), g(x, y))))∀y∀x(F(x, y)→F(f(x, y), x))F(f(x, y), g(x, y))∀x(F(x, a)→F(f(x, y), g(x, y)))

A：在 I 下，上面 7 个公式分别化为

(x - 1) < (x + 1)∀x∀y(x - y < x + y)∀x∃y(x - y < x + y)∀y((y < 0) → ∀x(x - y ≥ x + y))∀y∀x(x < y → (x - y < x))(x - y) < (x + y)∀x((x < 0) → (x - y < x + y)

1, 3, 4 是真命题；而 2, 5 是假命题；6, 7 真值不定

2. 量词

设个体域为 D = {a, b, c}，将下列各公式中的量词消去

∀x∀y(F(x) ∨ G(y))∃x∃y(F(x) ∧ G(y))∃x∀y(F(x) → G(y))∃x∃y(F(x) → G(y))3. 前束范式

Q：求下列公式的前束范式

∀x(F(x) → ∃yG(x, y))∀xF(x) → ∃yG(x, y)∃x(¬∃yF(x, y) → (∃zF(z) → H(x)))4. 证明

Q：找出证明序列中的错误

5. 推理证明

学术委员会的每个成员都是博士并且是教授。有些成员是青年人。因而有的成员是青年教授

6. 推理证明

Q：有些病人相信所有的意思。但是病人都不相信骗子。所以，医生都不是骗子。

符号化：设 F(x)：x 是病人，G(x)：x 是医生，H(x)：x 是骗子，L(x, y)：x 相信 y。

前提：∃x(F(x) ∧ ∀y(G(y) → L(x, y))), ∀x(F(x) → ∀y(H(y) → ¬L(x, y))

结论：∀x(G(x) → ¬H(x))

【本文地址】

公司简介

联系我们