下载文档原格式
《离散数学》课程教学大纲课程编号：06082002 适用专业：计算机科学与技术学时数：60学分数：4 开课学期：第 2 学期先修课程：线性代数、高级语言程序设计(C语言)执笔者：傅彦、顾小丰、刘启和、王庆先、王丽杰编写日期：2011.03 审核人（教学副院长）：周世杰一、课程性质和目标（用小四号黑体字）授课对象：本科生课程类别：学科基础课教学目标（本课程对实现培养目标的作用；学生通过学习该课程后，在思想、知识、能力和素质等方面应达到的目标）：离散数学是一门理论兼实际应用的综合性学科，即具有严备的理论基础，又具备应用科学的特点。
它是计算机科学和其他应用科学的基础理论课。
在课堂教学中，不仅要求学生掌握离散数学具体内容，更重要的是强调离散数学课程的思想，特别是离散数学中逻辑的概念可以说是贯穿到整个教学中；通过课后实验，学生不仅能够加深对离散数学知识的进一步理解，而且还可以从实验中提高自己的实践动手能力和编程能力，最关键的是提高学生学习离散数学的兴趣和了解离散数学与其他课程之间的关系。
通过本课程学习，培养和训练学生的抽象思维能力和严格的逻辑推理的能力，使学生了解离散数学在计算机学科和日常生活中的作用，为学生今后处理离散信息以及用计算机处理大量的日常事物和科研项目，从事计算机科学和应用打下坚实基础，特别是对那些从事计算机科学与理论研究的高层次计算机人员来说，更是一门必不可少的基础理论工具。
二、课程内容安排和要求（用小四号黑体字）（一）教学内容、要求及教学方法（用五号宋体加粗）第1章集合论 2学时掌握：集合的基本概念（集合的概念及表示、集合与元素的关系、集合与集合的关系、几个特殊的集合）、集合的运算。
理解：集合的应用。
了解：粗糙集简介（粗糙集合研究现状、知识与知识库、粗糙集的基本概念、成员关系，粗相等和粗包含）（本部分自学）。
教学方法：问题＋实例的讲授式教学方法第2章计数问题 2学时理解：基本原理（乘法原理、加法原理）、排列与组合（排列问题、组合问题）、容斥原理与鸽笼原理了解：递归关系、离散概率简介、计数问题的应用。
推理离散数学
推理和离散数学是两个不同的概念，但它们之间存在一定的联系。
推理是一种逻辑过程，通过已知的事实或假设来得出新的结论。
在推理过程中，需要使用一些逻辑推理规则和方法，如演绎推理、归纳推理、类比推理等。
推理在数学、哲学、法律、医学等领域都有广泛的应用。
离散数学则是一门研究离散结构和离散量的数学学科，它主要研究离散对象（如集合、图、树、逻辑等）及其相互之间的关系和性质。
离散数学在现代数学、计算机科学、信息科学等领域都有重要的应用。
在离散数学中，逻辑推理是一个重要的工具，用于证明离散对象的性质和定理。
例如，在集合论中，可以使用逻辑推理来证明集合的一些基本性质，如并集、交集、补集等的性质。
在图论中，可以使用逻辑推理来证明图的一些基本性质，如连通性、欧拉路径等。
因此，可以说推理和离散数学之间存在一定的联系，推理是离散数学中的一个重要工具和方法，而离散数学则是推理在数学领域的一个重要应用领域。
第5章一阶逻辑等值演算与推理主要内容1. 等值式与基本的等值式①在有限个体域中消去量词等值式②量词否定等值式③量词辖域收缩与扩张等值式④量词分配等值式2. 基本规则①置换规则②换名规则③代替规则3. 前束范式4. 推理理论①推理的形式结构②推理正确③构造证明④新的推理规则全称量词消去规则，记为UI全称量词引入规则，记为UG存在量词消去规则，记为EI存在量词引入规则，记为EG学习要求1. 深刻理解重要的等值式，并能熟练地使用它们。
2. 熟练地使用置换规则、换名规则和代替规则。
3. 准确地求出给定公式的前束范式（形式可不唯一）。
4. 正确地使用UI、UG、EI、EG规则，特别地要注意它们之间的关系。
5. 对于给定的推理，正确地构造出它的证明。
5.1 一阶逻辑等值式与置换规则定义5.1设A，B是一阶逻辑中任意两个公式，若A B是永真式，则称A与B是等值的。
记做A B，称A B是等值式。
谓词逻辑中关于联结词的等值式与命题逻辑中相关等值式类似。
下面主要讨论关于量词的等值式。
一、基本等值式第一组代换实例由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式，因而第二章的16组等值式给出的代换实例都是一阶逻辑的等值式的模式。
例如：xF(x)┐┐xF(x)x y(F(x,y)→G(x,y))┐┐x y(F(x,y)→G(x,y))等都是(2.1)式的代换实例。
又如：F(x)→G(y)┐F(x)∨G(y)x(F(x)→G(y))→zH(z)┐x(F(x)→G(y))∨zH(z))等都是(2.1)式的代换实例。
第二组消去量词等值式设个体域为有限域D={a1,a2,…,a n}，则有(1)xA(x)A(a1)∧A(a2)∧…∧A(a n)(2)xA(x)A(a1)∨A(a2)∨…∨A(a n) (5.1)第三组量词否定等值式设A(x)是任意的含有自由出现个体变项x的公式，则(1)┐xA(x)x┐A(x)(2)┐xA(x)x┐A(x) (5.2)(5.2)式的直观解释是容易的。
离散数学推理规则公式
离散数学的推理规则包括以下几种：
1. 前提引入规则（P规则）：可以在证明的任何时候引入前提。
2. 结论引入规则（T规则）：在证明的任何时候，已证明的结论都可以作为后续证明的前提。
3. 置换规则：在证明的任何时候，命题公式中的任何子命题公式都可以用与之等价的命题公式置换。
4. 假言推理规则（P∧ (P→Q) ⇒ Q）。
5. 附加规则（P ⇒ P∨Q）。
6. 化简规则（P∧ Q ⇒ P）。
7. 拒收式规则（¬Q∧(P→Q) ⇒ ¬P）。
8. 假言三段论规则((P→Q)∧(Q→R) ⇒ P→R）。
9. 析取三段论规则（¬P∧(P∨Q) ⇒ Q）。
10. 构造性二难规则((P∨Q)∧(P→R)∧(Q→S) ⇒ (S∨R))。
以上内容仅供参考，建议查阅离散数学书籍或咨询数学领域专业人士获取更多专业信息。
推理理论中的推理规则（离散数学）推理理论是一个研究推理方法与规则的学问，其中推理规则是重要的一部分。
推理规则是指在一定的条件下，由一个或多个命题出发，推出另一个命题的规则。
在离散数学中，推理规则包括一些基础的规则和一些复杂的规则。
1. 充分必要条件充分必要条件是指一个命题P能成立的充分必要条件是命题Q 成立。
即P⇔Q。
这里的充分必要条件是指两个命题是等价的，即当且仅当P成立时Q成立，Q成立时P也成立。
例如，一个三角形是等腰三角形的充分必要条件是它有两个相等的角。
2. 反证法反证法是一种常用的推理规则，它常用于证明一个命题的反命题成立。
即假设命题P不成立，通过推理得到矛盾，从而证明了P成立。
例如，证明“所有偶数都不是素数”这个命题可以采用反证法，假设有一个偶数是素数，然后推导出矛盾，从而证明“所有偶数都不是素数”。
3. 等价变形等价变形是指在推理过程中将命题变形成等价的命题。
例如，将P∧Q推导为Q∧P是一种等价变形。
等价变形可以通过逻辑符号的转换、语法规则的变换等方式实现。
4. 全称推理全称推理是指从一个全称命题出发，推出另一个全称命题。
例如，从“对于任意一个自然数n，n+1>n”这个全称命题可以推出“对于任意一个自然数m，m+2>m”。
5. 假言推理假言推理是指从一个条件命题和它的前件出发，推出它的后件的命题。
例如，从“如果今天下雨，那么他就不去逛公园。
今天不下雨”这两个命题可以推出“他会去逛公园”。
6. 假命题推理假命题推理是指从一个假命题出发进行推理，最终得到矛盾。
例如，从假设“1=2”出发，我们可以通过推导得到矛盾，并证明1不等于2。
7. 归谬法归谬法是指从前提推导出矛盾的方法，一般用于证明前提错误的情况。
例如，如果要证明“所有汉语拼音都是辅音加韵母”这个命题是错误的，可以通过归谬法证明，即找出一个汉语拼音不符合这个规则。
8. 消解法消解法是推理中常用的一种方法，可用于在两个命题中推导得到新的命题。
第一章命题逻辑基本概念课后练习题答案1.将下列命题符号化，并指出真值：（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；（2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1；（3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1；（4）p∧q,其中，p:3是素数，q:3是偶数,真值为0；（5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.2.将下列命题符号化，并指出真值：（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1；（2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1；（3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；（4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1；（5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；3.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨；（2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.4.因为p与q不能同时为真.5.设p:今天是星期一，q:明天是星期二，r:明天是星期三：（1）p→q，真值为1（不会出现前件为真，后件为假的情况）；（2）q→p，真值为1（也不会出现前件为真，后件为假的情况）；（3）p q，真值为1；（4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1.返回第二章命题逻辑等值演算本章自测答案5.(1)：∨∨,成真赋值为00、10、11；(2)：0，矛盾式，无成真赋值；(3)：∨∨∨∨∨∨∨,重言式，000、001、010、011、100、101、110、111全部为成真赋值；7.(1)：∨∨∨∨⇔∧∧；(2)：∨∨∨⇔∧∧∧；8.(1)：1⇔∨∨∨,重言式；(2)：∨⇔∨∨∨∨∨∨；(3)：∧∧∧∧∧∧∧⇔0，矛盾式.11.(1)：∨∨⇔∧∧∧∧；(2)：∨∨∨∨∨∨∨⇔1；(3)：0⇔∧∧∧.12.A⇔∧∧∧∧⇔∨∨.第三章命题逻辑的推理理论本章自测答案6.在解本题时，应首先将简单陈述语句符号化，然后写出推理的形式结构*，其次就是判断*是否为重言式，若*是重言式，推理就正确，否则推理就不正确，这里不考虑简单语句之间的内在联系(1)、(3)、(6)推理正确，其余的均不正确，下面以(1)、(2)为例，证明(1)推理正确，(2)推理不正确(1)设p:今天是星期一，q:明天是星期三，推理的形式结构为(p→q)∧p→q(记作*1)在本推理中，从p与q的内在联系可以知道，p与q的内在联系可以知道，p与q不可能同时为真，但在证明时，不考虑这一点，而只考虑*1是否为重言式.可以用多种方法（如真值法、等值演算法、主析取式）证明*1为重言式，特别是，不难看出，当取A为p,B为q时，*1为假言推理定律，即(p→q)∧p→q ⇒ q(2)设p:今天是星期一，q:明天是星期三，推理的形式结构为(p→q)∧p→q(记作*2)可以用多种方法证明*2不是重言式，比如，等值演算法、主析取范式（主和取范式法也可以）等(p→q)∧q→p⇔(┐p∨q) ∧q →p⇔q →p⇔┐p∨┐q⇔⇔∨∨从而可知，*2不是重言式，故推理不正确，注意，虽然这里的p与q同时为真或同时为假，但不考虑内在联系时，*2不是重言式，就认为推理不正确.9.设p:a是奇数，q:a能被2整除，r:a：是偶数推理的形式结构为(p→q┐)∧(r→q)→(r→┐p) (记为*)可以用多种方法证明*为重言式，下面用等值演算法证明：(p→┐q)∧(r→q)→(r→┐p)⇔(┐p∨┐q) ∨(q∨┐r)→(┐q∨┐r) (使用了交换律)⇔(p∨q)∨(┐p∧r)∨┐q∨┐r⇔(┐p∨q)∨(┐q∧┐r)⇔┐p∨(q∨┐q)∧┐r⇔110.设p:a,b两数之积为负数，q:a,b两数种恰有一个负数，r：a，b都是负数.推理的形式结构为(p→q)∧┐p→(┐q∧┐r)⇔(┐p∨q) ∧┐p→(┐q∧┐r)⇔┐p→(┐q∧┐r) (使用了吸收律)⇔p∨(┐q∧┐r)⇔∨∨∨由于主析取范式中只含有5个W极小项，故推理不正确.11.略14.证明的命题序列可不惟一，下面对每一小题各给出一个证明① p→(q→r)前提引入② P前提引入③ q→r①②假言推理④ q前提引入⑤ r③④假言推理⑥ r∨s前提引入（2）证明：① ┐(p∧r)前提引入② ┐q∨┐r①置换③ r前提引入④ ┐q ②③析取三段论⑤ p→q前提引入⑥ ┐p④⑤拒取式（3）证明：① p→q前提引入② ┐q∨q①置换③ (┐p∨q)∧(┐p∨p) ②置换④ ┐p∨(q∧p③置换⑤ p→(p∨q) ④置换15.(1)证明：① S结论否定引入② S→P前提引入③ P①②假言推理④ P→(q→r)前提引入⑤ q→r③④假言推论⑥ q前提引入⑦ r⑤⑥假言推理（2）证明：① p附加前提引入② p∨q①附加③ (p∨q)→(r∧s)前提引入④ r∧s②③假言推理⑤ s④化简⑥ s∨t⑤附加⑦ (s∨t)→u前提引入⑧ u⑥⑦拒取式16.(1)证明：① p结论否定引入② p→ ┐q前提引入③ ┐q ①②假言推理④ ┐r∨q前提引入⑤ ┐r③④析取三段论⑥ r∧┐s前提引入⑦ r⑥化简⑧ ┐r∧r⑤⑦合取（2）证明：① ┐(r∨s)结论否定引入② ┐r∨┐s①置换③ ┐r②化简④ ┐s②化简⑤ p→r前提引入⑥ ┐p③⑤拒取式⑦ q→s前提引入⑧ ┐q④⑦拒取式⑨ ┐p∧┐q⑥⑧合取⑩ ┐(p∨q)⑨置换口p∨q前提引入⑾①口┐(p∨q) ∧(p∨q) ⑩口合取17．设p：A到过受害者房间，q: A在11点以前离开，r：A犯谋杀罪，s：看门人看见过A。
离散数学中的逻辑推理方法逻辑推理是离散数学中的重要概念，它是一种通过推理和论证来得出结论的方法。
逻辑推理在数学、计算机科学、哲学等领域都有广泛的应用。
本文将探讨离散数学中的逻辑推理方法，包括命题逻辑、谓词逻辑和推理规则。
命题逻辑是逻辑推理的基础，它研究的是命题之间的关系。
命题是陈述一个明确的陈述句，可以是真或假。
命题逻辑使用逻辑运算符来连接命题，包括合取、析取、蕴含和等价。
合取表示“且”，析取表示“或”，蕴含表示“如果...则”，等价表示“当且仅当”。
通过这些逻辑运算符，我们可以对命题进行逻辑推理。
谓词逻辑是命题逻辑的扩展，它研究的是命题中的变量和量词。
谓词逻辑引入了谓词符号和量词符号。
谓词符号表示一个命题中的属性或关系，而量词符号表示命题的范围。
谓词逻辑使用量词来限定变量的取值范围，包括全称量词和存在量词。
全称量词表示对于所有的变量都成立，存在量词表示存在一个变量成立。
通过谓词逻辑，我们可以推理出更加复杂的命题。
在逻辑推理中，我们可以使用一些推理规则来推导出新的命题。
其中最常用的推理规则有假言推理、析取三段论和拒取三段论。
假言推理是通过蕴含关系来推导新的命题。
如果我们知道一个条件蕴含另一个条件，那么我们可以推导出新的条件。
析取三段论是通过两个条件的析取来推导出一个新的条件。
拒取三段论是通过两个条件的否定来推导出一个新的条件。
这些推理规则可以帮助我们在逻辑推理中得出正确的结论。
除了推理规则，逻辑推理还涉及到一些重要的概念，如充分必要条件和等价条件。
充分必要条件是指一个条件是另一个条件的必要条件，同时另一个条件也是这个条件的充分条件。
等价条件是指两个条件互相蕴含，即一个条件成立时另一个条件也成立。
通过理解这些概念，我们可以更好地进行逻辑推理。
总之，离散数学中的逻辑推理方法是一种通过推理和论证来得出结论的方法。
命题逻辑和谓词逻辑是逻辑推理的基础，通过逻辑运算符和量词来连接和限定命题。
推理规则和重要概念如充分必要条件和等价条件可以帮助我们进行逻辑推理。
离散数学推理证明1、在自然推理系统F中，构造下面推理的证明不存在能表示成分数的无理数，有理数都能表示成分数。
因此，有理数都不是无理数。
个体域为实数集合。
令F ( x ) : x F(x):xF(x):x是无理数G ( x ) : x G(x):xG(x):x是有理数H ( x ) : x H(x):xH(x):x能表示成分数命题符号化：不存在能表示成分数的无理数：¬ ∃x ( H ( x ) ∧F ( x ) ) \lnot \exist x (H(x) \wedge F(x))¬∃x(H(x)∧F(x))有理数都能表示成分数：∀x ( G ( x ) →H ( x ) ) \forall x(G(x)\rightarrow H(x))∀x(G(x)→H(x))有理数都不是无理数：∀x ( G ( x ) →¬ F ( x ) ) \forall x(G(x) \rightarrow \lnot F(x))∀x(G(x)→¬F(x))证明：（1）¬ ∃x ( H ( x ) ∧F ( x ) ) \lnot \exist x (H(x) \wedge F(x))¬∃x(H(x)∧F(x))（2）∀x ( ¬ H ( x ) ∨¬ F ( x ) ) \forall x (\lnot H(x) \vee \lnot F(x))∀x(¬H(x)∨¬F(x)) 量词转换、摩根律（3）¬ H ( a ) ∨¬ F ( a ) \lnot H(a) \vee \lnot F(a)¬H(a)∨¬F(a) 去掉全称量词（4）H ( a ) →¬ F ( a ) H(a) \rightarrow \lnot F(a)H(a)→¬F(a)（5）∀x ( G ( x ) →H ( x ) ) \forall x(G(x)\rightarrow H(x))∀x(G(x)→H(x))（6）G ( a ) →H ( a ) ) G(a)\rightarrow H(a))G(a)→H(a)) 去掉全称量词（7）G ( a ) →¬ F ( a ) G(a) \rightarrow \lnot F(a)G(a)→¬F(a) (4)与(6)（8）∀x ( G ( x ) →¬ F ( x ) ) \forall x(G(x) \rightarrow \lnot F(x))∀x(G(x)→¬F(x)) 添加全称量词2、在自然推理系统中，构造下面推理的证明任何自然数都是整数；存在着自然数。
