范文为教学中作为模范的文章，也常常用来指写作的模板。常常用于文秘写作的参考，也可以作为演讲材料编写前的参考。范文怎么写才能发挥它最大的作用呢？以下是我为大家搜集的优质范文，仅供参考，一起来看看吧

离散数学例题4.5.3篇一

第一部分 集合论

第一章集合的基本概念和运算

1-1 设集合 a ={1，{2}，a，4，3}，下面命题为真是[ b ]

a．2 ∈a；b．1 ∈ a；c．5 ∈a；d．{2}  a。

1-2 a,b,c 为任意集合，则他们的共同子集是[ d ]

a．c；b．a；c．b；d．ø。

1-3 设 s = {n，z，q，r}，判断下列命题是否成立 ？

（1）n  q，q ∈s，则 n  s［不成立］

（2）-1 ∈z，z ∈s，则-1 ∈s［不成立］

1-4 设集合 a ={3，4}，b = {4，3} ∩ ø，c = {4，3} ∩{ ø }，d ={ 3，4，ø }，2e = {x│x ∈r 并且 x-7x + 12 = 0}，f = { 4，ø，3，3}，试问哪两个集合之间可用等号表示 ？

答：a = e；b = c；d = f

1-5 用列元法表示下列集合（1）a = { x│x ∈n 且 x2 ≤ 9 }

（2）a = { x│x ∈n 且 3－x 〈 3 }

答：（1）a = { 0，1，2，3 }；

（2）a = { 1，2，3，4，……} = z+；

第二章二元关系

2-1 给定 x =（3, 2，1），r 是 x 上的二元关系，其表达式如下：

r = {〈x，y〉x，y ∈x 且 x≤ y }

求：(1)domr =?;(2)ranr =?;(3)r 的性质。

答：r = {<2，3>，<1,2>，<1,3>}；

domr={r中所有有序对的x}={2,1,1}={2,1};

ranr={r中所有有序对的y}={3,2,3}={3,2}；

r 的性质:反自反,反对称,传递性质.2-2 设 r 是正整数集合上的关系，由方程 x + 3y = 12 决定，即

r = {〈x，y〉│x，y∈z+ 且 x + 3y= 12}，试求：

（1）r 的列元表达式；（2）给出 dom（r。r）。

答：根据方程式有：y=4-x/3，x 只能取 3，6,9。

（1）r = {〈3，3〉,〈6，2〉,〈9，1〉}；

至于(2),望大家认真完成合成运算 r。r={<3,3>}.然后,给出 r。r 的定义域,即

（2）dom（r。r）= {3}。

2-3 判断下列映射 f 是否是 a 到 b 的函数；并对其中的 f：a→b 指出他的性质，即

是否单射、满射和双射，并说明为什么。

（1）a = {1，2，3}，b = {4，5}，f = {〈1，4〉〈2，4〉〈3，5〉}。

（2）a = {1，2，3} = b，f = {〈1，1〉〈2，2〉〈3，3〉}。

（3）a = b = r，f=x。

（4）a = b = n，f=x2。

（5）a = b = n，f = x + 1。

答：（1）是 a 到 b 的函数，是满射而不是单射；

（2）是双射；

（3）是双射；

（4）是单射，而不是满射；

（5）是单射而不是满射。

2-4 设 a ={1，2，3，4}，a 上的二元关系

r ={〈x，y〉︱（x-y）能被3整除}，则自然映射 g：a→a/r使 g(1)=[c]

a．｛1,2｝；b．｛1,3｝；c．｛1,4｝；d．｛1｝。

2-5 设 a ={1，2，3}，则商集a/ia =[d]

a．｛3｝；b．｛2｝；c．｛1｝；d．｛｛1｝，｛2｝，｛3｝｝。

2-6．设ｆ(x)＝x+1，ｇ(x)＝x-1 都是从实数集合ｒ到ｒ的函数，则ｆ。ｇ＝[c]

a．x+1；b．x-1；c．x；d．x2。

第三章 结构代数(群论初步)

3-1 给出集合及二元运算，阐述是否代数系统，何种代数系统 ？

（1）s1 = {1，1/4,1/3,1/2,2，3，4}，二元运算 *是普通乘法。

（2）s2 = {a1，a2，……，an}，ai ∈r，i = 1，2，……，n ；

二元运算。定义如下：对于所有 ai，aj ∈s2，都有 ai。aj = ai。

（3）s3 = {0，1}，二元运算 * 是普通乘法。

答：（1）二元运算*在s1上不封闭．所以，＂s1，*＂不能构成代数系统。

（2）由二元运算的定义不难知道。在 s2 内是封闭的，所以，〈s2。〉构成代数

系统；然后看该代数系统的类型：该代数系统只是半群。

（3）很明显，〈{0，1}，*〉构成代数系统；满足结合律，为半群；1是幺元，为独异

点；而 0 为零元；结论：仅为独异点，而不是群。

3-2 在自然数集合上，下列那种运算是可结合的［a］

a．x*y = max(x,y)；b．x*y = 2x+y ；

c．x*y = x2+y2 ；d．x*y =︱x-y︱..3-3 设 z 为整数集合，在 z 上定义二元运算。，对于所有 x，y ∈z都有

x。y=x + y，试问〈z。〉能否构成群，为什麽 ？

答：由题已知，集合z满足封闭性；二元运算满足结合律，依此集合z为半群；有幺元为 －5，为独异点.假设代数系统的幺元是集合中的元素 e,则一个方程来自于二元运算定义, 即e。x= e + x，一个方程来自该特殊元素的定义的性质,即e。x = x.由此而来的两个方程联立结果就有: e+x=x 成立.削去 x,e=0 的结果不是就有了吗!；每个元素都有逆.求每个元素的逆元素,也要解联方程,如同求幺元一样的道理；结论是：代数系统〈 z。〉构成群。

第二部分图论方法

第四章 图

4-1 10 个顶点的简单图 g 中有 4 个奇度顶点，问 g 的补图中有几个偶数度顶点 ？ 答：因为10阶完全图的每个顶点的度数都是n-1=9――为奇数。这样一来，一个无向简单图 g 的某顶点的度数是奇数，其补图的相应顶点必偶数，因为一个偶数与一个奇数之和才是奇数．所以，ｇ的补图中应有 10-4＝6 个奇数度顶点。

4-2 是非判断：无向图g中有10条边,4个3度顶点,其余顶点度数全是2,共有 8 个顶点.[是]

4-3 填空补缺：1条边的图 g 中，所有顶点的度数之和为[2]

第五章树

5-1握手定理的应用（指无向树）

（1）在一棵树中有 7 片树叶，3 个 3 度顶点，其余都是 4 度顶点，问有(有1个4度顶点)个？

（2）一棵树有两个 4 度顶点，3 个 3 度顶点，其余都是树叶，问有(9个1度顶点)片？

5-2 一棵树中有 i 个顶点的度数为 i（i=2，…k），其余顶点都是树叶(即一度顶点)，问树叶多少片？设有x片,则 x=

答：假设有 x 片树叶，根据握手定理和树的顶点与边数的关系，有关于树叶的方程，解方程得到树叶数 x = σi（i—2）i + 2，（i = 2，3，……k）。

5-3 求最优 2 元树：用 huffman 算法求带权为 1，2，3，5，7，8 的最优 2 元树 t。试问：（1）t 的权 w（t）？（2）树高几层 ？

答：用 huffman 算法，以 1，2，3，5，7，8 为权，最优 2 元树 t ；然后，计算并回答所求问题：（1）t 的权 w（t）= 61；（2）树高几层：4 层树高。

5-4以下给出的符号串集合中，那些是前缀码？将结果填入[]内.b1 = {0，10，110，1111}[是]b2 = {1，01，001，000}[是]b3 = {a，b，c，aa，ac，aba，abb，abc}[非]b4 = {1，11，101，001，0011}[非]

5-5(是非判断题)11阶无向连通图g中17条边，其任一棵生成树 t 中必有6条树枝 [非]

5-6(是非判断题)二元正则树有奇数个顶点。[是]

5-7 在某次通信中 a，b，c，d，e 出现的频率分别为 5%;10%;20%;30%;35%.求传输他们的最佳前缀码。

1、最优二元树 t；2.每个字母的码字；

答：每个字母出现频率分别为：g、d、b、e、y：14%，o：28%；(也可以不归一,某符号

出现次数即为权，如右下图).。100（近似）7.。563..4。282..2..2。..1..14141414111

1所以，得到编码如下：g（000），d（001），b（100），e（101），y（01），o（11）。

第三部分逻辑推理理论

第六章 命题逻辑

6-1 判断下列语句是否命题，简单命题或复合命题。

（1）2月 17 号新学期开始。[真命题]

（2）离散数学很重要。[真命题]

（3）离散数学难学吗 ？[真命题]

（4）c 语言具有高级语言的简洁性和汇编语言的灵活性。[复合命题]

（5）x + 5 大于 2。[真命题]

（6）今天没有下雨，也没有太阳，是阴天。[复合命题]

6-2 将下列命题符号化.（1）2 是偶素数。

（2）小李不是不聪明，而是不好学。

（3）明天考试英语或考数学。（兼容或）

（4）你明天不去上海，就去北京。（排斥或）

答：（1）符号化为： p ∧ q。

（2）符号化为：p ∧ ﹃q。

（3）符号化为：p ∨ q。

（4）符号化为：（﹃p ∧ q）∨（p ∧ ﹃q）。

6-3分别用等值演算法,真值表法,主析取范式法,判断下列命题公式的类型.（1）﹃（p→q）∧ q；（2）（（p→q）∧ p）→q；（3）（p→q）∧ q。答：（1）0；

（2）σ（0，1，2，3）；

（3）σ（1，3）。

以下两题(6-4;6-5)为选择题,将正确者填入[]内.6-4 令 p：经一堑；q：长一智。命题’’只有经一堑，才能长一智’’符号化为[b]

a． p→q；b．q→p；c．p∧q；d．﹁q→﹁p

6-5 p：天气好；q：我去游玩．命题 ”如果天气好，则我去游玩” 符号化为［b］

a． p→q；b．q→p；c．p∧q；d．﹁q→p

6-6证明题:用不同方法(必须有构造证明法)判断推理结果是否正确。

如果今天下雨，则明天不上体育课。今天下雨了。所以，明天没有上体育课。答：将公式分成前提及结论。

前提：（p→﹃q），p；

结论：﹃q；

证明：（1）（p→﹃q）前提引入

（2）p前提引入

（3）（p→﹃q）∧p（1）（2）假言推理

（4）﹃q

要证明的结论与证明结果一致，所以推理正确。

第七章谓词逻辑

7-1 在谓词逻辑中用 0 元谓词将下列命题符号化

（1）这台机器不能用。

（2）如果 2 ＞ 3，则 2 ＞ 5。

答：（1）﹃f（a）。

（2）l（a，b）→ h（a，z）。

7-2 填空补缺题：设域为整数集合ｚ，命题xy彐z（x-y=z）的真值为（0）

7-3在谓词逻辑中将下列命题符号化

（1）有的马比所有的牛跑得慢。

（2）人固有一死。

答：（1）符号化为：彐x（f（x）∧ 彐y（g（y）∧ h（x，y）））。

（2）与（1）相仿，要注意量词、联结词间的搭配：

x（f（x）→y（g（y）→ h（x，y）））。

《附录》习题符号集

ø 空集, ∪ 并, ∩ 交,⊕ 对称差,～ 绝对补,∑ 累加或主析取范式表达式缩写 , － 普通减法, ÷ 普通除法, ㏑ 自然对数, ㏒ 对数，﹃ 非，量词 ”所有”，”每个”，∨ 析取联结词，∧ 合取联结词，彐 量词”存在”，”有的”。

2010年8月12号。

离散数学例题4.5.3篇二

浅谈离散数学

【摘要】离散数学是一门理论性强,知识点多,概念抽象的基础课程,学生学习起来普遍感到难度很高。本文从离散数学内容、学生学习兴趣的激发、教学内容的安排、教学方式方法的使用等方面,探讨了如何上好、学好离散数学课。

【关键词】离散数学教学方法教师 学生

离散数学研究的是离散量，是计算机科学与技术系各专业的核心课程。课程内容具有知识点多、散、抽象等特点,加之学生不能认识到该课程的重要性,缺乏学习兴趣和学习主动性,不仅忽视该课程的学习,甚至害怕这门课程。因此,创新教学方法,提高学生自主学习的积极性,对提高学生的能力、提升教学质量和水平具有重要的意义。通过一学期的学习和专研,我积累了少许经验,总结了一些关于离散数学的教学方法，仅供大家参考。

一、离散数学的特点

本课程介绍计算机科学与技术系各专业所需要的离散数学基础知识,主要有以下两点特点：

1、知识点集中，概念和定理多：《离散数学》是建立在大量概念之上的逻辑推理学科，概念的理解是我们学习这门学科的核心。掌握、理解和运用这些概念和定理是学好这门课的关键。要特别注意概念之间的联系，而描述这些联系的则是定理和性质。

2、方法性强：离散数学的特点是抽象思维能力的要求较高。培养学生抽象思维能力、逻辑推理能力、缜密概括能力以及分析和解决实际问题能力的主干课程,对学习其他诸多课程,具有重要的指导作用。《离散数学》的证明题多，不同的题型会需要不同的证明方法，同一个题也可能有几种方法，具有很强的方法性。

二、教学困难所在1、离散数学是一门理论性强,知识点多,概念抽象的基础课程, 内容具有知

识点多、散、抽象等特点，学生学者困难；

2、学生不能认识到该课程的重要性,缺乏学习兴趣和学习主动性,不仅忽视该课程的学习,甚至害怕这门课程。

3、离散数学课程在课堂教学难度、教学时间等方面的原因,很多学校都出现师生、学生之间的交流较少，从而使学生学习困难。

三、离散数学的教学方法引导学生提高对离散数学课程应用性的认识,激发学生学习的兴趣和爱好,增强汲取知识的自主性

离散数学课程是一门基础性课程,学习离散数学课程对学生今后的学习和工作,具有重要的作用,例如培养学生的抽象思维能力和缜密的逻辑推理能力,为学生今后处理离散信息,提高专业理论水平,从事计算机的实际工作提供必备的数学工具;通过学习,可以掌握数理逻辑,集合论,代数结构和图论的基本概念和原理,并会运用离散数学的方法,分析和解决计算机理论和应用中的一些问题等。学习主动性是学生的力量之源,因此,引导学生充分认识学习离散数学课程的作用,能够激发学生学习的爱好和热情,提升学生学习的积极性和主动性,从而使学生学有成效。认真备课,合理准备教学内容和安排教学环节,优化教学方式方法

备好课是教学取得预期效果的前提和基础,针对学生学习具体情况,合理准备教学内容和安排教学环节,使用恰当的教学方法,在教学中可以起到事半功倍的效果。

(1)合理地准备教学内容。根据课程教学大纲和离散数学课程定理定义比较多、知识比较抽象的特点以及学生的实际情况,准备深度和广度适合学生特点的教学内容。

(2)合理地讲解课程内容,重难点突出讲解,注意轻重缓急。对于离散数学中比较重要、比较抽象的概念和定理,如逻辑的推理理论、关系的性质、群、图等,认真分析,用多种方式和方法深入

讲解,可以使用解析法、图示法、矩阵法举实例等多种方法讲解。对于比较容易理解和掌握的内容,可以一笔带过。这样,学生对所学内容就会有重点地学习,主次分明,学生不仅可以对所学内容掌握透彻,更能熟练把握离散数学中分析问题和解决问题的思路、方式和方法。

(3)启发式教学和教师讲授相结合。很多人认为,大学教学课时紧,内容多,关键靠学生自主学习,我却认为并不完全是这样的。如果教师不顾学生的理解情况,只顾在讲台上讲授知识,课堂氛围会很沉闷,很多同学不能专注于该门课程的学习,经常走神,教学很难达到预期的效果。因此,有针对性地提问和展开讨论,不仅能够培养学生的思考能力,更能调动学生学习的兴趣和积极性,从而使教学达到最佳效果。也可以引进有趣生动的例子说明概念，既活跃课堂，又巩固了学生的记忆。3 合理布置作业,认真批改作业,有针对性地安排习题课和课后答疑

学数学就要做数学，《离散数学》的学习也不例外。学习数学不仅限于学习数学知识，更重要的还在于学习数学思维方法。为了强化学生能力的训练,培养学生的抽象思维能力、逻辑推理能力、实际问题的解决能力等,在保证作业数量的同时,更要提高布置作业的质量,增加典型简答题、讨论题、推理题、实际应用题等习题在作业中的分量,使学生在掌握各种基本知识和基本技能的同时,提高自身的综合能力。

认真检查和批改作业,是督促学生学习的主要途径,也是教师了解学生理解和掌握所学课程情况的主渠道。必要时,教师可以批改一部分作业,其他作业让同学们之间互相检查和批改,不仅可以督促学生学习,更能让学生在批改其他同学作业时逐步认识到自身的缺陷和不足,以备今后更有针对性地学习。

教师在作业检查和批改过程中发现的主要问题和疑难以及学生提出的有代表性的问题,有必要安排习题课进行讲解,帮助学生对解决疑难,加深对所知识的理解。对于学生比较争论的问题,可以展开讨论,鼓励学生大胆发言,培养学生探索未知的精神和创造性解决实际问题的能力。

四、总结

从此上看，上好离散数学课,关键是根据学生具体实际,有针

对性地安排教学内容,合理使用教学方式方法,最大限度地激发学生的学习兴趣,充分发挥教师的主导作用和学生的主体作用,达到教与学和谐。

参考文献

[1] 屈婉玲,耿素云,张立昂.离散数学[m].北京:高等教育出版社.2008.[2] 黄巍,金国祥.”离散数学”课程教学改革的探讨[j].中国电力教育,2009(8):82-83.[3] 周小燕,胡丰华.对提高离散数学教学质量的探讨[j].浙江科技学院学报,2007,19(2):156-158.[4] 龙浩,张佳佳.怎样教好《离散数学》课[j].贵阳学院学报,2007,2(1):53-57.[5] 廖仲春.离散数学的教学探讨[j].湖南工业职业技术学院学报,2008,8(5)http://

离散数学例题4.5.3篇三

第一章

数学语言与证明方法

例1 设e={ x | x是北京某大学学生}, a,b,c,d是e的子集, a= { x | x是北京人}，b= { x | x是走读生}, c= { x | x是数学系学生}，d= { x | x是喜欢听音乐的学生}.试描述下列各集合中学生的特征:

(ad) ~ c={ x | x是北京人或喜欢听音乐,但不是数学系学生} ~ ab={ x | x是外地走读生}(a-b) d={ x | x是北京住校生, 并且喜欢听音乐} ~ d  ~ b={ x | x是不喜欢听音乐的住校生} 例3 证明:(1)ab=ba(交换律)证 x

xab

 xaxb

(并的定义)

xbxa

(逻辑演算的交换律)

xba

(并的定义)(2)a(bc)=(ab)(ac)(分配律)证 x

xa(bc)

 xa(xb xc)

(并,交的定义)

(xaxb)(xaxc)

(逻辑演算的分配律)

x(ab)(ac)

(并,交的定义)(3)ae=e(零律)证 x

xae

 xaxe

(并的定义)

 xa1

(全集e的定义)

1

(逻辑演算的零律)

xe

(全集e的定义)(4)ae=a(同一律)证 x

xae

 xaxe

(交的定义)

 xa1

(全集e的定义)

 xa

(逻辑演算的同一律)例4 证明 a(ab)=a（吸收律）证 利用例3证明的4条等式证明

a(ab)

=(ae)(ab)

(同一律)

= a(eb)

(分配律)

= a(be)

(交换律)

= ae

(零律)

= 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

(交换律,结合律)

=(a – b)– c

(补交转换律)例6 证明(ab)(ac)=(bc)(ac))((ac)a 例7 设a,b为任意集合, 证明:(1)aab 证 x xa  xaxb

(附加律)

 xab

(2)aba

证 x xab  xaxb

 xa

(化简律)(3)a-ba

证 x xa-b  xaxb

 xa

(化简律)(4)若ab, 则p(a)p(b)证 x xp(a) xa

 xb

(已知ab)

 xp(b)例8 证明 ab=ab-ab.证

ab=(a~b)(~ab)

=(a~a)(ab)(~b~a)(~bb)

=(ab)(~b~a)

=(ab)~(ab)

=ab-ab 例3 若a-b=a, 则ab=

证 用归谬法, 假设ab, 则存在x,使得

xab  xaxb  xa-bxb

(a-b=a)

 xaxbxb  xbxb，矛盾 例4 证明

是无理数

证

假设

是有理数, 存在正整数n,m, 使得

=m/n,不妨设m/n为既约分数.于是m=n, m2=2n2, m2是偶数, 从而m是偶数.设m=2k, 得(2k)2=2n2, n2=2k2, 这又得到n也 是偶数, 与m/n为既约分数矛盾.例6 对于每个正整数n, 存在n个连续的正合数.证

令x=(n+1)!

则 x+2, x+3,…, x+n+1是n个连续的正合数:

i | x+i，i=2,3,…,n+1 例7 判断下述命题是真是假:

若ab=ac, 则b=c.解

反例: 取a={a,b}, b={a,b,c}, c={a,b,d}, 有

ab=ac = {a,b} 但bc, 故命题为假.例8 证明:对所有n1, 1+2+ … +n=n(n+1)/2 证

归纳基础.当n=1时, 1=1(1+1)/2, 结论成立.归纳步骤.假设对n1结论成立, 则有

1+2+ … +n +(n+1)=n(n+1)/2 +(n+1)

(归纳假设)

=(n+1)(n+2)/2 得证当n+1时结论也成立.例9 任何大于等于2的整数均可表成素数的乘积 证 归纳基础.对于2, 结论显然成立.归纳步骤.假设对所有的k(2kn)结论成立, 要证结论 对n+1也成立.若n+1是素数, 则结论成立;否则n+1=ab, 2a,b

命题逻辑

例1 下列句子中那些是命题？

(1)北京是中华人民共和国的首都.(2)2 + 5 ＝8.(3)x + 5 ＞ 3.(4)你会开车吗？

(5)2050年元旦北京是晴天.(6)这只兔子跑得真快呀！(7)请关上门！(8)我正在说谎话.(1),(2),(5)是命题,(3),(4),(6)~(8)都不是命题

例2 将下列命题符号化.(1)王晓既用功又聪明.(2)王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功.(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.解

(1)p∧q

(2)p∧q

(3)p∧q(4)记 r:张辉是三好生, s:王丽是三好生，r∧s(5)简单命题，记 t:张辉与王丽是同学 例3 将下列命题符号化(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)元元只能拿一个苹果或一个梨.(5)王晓红生于1975年或1976年.解

(1)p∨r, 真值:1(2)

p∨q, 真值: 1(3)r∨s,真值: 0(4)记t:元元拿一个苹果,u:元元拿一个梨

(t∧u)∨(t∧u)(5)记v:王晓红生于1975年,w:王晓红生于1976年

(v∧w)∨(v∧w)又可形式化为

v∨w

例4 设p:天冷, q:小王穿羽绒服，将下列命题符号化

(1)只要天冷，小王就穿羽绒服.pq(2)因为天冷，所以小王穿羽绒服.pq

(3)若小王不穿羽绒服，则天不冷.qp 或 pq(4)只有天冷，小王才穿羽绒服.qp(5)除非天冷，小王才穿羽绒服.qp(6)除非小王穿羽绒服，否则天不冷.pq

(7)如果天不冷，则小王不穿羽绒服.pq 或 qp(8)小王穿羽绒服仅当天冷的时候.qp 例5 求下列复合命题的真值

(1)2+2＝4 当且仅当 3+3＝6.(2)2+2＝4 当且仅当 3是偶数.0(3)2+2＝4 当且仅当 太阳从东方升起.(4)2+2＝5 当且仅当 美国位于非洲.(5)f(x)在x0处可导的充要条件是它在 x0处连续.0 例6 公式a=( p1  p2  p3)(p1 p2)

000是成真赋值，001是成假赋值

公式b=(pq)r

000是成假赋值，001是成真赋值 例3 证明 p(qr)(pq)r 证

p(qr)

 p(qr)

（蕴涵等值式）

(pq)r

（结合律）

 (pq)r

（德摩根律）

(pq)r

（蕴涵等值式 例4 证明: p(qr)

(pq)r 方法一

真值表法（见例2）

方法二

观察法.容易看出000使左边成真, 使右边成假.方法三

先用等值演算化简公式, 再观察.例5 用等值演算法判断下列公式的类型(1)q(pq)解

q(pq)

 q(pq)

（蕴涵等值式）

 q(pq)

（德摩根律）

 p(qq)

（交换律，结合律）

 p0

（矛盾律）

 0

（零律）该式为矛盾式.(2)(pq)(qp)解

(pq)(qp)

(pq)(qp)

（蕴涵等值式）

(pq)(pq)

（交换律）

 1 该式为重言式.(3)((pq)(pq))r)

解

((pq)(pq))r)

(p(qq))r

（分配律）

 p1r

（排中律）

 pr

（同一律）

非重言式的可满足式.如101是它的成真赋值,000是它的 成假赋值.例1 求(pq)r 的析取范式与合取范式 解

(pq)r

 (pq)r

(pq)r

析取范式

(pr)(qr)

合取范式 注意: 公式的析取范式与合取范式不惟一.例1(续)求(pq)r 的主析取范式与主合取范式 解(1)(pq)r (pq)r

pq (pq)1

同一律

(pq)(rr)

排中律

(pqr)(pqr)

分配律

 m4m5

r (pp)(qq)r

同一律, 排中律

(pqr)(pqr)(pqr)(pqr)

 m0 m2 m4 m6

得

(pq)r  m0 m2 m4 m5  m6 可记作

 (0,2,4,5,6)(2)(pq)r (pr)(qr)

pr  p0r

同一律

 p(qq)r

矛盾律

分配律

(pqr)(pqr)

分配律

 m1m3

qr (pp)qr

同一律, 矛盾律

(pqr)(pqr)

分配律

 m3m7 得

(pq)r  m1m3m7 可记作

 (1,3,7)例2(1)求 a (pq)(pqr)r的主析取范式 解 用快速求法

(1)pq (pqr)(pqr) m2 m3

pqr  m1

r (pqr)(pqr)(pqr)(pqr)

 m1 m3 m5 m7 得

a m1 m2 m3 m5 m7  (1,2,3,5,7)(2)求 b p(pqr)的主合取范式

解 p (pqr)(pqr)(pqr)(pqr)

 m4m5m6m7

pqr  m1 得

b m1m4m5m6m7  (1,4,5,6,7)例3 用主析取范式判断公式的类型:(1)a (pq)q

(2)b p(pq)

(3)c(pq)r 解(1)a  ( pq)q (pq)q  0

矛盾式(2)b   p(pq) 1  m0m1m2m3

重言式(3)c  (pq)r (pq)r

(pqr)(pqr)(pqr)

(pqr)(pqr)(pqr)

 m0m1m3 m5m7

非重言式的可满足式 例4 用主析取范式判断下面2组公式是否等值:(1)p与(pq)(pq)解

p  p(qq)(pq)(pq) m2m3

(pq)(pq) (pq)(pq)

(pq)(pq) m2m3 故

p (pq)(pq)(2)(pq)r 与 p(qr)解(pq)r (pqr)(pqr)

(pqr)(pqr)(pqr)(pqr)

 m1m3m5 m6m7

p(qr)(pq)(p r)

(pqr)(pqr)(pqr)(pqr)

 m5 m6m7 故

(pq)r

p(qr)例5 某单位要从a,b,c三人中选派若干人出国考察, 需满 足下述条件:(1)若a去, 则c必须去;(2)若b去, 则c不能去;(3)a和b必须去一人且只能去一人.问有几种可能的选派方案? 解

记p:派a去, q:派b去, r:派c去

(1)pr，(2)qr，(3)(pq)(pq)求下式的成真赋值

a=(pr)(qr)((pq)(pq))例6 求a=(pqr)(pqr)(pqr)的主合取范式 解

a  m1m3m7

 m0m2m4m5m6 例1 判断下面推理是否正确:(1)若今天是1号, 则明天是5号.今天是1号.所以, 明天是5号.解

设 p: 今天是1号, q: 明天是5号

推理的形式结构为

(p®q)ùp®q 证明

用等值演算法

(p®q)ùp®q

û ø((øpúq)ùp)úq

û((pùøq)úøp)úq

û øpúøqúq û 1 得证推理正确

(2)若今天是1号, 则明天是5号.明天是5号.所以, 今天是1号.解

设p: 今天是1号, q: 明天是5号.推理的形式结构为

(p®q)ùq®p 证明

用主析取范式法

(p®q)ùq®p

û(øpúq)ùq®p

û ø((øpúq)ùq)úp

û øqúp

û(øpùøq)ú(pùøq)ú(pùøq)ú(pùq)

û m0úm2úm3

01是成假赋值, 所以推理不正确.例2 在自然推理系统p中构造下面推理的证明: 前提: púq, q®r, p®s, øs 结论: rù(púq)证明 ① p®s

前提引入

② ø s

前提引入 ③ ø p

①②拒取式 ④ púq

前提引入

⑤ q

③④析取三段论

⑥ q®r

前提引入

⑦ r

⑤⑥假言推理 ⑧ rù(púq)

⑦④合取 推理正确, rù(púq)是有效结论

例3 构造推理的证明: 若明天是星期一或星期三, 我就有 课.若有课, 今天必需备课.我今天下午没备课.所以, 明天 不是星期一和星期三.解 设 p:明天是星期一, q:明天是星期三，r:我有课，s:我备课 前提:(púq)®r, r®s, øs 结论: øpùøq

例4 构造下面推理的证明: 前提: øpúq, øqúr, r®s 结论: p®s

证明 ① p

附加前提引入 ② øpúq

前提引入

③ q

①②析取三段论 ④ øqúr

前提引入

⑤ r

③④析取三段论

⑥ r®s

前提引入

⑦ s

⑤⑥假言推理 推理正确, p®s是有效结论 例5 构造下面推理的证明

前提: ø(pùq)úr, r®s, øs, p 结论: øq

证明

用归缪法

① q

结论否定引入 ② r®s

前提引入 ③ øs

前提引入 ④ ør

②③拒取式 ⑤ ø(pùq)úr

前提引入

⑥ ø(pùq)

④⑤析取三段论 ⑦ øpúøq

⑥置换

⑧ øp

①⑦析取三段论 ⑨ p

前提引入 ⑩ øpùp

⑧⑨合取 推理正确, øq是有效结论

例6 用归结证明法构造下面推理的证明: 前提:(p®q)®r, r®s, øs 结论:(p®q)®(pùs)解

(p®q)®r û ø(øpúq)úr û(pùøq)úr û(púr)ù(øqúr)

r®s û ørús



(p®q)®(pùs)û ø(øpúq)ú(pùs)û(pùøq)ú(pùs)

û pù(øqús)推理可表成

前提: púr, øqúr, ørús, øs 结论: pù(øqús)

第3章 一阶逻辑 例1(1)4是偶数

4是个体常项, “是偶数”是谓词常项, 符号化为: f(4)(2)小王和小李同岁

小王, 小李是个体常项, 同岁是谓词常项.记a:小王，b: 小李, g(x,y): x与y同岁, 符号化为: g(a,b)(3)x< y

x,y是命题变项, < 是谓词常项, 符号化为: l(x,y)(4)x具有某种性质p

x是命题变项, p是谓词变项, 符号化为: p(x)例2 将下述命题用0元谓词符号化, 并讨论它们的真值:(1)

是无理数, 而

是有理数(2)如果2>3，则3<4 解

(1)设f(x): x是无理数, g(x): x是有理数 符号化为 真值为0(2)设 f(x,y): x>y, g(x,y): x

个体域分别取(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))m(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)xy(f(x)g(y)h(x,y))(2)x(f(x)(y(g(y)h(x,y)))(3) xy(f(x)g(y)h(x,y))(4) xy(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.例8 给定解释i 如下:

(a)个体域 d=n

(b)

(c)

(d)谓词

说明下列公式在 i 下的含义, 并讨论其真值

(1)xf(g(x,a),x)x(2x=x)

假命题

(2)xy(f(f(x,a),y)f(f(y,a),x))xy(x+2=yy+2=x)

假命题(3)xyzf(f(x,y),z)

xyz(x+y=z)

真命题

(4)xf(f(x,x),g(x,x))

x(2x=x2)

真命题(5)f(f(x,a), g(x,a))x+2=2x

不是命题

(6)x(f(x,y)f(f(x,a), f(y,a)))x(x=yx+2=y+2)

真命题

例8(1)~(4)都是闭式, 在i下全是命题.(5)和(6)不是闭式, 在i下(5)不是命题,(6)是命题

例9 判断下列公式的类型:(1)x(f(x)g(x))取解释i1, d1=r，:x是整数，:x是有理数, 取解释i2, d2=r，:x是整数，:x是自然数, 非永真式的可满足式(2)(xf(x))(xf(x))

这是 pp 的代换实例, pp是重言式，永真式(3)(xf(x)yg(y)) yg(y)这是(pq)q的代换实例, (pq)q是矛盾式

矛盾式 例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)

换名规则

或者  xf(x,u,z) yg(x,y,z)

代替规则

 xf(x,u,z) yg(v,y,z)

代替规则(2)x(f(x,y) yg(x,y,z)) x(f(x,y) tg(x,t,z))

换名规则

或者  x(f(x,t) yg(x,y,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)xyf(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))例3 给定解释i:(a)d={2,3},(b)

(c)

:x是奇数，: x=2  y=2，: x=y.在i下求下列各式的真值:(1)x(f(f(x))g(x, f(x)))

解

(f(f(2))g(2, f(2)))(f(f(3))g(3, f(3)))(11)(01) 1(2)xyl(x,y)解

yl(2,y)yl(3,y)(l(2,2)l(2,3))(l(3,2)l(3,3))(10)(01) 0 例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)解

 xf(x)xg(x)

量词否定等值式  x(f(x)g(x))

量词分配等值式 解2  xf(x)yg(y)

换名规则  xf(x)yg(y)

量词否定等值式  x(f(x)yg(y))

量词辖域扩张  xy(f(x)g(y))

量词辖域扩张

第4章 关系 例1 <2,x+5>=<3y4,y>，求 x, y.解

3y4=2, x+5=y  y=2, x= 3 例2

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

ab={<0,a>,<0,b>,<0,c>,<1,a>,<1,b>,<1,c>}

ba ={,,,,,}a = {}, b = 

p(a)a = {<,>, <{},>}

p(a)b = 

例3

(1)r={ | x,yn, x+y<3}={<0,0>, <0,1>, <0,2>, <1,0>, <1,1>, <2,0>}

精选文章

基于你的浏览为你整理资料合集

最新离散数学例题4.5.3(5篇) 文件夹

最新数学教学设计方案案例(大全8篇)

4.5分 4.6万阅读

初中数学拓展题解题技巧 数学活动方案

3分 4.7万阅读

数学教学设计案例含课程思政 小学数学教学设计案例及反思

4.6分 3.6万阅读

最新草莓数学题 草莓数学教案(优秀九篇)

3.9分 4.7万阅读

最新以距离为话题自拟题目 以距离为话题字大全(3篇)

5分 1.3万阅读

最新小学校园广播稿字 小学校园广播稿散文(5篇)

5分 4.5万阅读

证明函数可导的例题大全

3.5分 4万阅读

最新证明函数可导性例题 证明函数可导一定连续汇总

3.8分 4万阅读

最新小学三年级数学吨的认识教学反思(5篇)

4.4分 2.3万阅读

最新小学数学老师教育教学工作总结(5篇)

4.2分 1.4万阅读

最新数学教学培训个人总结(5篇)

4.6分 4万阅读

最新双减优化作业设计课题研究小学数学(13篇)

2.3分 3.2万阅读

最新坚守比离开更重要例子 离开比坚守更重要议论文(16篇)

2.7分 1.1万阅读

最新小学数学课程思政教学案例(14篇)

2.8分 3.8万阅读

最新小学数学课程思政教学案例(二十篇)

5分 4.7万阅读

最新小学数学分层作业设计课题开题报告(15篇)

3.2分 3.3万阅读

最新初中数学思政教学案例(十一篇)

3.7分 3万阅读

最新小学数学作业设计课题研究通用

3.5分 2.2万阅读

2025年中学教学工作规划例文5篇最新

4分 1.4万阅读

离婚协议书5篇最新版(优秀13篇)

3.6分 1.2万阅读