离散基础及数学 1

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

什么是数理逻辑？数理逻辑是用数学方法研究思维规律的一门学科。所谓数学方法是指:用一套数学的符号系统来描述和处理思维的形式与规律。因此，数理逻辑又称为符号逻辑。

2数理逻辑的创始人--莱布尼茨

(Leibniz,GottfriedWilhelm)

1646.7.1-1716.11.14

德国数学家、物理学家、哲学家等，一个举世罕见的科学天才。研究领域涉及到逻辑学、数学、力学、地质学、法学、历史学、语言学、生物学以及外交、神学等诸多方面.出生于德国东部莱比锡的一个书香之家，父亲是莱比锡大学的道德哲学教授，母亲出生在一个教授家庭。莱布尼兹的父亲在他年仅6岁时便去世了，给他留下了丰富的藏书。315岁时，进了莱比锡大学学习法律，一进校便跟上了大学二年级标准的人文学科的课程，还广泛阅读了培根、开普勒、伽利略等人的著作，并对他们的著述进行深入的思考和评价。在听了教授讲授欧几里德的《几何原本》的课程后，莱布尼兹对数学产生了浓厚的兴趣。17岁时他在耶拿大学学习了短时期的数学，并获得了哲学硕士学位。19岁设计出世界第一台乘法器，被认为是现代机器数学的先驱者。

Leibniz之梦：有一天所有的知识，包括精神和无形的真理，能够通过通用的代数演算放入一个单一的演绎系统。1693年，发现了机械能的能量守恒定律。与牛顿并称为微积分的创立者。系统阐述了二进制记数法，并把它和中国的八卦联系起来。4主要内容命题、命题逻辑联结词命题变元、合式公式重言式、永真蕴含、恒等式代入规则、替换规则对偶原理范式及其判定问题命题演算的推理应用与拓展历史人物与事件51.1命题和逻辑联结词现实语言翻译判定推理应用：文本分析实例；计算机电路设计；计算机程序构造；程序正确性证明，知识库提取，知识库构建，知识推理等。61.1.1命题的概念所谓命题，是指具有非真必假的陈述句。而疑问句、祈使句和感叹句等因都不能判断其真假，故都不是命题。1.定义：一个具有真假意义的陈述句被称为一个命题。或真或假，不能既真又假。例1:判断下面语句是否是命题华盛顿是美国的首都。多伦多是加拿大的首都。

1+101=110几点了？x+1=3真热呀！或真或假，不能既真又假71.1.1命题的概念理发师问题：理发师给所有不给自己理发的人理发分析：（1）理发师给自己理发（2）理发师不给自己理发不能给自己理发需要给自己理发悖论81.1.1命题的概念2.命题的真值及表示命题用大写的英文字母，如，，…表示。

P：今天是星期二。命题仅有两种可能的真值—真和假，且二者只能居其一。如果一个命题的真值是真，则用1或(Ture)来表示；如果一个命题的真值是假，则用0或（False）来表示。定义：一个命题不能再分解为更简单的命题，这个命题称为原子命题。9如果下周日下雪，那么我就去滑雪。如果下周日不下雨并且没有考试，那么我去海边玩。这次演讲比赛，我们班将由赵明或者张强参加。命题原子命题？分子命题（复合命题）101.1.2逻辑联结词否定词“并非”合取词“并且”析取词“或者”蕴涵词“如果……，那么……”（单向词、单条件）双向蕴涵词“当且仅当”（双向词、等值）异或词“或者(不可兼或)”11定义：设P是一个命题，则P的否定是一个新的命题，记作“”，读作“非P”。

否定词“┐”的意义如下表：1.否定——或真值表：利用运算对象真值的所有可能组合判断命题的真假。12例：找出命题“所有的素数都是奇数”的否定。

“并非所有的素数都是奇数。”“所有的素数都不是奇数。”1.否定——对整体否定，不是对局部的否定132.合取——∧定义：表征意义两命题合取的真值表或142.合取——∧153.析取——∨定义：表征意义两命题析取的真值表或163.析取——∨可兼或不可兼或174.蕴涵——→（单条件）定义：表征意义蕴涵的真值表或184.蕴涵——→（单条件）政治家竞选时许诺“如果我当选了，那么我将会减税”。如果今天是星期五，那么2+2=4.与程序设计中ifpthenS语句的区别。现实世界中无意义的语言也可以翻译194.蕴涵——→（单条件）在日常生活中，用条件式表示前提和结论之间的因果或实质关系，这种条件式称为形式条件命题。然而在命题逻辑中，一个条件式的前提并不要求与结论有任何关系，这种条件式称为实质条件命题。205.等价——（双条件或等值）定义：表征意义双条件的真值表PQP↔QPQP↔Q或216.异或——

（不可兼或）

定义：表征意义：例如，实数a要么是有理数，要么是无理数。又如，大连到北京的Z81卧铺车要么是18:26，要么是8:26发车异或的真值表或221.1.2逻辑联结词注意：由逻辑联结词联结的命题之间不需要任何关系。如无特殊说明，一般的优先次序，括号优先：23∧∨→

逻辑翻译—句子到逻辑表达式的翻译步骤：确定给定的句子是否为命题；找出各原子命题并确定句子中的连词为对应的联结词；用正确的语法把原命题表示成由原子命题、联结词和圆括号组成的公式。24逻辑翻译翻译下列命题：(1)他既聪明又用功。(2)他虽聪明但不用功。解：原子命题P：他聪明。

Q：他用功。则有：

(1)翻译成：P∧Q

(2)翻译成：P∧¬Q25逻辑翻译除非有时间，我才去看电影A：我有时间。B：我去看电影。翻译为：B→A我不承认你是对的，除非太阳从西边出来A：我不承认你是对的。B：太阳从西边出来。翻译为：¬B→A26逻辑翻译如果你和他都不固执己见的话，那么不愉快的事情就不会发生了。P：你固执己见。Q：他固执己见。R：不愉快的事情不会发生。翻译为：(¬PΛ¬Q)→R如果你和他不都是固执己见的话，那么不愉快的事情就不会发生了。¬(PΛQ)→R27逻辑翻译P：这个材料很有趣。Q：这个习题很难。R：这门课程使人喜欢。1、这个材料很有趣，而且这些习题很难。2、这个材料无趣，习题也不难，那么，这门课程就不会使人喜欢。3、这个材料无趣，习题也不难，而且这门课程也不使人喜欢。4、这个材料很有趣意味着这些习题很难，反之亦然。5、或者这个材料很有趣，或者这些习题很难，而且两者恰具其一。28逻辑翻译除非你已满16周岁，否则只要你的身高不足4英尺就不能乘公园滑行铁道游乐车。P：你能乘坐公园滑行铁道游乐车。Q：你身高不足4英尺。R：你已满16周岁。翻译成：(¬RΛ

Q)→¬P29逻辑难题一个岛上居住着两类人——骑士和流氓。骑士说的都是实话，而流氓只会说谎。你碰到两个人A和B，如果A说“B是骑士”，B说“我们两个不是一类人”，请判断A、B到底是流氓还是骑士。解：解析原子命题，P:A是骑士；Q:B是骑士；A说的翻译：Q，B说的翻译：(P∧┐Q)∨(┐P∧Q)PQ(P∧┐Q)∨(┐P∧Q)00001110111030例外一种解法解答：枚举法，只有4种可能。假设都是骑士。B说的是谎话，不成立。假设A是骑士，B是流氓。A是说假话了，不成立。假设A是流氓，B是骑士。A说真话了，不成立。假设都是流氓，成立。答案是都是流氓。311.2合式公式与真值表

有了命题和逻辑联结词，如何用严谨的数学符号来表达逻辑呢？本节将引入合式公式的概念，学会如何规范地书写逻辑表达式；同时，真值表作为一种强大的分析工具，能直观地展现出命题在不同情况下的真假结果；其次，如何将文字描述准确地翻译成逻辑表达式。321.2.1合式公式命题变元用P表示一个抽象的命题，而不是一个具体的命题时，称它为以表示任意命题命题变元不能确定真值合式公式由命题变元、逻辑联接词及圆括号构成合式公式合式公式递归定义（1）真值T和F是合式公式。（2）单个命题变元是合式公式。（3）如果A是合式公式，那么¬A是合式公式。（4）如果A和B均是合式公式，那么和都是合式公式。（5）当且仅当有限次的应用(1)、(2)、(3)、（4）条规则由逻辑联结词、圆括号所组成的有意义的符号串是合式公式。上面的定义成为递归定义法，(1)、（2）称为递归定义基础，（3）和（4）称为递归定义的归纳，（5）称为递归定义的界限。331.2.1合式公式判断下列字符串哪些是合式公式，哪些不是？

P，¬P，PQ341.2.1合式公式几个概念：命题命题变元命题公式——合式公式命题公式vs命题

命题公式：没有真假意义命题：有真假意义351.2.2真值表设P是一个命题公式，P1，P2，…，Pn是出现在P中的所有命题变元，对于这些命题变元真值指派的每一种可能的组合，都能唯一的确定P的真值。将这些真值列成一个表，称为命题公式P的真值表。给出命题公式的真值表

0000101101101101111036应用实例系统规范性说明在说明硬件系统和软件系统时，将自然语言语句翻译成逻辑表达式是很重要的一部分。系统和软件工程师从自然语言中提取需求，生成精确、无二义的规范说明，这些说明可以作为系统开发的基础。37应用实例确定下列系统规范性说明是否一致“诊断消息存放在缓冲区中或是被重传”“诊断消息没有存储在缓冲区中”“如果诊断消息存储在缓冲区中，那么它被重传”解：P：诊断消息存储在缓冲区中Q：诊断消息被重传三个命题分别是P∨Q，¬P,P→QPQP∨Q

¬PP→Q0001101111101001110138逻辑难题

侦探调查了有关罪案的四位证人，从证人的话侦探得出的结论是：如果男管家说的是真话，那么厨师说的也是真话；厨师和园丁说的不可能都是真话；园丁和杂役不可能都在说谎；如果杂役说真话，那么厨师在说谎。能判定四个人分别在说谎还是说真话吗？解：原子命题：M:男管家说真话

C:厨师说真话

G:园丁说真话Z:杂役说真话39符号化并构造真值表：ＭＣＧＺＭＣ(C∧¬G)∨(¬C∧G)∨(¬C∧¬G)(G∧¬Z)∨(¬G∧Z)∨(G∧Z)ＺＣＭＣＧＺＭＣ¬(C∧G),G∨Z,ＺＣ００００１

1０１０００１１1

0１００１０１１１１００１１１１０１０１００１１０１

１１１１１０0０

401.3永真式、等价式及代入规则和替换规则逻辑推理中，有些命题框架在任何情况下都为真，而有些不同形式的命题在逻辑上却完全等价。本节将重点讲解永真式和等价式，并详细剖析代入规则和替换规则。掌握这些规律，能够帮助我们化简复杂的逻辑表达式，是实现布尔代数化简、提升计算效率的核心基础。411.3.1永真式永真式给定一个命题公式，若无论对其中的命题变元作何种真值指派，其对应的真值永为T，则称该命题公式为重言式或永真式。永假式给定一个命题公式，若无论对其中的命题变元作何种真值指派，其对应的真值永为F，则称该命题公式为永假式或矛盾。至少存在一组真值指派使命题公式取值为T的命题公式，称为可满足的。42对命题公式，，做出真值表０１０１１０001011100111431.3.1永真式1.3.1永真式

P

P

T,P

P

F永真式与永假式取决于公式本身的结构，不依赖变元的真值指派。例如(P

Q

R)(P

Q

R)就是一个永真式(P

Q

R)(P

Q

R)就是一个永假式永真式的性质：若公式A是永真式，并且P1，P2，…，Pn是出现于A中的变元，若用公式B代换A中的原子变元Pi(i=1,2,…,n),所得到的公式设为A’，则A’也是永真式。（注意代换过程从左向右要进行到底）。对非永真式，这条性质不一定成立。44(1)重言式的否定是一个矛盾式，一个矛盾式的否定是重言式，所以只研究其中之一就可以了。(2)重言式的析取，合取，单条件，双条件都是重言式。于是可由简单的重言式推出复杂的重言式。(3)由重言式可以产生许多有用的恒等式。451.3.1永真式1.3.2等价式定义：设A、B是两个命题公式，P1，P2，，Pn

是出现在A和B中的所有命题变元。如果对于P1，P2，，Pn的2n

个真值指派的每一组，公式A和B的真值相同，则称A和B等价。记作A

B。判断公式等价方法：真值表法等价公式变换46真值表判定公式等价性利用真值表证明公式等价性证明与是相互等价的。001101001000111147基本的等价公式48

基本的等价公式49

公式的等价性50181822

Q

ÚPÙ

ØQ

E(QÚP)Ù(QÚØQ)E(QÚP)ÙT

EPÚQ

EPÙ

ØQÚQÛÛÛÛ和替换规则证明：公式的等价性

51将语句“情况并非如此，如果他不来，那么我也不去”化简。P：他来。Q：我去。符号化为：化简：化简后：我去了，他没来。

等价式的应用52等价式的应用如果电话号码数据库是打开的，那么监督程序被置于关闭状态，只要系统不在初态。P：电话号码数据库是打开的Q:监督程序被置于关闭状态R:系统不在初态R(P

Q)53

1.代入规则在一个重言式中，某个命题变元出现的每一处均代以同一个公式后，所得到的新的公式仍是重言式，这条规则称之为带入规则。541.3.3代入规则和替换规则1.代入规则应用代入规则和替换规则及已有的重言式可以证明新的重言式是重言式，那么用代P得到的式子仍然是重言式。

E10：用

代

P，代Q

552.替换规则下面我们给出子公式，及关于公式等价的一个定理定义：设A是一个公式，A´是A的一部分，且A´也是一个命题公式，则称A´是A的子公式。替换规则：设A

是公式A的子公式，B

是一命题公式且A

B，将A中的A

用B

来取代，则所得到的是一个新公式，

记为B，且A

B。例1（P(Q

R))(P

Q

R)P证明：左边(P(Q

R))(P(Q

R))

P((Q

R)

(Q

R))

P

T

P.561.4对偶式与蕴涵式定义：注意:求对偶式并不要求将“非”变原，而且对偶式是相互的。举例：求的对偶式求的对偶式57对偶原理定理1.1：证明：由德•摩根律可知，对公式A求否定，直到¬深入到命题变元之前位置，在这个过程中，所有的变，变，T变F，F变T。得证(1)。58对偶原理

定理1.2:

证明：

意味着

永真

于是有

永真由定理1.1知，下式也永真利用代入规则，以

取代Pi

，得

永真。即59对偶原理例：证明：设则由于，因此，60对偶原理试证明：61

(ØPÚØQÚØPÚQ)Ù(PÚQÚØPÚQ)(P«Q)®(ØPÚQ)ÛØ(P«Q)

Ú(ØPÚQ)Û((ØPÚØQ)Ù(PÚQ))Ú(ØPÚQ)ÛÛ(TÚØP)

Ù(TÚQ)ÛTÙTÛT证明：对偶原理试证明：62(P«Q)Ù(ØPÙQ)

((P«Q)®(ØPÚQ)Û证明：由上例（1）有：T的对偶是F。Û((ØPÚØQ)Ù(PÚQ))Ú(ØPÚQ)

((ØPÚØQ)Ù(PÚQ))Ú(ØPÚQ)互为对偶，因此(P«Q)Ù(ØPÙQ)和((P«Q)®(ØPÚQ)互为对偶由对偶定理1.1可知(P«Q)Ù(ØPÙQ)ÛF

对偶原理定理1.3:证明：

意味着

永真由逆反律得

永真根据定理1.1

为永真式利用带入规则，以

取代，得

永真即631.4.2蕴含式定义：当且仅当A→B是一个永真式时，称A永真蕴含B

，记作要证明A永真蕴含B

，只需要证明A→B是一个永真式假定前件A是真，若能推出后件B必为真，则A→B永真，于是.假定后件B是假，若能推出前件A必为假，则A→B永真，于是.641.4.2蕴含式65常用永真蕴含式661.4.2蕴含式定义：假设H1,…,Hm

,Q是命题公式。如果（H1…Hm

）Q，则称H1,…,Hm

共同蕴涵Q，并记作H1,…,Hm

Q定理：如果H1…Hm

P

Q，则H1,…,Hm

P

Q证明：H1…Hm

P

为真，保证了P为真；H1…Hm

P

Q，保证了Q为真；

于是有P

Q为真，得证。67等价式和蕴含式的关系设P和Q是命题公式，的充分必要条件是并且设A、B、C是公式且有，，则设A,B,C是公式，若有，，则68全功能联结词集合前面我们已经学习了6个逻辑联结词：

是不是这些逻辑联结词都是必不可少的呢？在前面介绍的等价公式中我们已经发现，有些逻辑联结词是可以被其它逻辑联结词代替的：例如：P

Q

P

Q

P

Q

（P

Q）

（P

Q）

P

Q

(

P

Q)

P

Q

(

P

Q)

从上面的讨论我们可以看出逻辑联结词集合{

，，}是全功能的，但不是最小的。逻辑联结词全功能最小完备集是指用该集合中的逻辑联结词能表示所有的命题公式，并且删除一个至少有一个公式不能被表示。例如：{，}和{，}均是最小功能完备集▽69逻辑部件非门的图示：ＰＰ逻辑部件与门的图示：ＰＰＱＱ逻辑部件或门的图示：ＰＰＱＱ70应用：汽车报站系统令Ｐ：汽车运行的方向（上行为０下行则为１）Ｑ：当前站点（用数字表示）Ｒ：下一站点（用数字表示）于是其逻辑表达式为：ＰＱＲ＝（ＰＱ）Ｒ＝ＰＱＲ请同学完成该逻辑表达式的图示．

71

ＰＰ

Ｐ

ＱＱ

ＱＲ721.5范式和判定问题公式的标准形式——范式

用来在有限步内判定公式永真、永假、可满足的73析取范式和合取范式定义：若一个命题公式是一些命题变元及其否定的积，则称之为基本积；若这个命题公式是一些变元及其否定之和，称为基本和。

一个由基本积的和组成的公式，如果与给定的公式A等价，则称它是A的析取范式。一个由基本和的积组成的公式，如果与给定的命题公式A等价，则称它是A的合取范式。74析取范式和合取范式定理1.4：一个基本积是永假式，当且仅当它含有形式的两个因子。证明：（充分性）由于

是永假式，而

，所以含有和形式的两个因子时基本积是永假式。

（必要性）用反证法。设基本积为假但不含和形式的因子，于是给这个基本积中的命题变元指派真值T，给带有否定的命题变元指派真值F，得基本积的真值是T，与假设矛盾。证毕。

75析取范式和合取范式定理1.5:一个基本和是永真式，当且仅当它含有形式的两个因子。76析取范式和合取范式例：求命题公式P（QR）的析取范式解：P（QR）P（QR）

/*这是一个合取范式*/

（PQ）（PR）/*使用与对或的分配律，化成析取范式*/77析取范式与合取范式例：求命题公式(PQ)(PQ)的合取范式解：(PQ)(PQ)((PQ)(PQ))((PQ)(PQ))/*消*/

((PQ)(PQ))((PQ)(PQ))/*消

并且否定深入到单个变元前*/

(PQ)(PQ)/*析取范式*/((PQ)P)((PQ)Q)(PQ)(PQ)/*使用或对与的分配律及补余律，现在是合取范式的形式*/78析取范式和合取范式79析取范式和合取范式80主析取范式定义1.10：在含n个变元的基本积中，若每个变元与其否定不同时存在，而二者之一必出现且仅出现一次，则称这种基本积为极小项。例：两个命题变元P、Q的极小项为

n个变元，极小项个数2n81主析取范式假定有P、Q、R三个变元82主析取范式每个极小项只有一个真值指派使其为T任何两个极小项的合取必为假（因为在2n种真值指派中，只有一个极小项取值为真）所有极小项的析取必为真83主析取范式定义1.11：一个由极小项的和组成的公式，如果与命题公式A等价，则称它是公式A的主析取范式。对任何命题公式(永假式除外)都可求得与其等价的主析取范式，而且主析取范式的形式唯一。84主析取范式求主析取范式的方法：先化成与其等价的析取范式；若析取范式的基本积中同一命题变元出现多次，则将其化成只出现一次；去掉析取范式中所有为永假式的基本积，即去掉基本积中含有形如PΛ¬P的子公式的那些基本积；若析取范式中缺少某一命题变元如P，则可用公式将命题变元P补充进去，并利用分配律展开，然后合并相同的基本积85主析取范式86主析取范式主析取范式和真值表的关系：右图为对应的真值表：极小项0000001101000111100010111101111187主合取范式定义1.12：在含n个变元的基本和中，若每个变元与其否定不同时存在，而二者之一必出现且仅出现一次，则称这种基本和为极大项。例：两个命题变元P、Q的极大项为

n个变元，极大项个数2n88主合取范式假定有P、Q、R三个变元89每个极大项只有一组真值指派使其为F任何两个极大项的析取必为真（因为在2n种真值指派中，只有一个极大项取值为假）所有极大项的合取必为假。90主合取范式定义1.13：一个由极大项的积组成的公式，如果与命题公式A等价，则称它是公式A的主合取范式。对任何命题公式(永真式除外)都可求得与其等价的主合取范式，而且主合取范式的形式唯一。91主合取范式92主合取范式主合取范式和真值表的关系：右图为对应的真值表：极大项00000011010001111000101111011111与极小项联系？93极小项和极大项的关系极小项和极大项有下列的关系：94由合取（析取）范式求主析取（合取）范式二者可以互相转化已知公式A的主合取范式为：求主析取范式。解：A的主合取范式为M1ΛM3，可知A的主析取范式为于是可直接写出A的主析取范式95主析取范式和主合取范式一个命题公式是永真式，它的命题变元的所有极小项均出现在其主析取范式中，不存在与其等价的主合取范式；一个命题公式是永假式，它的命题变元的所有极大项均出现在其主合取范式中，不存在与其等价的主析取范式；一个命题公式是可满足的，它既有与其等价的主析取范式，也有与其等价的主合取范式．96主析取范式和主合取范式例:求下列公式的主范式：（PQ)R解：（PQ)R

(

PQ)R

(PQ)R(PR)(QR)(PR(QQ))(QR(PP))(PQR)(PQR))(PQR)(PQR)M1,3,5/*其中

表示求合取*/m0,2,4,6,7/*即该公式是可满足的，应存在与其等价的主析取范式*/97主析取范式和主合取范式例：求下列命题公式的主范式：（P

QR）（P

QS）解：（P

QR）（P

QS）

（PQRS）（PQRS）（PQRS）（PQRS）

m11,10,6,4/*这里代表析取*/M0，1，2，3，5，7，8，9，10，12，13，14，15从上面的解题过程中我们可以看出，如果与一个命题公式等价的一种主范式一经求出，另一种形式立刻可以得出，除非是永真（或永假）式。981.6命题演算的推理理论数理逻辑的一个主要任务就是提供一套推理规则，给定一些前提，利用所提供的推理规则，推导出一些结论来，这个过程称为演绎或证明。生活中：倘若认定前提是真的，从前提推导出结论的论证是遵守了逻辑推理规则，则认为此结论是真的，并且认为这个论证过程是合法的。数理逻辑中：不关心前提的真实真值，把注意力集中于推理规则的研究，依据这些推理规则推导出的任何结论，称为有效结论，而这种论证则被称为有效论证。99有效结论定义:设A和B是两个命题公式，当且仅当AB是个永真式，即AB，则说B是A的有效结论，或B由A可逻辑的推出。可把该定义推广到有n个前提的情况。100有效结论定义：例：H1：今天周一或者今天下雨。H2：今天不是周一。C：今天下雨。101证明有效结论的方法1，真值表法思路:“证明使前提集合取值为真的那些组真值指派，也一定使结论取值为真”。例:考察结论C是否是下列前提H1，H2,H3的结论。(1)H1：P→Q，H2：P，C：QPQH1H2CH1ΛH2→C001001011011100101111111102真值表法(2)

真值表构造如下：00000101001110010111011111110011

11011101

10101010

11110000103真值表法(3)00011011110001110001104真值表法例：一份统计表格的错误或者是由于材料不可靠，或者是由于计算有错误；这份统计表格的错误不是由于材料不可靠，所以这份统计表格是由于计算有错误。解：设P:一份统计表格的错误是由于材料不可靠。

Q:一份统计表格的错误是由于计算有错误。于是问题可符号化为：(PQ)PQ105真值表法PQ(PQ)PQ0000011110001101106证明有效结论的方法2，直接证法在命题变元较多的情况下，真值表法显得不方便，我们采用直接证明法，为此先给出如下的定义定义：设S是一个命题公式的集合，从S推出命题公式C的推理过程是命题公式的一个有限序列：C1，C2，…，Cn。其中，Ci或者属于S，或者是某些Cj(j<i)的有效结论，并且Cn就是C。如何构造这个推理序列以得出结论C呢？只要遵循下面的推理规则，使用列出的等价式或永真蕴涵式，就能构造出满足要求的公式序列。为了帮助大家记忆，我们把常用的等价式和永真蕴涵式再次列出来。107直接证法直接证明法：使用推理规则和给定的等价式及永真蕴涵式进行推导证明。推理规则：规则P：在推导过程中，任何时候都可以引入前提。引入一个前提称为使用一次P规则。规则T：在推导中，如果前面有一个或多个公式永真蕴含公式S，则可以把公式S引进推导过程中。换句话说，引进前面推导过程中的推理结果称为使用T规则。108直接证法解:{1}(1)¬(P∧¬Q)P规则

{1}(2)¬P∨QT规则(1)和E11{1}(3)P→QT规则(2)和E27{4}(4)¬Q∨RP规则

{4}(5)Q→RT规则(4)和E27{1,4}(6)P→RT,(3),(5)和I12{7}(7)¬RP规则

{1,4,7}(8)¬PT,(6),(7)和I12109直接证法例：证明公式SR可由公式PQ，PR，QS推出解：问题即证PQ，PR，QSSR(1)

PQP规则(2)

PQT规则和1(3)

QSP规则(4)

QST规则和3(5)

PST规则及2和4(6)

SPT规则和5(7)

PRP规则(8)（PR）（RP）T规则和7(9)

PRT规则和8(10)

SRT规则及6和9；(11)SRT规则和9得证。110直接证法例：(PQ)(RS),(QP)R,R

PQ(1)RP规则(2)(QP)RP规则(3)QPT规则及1和2(4)

RST规则及1(5)

(PQ)(RS)P规则(6)

PQT规则及4和5(7)(PQ)(QP)T规则及3和6(8)PQT规则和7111直接证法推理规则：CP规则：如果能从R和前提集合中推导出S来，则就能够从前提集合中推导出R→S。换句话说，当结论是R

S的形式的时候，可以把结论的前件当作一个附加前提使用，并且它和前提一起若能推出结论的后件，则问题得证实际上恒等式E28就可以推出CP规则：（

P∧Q

）

R

（

P∧Q

）∨

R

（

P∨

Q

）∨R

P∨（

Q∨R

）

P

（Q

R）112直接证法解：{1}(1)RP规则（附加前提）

{2}(2)¬R

∨PP规则

{1,2}(3)PT规则,(1),(2)和I9{4}(4)P→(Q→S)P规则

{1,2,4}(5)Q→ST规则,(3),(4)和I10{6}(6)QP规则

{1,2,4,6}(7)ST规则,(5),(6)和I10

{1,2,4,6}(8)R→SCP规则,(1),(7)113例：证明RS是前提P(QS),R(PQ)的有效结论解：原证明即证:P(QS),R(PQ)RS(1)

RP规则（附加前提）(2)

R(PQ)P规则(3)

PQT规则及1和2(4)

PT规则和3(5)

P(QS)P规则(6)

QST规则及4和5(7)

QT规则和3(8)

ST规则及6和7(9)RSCP规则及1和8直接证法114

例：证明P(QR),Q,PSSR解

(1)

SP规则（附加前提）

(2)

PSP规则

(3)

PT规则及1和2(4)

P(QR)P规则

(5)

QRT规则及3和4(6)

QP规则

(7)

RT规则及5和6(8)

SRCP规则及1和7直接证法115证明有效结论的方法3，间接证明法（反证法）定义：设公式H1,H2,…Hm中的原子变元是P1,P2,…Pn。如果给各原子变元P1,P2,…Pn指派某一个真值集合，能使H1ΛH2Λ…ΛHm具有真值T，则命题公式集合{H1,H2,…Hm}称为一致的(或相容的)；对于各原子变元的每一个真值指派，如果命题公式H1,H2,…Hm中至少有一个是假，从而使得H1ΛH2Λ…ΛHm是假，则称命题公式集合是不一致的(或不相容的)。例如：令H1=P，H2=¬P，则H1∧H2=P∧¬P是矛盾式，所以P，¬P是不相容的。116反证法定理：若存在一个公式R，使得

H1∧H2∧…∧Hm

R∧¬R

则公式H1，H2，…,Hm是不相容的。证明：设，H1∧H2∧…∧Hm

R∧¬R则意味着（H1∧H2∧…∧Hm

）→（R∧¬R）是重言式，而R∧¬R是矛盾式，所以前件H1∧H2∧…∧Hm必永假。因此，H1，H2，…,Hm是不相容的。117反证法定理：设命题公式集合{H1，H2，…，Hm}是一致的，于是从前提集合出发可以逻辑的推出公式C的充要条件是从前提集合{H1，H2，…，Hm，C}出发，可以逻辑地推出一个矛盾（永假）式。证明：必要性：由于H1

H2

…HmC，即H1

H2

…Hm

C为永真式，因而使H1

H2

…Hm为真的真值指派一定使C为真，C为假，从而使H1

H2

…HmC为假。必要性证完。118反证法证充分性：由于{H1

H2

…HmC}可以逻辑地推出一个矛盾，即H1

H2

…HmCF即H1

H2

…HmCF为永真式，即H1

H2

…HmC为假，由假设知{H1，H2，…，Hm}是一致的，所以任何使H1

H2

…Hm为真的命题变元的真值指派必然使C为假，从而使C为真。故有H1

H2

…HmC该定理说明用直接证明法可以证明的结论，用间接证明法都可以证明，反之亦然。因此，为了证明B是A的结论，可以把A和B作为前提，然后推出一个矛盾，从而使问题得证。下面用例子说明。119反证法F规则：如果前提集合和¬S不相容，那么可以从前提集合中推出S。例：证明¬(P∧Q)是¬P∧¬Q的有效结论。解：把¬¬(P∧Q)作为假设前提，并证明该假设前提导致一个永假式。{1}(1)¬¬(P∧Q)P规则（假设前提）{1}(2)P∧QT规则，(1)和E10{1}(3)PT规则，(2)和I1{4}(4)¬P∧¬QP规则{4}(5)¬PT规则，(4)和I1{1,4}(6)P∧¬PT规则，(3),(5)和I16{1,4}(7)¬(P∧Q)F规则，(1),(6)120反证法例：证明PQ，PR，QRR解(1)

RP规则（假设前提）

(2)

PRP规则

(3)

PT规则及1和2(4)

PQP规则

(5)

QT规则及3和4(6)

QRP规则

(7)

RT规则及5和6(8)

RRT规则及1和7(9)

RF规则及1和8121反证法例：足坛4支甲级队进行比赛，已知情况如下：前提：1、若大连万达获冠军，则北京国安和上海申花获得亚军

2、若上海申花获亚军，则大连万达不能获冠军

3、若陕西国力获亚军，则北京国安不能获亚军

4、最后大连万达获冠军结论：5、陕西国力未获亚军122反证法用推理的方法证明由{1、2、3、4}能否推出5解：首先将命题符号化令P：大连万达获冠军

Q：北京国安获亚军

R：上海申花获亚军

S：陕西国力获亚军123反证法于是问题可符号化为：P(QR),RP,SQ,PS/*注意这里自然语言中的和表示的是排斥或，所以用来表示*/解(1)

SP规则（假设前提）

(2)ST规则和(1)(3)SQP规则

(4)

QT规则(2)和(3)(5)PP规则

(6)P(QR)P规则

(7)QRT规则(5)和(6)(8)RT规则(4)和(7)(9)

RPP规则124反证法(10)

PT规则(8)和(9)(11)PPT规则(5)和(10)(12)

SF规则(1)和(11)

/*问题得证*/125证明有效结论使用方法规律当要证明的结论是条件式时，可考虑使用CP规则当要证明的结论比较简单，而仅仅使用前提推导不明显时，可考虑使用间接证明法即F规则，以使推导过程变得简捷。1261.7应用与拓展布尔逻辑布尔逻辑（BooleanLogic）是根据19世纪英国数学家乔治.布尔（GeorgeBoole）而命名的。布尔逻辑在电子学、计算机硬件和软件上有很多应用。如在电子工程的电路设计中，可以用0和1代表数字电路中的不同状态；在软件设计中，也常常使用布尔逻辑来表示程序的运行状况。基于布尔逻辑的的信息检索也称为布尔逻辑搜索，指利用布尔逻辑运算符连接各个检索词构成逻辑检索式，然后由计算机进行相应运算，以找出所需信息的方法。（1）逻辑与该运算符用符号“and”或“*”表示，相应的逻辑表达式为“AandB”或“A*B”，检索记录同时含有检索词A和B的网页被命中。应用该运算符可以缩小检索范围，提高查询准确率。（2）逻辑或该运算符用符号“or”表示，相应的逻辑表达式为“AorB”，在检索记录中凡含有检索词A或检索词B或同时含有检索词A和B的，均为命中网页。应用该运算符可以扩大检索范围，提高查全率。Google用大写的“OR”或者符号“|”表示逻辑“或”操作。例如查找有关计算机辅助设计方面的文献，用英文检索时若只输入这个词组的缩写“CAD”或全称“ComputerAidedDesign”就会造成漏检，必须输入检索式“CADORComputerAidedDesign”才能保证查全率。（3）逻辑非该运算符用符号“not”或“-”表示，相应的逻辑表达式为“AnotB”或“A-B”，在检索记录中含有检索词A但不包含检索词B的文献，才算命中文献。使用该运算符可以缩小检索范围，提高查找准确率。1271.7应用与拓展命题逻辑与可满足性问题（SAT）可满足性问题（BooleanSatisfiability,SAT）是指：给定一个布尔/命题公式，问是否存在一组真假赋值使为真；如果存在就称可满足（SAT），否则称不可满足（UNSAT）。命题逻辑以“赋值—真值”为语义基础，因此SAT可以看作命题逻辑中最核心、最具计算意义的判定问题：它把“公式在某个赋值下是否能为真”抽象成统一的求解任务。命题逻辑里的推理问题能自然过渡到SAT/UNSAT的判定：例如知识库KB（KnowledgeBase）是否能推出结论q，可转化为检查是否不可满足；若不可满足，说明不存在“KB成立但为假”的反例，于是成立。 SAT在AI中常被视为一种“通用的离散推理与约束求解引擎”，尤其适合处理由大量规则、约束、互斥关系组成的组合问题。很多AI任务可以先用命题变量表示关键决策或状态（例如“某动作是否在时刻执行”“某资源是否被占用”“某规则是否同时满足”），再把业务规则与逻辑约束写成命题公式，并转成求解器更易处理的形式，最后交给SAT求解器判断是否存在满足赋值：若为SAT，则求解器给出的赋值就是一组可行方案；若为UNSAT，则表示这些约束无法同时成立，从而提示知识库或策略之间存在冲突。基于这种思想，SAT常用于知识表示与自动推理中的一致性检查与反例搜索，也广泛出现在经典规划、调度、配置管理、形式化验证等场景中：它把“推理/规划/约束满足”统一为“是否存在满足解”的计算问题，使得符号化的AI过程可以借助成熟的求解技术实现高效自动化。1281.7应用与拓展MaxSAT用于可解释AI的规则学习在可解释AI中，一个常见目标是学习“人能读懂”的模型，例如规则列表（rulelist）、决策等，同时又希望预测尽量准确、模型尽量简短、并满足一些结构性约束。这类需求很自然地落到MaxSAT（最大可满足性）或加权MaxSAT：把必须满足的逻辑条件写成硬约束，把“尽量满足”的偏好写成软约束并赋予权重（例如“少用规则/少用特征”对应惩罚，“尽量分类正确”对应奖励或减少错误惩罚），最终求解器给出一个在硬约束可行的前提下、软约束最优的解。这样得到的解往往不仅是一个可解释模型，还能直接解释“为什么它在约束与准确率之间做了这种折中”。在工程层面，Open-WBO是一个可直接使用的开源MaxSAT求解器，官方页面说明它实现了多种MaxSAT算法，并且其求解通常建立在对底层SAT求解器的序列调用之上。在“可解释模型学习”的学术证据方面，有明确把MaxSAT作为核心技术的工作，有相关研究讨论了通过MaxSAT学习可解释的决策树模型，并将其作为把可解释性与精度统一到组合优化框架中的方法路线之一1291.7应用与拓展GoogleOR-Tools的CP-SAT在很多AI场景里，“智能”并不一定是深度学习，而是把现实任务写成离散决策+约束：例如员工排班要满足工时上限、技能匹配、班次覆盖、休息间隔；生产调度要满足机器容量、工序先后、交付期；资源分配要满足互斥与预算等。这类问题可以用命题变量/整数变量描述，再用逻辑约束把可行性条件表达出来，最终交给求解器自动搜索满足解或最优解。Google的OR-Tools提供的CP-SAT（约束求解-ConstraintProgramming（CP）-可满足性问题-SatisfiabilityProblem（SAT））求解器是工业界非常常用的选择之一，它面向的是“整数/组合优化”类问题：用户把决策变量设为整数或布尔变量，把现实约束（如排班覆盖、资源容量、互斥条件、先后顺序、时间窗等）写进模型，求解器就会返回是否存在可行解以及最优解等状态，并在可行时给出一组具体赋值作为方案。OR-Tools官方文档明确把CP-SAT定位为面向整数规划的核心求解器，并提供了从建模到求解的完整接口与返回状态说明。从“为什么它叫CP-SAT”这个角度看，它的关键思想是把约束规划（CP）的建模与传播能力，与SAT求解器的搜索与学习机制结合起来：求解过程中，CP侧会通过约束传播不断缩小变量的取值范围，而一旦搜索走到冲突（不可行）分支，底层会进行冲突分析并学习出能够排除同类失败分支的约束，从而减少重复探索、显著加速后续搜索。1301.7应用与拓展Microsoft的Z3在AI的“自动推理”与“程序分析”方向里，经常需要回答这类问题：某段程序在所有输入下是否满足性质？是否存在输入触发断言失败？两个实现是否等价？这类问题通常要处理的不只是布尔逻辑，还包括整数、位向量、数组等结构，因此更一般的形式是SMT（SatisfiabilityModuloTheories）。但关键点是：很多SMT求解器的总体框架依然以SAT为核心驱动——先在命题层面猜测一组真假组合，再由“理论求解器”检查这些组合能否在算术/数组等理论下同时成立；一旦发现矛盾，就把矛盾原因“回传”为新的约束，继续推动SAT层剪枝。Z3是一个典型且广泛落地的SMT求解器：它不仅能处理纯命题逻辑，还能处理算术、位向量、数组、未解释函数、量词（第二章的概念）等更丰富的理论结构，因此特别适合把“程序语义+约束”形式化后交给工具自动推理。MicrosoftResearch的官方出版页面就明确指出，Z3是其研究团队发布的SMT求解器，并被用于多种软件验证与分析应用。从“命题逻辑如何过渡到更强的SMT”来看，Z3的关键在于：虽然它支持算术、数组等多种理论，但整体求解仍由SAT的布尔搜索驱动。论文“Z3:AnEfficientSMTSolver“[3]指出，Z3集成了现代的DPLL-basedSATsolver，并与核心理论求解器及处理算术、数组等的求解模块协同工作。其过程可理解为：先对公式做命题抽象，由SAT选择一组原子命题的真假组合；再由理论求解器检查这些选择在相应理论下是否一致，若发现矛盾则返回冲突信息来剪枝后续搜索，直到找到解或证明不可满足。1311.8历史人物与事件数理逻辑创始人——戈特弗里德・威廉・莱布尼茨戈特弗里德・威廉・莱布尼茨（GottfriedWilhelmLeibniz）是17世纪德国著名的哲学家、数学家，在数理逻辑的发展历程中占据着至关重要的地位。1646年7月1日，莱布尼茨出生于德国东部的莱比锡。他的父亲是莱比锡大学的伦理学教授，在父亲的影响下，莱布尼茨自幼便接触到了丰富的知识。少年时期的莱布尼茨展现出了惊人的天赋和学习能力，他广泛阅读各类书籍，包括哲学、历史、文学等。15岁时，他进入莱比锡大学学习法律，同时也深入钻研哲学和数学。1666年，莱布尼茨获得阿尔特多夫大学法学博士学位。此后，他涉足政治和外交领域，曾在美因茨选帝侯的宫廷中担任法律顾问和外交官。在这个过程中，他有机会接触到欧洲各地的学者和思想家，拓宽了自己的学术视野。莱布尼茨在数学、哲学、物理学、语言学等多个领域都取得了卓越的成就。他独立发明了微积分，与牛顿的微积分体系有所不同，但同样对数