《离散数期末复习1》由会员分享，可在线阅读，更多相关《离散数期末复习1（56页珍藏版）》请在金锄头文库上搜索。
1、离散数学期末复习大纲数理逻辑部分以判定推理为主：包括对给定合 式公式属性的判定及熟练使用条规则进行有 效推理。 关系函数部分：以关系的基本概念、关系性质 的形式化描述，等价关系和划分，偏序关系和 哈斯图。函数掌握特种函数，满射、单射、双 射函数相关的证明。 代数系统部分：掌握代数系统的基本概念，包 括子代数，代数系统的同态、同构，积代数和 商代数的求法等，特殊代数系统掌握群相关的 内容，如何求子群等。 图论部分掌握图的基本概念，图的矩阵表 示及矩阵携带的信息，重点掌握树相关的 概念。 平时成绩占分。 针对各部分所做的练习。 、求下列公式的主范式，并判定公式的 属性。 例1.1(pqr)(pqr
2、)(pq) 解：上式=(pqr)(pqr)(pq)(r r)=(pqr)(pqr)(pqr)(pqr) =m7, m3, m1,m0其中表示析取。 该公式含三个变元，与其等价的主析取范式四项，所以 它是可满足的。 例1.2 (p(qr)(p (q r) 解：上式 (p(qr) (p(qr) = (pq)(pr)(pq)(pr) = (pqr)(pqr) (pqr)(pqr) (pqr)(pqr) (pqr)(pqr) =M4,M5, M6,M2, M3,M1其中表示合取。 该公式是可满足的。 例1.3刚进入大学的小张与寝室里的其他三 人聊天，这三个人根据小张的口音分别作 出下述判断： 甲说：小
3、张不是苏州人，是上海人。 乙说：小张不是上海人，是苏州人。 丙说：小张既不是上海人，也不是杭州人 。 小张听后，笑曰：你们三人有一人全说对 了，有一人全说错了，还有一人对错各半 。 试用命题逻辑推断小张究竟是哪里人。 解：首先符号化： 设：小张是苏州人 ：小张是上海人 ：小张是杭州人 根据题意有： 甲：PQ, 乙： Q P, 丙： Q R 分析小张只可能是其中一个城市的人或者 不是这三个城市的人。 根据甲乙丙三人的说话内容可以判断：丙 至少说对了一半，因此甲或乙必有一人全 错了。若甲全错了，则有Q P即乙全对 了。若乙全错了，则甲全对。所以丙必是 一对一错。 将小张的话符号化为： (PQ) (
4、QR)(QR) (QP)(QR) (QR)T 化简得： (PQR) ( PQR) 小张不可能既是苏州人又是杭洲人，所以 只能是上海人。 例1.4甲乙丙丁人中仅有两个人代表单位 参加了市里的桥牌比赛，关于谁参加比赛 ，下列种说法都是正确的： 甲和乙两人中有一人参加； 若丙参加，则丁必参加； 乙和丁两人中至多参加一人； 若丁不参加，则甲也不参加。 试判断哪两个人参加了比赛。 解：符号化命题如下： 设：甲参加了比赛； ：乙参加了比赛 ：丙参加了比赛 ：丁参加了比赛 依题意将1,2,3,4分别符号化为： (AB)(AB) (CD)(BD)(DA) T 将上式化为主析取范式应有24=16个极小项 即m0
5、000, m0001, m0010, m0011, m0100, m0101,m0110, m0111, m1000, m1001, m1010, m1011, m1100,m1101, m1110, m1111 根据题意去掉不合法的 得到的结论是甲和丁参加了比赛。 例1.5当p，q，r，s四个人考试成绩出来后，有人 问四个人中谁的成绩最好，p说“不是我”，q说“是 s”，r说是“q”，s说“不是我”。四个人的回答只有一 个人符合实际，问哪一位的成绩最好。若有两人 成绩并列最好，是谁？ 解：令p: p的成绩最好；q：q的成绩最好；r：r的 成绩最好；s：s的成绩最好。 若只有p回答正确： p
6、s q s 若只有q回答正确： p s q s 若只有r回答正确： p s q s 若只有s回答正确： p s q s 由于 (p s q s) ( p s q s) ( p s q s) ( p s q s) = (p q s) (p q s) =(p q r s) (p q r s) (p q r s) (p q r s) 若只有一个人成绩最好，必是p q r s为真，即p成绩最好；若有两个人成绩 并列最好，可能是p,s或者p,r练习：利用主范式判断下式的类型 (pq) (qr) (p q) r) 结果 = M4,M6,M2 该公式是可满足的 、对下面的问题首先符号化，然后使用条规 则进行
7、有效推理证明。 2.1每一个自然数不是奇数就是偶数，自然数是偶 数当且仅当它能被2整除，并不是所有的自然数都 能被2整除。因此，有的自然数是奇数。 解法1：首先定义如下谓词： N(x):x是自然数 Q(x):x是奇数 E(x):x是偶数 I(x):x能被2整除 于是问题可用符号表述为： (x)(N(x)(Q(x)E(x), (x)(N(x) E(x) I(x), (x)(N(x) I(x) ，(x)(N(x) Q(x) 推理证明过程如下： 1 (x)(N(x) I(x) P规则 2 (x)(N(x) I(x) T规则和1 3 N(a) I(a) ES规则和2 4 N(a) T规则和3 5 I(
8、a) T规则和3 6 (x)(N(x)(Q(x)E(x) P规则 7 N(a)(Q(a)E(a) US规则和 8 Q(a)E(a) T规则和 9 (x)(N(x) E(x) I(x) P规则 10 (N(a) E(a) I(a) US规则和 11 (N(a) E(a) T规则5和10 12 N(a)E(a) T规则和11 13 E(a) T规则4和12 14 Q(a) T规则8和13 15 N(a)Q(a) T规则4和14 16(x)(N(x) Q(x) EG规则和15 问题得证。 解法2：采用反证法。证明过程如下 1(x)(N(x) I(x) P规则 2(x)(N(x) I(x) T规则和1
9、 3 N(a) I(a) ES规则和2 4 N(a) T规则和3 5 I(a) T规则和3 6 (x)(N(x) Q(x) P规则(假设前提) 7 (x)( N(x) Q(x) T规则和6 8 N(a) Q(a) US规则和 9 Q(a) T规则和8 10 (x)(N(x)(Q(x)E(x) P规则 11 N(a)(Q(a)E(a) T规则和10 12 Q(a)E(a) T规则4和11 13 E(a) T规则9和12 14 (x)(N(x) E(x) I(x) P规则 15 (N(a) E(a) I(a) US规则和14 16 N(a) E(a) T规则4和13 17 I(a) T规则15和1
10、6 18 I(a) I(a) T规则5和17 19(x)(N(x) Q(x) F规则6和18 问题得证 例2.2天鹅都会飞，而癞蛤蟆不会飞； 所以癞蛤蟆不是天鹅。 解：令TE(x):x是天鹅 l(x):x是癞蛤蟆 F(x):x会飞 于是问题可符号化为： (x)(TE(x) F(x), (x)(l(x) F(x) (x)(l(x) TE(x). 证明过程如下： 1(x)(l(x) TE(x) P规则(假设 前提) 2(x)(l(x) TE(x) T规则和 3 l(a) TE(a) ES规则2 4 l(a) T规则3 5 TE(a) T规则3 6 (x)(TE(x) F(x) P规则 7 TE(a) F(a) US规则和6 8 F(a) T规则5和7 9 (x)(l(x) F(x) P规则 10 l(a) F(a) US规则和9 11 F(a) l(a) T规则和10 12 l(a) T规则8和11 13 l(a) l(a) T规则4和12 14 (x)(l(x) TE(x) F规则和13 问题得证。 例2.3 所有牛都有角，有些动物是牛，所以 有些动物有角 解：设(x):x是牛 (x):x有角 A(x):x是动物 于是问题可描述成： (x)(x) (x),(x)(A(x)(x) (x)(A(x)(x) 证明： 、(x)(A(x)(x) P规则 、A(a)(a)
