离散数学-第1章-命题逻辑省名师优质课赛课获奖课件市赛课一等奖课件

第一章命题逻辑（PropositionLogic）命题符号化及联结词命题公式及分类等值演算联结词全功效集对偶与范式推理理论1234561/81介绍逻辑学：

研究推理一门学科数理逻辑：

用数学方法研究推理一门数学学科——一套符号体系+一组规则2/812介绍数理逻辑内容：

古典数理逻辑：命题逻辑、谓词逻辑

当代数理逻辑：逻辑演算、公理化集合论、递归论、模型论、证实论3/813命题逻辑命题(Proposition)：

一个有确定真或假意义语句。命题符号化及联结词14/814EXAMPLE1以下句子都是命题：

1.华盛顿是美国首都。2.多伦多是加拿大首都。3.1+1=2。4.2+2=3。

命题1和3是真命题，2和4是假命题。命题符号化及联结词5/815命题符号化及联结词EXAMPLE2考虑以下句子：1.现在几点了？2.认真阅读一下。3.x+1=2.4.x+y=z.句子1和2不是命题，因为它们都不是陈说句。句子3和4不是命题，因为x，y和z值不确定，使得它们真值都不唯一。6/816命题语句形式：陈说句非命题语句：疑问句、命令句、感叹句、非命题陈说句：悖论语句（真值不唯一）命题符号化及联结词7/817命题符号表示：大小写英文字母：P、Q、R、p、q、r……命题真值(TruthValues)表示：真：T、1

假：F、0命题符号化及联结词8/818命题语句真值确定几点说明：1、时间性2、区域性3、标准性命题真值间关系表示：

真值表(TruthTable)命题符号化及联结词9/819DEFINITION1.

设p为任一命题，复合命题“非p”（或“p否定”）称为p否定式。记作﹁p。﹁为否定联结词。真值表见Table1。(Letpbeaproposition.Thestatement“Itisnotthecasethatp.”isanotherproposition,calledthenegationofp.Thenegationofpisdenotedby﹁p.Theproposition﹁pisread“notp.”)p否定命题符号化及联结词10/8110Table1Table1否定命题真值表p﹁p1001命题符号化及联结词11/8111EXAMPLE3设p表示“今天是星期五”，则﹁p表示“今天不是星期五”。显然，当p真值为0时，﹁p真值为1。命题符号化及联结词12/8112命题符号化及联结词设p，q为两命题，复合命题“p而且q”（或“p和q”）称作p与q合取式。记作p∧q。∧为合取联结词。真值表见Table2。(Letpandqbepropositions.Theproposition"pandq,"denotedbyp∧q,isthepropositionthatistruewhenbothpandqaretrueandisfalseotherwise.Thepropositionp∧qiscalledtheconjunctionofpandq.)p和q合取DEFINITION2.13/8113命题符号化及联结词Table2Table2两个命题合取真值表pqp∧q00011011000114/8114EXAMPLE4用p表示命题“今天是星期五”，q表示命题“今天下雨”，则命题p与q合取式是什么？解答：

p与q合取式p∧q是“今天是星期五，而且今天下雨。”假如是星期五，又下雨，则该命题为真；假如是除星期五外任意一天，或者虽是星期五但没下雨，则该命题为假。命题符号化及联结词15/8115命题符号化及联结词设p，q为两命题，复合命题“p或q”称作p与q析取式。记作p∨q。∨为析取联结词。真值表见Table3。

(Letpandqbepropositions.Theproposition"porq,"denotedbyp∨q,isthepropositionthatisfalsewhenpandqarebothfalseandtrueotherwise.Thepropositionp∨qiscalledthedisjunctionofpandq.)p和q析取DEFINITION3.16/8116命题符号化及联结词Table3Table3两个命题析取真值表pqp∨q00011011011117/8117还是以Example4为例，命题p与q析取式是什么？解答：

p与q析取式p∨q是“今天是星期五或今天下雨。”只有今天既不是星期五，又没有下雨，则该命题为假；假如今天是星期五或者今天下雨了（包含下雨星期五），则该命题就为真。EXAMPLE5命题符号化及联结词18/8118命题符号化及联结词设p，q为两命题，复合命题“假如p，则q”称作p与q蕴含式。记作p→q。称p为蕴含式前件(hypothesis)，q为蕴含式后件(conclusion)。→称作蕴含联结词。真值表见Table4。(Letpandqbepropositions.Theimplicationp→qisthepropositionthatisfalsewhenpistrueandqisfalseandtrueotherwise.)假如p，则q单条件，蕴涵p：前提q：结论DEFINITION4.19/8119命题符号化及联结词Table4Table4蕴含式p→q真值表pqp→q00011011110120/8120命题符号化及联结词用p表示命题“天下雨”，用q表示命题“我骑自行车上班”，将以下命题符号化：（1）只要不下雨，我就骑自行车上班。（2）只有不下雨，我才骑自行车上班。解答：（1）中，﹁p是q充分条件，因而符号化为﹁p→q；（2）中，﹁p是q必要条件，因而符号化为q→﹁p。EXAMPLE621/8121命题符号化及联结词设p，q为两命题，复合命题“p当且仅当q”称作p与q等价式。记作p↔q，↔称作等价联结词。真值表见Table5。(Letpandqbepropositions,Thebiconditionalp↔qisthepropositionthatistruewhenpandqhavethesametruthvaluesandisfalseotherwise.)p当且仅当q双条件，等价DEFINITION5.22/8122命题符号化及联结词Table5Table5等价式p↔q真值表pqp↔q00011011100123/8123命题符号化及联结词将下一命题符号化：

“只有（仅当）你是计算机科学系学生或者你不是新生，你才能够经过校园网上Internet。”解答：a→(c∨﹁f)EXAMPLE7cfa24/8124

将下一命题符号化：“假如你身高小于4英尺，你就不能乘坐过山车，除非你超出了16岁。”解答：(1)(r∧﹁s)→﹁q.(2)﹁s→(r→﹁q).EXAMPLE8rqs假如你身高小于4英尺，而且你不超出16岁，那么你就不能乘坐过山车。假如你不超出16岁，那么当你身高小于4英尺时，你就不能乘坐过山车。命题符号化及联结词25/8125命题符号化及联结词“说离散数学是枯燥无味或毫无价值，那是不正确。”p：离散数学是有味道；q：离散数学是有价值；EXAMPLE9符号化为：﹁(﹁p∨﹁q)26/8126命题逻辑命题公式及分类2P、Q、R……称为原子命题(AtomicProposition)。原子命题或加上逻辑联结词组成表示式成为复合命题(CompositionalProposition)。从命题常量到命题变量(PropositionalVariable)命题公式：1.原子命题是命题公式；2.设P是命题公式，则﹁P也是命题公式；3.设P、Q是命题公式，则(P∧Q)、(P∨Q)、(P→Q)、(P↔

Q)也是命题公式；4.有限次地使用1、2、3所得到也是命题公式。PropositionFormulas,Well-FormedFormulas(wff)27/8127命题公式及分类命题公式运算规则：逻辑联接词优先级：

﹁

、∧、∨、→、↔命题公式表示式运算规律：同代数表示式命题公式运算方法：

全部公式中命题变量用指定命题（真值）代入（或指派），得到一个公式对应真值。性质1：假如一个命题公式有n个互异命题变量，则命题公式对应真值有2n种可能分布。28/8128命题公式及分类EXAMPLE10求以下命题公式真值表：（1）p∧(q∨﹁r).Table6p∧(q∨﹁r)真值表pqr﹁rq∨﹁rp∧(q∨﹁r)00000101001110010111011110101010101110110000101129/8129命题公式及分类EXAMPLE10求以下命题公式真值表：（2）(p∧(p→q))→q.Table7(p∧(p→q))→q真值表pqp→q

p∧(p→q)(p∧(p→q))→q0001101111010001111130/8130命题公式及分类EXAMPLE10求以下命题公式真值表：（3）﹁(p→q)∧q.Table8﹁(p→q)∧q真值表pqp→q﹁(p→q)﹁(p→q)∧q0001101111010010000031/8131命题公式及分类永真式(Tautology)：公式中命题变量不论怎样代入，公式对应真值恒为1。

永假式(Contradiction)：公式中命题变量不论怎样代入，公式对应真值恒为0。

可满足式(Satisfaction)：公式中命题变量不论怎样代入，公式对应真值总有一个情况为1。普通命题公式(Contingency)：既不是永真公式也不是永假公式。32/8132命题公式及分类性质2：（1）设P是永真命题公式，则P否定公式是永假命题公式；（2）设P是永假命题公式，则P否定公式是永真命题公式；（3）设P、Q是永真命题公式，则(P∧Q)、(P∨Q)、(P→Q)、(P↔

Q)也是永真命题公式。33/8133命题公式及分类小结1.命题概念：定义、逻辑值、符号化表示2.从简单命题到复合命题：逻辑联接词：运算方法、运算优先级3.从命题常量到命题变量，从复合命题到命题公式：命题公式真值描述：真值表4.命题公式分类：永真公式、永假公式、可满足公式、普通公式34/8134PropositionalEquivalences设A，B为两命题公式，若等价式A↔B是重言式，则称A与B是等值。记作A

B。(ThepropositionsAandBarecalledlogicallyequivalentifA↔Bisatautology.ThenotationA

BdenotesthatAandBarelogicallyequivalent.)逻辑等值，或逻辑等价DEFINITION6.命题逻辑等值演算335/8135证实﹁(p∨q)与﹁p∧﹁q是等值。（这个等值关系是德·摩根(DeMorgan)定律之一。德·摩根是十九世纪中叶英国数学家。）解答：真值表见Table9。因为对于p和q全部可能组合，﹁(p∨q)和﹁p∧﹁q真值都相同，所以这两个命题是等值。EXAMPLE11等值演算36/8136Table9Table9﹁(p∨q)与﹁p∧﹁q真值表pqp∨q﹁(p∨q)﹁p﹁q﹁p∧﹁q0001101101111000110010101000等值演算37/8137证实p→q与﹁p∨q是等值。解答：真值表见Table10。因为对于p和q全部可能组合，p→q和﹁p∨q真值都相同，所以这两个命题是等值。EXAMPLE12等值演算38/8138Table10Table10p→q与﹁p∨q真值表pqp→q﹁p﹁p∨q00011011110111001101等值演算39/8139证实p∨(q∧r)与(p∨q)∧(p∨r)是等值。（分配律）解答：真值表见Table11。因为对于p、q和r全部可能组合，p∨(q∧r)和(p∨q)∧(p∨r)真值都相同，所以这两个命题是等值。EXAMPLE13等值演算40/8140Table11Table11p∨(q∧r)与(p∨q)∧(p∨r)真值表pqrq∧rp∨(q∧r)p∨qp∨r(p∨q)∧(p∨r)0000010100111001011101110001000100011111001111110101111100011111等值演算41/8141下面给出24个主要等值式（祥见P9）：双重否定律、等幂律、交换律、结合律、分配律、德·摩根律、吸收律、零律、同一律、排中律、矛盾式、蕴含等值式、等价等值式、假言易位、等价否定等值式、归谬论。依据已知等值式，推演出另外一些等值式过程称为等值演算。在进行等值演算时，往往用到置换规则。等值演算42/8142证实﹁(p∨(﹁p∧q))与﹁p∧﹁q是等值。EXAMPLE1400等值演算43/8143证实(p∧q)→(p∨q)是重言式。EXAMPLE15111等值演算44/8144判断命题公式逻辑等价方法：1.真值表2.命题公式演算

基本等值定理；公式代入不变性（置换规则）；等值关系传递性。等值演算45/8145命题公式逻辑等价关系应用：1、判定是否逻辑等价（等值）；2、判断是否为永真公式或永假公式；3、命题公式化简。等值演算46/8146设p,q为两命题，复合命题“p,q之中恰有一个成立”称为p与q排斥或或异或。记作pq，称作排斥或或异或联结词。真值表见Table12。(Letpandqbepropositions.Theexclusiveorofpandq,denotedbypq,isthepropositionthatistruewhenexactlyoneofpandqistrueandisfalseotherwise.)p和q异或DEFINITION7.命题逻辑联结词全功效集447/8147Table12联结词全功效集011000011011p

qpqTable12异或p

q真值表p

q

(p∧﹁q)∨(﹁p∧q)48/8148设p,q为两命题，复合命题“p与q否定”称为p与q与非式。记作pq，称作与非联结词。真值表见Table13。(Letpandqbepropositions.Theandnotofpandq,denotedbyp

q,isthepropositionthatisfalsewhenpandqarebothtrueandtrueotherwise.)p和q与非DEFINITION8.联结词全功效集49/8149Table13Table13与非式pq真值表pqp

q000110111110p

q

﹁(p∧q)联结词全功效集50/8150设p,q为两命题，复合命题“p或q否定”称为p与q或非式。记作pq，称作或非联结词。真值表见Table14。(Letpandqbepropositions.Theornotofpandq,denotedbyp

q,isthepropositionthatistruewhenpandqarebothfalseandfalseotherwise.)p和q或非DEFINITION9.联结词全功效集51/8151Table14Table14与非式pq真值表pqp

q000110111000p

q

﹁(p∨q)联结词全功效集52/8152逻辑联结词集是功效完备集(FunctionallyCompleteSet)：

任一个命题公式都能够等价于仅包含这些逻辑联结词联结起来公式。逻辑联结词集是极小功效完备集：是功效完备集而且没有冗余联结词。联结词全功效集53/8153例1：

﹁、∧、∨、﹁、∧、∨、

、

是功效完备，但不是极小功效完备。例2：

﹁、∧、是极小功效完备。例3：

﹁、∨、是极小功效完备。联结词全功效集54/8154DEFINITION10.命题公式P对偶公式(Dual)：将P中析取联结词换成合取联结词，合取联结词换成析取联结词，1换成0，0换成1（假如存在话）。记为P*.命题逻辑对偶与范式555/8155对偶原理(DualityPrinciple)：

设P，Q是两命题公式，假如

P

Q，

则

P*

Q*。例：A：(P∧﹁

Q)∨QB：P∨Q这里，A

B，分析是否A*

B*。对偶与范式56/8156命题公式标准化——范式小项(smallitem)/合取式(conjunctiveform):

若干个原子命题或其否定合取。大项(largeitem)/析取式(disjunctiveform):

若干个原子命题或其否定析取。析取范式(disjunctivenormalform)：

若干个小项析取。合取范式(conjunctivenormalform)：

若干个大项合取。对偶与范式57/8157定理证实思绪：1、消去对

﹁、∧、∨

来说冗余联结词；2、将否定联结词移到命题变量前面；3、消除多出否定联结词；4、利用分配律化成合取范式和析取范式。定理1：任意一个命题公式都存在与之等价合取范式和析取范式。范式存在定理对偶与范式58/8158令A(a1、a2、…、an)是包含有n个变量公式，极小项(extremal~):小项中恰包含n个变量或其否定。极大项(extremal~):大项中恰包含n个变量或其否定。主析取范式(Uniquedisjunctivenormalform):

若干个极小项析取。主合取范式(Uniqueconjunctivenormalform):

若干个极大项合取。对偶与范式59/8159以三个命题变项p,q,r为例，可形成23=8个极小项，每个极小项对应一个二进制数，也对应一个十进制数，二进制数是该极小项成真赋值，十进制数可做该极小项抽象表示法角码。对应情况以下：﹁p∧﹁q∧﹁r——000——0，记作m0；﹁p∧﹁q∧r——001——1，记作m1；﹁p∧q∧﹁r——010——2，记作m2；﹁p∧q∧r——011——3，记作m3；p∧﹁q∧﹁r——100——4，记作m4；p∧﹁q∧r——101——5，记作m5；p∧q∧﹁r——110——6，记作m6；p∧q∧r——111——7，记作m7。主析取范式：如m1∨m2∨m5可用(1,2,5)表示。对偶与范式60/8160以三个命题变项p,q,r为例，可形成23=8个极大项，每个极大项对应一个二进制数，也对应一个十进制数，二进制数是该极大项成假赋值，十进制数可做该极大项抽象表示法角码。对应情况以下：p∨q∨r——000——0，记作M0；p∨q∨﹁r——001——1，记作M1；p∨﹁q∨r——010——2，记作M2；p∨﹁q∨﹁r——011——3，记作M3；﹁p∨q∨r——100——4，记作M4；﹁p∨q∨﹁r——101——5，记作M5；﹁p∨﹁q∨r——110——6，记作M6；﹁p∨﹁q∨﹁r——111——7，记作M7。主合取范式：如M0∧

M3∧

M6可用(0,3,6)表示。对偶与范式61/8161EXAMPLE16求p∧q∨r主析取范式和主合取范式：解：(p∧q)∨r((pq)(rr))(r(pp))(pqr)(pqr)(pr)(pr)(pqr)(pqr)((pr)(qq))((pr)(qq))(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m7m6m5m3m1(1,3,5,6,7)（主析取范式）

M0M2M4(0,2,4)（主合取范式）对偶与范式62/8162例6张先生手中有代号为A、B、C、D、E五种股票，依据当前股市情况及张先生本人经济需求，需要有若干个股票抛出，但又必须满足以下复杂要求：（1）若A抛出，则B也抛出；（2）B和C要留一个股票且只能留一个；（3）C和D要么全抛，要么都不抛；（4）D和E两种股票中必定有一个或两种要抛出；（5）若E抛出，则A、B也抛出。上述五种条件全部满足，问有几个合理方案供张先生选择。﹁A→﹁BC↔D﹁D∨﹁E﹁E→﹁A∧﹁B解答：留ABE或CD（将题意置换成主析取范式）。对偶与范式BC63/8163小结1、命题公式等价演算2、命题公式标准化描述表示、分类、判定、应用对偶与范式64/8164数理逻辑主要任务是借助于数学方法来研究推理逻辑。

推理是从前题推出结论思维过程，前提是已知命题公式，结论是从前题出发应用推理规则推出命题公式。命题逻辑推理理论665/8165DEFINITION11.若A1∧A2∧…∧Ak→B为重言式，则称从A1,A2,…,Ak推出结论B推理正确，记作A1∧A2∧…∧Ak

B。B是A1,A2,…,Ak逻辑结论或有效结论。称A1∧A2∧…∧Ak→B为推理形式结构。推理理论66/8166判断推理是否正确方法有以下几个：

（1）真值表法；（2）等值演算法；（3）主析取范式法。（即判断A1∧A2∧…∧Ak→B是否为重言式）推理理论67/8167EXAMPLE17判断以下推理是否正确：假如天气凉快，小王就不去游泳，天气凉快，所以小王没去游泳。

解这类推理问题，应先将命题符号化，然后写出前提、结论和推理形式结构，最终进行判断。

在这里，设p：天气凉快；q：小王去游泳。前提：p→﹁q,p。结论：﹁q。推理形式结构：((p→﹁q)∧p)→﹁q。下面分别用三种方法来判断该蕴含式是否为重言式。推理理论68/8168Table15（1）真值表法Table15((p→﹁q)∧p)→﹁q(*)真值表pq﹁qp→﹁q(p→﹁q)∧p(*)000110111010111000101111真值表最终一列全为1，因而（*）是重言式，所以推理正确。推理理论69/8169（2）等值演算法((p→﹁q)∧p)→﹁q((﹁p∨﹁q)∧p)→﹁q

﹁((﹁p∨﹁q)∧p)∨﹁q

﹁(﹁p∨﹁q)∨﹁p∨﹁q

﹁(﹁p∨﹁q)∨(﹁p∨﹁q)1该蕴含式是重言式，所以推理正确。推理理论70/8170((p→﹁q)∧p)→﹁q((﹁p∨﹁q)∧p)→﹁q

﹁((﹁p∨﹁q)∧p)∨﹁q

﹁(﹁p∨﹁q)∨﹁p∨﹁q(p∧q)∨(﹁p∧(q∨﹁q))∨(﹁q∧(p∨﹁p))(p∧q)∨(﹁p∧q)∨(﹁p∧﹁q))∨(﹁q∧p)∨(﹁q∧﹁p)(p∧q)∨(﹁p∧q)∨(﹁p∧﹁q))∨(p∧﹁q)m3∨m1∨m0∨m2(0,1,2,3)（3）主析取范式法该蕴含式主析取范式中含有4个极小项，因而是重言式。推理理论71/8171为了更加好地判断推理正确性，引入结构证实方法。在数理逻辑中，证实是一个描述推理过程命题公式序列，其中每个命题公式或者是已知前提，或者是由一些前提应用推理规则得到结论。其中有些规则建立在推理定律（重言蕴含式）基础之上。

主要8条推理定律：附加、化简、假言推理、拒取式、析取三段论、假言三段论、等价三段论、结构性二难。除此之外，每个等值式均产生两条推理定律。推理理论72/8172推理规则：1、前提引入规则：引入前提。2、结论引入规则：将前面步骤结论作为前提。3、置换规则：命题公式可用等价公式置换。4、假言推理规则：A

B,A╞B5、附加规则：A╞A∨B6、化简规则：A∧B╞A7、拒取式规则：A

B,B╞

A8、假言三段论规则：A

B,BC╞AC9、析取三段论规则：A∨B,B╞A10、结构性二难规则：A

B,CD,A∨C╞B∨D11、合取引入规则：A,B╞A∧B推理理论73/8173EXAMPLE18写出对应下面推理证实：若数a是实数，则它不是有理数就是无理数。若a不能表示成份数，则它不是有理数。a是实数且它不能表示成份数。所以a是无理数。解：将简单命题符号化：

p：a是实数；q：a是有理数；

r：a是无理数；s：a能表示成份数。前提：p→(q∨r),﹁s→﹁q,p∧﹁s。结论：r。推理理论74/8