应用离散数学-命题逻辑

离散数学中的逻辑关系及其应用离散数学是数学的一个分支，主要研究离散的结构及其上的操作。

逻辑关系是离散数学中的一个重要概念，它在数学、计算机科学等领域都有广泛应用。

本文将介绍离散数学中的逻辑关系及其应用。

1. 逻辑关系的定义及性质离散数学中的逻辑关系是指一种二元关系，即对于某个集合中的两个元素，这两个元素之间有一种特定的关系。

在逻辑中，这个关系通常表示为“P → Q”，其中P和Q是两个命题，表示“如果P成立，则Q也成立”的关系。

逻辑关系有以下几种性质：（1）自反性：对于任意元素a，a与自己之间存在关系。

（2）对称性：对于任意元素a和b，如果a与b之间存在关系，那么b与a之间也存在关系。

（3）传递性：对于任意元素a、b和c，如果a与b之间存在关系，b与c之间也存在关系，那么a与c之间也存在关系。

2. 逻辑关系的应用（1）逻辑门电路逻辑门电路是计算机硬件的基本组成部分，它们的功能是根据输入的命题逻辑值计算出输出的命题逻辑值。

逻辑门电路包括与门、或门及非门等，它们之间的逻辑关系可以用逻辑代数中的公式来表示。

（2）判断与证明逻辑关系在数学证明中有广泛应用，可以用来判断某些语句、假设或结论是否成立。

常见的逻辑关系有蕴含关系、等价关系和充分必要条件等，它们在判断和证明中有重要作用。

（3）数据结构逻辑关系在数据结构中也有着广泛的应用。

例如在二叉树中，每个节点有两个子节点，子节点之间存在着父子关系。

在图论中，节点之间则存在着边的关系。

这些关系可以使用逻辑关系来描述和分析。

3. 总结逻辑关系是离散数学中的重要概念，它无处不在，在数学、计算机科学等领域都有着广泛的应用。

熟练掌握逻辑关系的定义及性质，对于深入理解离散数学和其它相关领域有着重要的意义。

离散数学-----命题逻辑逻辑：是研究推理的科学。

公元前四世纪由希腊的哲学家亚里斯多德首创。

作为一门独立科学，十七世纪，德国的莱布尼兹(Leibniz)给逻辑学引进了符号, 又称为数理逻辑(或符号逻辑)。

逻辑可分为：1. 形式逻辑（是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。

）→数理逻辑（是用数学方法研究推理的形式结构和规律的数学学科。

它的创始人Leibniz，为了实现把推理变为演算的想法，把数学引入了形式逻辑中。

其后，又经多人努力，逐渐使得数理逻辑成为一门专门的学科。

）2. 辩证逻辑（是研究反映客观世界辩证发展过程的人类思维的形态的。

）一、命题及其表示方法1、命题数理逻辑研究的中心问题是推理,而推理的前提和结论都是表达判断的陈述句，因而表达判断的陈述句构成了推理的基本单位。

基本概念：命题：能够判断真假的陈述句。

命题的真值：命题的判断结果。

命题的真值只取两个值:真（用T(true)或1表示）、假（用F(false)或0表示）。

真命题：判断为正确的命题，即真值为真的命题。

假命题：判断为错误的命题，即真值为假的命题。

因而又可以称命题是具有唯一真值的陈述句。

判断命题的两个步骤：1、是否为陈述句；2、是否有确定的、唯一的真值。

说明：（1）只有具有确定真值的陈述句才是命题。

一切没有判断内容的句子，无所谓是非的句子，如感叹句、祁使句、疑问句等都不是命题。

（2）因为命题只有两种真值，所以“命题逻辑”又称“二值逻辑”。

（3）“具有确定真值”是指客观上的具有，与我们是否知道它的真值是两回事。

2、命题的表示方法在书中，用大写英文字母A,B,…,P,Q或带下标的字母P1,P2,P3 ,…,或数字(1),*2+, …,等表示命题，称之为命题标识符。

命题标识符又有命题常量、命题变元和原子变元之分。

命题常量：表示确定命题的命题标识符。

命题变元：命题标识符如仅是表示任意命题的位置标志，就称为命题变元。

第二章 命题逻辑习题．解 ⑴不是陈述句，所以不是命题。

⑵x 取值不确定，所以不是命题。

⑶问句，不是陈述句，所以不是命题。

⑷惊叹句，不是陈述句，所以不是命题。

⑸是命题，真值由具体情况确定。

⑹是命题，真值由具体情况确定。

⑺是真命题。

⑻是悖论，所以不是命题。

⑼是假命题。

2．解 ⑴是复合命题。

设p ：他们明天去百货公司；q ：他们后天去百货公司。

命题符号化为q p ∨。

⑵是疑问句，所以不是命题。

⑶是悖论，所以不是命题。

⑷是原子命题。

⑸是复合命题。

设p ：王海在学习；q ：李春在学习。

命题符号化为pq 。

⑹是复合命题。

设p ：你努力学习；q ：你一定能取得优异成绩。

p q 。

⑺不是命题。

⑻不是命题⑼。

是复合命题。

设p ：王海是女孩子。

命题符号化为：p 。

3．解 ⑴如果李春迟到了，那么他错过考试。

⑵要么李春迟到了，要么李春错过了考试，要么李春通过了考试。

⑶李春错过考试当且仅当他迟到了。

⑷如果李春迟到了并且错过了考试，那么他没有通过考试。

4．解 ⑴p (q r )。

⑵p q 。

⑶q p 。

⑷q p 。

习题1．解 ⑴是1层公式。

⑵不是公式。

⑶一层： pq ，p二层：p q所以，)()(q p q p ↔⌝→∨是3层公式。

⑷不是公式。

⑸(pq )(q ( q r ))是5层公式，这是因为一层：p q ，q ，r二层：q r 三层：q ( qr )四层：(q ( q r ))2．解 ⑴A =(p q )q 是2层公式。

真值表如表2-1所示：pqq p ∨A0 0 0 0 0 1 1 1 1 0 1 0 1111⑵p q p q A →→∧=)(是3层公式。

真值表如表2-2所示：pqq p →)(q p q →∧A0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 11111⑶)()(q p r q p A ∨→∧∧=是3层公式。

真值表如表2-3所示：pqrq p ∧r q p ∧∧q p ∨A0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 1 1 1 1 0 1 0 1 1 1 111111⑷)()()(r q r p q p A ∨∧∨⌝∧∨=是4层公式。

ＤＯＩ:１０.１９３９２/ｊ.ｃｎｋｉ.１６７１￣７３４１.２０２００５０３３案例教学法在离散数学教学中的应用研究以命题逻辑为例李艳艳文山学院数学学院㊀云南文山㊀６６３０９９摘㊀要:案例教学法是一种以案例为基础的教学法ꎬ是由美国哈弗法学院前院长克里斯托弗.朗代尔于１８７０年首创ꎬ在医学㊁管理学等许多学科应用广泛ꎮ本文将案例教学法应用到离散数学命题逻辑部分ꎬ通过选择真实可信的㊁客观生动的㊁与教学内容相关度高的案例ꎬ使原本理论性强ꎬ枯燥乏味的内容ꎬ变得生机勃勃ꎬ从而提高学生学习的兴趣ꎮ关键词:案例教学法ꎻ离散数学ꎻ命题逻辑中图分类号:Ｏ１５８㊀㊀文献标识码:Ａ㊀㊀案例教学法是一种以案例为基础的教学法ꎬ要求案例要真实可信㊁客观生动㊁相关性大ꎮ离散数学是研究离散量的结构及其相互关系的一门学科ꎮ通常研究的领域包括:数理逻辑㊁集合论㊁代数结构㊁关系论等ꎮ传统的离散数学课堂是数学概念㊁定理㊁例题的交叉上演ꎬ课堂枯燥乏味ꎮ学生对这门课程在实际生活中的应用不太了解㊁学习劲头不足ꎮ为了改变这种教学现状ꎬ激励学生们学习的兴趣ꎬ就要在教学方法和教学手段等方面改进ꎮ本文研究案例教学法在该门课程命题逻辑部分的应用ꎮ１案例分析命题逻辑部分是离散数学的一个重点ꎬ并且这部分内容定义㊁定理较多㊁抽象ꎮ本部分通过选用生活实际中的案例ꎬ提高学生学习的主动性ꎮ案例１如果张三作案ꎬ那么李四一定是主犯ꎻ如果张三没作案ꎬ那么王五参与作案ꎮ如果李四不是主犯ꎬ那么王五没有参与作案ꎮ由此可以推出以下哪项?(㊀)Ａ.张三没作案Ｂ.李四一定是主犯Ｃ.李四不一定是主犯Ｄ.王五参与作案Ｅ.张三作案解:命题符号化:设ｐ:张三作案ꎬｑ:李四为主犯ꎬｒ:王五参与作案ꎬ则已知事实为(ｐңｑ)ɡ(¬ｐңｒ)ɡ(¬ｑң¬ｒ)ꎮ(¬ｑң¬ｐ)ɡ(¬ｐңｒ)ɡ(¬ｑң¬ｒ)⇔(¬ｑңｒ)ɡ(¬ｑң¬ｒ)⇔１(ｐң¬ｑ)ɡ(ｐᶱｒ)ɡ(¬ｑң¬ｔ)ɡ(ｔᶱ¬ｎ)所以¬ｑ的真值为０ꎬ那么ｑ的真值就为１ꎮ从而推断李四一定为主犯ꎬ答案为Ｂꎮ案例２如果甲和乙考试都没及格的话ꎬ那么丙就一定及格了ꎮ上述前提再增加以下哪项ꎬ就可以推出 甲考试及格了 的结论ꎮ(㊀㊀)Ａ.丙及格了Ｂ.乙和丙都没有及格Ｃ.丙没有及格Ｄ.乙和丙都及格了解:命题符号化:设ｐ:甲考试及格ꎬｑ:乙考试及格ꎬｒ:丙考试及格ꎬ则命题为(¬ｐɡ¬ｑ)ңｒꎮ由等值演算知(¬ｐɡ¬ｑ)ңｒ⇔(¬ｒɡ¬ｑ)ңｐ所以再增加条件:当乙和丙考试都没有及格时ꎬ就可以推出甲考试及格了ꎬ因此选Ｂꎮ案例３[２]某机构决定从五位业务骨干终选派一人到国外学习ꎬ这五位骨干分别是赵㊁钱㊁孙㊁李㊁周ꎮ在决定选派人选之前有如下对话:赵说:或者是我去ꎬ或者是孙去ꎻ钱说:周不去ꎻ孙说:如果不是李去ꎬ那么就是钱去ꎻ李说:既不是我去ꎬ也不是钱去ꎻ周说:既不是孙去ꎬ也不是赵去ꎮ最终确定人选后发现以上对话中只有两个人说对了ꎬ那么被选中的是(㊀)ꎮＡ.赵㊀Ｂ.钱㊀Ｃ.周㊀Ｄ.李解:命题符号化ｐ:赵去ꎬｑ:孙去ꎬｒ:周去ꎬｓ:李去ꎬｔ:钱去ꎮ根据他们之间的对话赵说㊁钱说㊁孙说㊁李说㊁周说的符号化分别为:ｐᶱｑꎻ¬ｒꎻ¬ｓңｔꎻ¬ｓɡ¬ｔꎻ¬ｐɡ¬ｑꎬ从中可以发现ｐᶱｑ与¬ｐɡ¬ｑ互为否命题ꎬ¬ｓңｔ与¬ｓɡ¬ｔ互为否命题ꎬ则必有一真一假ꎬ又由题意知只有两个人说多了ꎬ则钱说的必然为假ꎬ所以选派周去ꎮ则选Ｃꎮ案例４如果不学习电吉他ꎬ阿健就当不了乐队主唱ꎻ如果他想玩乐器ꎬ他会选择电吉他ꎻ如果他不玩乐器ꎬ他就当主唱ꎮ由此可以推出ꎬ阿健将(㊀)ꎮＡ.当主唱Ｂ.学习电吉他Ｃ.不学习电吉他Ｄ.不当主唱解:命题符号化:设ｐ:学习吉他ꎬｑ:乐队主唱ꎬｒ:玩乐器ꎮ根据已知条件得¬ｐң¬ｑꎬｒңｐꎬ¬ｒңｑꎮ使用推理理论求解结论①ｒңｐ㊀前提引入㊀㊀㊀②¬ｒңｑ前提引入③¬ｑңｒ②置换④¬ｑңｐ①③假言三段论⑤¬ｐң¬ｑ前提引入⑥ｑңｐ⑤置换⑦ｐ④⑥两难由此可知学习电吉他ꎮ故选Ｂꎮ案例５如果甲和乙考试都没及格的话ꎬ那么丙就一定及格了ꎮ上述前提再增加以下哪项ꎬ就可以推出 甲考试及格了 的结论ꎮ(㊀㊀)Ａ.丙及格了㊀Ｂ.乙和丙都没有及格Ｃ.丙没有及格㊀Ｄ.乙和丙都及格了解:命题符号化:ｐ:甲考试及格ꎬｑ:乙考试及格ꎬｒ:丙考试及格ꎮ则原命题可表述为(¬ｐɡ¬ｑ)ңｒꎬ做等值演算得: (¬ｐɡ¬ｑ)ңｒ⇔(ｐᶱｑ)ᶱｒ⇔(ｑᶱｒ)ᶱｐ⇔(¬ｑɡ¬ｒ)ңｐ则ꎬ要得到甲考试及格了ꎬ需增加乙和丙都没有及格ꎮ案例６唐三藏一行西天取经ꎬ遇到火焰山ꎮ八戒说ꎬ只拣无火处走便罢ꎮ唐三藏道ꎬ我只欲往有经处去ꎮ沙僧道ꎬ有经处有火ꎮ沙僧的意思是ꎬ凡有经处皆有火ꎮ如果沙僧的话为真ꎬ则以下哪一项陈述必然为真ꎮ(㊀㊀)Ａ.有些无火处有经Ｂ.有些有经处无火㊀Ｃ.凡有火处皆有经㊀Ｄ.凡无火处皆无经解:将沙僧的话命题符号化:ｐ:有经ꎬｑ:有火ꎬ则原意为:ｐңｑꎬ根据假言易位知:ｐңｑ⇔¬ｑң¬ｐꎮ则知ꎬ无火处无经ꎮ２总结通过选择符合实际又有趣的案例ꎬ使得原本枯燥的命题逻辑ꎬ变得生动ꎬ而且富有实用价值ꎬ这样可以培养学生的学习兴趣ꎬ从而提高学习效果ꎮ所以教师应该悉心钻研适合学生的案例ꎬ提高学生分析问题和解决问题的能力ꎬ并学以致用ꎮ参考文献:[１]王海林ꎬ钱建刚ꎬ苏建新.案例教学法在军事运筹学教学中的应用[Ｊ].空军雷达学院学报ꎬ２０１１ꎬ１５(１):１８￣２０.[２]李永新.行政职业能力测验[Ｍ].北京:人民日报出版社ꎬ２０１４ꎬ２２３￣２３７.基金项目:«线性代数»重点课程建设项目(项目编号:ＷＹＺＬ１８０２１４)作者简介:李艳艳(１９８２￣)ꎬ女ꎬ甘肃庆阳人ꎬ硕士ꎬ副教授ꎬ研究方向:矩阵理论及其应用㊁数值分析ꎬ大学数学教学ꎮ７３㊀科技风２０２０年２月科教论坛。

利用离散数学中命题逻辑知识解决公务员逻辑判断题：据相关研究部门统计我国的大学生有 80% 愿意报考公务员，而其他国家不会超过 10%，分析其原因一方面跟这几年我国大学生就业压力大有关，另一方面公务员职业大家认为很风光，很体面，而且福利高，保障好，所以导致了公务员考试一热再热，被称为“中国第一考”，公务员成为大学生，硕士生，甚至博士生就业的第一选择，并且相当一部分已经在大家也比较羡慕的事业单位工作的人员也热衷于报考公务员。

那么在如此激烈的竞争中，公务员笔试的每一分都有可能决定一个人的命运。

公务员考试的《行政职业能力测试》中大概有15% 的题目是逻辑判断题，这类问题难度不大，如果方法选择不当就很难下手，在各类公务员考试辅导书中对于该类问题的解法都需要记好多模式。

例如华图教育编著的《行政职业能力测验》中首先将命题分为性质命题和复合命题，对于性质命题又分为 5 类，性质命题之间的关系分为反对关系，下反对关系，矛盾关系，差等关系，这四种关系之间的推理特征又列了一个表格，互换主谓项也有一个推理表。

对于复合命题又分为联言命题，相容选言命题，不相容选言命题，充分条件假言命题，必要条件假言命题，充要条件假言命题，负命题这七类，还给出了这些命题的负命题的形式和复合命题之间的推理等许多形式，面对这么多形式当我们解决问题时很容易混淆也就容易出错，所以往往很多考生在这部分的得分不是很理想，也就让挤公务员这条独木桥的考生丧失了一定的竞争力。

其实这些问题没有必要做的这么复杂，它就是离散数学知识的简单应用。

本文利用离散数学中命题逻辑部分的相关知识解决该类问题，从而使该类问题简单易懂而且得到的结果准确率高。

因此本文旨在帮助参加公务员考试的同学多拿分，助其圆梦。

1、预备知识下面首先给出参考文献中离散数学命题逻辑部分命题以及逻辑联结词的基础知识，以及复合命题的定义。

2、实例下面通过公务员考试的一些历年真题说明具体应用命题逻辑知识如何使该类问题简单易懂而且做出来的结果不会出错。

数理逻辑部分第1章命题逻辑命题符号化及联结词命题: 判断结果惟一的陈述句命题的真值: 判断的结果真值的取值: 真与假真命题: 真值为真的命题假命题: 真值为假的命题注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。

简单命题(原子命题)：简单陈述句构成的命题复合命题：由简单命题与联结词按一定规则复合而成的命题简单命题符号化用小写英文字母p, q, r, … ,p i,q i,r i (i≥1）表示简单命题用“1”表示真，用“0”表示假例如，令p：是有理数，则p 的真值为 0q：2 + 5 = 7，则q 的真值为 1联结词与复合命题1.否定式与否定联结词“”定义设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作p. 符号称作否定联结词，并规定p为真当且仅当p为假.2.合取式与合取联结词“∧”定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q 的合取式，记作p∧q. ∧称作合取联结词，并规定 p∧q为真当且仅当p 与q同时为真注意：描述合取式的灵活性与多样性分清简单命题与复合命题例将下列命题符号化.(1) 王晓既用功又聪明.(2) 王晓不仅聪明，而且用功.(3) 王晓虽然聪明，但不用功.(4) 张辉与王丽都是三好生.(5) 张辉与王丽是同学.解令p：王晓用功，q：王晓聪明，则(1) p∧q(2) p∧q(3) p∧q.令r : 张辉是三好学生，s :王丽是三好学生(4) r∧s.(5) 令t : 张辉与王丽是同学，t 是简单命题 .说明:(1)~(4)说明描述合取式的灵活性与多样性.(5) 中“与”联结的是两个名词，整个句子是一个简单命题.3.析取式与析取联结词“∨”定义设p,q为二命题，复合命题“p或q”称作p与q的析取式，记作p∨q. ∨称作析取联结词，并规定p∨q为假当且仅当p与q同时为假.例将下列命题符号化(1) 2或4是素数.(2) 2或3是素数.(3) 4或6是素数.(4) 小元元只能拿一个苹果或一个梨.(5) 王晓红生于1975年或1976年.解令p:2是素数, q:3是素数, r:4是素数, s:6是素数,则 (1), (2), (3) 均为相容或.分别符号化为: p∨r , p∨q, r∨s,它们的真值分别为 1, 1, 0.而 (4), (5) 为排斥或.令t :小元元拿一个苹果，u:小元元拿一个梨，则 (4) 符号化为 (t∧u) ∨(t∧u).令v :王晓红生于1975年,w:王晓红生于1976年,则 (5) 既可符号化为 (v∧w)∨(v∧w), 又可符号化为v∨w , 为什么4.蕴涵式与蕴涵联结词“”定义设p,q为二命题，复合命题“如果p,则q” 称作p与q的蕴涵式，记作p q，并称p是蕴涵式的前件，q为蕴涵式的后件. 称作蕴涵联结词，并规定，p q为假当且仅当p 为真q 为假.p q 的逻辑关系：q 为p 的必要条件“如果p，则q ” 的不同表述法很多：若p，就q只要p，就qp 仅当q只有q 才p除非q, 才p 或除非q, 否则非p.当p 为假时，p q 为真常出现的错误：不分充分与必要条件5.等价式与等价联结词“”定义设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作p q. 称作等价联结词.并规定p q为真当且仅当p与q同时为真或同时为假.说明:(1) p q 的逻辑关系:p与q互为充分必要条件(2) p q为真当且仅当p与q同真或同假联结词优先级:( ),, , , ,同级按从左到右的顺序进行以上给出了5个联结词：, , , , ，组成一个联结词集合{, , , , }，联结词的优先顺序为：, , , , ; 如果出现的联结词同级，又无括号时，则按从左到右的顺序运算; 若遇有括号时，应该先进行括号中的运算.注意: 本书中使用的括号全为园括号.命题常项命题变项命题公式及分类命题变项与合式公式命题常项：简单命题命题变项：真值不确定的陈述句定义合式公式 (命题公式, 公式) 递归定义如下：(1) 单个命题常项或变项p,q,r,…,p i ,q i ,r i ,…,0,1是合式公式(2) 若A是合式公式，则 (A)也是合式公式(3) 若A, B是合式公式，则(A B), (A B), (A B), (A B)也是合式公式(4) 只有有限次地应用(1)~(3)形成的符号串才是合式公式说明: 元语言与对象语言, 外层括号可以省去合式公式的层次定义(1) 若公式A是单个的命题变项, 则称A为0层公式.(2) 称A是n+1(n≥0)层公式是指下面情况之一：(a) A=B, B是n层公式；(b) A=B C, 其中B,C分别为i层和j层公式，且n=max(i, j)；(c) A=B C, 其中B,C的层次及n同(b)；(d) A=B C, 其中B,C的层次及n同(b)；(e) A=B C, 其中B,C的层次及n同(b).例如公式p 0层p 1层p q 2层(p q)r 3层((p q) r)(r s) 4层公式的赋值定义给公式A中的命题变项p1, p2, … , p n指定一组真值称为对A的一个赋值或解释成真赋值: 使公式为真的赋值成假赋值: 使公式为假的赋值说明：赋值=12…n之间不加标点符号，i=0或1.A中仅出现p1, p2, …, p n，给A赋值12…n是指p1=1, p2=2, …, p n=nA中仅出现p,q, r, …, 给A赋值123…是指p=1,q=2 , r= 3 …含n个变项的公式有2n个赋值.真值表真值表: 公式A在所有赋值下的取值情况列成的表例给出公式的真值表A= (q p) q p的真值表例 B = (p q) q的真值表例C= (p q) r的真值表命题的分类重言式矛盾式可满足式定义设A为一个命题公式(1) 若A无成假赋值，则称A为重言式(也称永真式)(2) 若A无成真赋值，则称A为矛盾式(也称永假式)(3) 若A不是矛盾式，则称A为可满足式注意：重言式是可满足式，但反之不真.上例中A为重言式，B为矛盾式，C为可满足式A= (q p)q p，B =(p q)q，C= (p q)r等值演算等值式定义若等价式A B是重言式，则称A与B等值，记作A B，并称A B是等值式说明：定义中，A,B,均为元语言符号, A或B中可能有哑元出现.例如，在 (p q) ((p q) (r r))中，r为左边公式的哑元.用真值表可验证两个公式是否等值请验证：p(q r) (p q) rp(q r) (p q) r基本等值式双重否定律 : A A等幂律：A A A, A A A交换律: A B B A, A B B A结合律: (A B)C A(B C)(A B)C A(B C)分配律: A(B C)(A B)(A C)A(B C) (A B)(A C) 德·摩根律: (A B)A B(A B)A B吸收律: A(A B)A, A(A B)A零律: A11, A00同一律: A0A, A1A排中律: A A 1矛盾律: A A0等值演算:由已知的等值式推演出新的等值式的过程置换规则：若A B, 则(B)(A)等值演算的基础：(1) 等值关系的性质：自反、对称、传递(2) 基本的等值式(3) 置换规则应用举例——证明两个公式等值例1 证明p(q r) (p q)r证p(q r)p(q r) （蕴涵等值式，置换规则）(p q)r（结合律，置换规则）(p q)r（德摩根律，置换规则）(p q) r（蕴涵等值式，置换规则）说明:也可以从右边开始演算（请做一遍）因为每一步都用置换规则，故可不写出熟练后，基本等值式也可以不写出应用举例——证明两个公式不等值例2 证明: p(q r) (p q) r用等值演算不能直接证明两个公式不等值,证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假.方法一真值表法（自己证）方法二观察赋值法. 容易看出000, 010等是左边的的成真赋值，是右边的成假赋值.方法三用等值演算先化简两个公式，再观察.应用举例——判断公式类型例3 用等值演算法判断下列公式的类型(1) q(p q)解q(p q)q(p q) （蕴涵等值式）q(p q) （德摩根律）p(q q) （交换律，结合律）p0 （矛盾律）0 （零律）由最后一步可知，该式为矛盾式.(2) (p q)(q p)解 (p q)(q p)(p q)(q p) （蕴涵等值式）(p q)(p q) （交换律）1由最后一步可知，该式为重言式.问：最后一步为什么等值于1(3) ((p q)(p q))r)解 ((p q)(p q))r)(p(q q))r（分配律）p1r（排中律）p r（同一律）这不是矛盾式，也不是重言式，而是非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.总结：A为矛盾式当且仅当A0A为重言式当且仅当A 1说明：演算步骤不惟一,应尽量使演算短些对偶与范式对偶式与对偶原理定义在仅含有联结词, ∧,∨的命题公式A中，将∨换成∧, ∧换成∨，若A中含有0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记为A*.从定义不难看出，(A*)* 还原成A定理设A和A*互为对偶式，p1,p2,…,p n是出现在A和A*中的全部命题变项，将A和A*写成n元函数形式，则 (1) A(p1,p2,…,p n) A* (p1, p2,…, p n)(2) A(p1, p2,…, p n) A* (p1,p2,…,p n)定理（对偶原理）设A，B为两个命题公式，若A B，则A* B*.析取范式与合取范式文字:命题变项及其否定的总称简单析取式:有限个文字构成的析取式如p, q, p q, p q r, …简单合取式:有限个文字构成的合取式如p, q, p q, p q r, …析取范式:由有限个简单合取式组成的析取式A 1A2Ar, 其中A1,A2,,A r是简单合取式合取范式:由有限个简单析取式组成的合取式A 1A2Ar, 其中A1,A2,,A r是简单析取式范式:析取范式与合取范式的总称公式A的析取范式: 与A等值的析取范式公式A的合取范式: 与A等值的合取范式说明：单个文字既是简单析取式，又是简单合取式p q r, p q r既是析取范式，又是合取范式(为什么)命题公式的范式定理任何命题公式都存在着与之等值的析取范式与合取范式.求公式A的范式的步骤：(1) 消去A中的, （若存在）(2) 否定联结词的内移或消去(3) 使用分配律对分配（析取范式）对分配（合取范式）公式的范式存在，但不惟一求公式的范式举例例求下列公式的析取范式与合取范式(1) A=(p q)r解 (p q)r(p q)r（消去）p q r（结合律）这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）(2) B=(p q)r解 (p q)r(p q)r（消去第一个）(p q)r（消去第二个）(p q)r（否定号内移——德摩根律）这一步已为析取范式（两个简单合取式构成）继续： (p q)r(p r)(q r) （对分配律）这一步得到合取范式（由两个简单析取式构成）极小项与极大项定义在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第i（1i n）个文字出现在左起第i位上，称这样的简单合取式（简单析取式）为极小项（极大项）.说明：n个命题变项产生2n个极小项和2n个极大项2n个极小项（极大项）均互不等值用m i表示第i个极小项，其中i是该极小项成真赋值的十进制表示. 用M i表示第i个极大项，其中i是该极大项成假赋值的十进制表示, m i(M i)称为极小项(极大项)的名称.m与M i的关系: m i M i , M i m ii主析取范式与主合取范式主析取范式: 由极小项构成的析取范式主合取范式: 由极大项构成的合取范式例如，n=3, 命题变项为p, q, r时，(p q r)(p q r) m1m3是主析取范式(p q r)(p q r) M1M5 是主合取范式A的主析取范式: 与A等值的主析取范式A的主合取范式: 与A等值的主合取范式.定理任何命题公式都存在着与之等值的主析取范式和主合取范式, 并且是惟一的.用等值演算法求公式的主范式的步骤：(1) 先求析取范式（合取范式）(2) 将不是极小项（极大项）的简单合取式（简单析取式）化成与之等值的若干个极小项的析取（极大项的合取），需要利用同一律（零律）、排中律（矛盾律）、分配律、幂等律等.(3) 极小项（极大项）用名称m i（M i）表示，并按角标从小到大顺序排序.求公式的主范式例求公式A=(p q)r的主析取范式与主合取范式.(1) 求主析取范式(p q)r(p q)r , （析取范式）① (p q)(p q)(r r)(p q r)(p q r)m 6m7,r(p p)(q q)r(p q r)(p q r)(p q r)(p q r)m 1m3m5m7③②, ③代入①并排序，得(p q)r m1m3m5m6m7（主析取范式）(2) 求A的主合取范式(p q)r(p r)(q r) , （合取范式）①p rp(q q)r(p q r)(p q r)M 0M2,②q r(p p)q r(p q r)(p q r)M 0M4③②, ③代入①并排序，得(p q)r M0M2M4 （主合取范式）主范式的用途——与真值表相同(1) 求公式的成真赋值和成假赋值例如 (p q)r m1m3m5m6m7，其成真赋值为001, 011, 101, 110, 111，其余的赋值 000, 010, 100为成假赋值.类似地，由主合取范式也可立即求出成假赋值和成真赋值.(2) 判断公式的类型设A含n个命题变项，则A为重言式A的主析取范式含2n个极小项A的主合取范式为1.A为矛盾式A的主析取范式为0A的主合取范式含2n个极大项A为非重言式的可满足式A的主析取范式中至少含一个且不含全部极小项A的主合取范式中至少含一个且不含全部极大项例某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习. 选派必须满足以下条件：(1)若赵去，钱也去；(2)李、周两人中至少有一人去；(3)钱、孙两人中有一人去且仅去一人；(4)孙、李两人同去或同不去；(5)若周去，则赵、钱也去.试用主析取范式法分析该公司如何选派他们出国解此类问题的步骤为：①将简单命题符号化②写出各复合命题③写出由②中复合命题组成的合取式④求③中所得公式的主析取范式解①设p：派赵去，q：派钱去，r：派孙去，s：派李去，u：派周去.② (1) (p q)(2) (s u)(3) ((q r)(q r))(4) ((r s)(r s))(5) (u(p q))③ (1) ~ (5)构成的合取式为A=(p q)(s u)((q r)(q r))((r s)(r s))(u(p q))④ A (p q r s u)(p q r s u) 结论：由④可知，A的成真赋值为00110与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）.A的演算过程如下:A (p q)((q r)(q r))(s u)(u(p q)) ((r s)(r s)) （交换律) B1= (p q)((q r)(q r))((p q r)(p q r)(q r)) （分配律）B2= (s u)(u(p q))((s u)(p q s)(p q u)) （分配律）B 1B2(p q r s u)(p q r s u) (q r s u)(p q r s)(p q r u)再令B3 = ((r s)(r s))得A B1B2B3(p q r s u)(p q r s u) 注意：在以上演算中多次用矛盾律要求：自己演算一遍推理理论推理的形式结构推理的形式结构—问题的引入推理举例:(1) 正项级数收敛当且仅当部分和有上界.(2) 若推理: 从前提出发推出结论的思维过程上面(1)是正确的推理，而(2)是错误的推理.证明: 描述推理正确的过程.判断推理是否正确的方法•真值表法•等值演算法判断推理是否正确•主析取范式法•构造证明法证明推理正确说明：当命题变项比较少时，用前3个方法比较方便, 此时采用形式结构“” . 而在构造证明时，采用“前提: , 结论: B”.推理定律与推理规则推理定律——重言蕴涵式构造证明——直接证明法例构造下面推理的证明：若明天是星期一或星期三，我就有课. 若有课，今天必备课. 我今天下午没备课. 所以，明天不是星期一和星期三.解设p：明天是星期一，q：明天是星期三，r：我有课，s：我备课推理的形式结构为例构造下面推理的证明:2是素数或合数. 若2是素数，则是无理数.若是无理数，则4不是素数. 所以，如果4是素数，则2是合数.用附加前提证明法构造证明解设p：2是素数，q：2是合数，r：是无理数，s：4是素数推理的形式结构前提：p∨q, p r, r s结论：s q证明① s附加前提引入②p r前提引入③r s前提引入④p s②③假言三段论⑤p①④拒取式⑥p∨q前提引入⑦q⑤⑥析取三段论请用直接证明法证明之。

离散数学命题逻辑离散数学是数学的一个分支，主要研究离散对象和离散结构。

在离散数学中，命题逻辑是一个重要的概念和工具。

命题逻辑是一种用于研究命题之间关系的逻辑系统，其中命题是指可以判断真假的陈述句。

在命题逻辑中，我们可以使用逻辑运算符来连接命题，从而形成更复杂的命题。

常见的逻辑运算符包括非（取反）、与（合取）、或（析取）、蕴含和等价。

通过使用这些运算符，我们可以构造和分析复杂的逻辑命题。

命题逻辑的核心是命题符号化，即将自然语言中的句子转化为逻辑符号来表示。

例如，我们可以用P表示命题'Peter是个学生'，用Q表示命题'今天下雨'。

那么，通过逻辑运算符的运用，我们可以构造出一些复合的命题，比如'Peter是个学生且今天下雨'，'不是Peter 是个学生或者今天不下雨'等等。

命题逻辑还具有一些重要的性质和规则。

比如，双重否定律表明，一个命题的否定的否定等价于该命题本身；分配律和结合律则规定了逻辑运算符之间的优先级和结合方式。

这些性质和规则可以帮助我们简化和分析复杂的逻辑表达式。

除了命题逻辑，离散数学中还有谓词逻辑和模态逻辑等其他形式的逻辑系统。

谓词逻辑扩展了命题逻辑，引入了谓词和量词，用于描述对象和关系之间的逻辑关系。

而模态逻辑则引入了一种特殊的逻辑运算符，用于表示命题在不同的世界或情境中的真假。

总之，离散数学中的命题逻辑是一个重要且基础的概念，它为我们分析和推理关于真假的陈述提供了强有力的工具。

通过理解命题逻辑的概念、性质和规则，我们可以更好地理解和应用逻辑思维，从而在各个学科领域中进行推理和证明。

离散数学第一章命题逻辑定义1。

设P为一命题，P的否定是一个新的命题，记作¬P。

若P为T，¬P为F；若P为F，¬P为T。

联结词“¬”表示命题的否定。

否定联结词有时亦可记作“¯”。

（P3）定义2。

两个命题P和Q的合取是一个复合命题，记作P∧Q。

当且仅当P,Q同时为T时，P∧Q为T，在其他情况下，P∧Q的真值都是F。

（P4）定义3。

两个命题P和Q的析取是一个复合命题，记作P∨Q。

当且仅当P，Q同时为F时，P∨Q的真值为F，否则P∨Q的真值为T。

（P5）定义4。

给定两个命题P和Q，其条件命题是一个复合命题，记作P→Q，读作“如果P，那么Q”或者“若P则Q”。

当且仅当P的真值为T，Q的真值为F时，P→Q的真值为F，否则P→Q的真值为T。

我们称P为前件，Q为后件。

（P6）定义5。

给定两个命题P和Q，其复合命题P⇆Q的真值为F。

（P7）定义6。

命题演算的合式公式（wff），规定为：（1）单个命题变元本身是一个合式公式。

（2）如果A是合式公式，那么¬A是合式公式。

（3）如果A和B是合式公式，那么（A∧B），（A∨B），（A→B）和（A⇆B）都是合式公式。

（4）当且仅当能够有限次地应用（1），（2），（3）所得到的包含命题变元，联结词和括号的符号串是合式公式。

（P9）定义7。

在命题公式中，对于分量指派真值得各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。

（P12）定义8。

给定两个命题公式A和B，设P1，P2，…，P n为所有出现于A和B中的原子变元，若给P1，P2，…，P n任一组真值指派，A和B的真值都相同，则称A和B是等价的或逻辑相等。

记作A⇔B。

（P15）定义9。

如果X是合式公式的A的一部分，且X本身也是一个合式公式，则称X为公式A 的字公式。

（P16）定理1。

设X是合式公式A的字公式，若X⇔Y，如果将A中的X用Y来置换，所得到公式B 与公式A等价，即A⇔B。