首页 > 最新更新 > 离散数学例题整理
热点专题网站地图搜索文档

离散数学例题整理

2022-07-27 17:54:16   文档大全网     [ 字体：小 中 大 ] [ 阅读： ]

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《离散数学例题整理》，欢迎阅读！
例题,离散,整理,数学
. .

第一章 定律证明:

(1) AB=BA (交换律) 证 x xAB

xA 或 xB, 自然有 xB 或 xA xBA

得证 ABBA.

同理可证 BAAB.

(2) A(BC)=(AB)(AC) (分配律) 证 x xA(BC)

xA或(xB且 xC )

(xA或xB)且(xA或xC) x(AB)(AC)

得证 A(BC)(AB)(AC). 类似可证 (AB)(AC)A(BC). (3) AE=E (零律)

证 根据并的定义, 有EAE. 根据全集的定义, 又有A EE. (4) AE=A (同一律)

证 根据交的定义, 有AEA. 又, x xA,

根据全集E的定义,

xE, 从而 xA且xE, xAE 得证 AAE.

例4 证明 A(AB)=A （吸收律） 证 利用例3证明的4条等式证明 A(AB)

= (AE)(AB) (同一律) = A(EB) (分配律) = A(BE) (交换律) = AE (零律) = A (同一律)

例5 证明 (A-B)-C=(A-C)-(B-C) 证 (A-C)-(B-C)

= (A ~C) ~(B ~C) (补交转换律)

= (A ~C) (~B ~~C) (德摩根律) = (A ~C) (~B C) (双重否定律) = (A ~C ~B)(A ~C C) (分配律) = (A ~C ~B)(A ) (矛盾律) = A ~C ~B (零律,同一律) = (A ~B) ~C (交换律,结合律)

1 / 13


. .

= (A – B) – C (补交转换律)

例6 证明 (AB)(AC)= (BC) - A 证 (AB)(AC)

=((AB) - (AC))((AC) - (AB)) =((AB)~A~C)((AC)~A~B) = (B~A~C)(C~A~B) =((B~C)(C~B))~A =((B-C)(C-B))~A = (BC) - A



例7 设A,B为任意集合, 证明: 若AB, 则P(A)P(B) 证 x xP(A) xA xB (已知AB) xP(B)

例8 证明 AB=AB-AB. AB=(A~B)(~AB)

=(A~A)(AB)(~B~A)(~BB) =(AB)(~B~A) =(AB)~(AB) =AB-AB



直接法若n是奇数, 则n2也是奇数. 假设n是奇数, 则存在kN, n=2k+1. 于是 n2 = (2k+1)2 = 2(2k2+2k)+1 得证n2是奇数.

间接法 若n2是奇数, 则n也是奇数. 只证:若n是偶数, 则n2也是偶数. 假设n是偶数, 则存在kN, n=2k. 于是 n2 = (2k)2= 2(2k2) 得证n2是偶数.

归谬法若A-B=A, 则AB=

证 用归谬法, 假设AB, 则存在x,使得 xAB xA且xB xA-B且xB (A-B=A) (xA且xB)且xB xB且xB, 矛盾

构造性对每正整数n, 存n个连的正合数. 证 令x=(n+1)! +1

2 / 13


. .

考虑如下n个连续正整数：x+1, x+2,…, x+n ， 对于i（i=1,2,3,…,n），x+i=(n+1)! +(1+i), 此式含有因子1+i，而1+i不等于1也不等于x+i， 因此x+i是合数。所以x+1, x+2,…, x+n 是n个连续的正合数。

非构造性对每个正整数n, 存在大于n的素数. 令x等于所有小于等于n的素数的乘积加1, 则 x不能被所有小于等于n的素数整除.

于是, x或者是素数, 或者能被大于n的素数整除. 因此,存在大于n的素数.

2

数学归：对所有n1, 1+3+5+ … +(2n-1)=n 归纳基础. 当n=1时, 1=12, 结论成立. 归纳步骤. 假设对n(n1)结论成立, 则考虑n+1的情况有

1+3+5+ … +(2n-1)+(2n+1)=n2 +(2n+1) = (n+1)2 得证当n+1时结论也成立.

第二数学归任>=2的整数均可表成素数的乘积 证 归纳基础. 对于2, 结论显然成立.

归纳步骤. 假设对所有的k(2kn)结论成立, 要证结论 对n+1也成立. 若n+1是素数, 则结论成立; 否则n+1=ab, 2a,b<n. 由归纳假设, a,b均可表成素数的乘积, 从而n+1 也可表成素数的乘积. 得证结论对n+1成立.

命题为假的证明——举反例 例11 证明下述命题不成立: 若AB=AC, 则B=C.

证明 反例: 取A={a,b}, B={a,b,c}, C={a,b,d}, 有 AB=AC = {a,b} 但BC, 故命题不成立.

第二章

例3 证明 p(qr) (pq)r 证 p(qr)

p(qr) （蕴涵等值式） (pq)r （结合律） (pq)r （德摩根律） (pq) r （蕴涵等值式）

(1) q(pq)

3 / 13


. .

解 q(pq)

q(pq) （蕴涵等值式） q(pq) （德摩根律）

p(qq) （交换律，结合律） p0 （矛盾律） 0 （零律） 该式为矛盾式.

(2) (pq)(qp) 解 (pq)(qp)

(pq)(qp) （蕴涵等值式） (pq)(pq) （交换律） 1

该式为重言式.

(pq)r 的析取式与合取式 解 (pq)r (pq)r

(pq)r析取式

(pr)(qr) 合取式

(pq)r 的主析取式主合取式 解 (1) (pq)r (pq)r pq (pq)1 同一律 (pq)(rr) 排中律

(pqr)(pqr) 分配律 m4m5

r (pp)(qq)r 同一律, 排中律

(pqr)(pqr)(pqr)(pqr) m0m2m4m6 分配律

得 (pq)rm0m2m4 m5 m6 可记作 (0,2,4,5,6)

(2) (pq)r (pr)(qr) prp0r 同一律 p(qq)r 矛盾律

(pqr)(pqr)分配律 M1M3

qr (pp)qr 同一律, 矛盾律 (pqr)(pqr) 分配律 M3M7

得 (pq)rM1M3M7 可记作 (1,3,7)

4 / 13


. .

快速求 A (pq)(pqr)r的主析取式 (1) pq (pqr)(pqr) m2m3 pqrm1

r(pqr)(pqr)(pqr)(pqr) m1m3m5m7

得 Am1m2m3m5m7 (1,2,3,5,7) (2) 求 Bp(pqr)的主合取式 解 p (pqr)(pqr)

(pqr)(pqr)

M4M5M6M7 pqrM1

得BM1M4M5M6M7 (1,4,5,6,7)

例3 用主析取式判断公式的类型:

(1) A(pq)q (3) C (pq)r

A(pq)q ( pq)q 0 矛盾式 (2) Bp(pq)

Bp(pq) 1 m0m1m2m3 重言式 (3) C (pq)r

C (pq)r (pq)r

(pqr)(pqr)(pqr) (pqr)(pqr)(pqr)

m0m1m3m5m7 非重言式的可满足式

用主析取式判断下面2组公式是否等值: (1) p与(pq)(pq)

解 p p(qq) (pq)(pq) m2m3 (pq)(pq) (pq)(pq) (pq)(pq) m2m3 故 p (pq)(pq) (2) (pq)r 与 p(qr)

解 (pq)r (pqr)(pqr) (pqr) (pqr)(pqr)(pqr) m1m3m5m6m7

p(qr) (pq)(pr)

(pqr)(pqr)(pqr)(pqr) m5m6m7

故 (pq)r 不等于p(qr)

例5 某单位要从A,B,C三人中选派若干人出国考察, 需满 足下述条件:

(1) 若A去, 则C必须去; (2) 若B去, 则C不能去;

(3) A和B必须去一人且只能去一人.

5 / 13


. .

问有几种可能的选派方案?

解 记p:派A去, q:派B去, r:派C去

(1) pr, (2) qr, (3) (pq)(pq) 求下式的成真赋值

A=(pr)(qr)((pq)(pq)) 求A的主析取式

A=(pr)(qr)((pq)(pq)) (pr)(qr)((pq)(pq)) ((pq)(pr)(rq)(rr)) ((pq)(pq))

((pq)(pq))((pr)(pq)) ((rq)(pq))((pq)(pq)) ((pr)(pq))((rq)(pq)) (pqr)(pqr) 成真赋值:101,010

结论: 方案1 派A与C去方案2派B去

A=(pqr)(pqr)(pqr)的主合取式 解A m1m3m7 M0M2M4M5M6



第二章

判断若今天是1号, 则明天是5号. 今天是1号. 所以, 明天是5号.

解 设 p: 今天是1号, q: 明天是5号 推理的形式结构为 (pq)pq 证明 用等值演算法 (pq)pq((pq)p)q



((p

p

q)p)q

qq 1

得证推理正确

判断若下午气温超过30度, 则小燕必去游泳，若她去游泳她就不去看电影了.

所以若小燕没去看电影, 下午气温必定超过了30度. m1

解 设p: 下午气温超过30度, q: 小燕去游泳，r: 小燕去看电影. 推理的形式结构为 ((pq)qr)rp) 证明 主析取式法 ((pq)qr)rp) p r

m1m3m4m5m6 m7

主析取式中缺少m0， m2，不是重言式，不正确。

6 / 13


. .

前提:pq, qr, ps, s结论: rpq 直接证明法

证明①ps 前提引入 ②s 前提引入 ③p ①②拒取式 ④pq 前提引入

⑤q ③④析取三段论 ⑥qr 前提引入 ⑦r ⑤⑥假言推理 ⑧rpq⑦④合取 推理正确rpq是有效结论

构造推理的证明: 若明天是星期一或星期三, 我就有

课. 若有课, 今天必需备课. 我今天下午没备课. 所以, 明天 不是星期一和星期三.

解 设 p:明天是星期一, q:明天是星期三， r:我有课， s:我备课

前提: (pq)r, rs, s 结论: pq

前提: (pq)r, rs, s 结论: pq 证明

①rs前提引入 ②s前提引入

③r ①②拒取式 ④ (pq)r前提引入 ⑤(pq) ③④拒取式 ⑥pq ⑤置换

结论有效, 即明天不是星期一和星期三

例4前提: pq, qr, rs结论: ps 证明①p 附加前提引入 ②pq 前提引入

③q ①②析取三段论 ④qr 前提引入

⑤r ③④析取三段论 ⑥rs 前提引入 ⑦s ⑤⑥假言推理 推理正确ps是有效结论

例5前提: (pq)r, rs, s, p结论: q 证明 用归缪法

①q 结论否定引入 ②rs 前提引入

7 / 13


. .

③s前提引入

④r ②③拒取式 ⑤(pq)r前提引入

⑥(pq) ④⑤析取三段论 ⑦pq ⑥置换

⑧p ①⑦析取三段论 ⑨p前提引入

⑩pp ⑧⑨合取 推理正确q是有效结论

例6前提: pqr, rs, s结论: pq 归结证明法 解pqr pqr

pqr pr)qr

rsrs

pqpq 把推理的前提改写成 前提prqrrss,pq (结论均为0, 不必写出) 前提prqrrss ,pq 证明①pr 前提引入 ②pq 前提引入 ③qr ①②归结 ④qr 前提引入 ⑤r ③④归结 ⑥rs前提引入 ⑦s⑤⑥归结 ⑧s前提引入

⑨ 0 ⑦⑧合取

第三章

将下述命题用0元谓词符号化, 并讨论它们的真值: (1) 根2是无理数, 而根3是有理数 (2) 如果2>3，则3<4

解 (1) 设F(x): x是无理数, G(x): x是有理数 符号化为 真值为0

(2) 设 F(x,y): x>y, G(x,y): x<y, 符号化为 F(2,3)G(3,4) 真值为1

8 / 13


. .

例3 在一阶逻辑中将下面命题符号化: (1) 人都爱美; (2) 有人用左手写字

个体域分别取(a) 人类集合, (b) 全总个体域 . 解: (a) (1) 设F(x): x爱美, 符号化为 x F(x) (2) 设G(x): x用左手写字, 符号化为 x G(x) (b) 设M(x): x为人， F(x), G(x)同(a)中 (1) x (M(x)F(x)) (2) x (M(x)G(x))

例4 将以下命题符号化, 并讨论其真值: (1) 对任意的x, 均有x2-3x+2=(x-1)(x-2) (2) 存在x, 使得x+5=3

分别取(a) 个体域D1=N, (b) 个体域D2=R

解 记F(x): x2-3x+2=(x-1)(x-2), G(x): x+5=3 (a) (1) x F(x) 真值为1 (2) x G(x) 真值为0 (b) (1) x F(x) 真值为1 (2) x G(x) 真值为1

例5 将下面命题符号化: (1) 兔子比乌龟跑得快

(2) 有的兔子比所有的乌龟跑得快 (3) 并不是所有的兔子都比乌龟跑得快 (4) 不存在跑得一样快的兔子和乌龟

解 用全总个体域，令F(x): x是兔子, G(y): y是乌龟, H(x,y): x比y跑得快, L(x,y): x和y跑得一样快 (1) xy(F(x)G(y)H(x,y)) (2) x(F(x)(y (G(y)H(x,y))) (3) xy(F(x)G(y)H(x,y)) (4) xy(F(x)G(y)L(x,y))

例6 公式 x(F(x,y)yG(x,y,z))

x的辖域:(F(x,y)yG(x,y,z))， 指导变元为x y的辖域:G(x,y,z)， 指导变元为y x的两次出现均为约束出现

y的第一次出现为自由出现, 第二次出现为约束出现 z为自由出现.

例7 公式 x(F(x)xG(x))

x的辖域:(F(x)xG(x))， 指导变元为x x的辖域:G(x)， 指导变元为x

x的两次出现均为约束出现. 但是, 第一次出现的x是x中 的x, 第二次出现的x是x中的x.

9 / 13


. .

例1 消去公式中既约束出现、又自由出现的个体变项 (1) xF(x,y,z) yG(x,y,z)

uF(u,y,z) yG(x,y,z) 换名规则 uF(u,y,z) vG(x,v,z) 换名规则 (2) x(F(x,y) yG(x,y,z))

x(F(x,y) tG(x,t,z)) 换名规则

例2 设个体域D={a,b,c}, 消去下面公式中的量词: (1) x(F(x)G(x))

(F(a)G(a))(F(b)G(b))(F(c)G(c)) (2) x(F(x)yG(y))

xF(x)yG(y) 量词辖域收缩 (F(a)F(b)F(c))(G(a)G(b)G(c)) (3) xyF(x,y)

x(F(x,a)F(x,b)F(x,c))

(F(a,a)F(a,b)F(a,c))(F(b,a)F(b,b)F(b,c)) (F(c,a)F(c,b)F(c,c))

例4 证明以下等值式:

x(M(x)F(x)) x(M(x)F(x))

证 左边 x (M(x)F(x)) 量词否定等值式 x(M(x)F(x)) x(M(x)F(x)) 例5 求公式的前束式 (1) xF(x)xG(x)

解1 xF(x)xG(x) 量词否定等值式 x(F(x)G(x)) 量词分配等值式 解2 xF(x)yG(y) 换名规则

xF(x)yG(y) 量词否定等值式 x(F(x)yG(y)) 量词辖域扩 xy(F(x)G(y)) 量词辖域扩

第四章

笛卡儿积

A={0, 1}, B={a, b, c}

AB={<0,a>,<0,b>,<0,c>,<1,a>,<1,b>,<1,c>} BA ={<a,0>,<b,0>,<c,0>,<a,1>,<b,1>,<c,1>}

(1) R={<x,y> | x,yN, x+y<3}

={<0,0>, <0,1>, <0,2>, <1,0>, <1,1>, <2,0>}

(2) C={<x,y> | x,yR, x2+y2=1}，其中R代表实数集合，

10 / 13


. .

C是直角坐标平面上点的横、纵坐标之间的关系， C中的所有的点恰好构成坐标平面上的单位圆. (3) R={<x,y,z> | x,y,zR, x+2y+z=3}， R代表了空间直角坐标系中的一个平面.



例1

R={<a,{b}>,<c,d>,<{a},{d}>,<d,{d}>}, 则 domR ={ a, c, {a}, d } ranR ={{b}, d, {d}}

fldR = { a, c, {a}, d, {b}, {d}}

例2R={<1,2>, <2,3>, <1,4>, <2,2>}

S={<1,1>, <1,3>, <2,3>, <3,2>, <3,3>} R1={<2,1>,<3,2>,<4,1>,<2,2>} R∘S = {<1,3>, <2,2>, <2,3> } S∘R ={<1,2>, <1,4>, <3,2>, <3,3>}

第六章

已知图G有10条边, 4个3度顶点, 其余顶点的度数均小 于等于2, 问G至少有多少个顶点? 解 设G有n个顶点. 由握手定理, 43+2(n-4)210 解得 n8

证明不存在具有奇数个面且每个面都具有奇数条棱的多面体. 证 用反证法. 假设存在这样的多面体, 作无向图G=<V,E>, 其中 V={v | v为多面体的面},

E={(u,v) | u,vVu与v有公共的棱 uv}.

根据假设, |V|为奇数且vV, d(v)为奇数. 这与握手定理的推论矛盾.

设9阶无向图的每个顶点的度数为5或6, 证明它至少有5个6度顶点或者至少

有6个5度顶点.

证 讨论所有可能的情况. 设有a个5度顶点和b个6度顶点 (1)a=0, b=9; (2)a=2, b=7;

11 / 13


. .

(3)a=4, b=5; (4)a=6, b=3; (5)a=8, b=1

(1)~(3) 至少5个6度顶点, (4)和(5) 至少6个5度顶点 子图

(1),(2),(3)是(1)的子图, (2),(3)是真子图, (1)是母图. (1),(3)是(1)的生成子图.

(2)是{d,e,f }的导出子图, 也是{e5, e6, e7}导出子图. (3)是{e1, e3, e5, e7}的导出子图

画出4阶3条边的所有非同构的无向简单图

解 总度数为6, 分配给4个顶点, 最大度为3, 且奇度顶点数

为偶数, 有下述3个度数列: (1) 1,1,1,3;(2)1,1,2,2;(3)0,2,2,2.

画出3个以1,1,1,2,2,3为度数列的非同构的无向简单图

(1) v1到v4,v4到v1长为3的通路各有多少条? (2) v1到自身长为1,2,3,4的回路各有多少条? (3) 长为4的通路共有多少条?其中有多少条回路? (4) 长度小于等于4的回路共有多少条?

(5) 写出D的可达矩阵, 并问D是强连通的吗? 解v1到v4长为3的通路有3条, v4到v1长为3的通路有0条

v1到自身长为1,2,3,4的回路各有1条 长为4的通路共有16条, 其中有3条回路 长度小于等于4的回路共有 8条

例1 已知无向树T中, 有1个3度顶点, 2个2度顶点, 其余顶 点全是树叶. 试求树叶数, 并画出满足要求的非同构的无 向树.

解 设有x片树叶,

12 / 13


. .

2(2+x)=13+22+x

解得x=3，故T有3片树叶. T的度数列为1, 1, 1, 2, 2, 3

例2 画出所有6阶非同构的无向树

解 5条边, 总度数等于10（同构性质：顶点数相等，边数相等，通过调整顶点顺序度数列相等） 可能的度数列: (1) 1,1,1,1,1,5 (2) 1,1,1,1,2,4 (3) 1,1,1,1,3,3 (4) 1,1,1,2,2,3 (5) 1,1,2,2,2,2

例1 求以1,3,4,5,6为权的最优2元树, 并计算它的权 解

例4 右图表示算式

((b+(c+d))a)((ef)(g+h)(ij)) 波兰符号法

b + cdaef + ghij 逆波兰符号法

bcd + + aefgh + ij

13 / 13


本文来源：https://www.wddqxz.cn/2be8d5ae6b0203d8ce2f0066f5335a8102d26667.html

相关推荐
最新更新
热门阅读
正在阅读