离散数学例题整理.docx

《离散数学例题整理.docx》由会员分享，可在线阅读，更多相关《离散数学例题整理.docx（17页珍藏版）》请在冰豆网上搜索。

离散数学例题整理

第一章

定律证明:

（1）AB=BA（交换律）

证xxAB

xA或xB,自然有xB或xA

xBA

得证ABBA.

同理可证BAAB.

（2）A（BC）=（AB）（AC）（分配律）

证xxA（BC）

xA或（xB且xC）

（xA或xB）且（xA或xC）

x（AB）（AC）

得证A（BC）（AB）（AC）.

类似可证（AB）（AC）A（BC）.

（3）AE=E（零律）

证根据并的定义,有EAE.

根据全集的定义,又有AEE.

（4）AE=A（同一律）

证根据交的定义,有AEA.

又,xxA,

根据全集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）（~BC）（双重否定律）

=（A~C~B）（A~CC）（分配律）

=（A~C~B）（A）（矛盾律）

=A~C~B（零律,同一律）

=（A~B）~C（交换律,结合律）

=（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）

证xxP（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,使得

xABxA且xB

xA-B且xB（A-B=A）

（xA且xB）且xB

xB且xB,矛盾

构造性对每正整数n,存n个连的正合数.

证令x=（n+1）!

+1

考虑如下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的素数.

数学归：

对所有n1,1+3+5+…+（2n-1）=n2

归纳基础.当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+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）（蕴涵等值式）

（pq）r（结合律）

（pq）r（德摩根律）

（pq）r（蕴涵等值式）

（1）q（pq）

解q（pq）

q（pq）（蕴涵等值式）

q（pq）（德摩根律）

p（qq）（交换律，结合律）

p0（矛盾律）

0（零律）

该式为矛盾式.

（2）（pq）（qp）

解（pq）（qp）

（pq）（qp）（蕴涵等值式）

（pq）（pq）（交换律）

1

该式为重言式.

（pq）r的析取范式与合取范式

解（pq）r

（pq）r

（pq）r析取范式

（pr）（qr）合取范式

（pq）r的主析取范式主合取范式

解

（1）（pq）r（pq）r

pq（pq）1同一律

（pq）（rr）排中律

（pqr）（pqr）分配律

m4m5

r（pp）（qq）r同一律,排中律

（pqr）（pqr）（pqr）（pqr）

m0m2m4m6分配律

得（pq）rm0m2m4m5m6

可记作（0,2,4,5,6）

（2）（pq）r（pr）（qr）

prp0r同一律

p（qq）r矛盾律

（pqr）（pqr）分配律

M1M3

qr（pp）qr同一律,矛盾律

（pqr）（pqr）分配律

M3M7

得（pq）rM1M3M7

可记作（1,3,7）

快速求A（pq）（pqr）r的主析取范式

（1）pq（pqr）（pqr）m2m3

pqrm1

r（pqr）（pqr）（pqr）（pqr）

m1m3m5m7

得Am1m2m3m5m7（1,2,3,5,7）

（2）求Bp（pqr）的主合取范式

解p（pqr）（pqr）

（pqr）（pqr）

M4M5M6M7

pqrM1

得BM1M4M5M6M7（1,4,5,6,7）

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

（1）A（pq）q（3）C（pq）r

A（pq）q（pq）q0矛盾式

（2）Bp（pq）

Bp（pq）1m0m1m2m3重言式

（3）C（pq）r

C（pq）r（pq）r

（pqr）（pqr）（pqr）

（pqr）（pqr）（pqr）

m0m1m3m5m7非重言式的可满足式

用主析取范式判断下面2组公式是否等值:

（1）p与（pq）（pq）

解pp（qq）（pq）（pq）m2m3

（pq）（pq）（pq）（pq）

（pq）（pq）m2m3

故p（pq）（pq）

（2）（pq）r与p（qr）

解（pq）r（pqr）（pqr）（pqr）

（pqr）（pqr）（pqr）

m1m3m5m6m7

p（qr）（pq）（pr）

（pqr）（pqr）（pqr）（pqr）

m5m6m7

故（pq）r不等于p（qr）

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

足下述条件:

（1）若A去,则C必须去;

（2）若B去,则C不能去;

（3）A和B必须去一人且只能去一人.

问有几种可能的选派方案

解记p:

派A去,q:

派B去,r:

派C去

（1）pr,

（2）qr,（3）（pq）（pq）

求下式的成真赋值

A=（pr）（qr）（（pq）（pq））

求A的主析取范式

A=（pr）（qr）（（pq）（pq））

（pr）（qr）（（pq）（pq））

（（pq）（pr）（rq）（rr））

（（pq）（pq））

（（pq）（pq））（（pr）（pq））

（（rq）（pq））（（pq）（pq））

（（pr）（pq））（（rq）（pq））

（pqr）（pqr）

成真赋值:

101,010

结论:

方案1派A与C去方案2派B去

A=（pqr）（pqr）（pqr）的主合取范式

解Am1m3m7

M0M2M4M5M6

第二章

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

今天是1号.所以,明天是5号.

解设p:

今天是1号,q:

明天是5号

推理的形式结构为（pq）pq

证明用等值演算法

（pq）pq（（pq）p）q

（（pq）p）q

pqq1

得证推理正确

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

解设p:

下午气温超过30度,q:

小燕去游泳，r:

小燕去看电影.

推理的形式结构为（（pq）qr）rp）

证明主析取范式法

（（pq）qr）rp）

pr

m1m3m4m5m6m7

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

前提:

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前提引入

③s前提引入

④r②③拒取式

⑤（pq）r前提引入

⑥（pq）④⑤析取三段论

⑦pq⑥置换

⑧p①⑦析取三段论

⑨p前提引入

⑩pp⑧⑨合取

推理正确q是有效结论

例6前提:

pqr,rs,s结论:

pq

归结证明法

解pqrpqr

pqrpr）qr

rsrs

pqpq

把推理的前提改写成

前提prqrrss,pq

（结论均为0,不必写出）

前提prqrrss,pq

证明①pr前提引入

②pq前提引入

③qr①②归结

④qr前提引入

⑤r③④归结

⑥rs前提引入

⑦s⑤⑥归结

⑧s前提引入

⑨0⑦⑧合取

第三章

将下述命题用0元谓词符号化,并讨论它们的真值:

（1）根2是无理数,而根3是有理数

（2）如果2>3，则3

解

（1）设F（x）:

x是无理数,G（x）:

x是有理数

符号化为

真值为0

（2）设F（x,y）:

x>y,G（x,y）:

x

符号化为F（2,3）G（3,4）

真值为1

例3在一阶逻辑中将下面命题符号化:

（1）人都爱美;

（2）有人用左手写字

个体域分别取（a）人类集合,（b）全总个体域.

解:

（a）

（1）设F（x）:

x爱美,符号化为xF（x）

（2）设G（x）:

x用左手写字,符号化为xG（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）xF（x）真值为1

（2）xG（x）真值为0

（b）

（1）xF（x）真值为1

（2）xG（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.

例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）

解1xF（x）xG（x）量词否定等值式

x（F（x）G（x））量词分配等值式

解2xF（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={,,,,,}

BA={,,,,,}

（1）R={|x,yN,x+y

={,,,,,}

（2）C={|x,yR,x2+y2=1}，其中R代表实数集合，

C是直角坐标平面上点的横、纵坐标之间的关系，

C中的所有的点恰好构成坐标平面上的单位圆.

（3）R={|x,y,zR,x+2y+z=3}，

R代表了空间直角坐标系中的一个平面.

例1

R={,,,},则

domR={a,c,{a},d}

ranR={{b},d,{d}}

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

例2R={,,,}

S={,,,,}

R1={,,,}

R°S={,,}

S°R={,,,}

第六章

已知图G有10条边,4个3度顶点,其余顶点的度数均小

于等于2,问G至少有多少个顶点

解设G有n个顶点.由握手定理,

43+2（n-4）210

解得n8

证明不存在具有奇数个面且每个面都具有奇数条棱的多面体.

证用反证法.假设存在这样的多面体,作无向图G=,

其中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;

（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片树叶,

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+cdaef+ghij

逆波兰符号法

bcd++aefgh+ij