离散数学问题_百度知道
离散数学问题
么是简单合取（析取）式，极小项，还有极大项，什么是范式
由有限个简单合取式构成的析取式称为析取范式如（p∧q）∨（p∧┓p∧┓r） 由有限个简单析取式构成的合取式称为合取范式仅由有限个命题变项或其否定构成的析取式称为简单析取式；(2)一个简单合取式是矛盾式，当且仅当它同时含一个命题变项及其否定。
r∧(p∨q) ∧( p∨q∨┓r)析取范式和合取范式统称为范式极小项为只由逻辑与和补运算符组成的 n 个变量的逻辑表达式例如，下列是极小项的例子:a b'c a' b c n 个变量有 2n 个极小项 - 这是因为在极小项表达式中一个变量要么是自身要么是它的补的形式 - n 个变量每个都有两种选择极大项是极小项想法的对偶。例如，下面是极大项的例子:a+b'+c a'+b+c n 个变量也有 2n 个极大项 - 这是因为在极大项表达式中一个变量要么是自身要么是它的补的形式 - n 个变量每个都有两种选择。不再使用 AND 和补运算，我们转而使用 OR 和补运算，处理是类似的。(1)一个简单析取式是重言式，当且仅当它同时含一个命题变项及其否定
采纳率：42%
好好自己做作业，一点都不乖
为您推荐：
其他类似问题
您可能关注的内容
离散数学的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
数学离散数学基础..doc 57页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
需要金币：150 &&
数学离散数学基础.
你可能关注的文档：
··········
··········
一、课程内容
·数理逻辑：是计算机科学的基础，应熟练掌握将现实生活中的条件化成逻辑公式，并能做适当的推理，这对程序设计等课程是极有用处的。
·集合论：数学的基础，对于学习程序设计、数据结构、编译原理等几乎所有计算机专业课程和数学课程都很有用处。熟练掌握有关集合、函数、关系等基本概念。
·代数结构：对于抽象数据类型、形式语义的研究很有用处。培养数学思维，将以前学过的知识系统化、形式化和抽象化。熟练掌握有关代数系统的基本概念，以及群、环、域等代数结构的基本知识。
·图论：对于解决许多实际问题很有用处，对于学习数据结构、编译原理课程也很有帮助。要求掌握有关图、树的基本概念，以及如何将图论用于实际问题的解决，并培养其使用数学工具建立模型的思维方式。
·讲课时间为两个学期，第一学期讲授数理逻辑与集合论，第二学期讲授代数结构和图论。考试内容限于书中的内容和难度，但讲课内容不限于书中的内容和难度。
二、数理逻辑发展史
·了解有关的背景，加深对计算机学科的全面了解，特别是理论方面的了解，而不限于将计算机看成是一门技术或工程性的学科。
·通过重要的历史事件，了解计算机科学中的一些基本思维方式和一些基本问题。
2. 数理逻辑的发展前期
·前史时期——古典形式逻辑时期：亚里斯多德的直言三段论理论
·初创时期——逻辑代数时期（17世纪末）
·资本主义生产力大发展，自然科学取得了长足的进步，数学在认识自然、发展技术方面起到了相当重要的作用。
·人们希望使用数学的方法来研究思维，把思维过程转换为数学的计算。
·莱布尼兹(Leibniz, )完善三段论，提出了建立数理逻辑或者说理性演算的思想：
·提出将推理的正确性化归于计算，这种演算能使人们的推理不依赖于对推理过程中的命题的含义内容的思考，将推理的规则变为演算的规则。
·使用一种符号语言来代替自然语言对演算进行描述，将符号的形式和其含义分开。使得演算从很大程度上取决与符号的组合规律，而与其含义无关。
·布尔(G. Boole, )代数：将有关数学运算的研究的代数系统推广到逻辑领域，布尔代数既是一种代数系统，也是一种逻辑演算。
3. 数理逻辑的奠基时期
·弗雷格(G. Frege, )：《概念语言——一种按算术的公式语言构成的纯思维公式语言》(1879)的出版标志着数理逻辑的基础部分——命题演算和谓词演算的正式建立。
·皮亚诺(Giuseppe Peano, )：《用一种新的方法陈述的算术原理》(1889)提出了自然数算术的一个公理系统。
·罗素(Bertrand Russell, )：《数学原理》(与怀特黑合著，, 1913)从命题演算和谓词演算开始，然后通过一元和二元命题函项定义了类和关系的概念，建立了抽象的类演算和关系演算。由此出发，在类型论的基础上用连续定义和证明的方式引出了数学（主要是算术）中的主要概念和定理。
·逻辑演算的发展：甘岑(G. Gentzen)的自然推理系统(Natural Deduction System)，逻辑演算的元理论：公理的独立性、一致性、完全性等。
·各种各样的非经典逻辑的发展：路易斯(Lewis, )的模态逻辑，实质蕴涵怪论和严格蕴涵、相干逻辑等，卢卡西维茨的多值逻辑等。
集合论的发展
·看待无穷集合的两种观点：实无穷与潜无穷
·康托尔(G. Cantor, )：以实无穷的思想为指导，建立了朴素集合论
·外延原则（集合由它的元素决定）和概括原则（每一性质产生一集合）。
·可数集和不可数集，确定无穷集合的本质在于集合本身能与其子集一一对应。能与正整数集合对应的集合是可数的，否则是不可数的。证明了有理数集是可数的，使用对角线法证明了实数集合是不可数的。
·超穷基数和超穷序数
·朴素集合论的悖论：罗素悖论
·公理集合论的建立：ZFC系统
6. 第三次数学危机与逻辑主义、直觉主义与形式主义
·集合论的悖论使得人们觉得数学产生了第三次危机，提出了数学的基础到底是什么这样的问题。
·罗素等的逻辑主义：数学的基础是逻辑，倡导一切数学可从逻辑符号推出，《数学原理》一书是他们这一思想的体现。为解决悖论产生了逻辑类型论。
·布劳维尔(Brouwer, )的直觉主义：数学是心灵的构造，只承认可构造的数学，强调构造的能行性，与计算机科学有重要的联系。坚持潜无穷，强调排中律不能用于无穷集合。海丁(Heyting)的直觉主义逻辑。
·希尔伯特(D. Hilbert)的形式主义：公理化方法与形式化方法，元数学和证明论，提倡将逻辑演算和数学证明本身形式
正在加载中，请稍后...君，已阅读到文档的结尾了呢~~
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
离散数学_命题逻辑.ppt
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='http://www.docin.com/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
[离散数学discrete2B.doc 10页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
需要金币：60 &&
[离散数学discrete2B
你可能关注的文档：
··········
··········
5. 联结词的完全集
【定义1.22】{0, 1}上的n元函数f : {0, 1}n?{0, 1}就称为一个n元真值函数。
联结词?实际上一个一元真值函数：
f?(0) = 1,
而联结词?、?、?和?则都是二元真值函数：
f?(0, 0) = 0,
f?(0, 1) = 0,
f?(1, 0) = 0,
f?(1, 1) = 1
f?(0, 0) = 0,
f?(0, 1) = 1,
f?(1, 0) = 1,
f?(1, 1) = 1
f?(0, 0) = 1,
f?(0, 1) = 1,
f?(1, 0) = 0,
f?(1, 1) = 1
f?(0, 0) = 1,
f?(0, 1) = 0,
f?(1, 0) = 0,
f?(1, 1) = 1
反过来，一个真值函数就可看成一个真值联结词。设f : {0, 1}n?{0, 1}是一个n元真值函数，则可如下定义一个n元真值联结词Nf :
对于n个命题变元p1, p2, …, pn，命题公式Nf(p1, p2, …, pn)在真值赋值函数&t1, t2, …, tn&下的真值为f(t1, t2, …, tn)。
显然互不相同的n元真值函数的个数为22n，因此可定义22n个n元真值联结词，例如1元真值函数有四个：
f1: 0?0, 1?0
f2: 0?0, 1?1
f3: 0?1, 1?0
f4: 0?1, 1?1
而2元真值函数有16个，可定义16个真值联结词，而我们常用的只不过是其中的4个。现在的问题是，是否所有的真值函数都可使用常用的这5个真值联结词来表示呢？
【定义1.23】设?是联结词的一个集合，称?为联结词的一个完全集，如果任意真值函数f都可用仅含?中联结词的命题公式A来表示，即对A中命题变元的任意一个真值赋值&t1, t2, …, tn&，A在&t1, t2, …, tn&下的真值为f(t1, t2, …, tn)。
【定理1.24】{?, ?, ?, ?}是联结词的一个完全集。
【证明】根据定义1.23只要证明对任意n元真值函数都可由只含?、?、?和?的n元命题公式来表示即可。对真值函数的元数n进行归纳证明。
归纳基：当n = 1时，一元真值函数只有4个，可分别用p?(?p)、p、?p和p?(?p)来表示，因此定理成立。
归纳步：假设当n = k时定理成立，要证n = k + 1定理也成立。设f(x1, x2, …, xk, xk+1)是一个k+1元真值函数，定义如下两个k元真值函数：
f1(x1, x2, …, xk) = f(x1, x2, …, xk, 0)
f2(x1, x2, …, xk) = f(x1, x2, …, xk, 1)
由归纳假设知f1和f2都可由只含?、?、?和?的k元命题公式来表示，设它们分别可由A1和A2表示，且假定A1和A2中的k个命题变元为p1, p2, …, pk。现在我们证f可由A = ((?pk+1)?A1)?(pk+1?A2)表示，其中pk+1是不同于p1, p2, …, pk的一个命题变元。即要证对命题变元p1, p2, …, pk, pk+1的一个真值赋值&t1, t2, …, tk, tk+1&时，A的真值是f(t1, t2, …, tk, tk+1)。当tk+1 = 0时，即pk+1被赋值为0，这时((?pk+1)?A1)与A1等值，而(pk+1?A2)的真值为1，所以A与A1等值，而按归纳假设有A1的真值为f1(t1, t2, …, tk)，即为f(x1, x2, …, xk, 0)。同理可证当tk+1 = 1时A的真值是f(x1, x2, …, xk, 1)，从而A的真值是f(t1, t2, …, tk, tk+1)。
【推论1.25】{?, ?}, {?, ?}和{?, ?}都是联结词的完全集。
【证明】1. 要证{?, ?}是联结词的一个完全集，只要证任一命题公式可与一个只含?和?的命题公式等值，事实上有：
(A?B)?((?A)?B)
(A?B)?(?((?A)?(?B)))
2. {?, ?}是联结词的一个完全集，因为：
(A?B)?(?((?A)?(?B)))
(A?B)?((?A)?B)
3. {?, ?}是联结词的一个完全集，因为：
(A?B)?(?((?A)?(?B)))
(A?B)?((?A)?B)
事实上，上述每个集合都是极小的完全集，即不能再从集合中去掉任意一个联结词还能保持是完全集。
【定理1.26】{?, ?, ?, ?}不是联结词的完全集。
【证明】总取0值的真值函数不能由只含此联结词集中的联结词的命题公式来表
正在加载中，请稍后...【图文】LiSan1-2_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
&&离散数学PPT
大小：1.17MB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢