离散数学-命题逻辑课件

2022/12/221Concept本章主要讨论：命题的表示、命题的演算命题演算中的公式及其应用命题逻辑推理第一章

命题逻辑2022/12/181Concept本章主要讨论：第一章命2022/12/222Concept本节主要讨论三个问题：命题的概念命题的真值及命题的表示原子命题与复合命题1.1

命题与命题的表示2022/12/182Concept本节主要讨论三个问题：12022/12/223一、命题的概念

命题是一个能确定是真的或是假的判断。（判断都是用陈述句表示）Allthefollowingstatementsarepropositions.1.Washington,D.C.,isthecapitaloftheUnitedStatesofAmerica.2.TorontoisthecapitalofCanada.3.1+1=2.4.2+2=3.Propositions1and3aretrue,whereas2and4arefalse.Concept2022/12/183一、命题的概念Propositions2022/12/224ExampleConsiderthefollowingsentences.1.Whattimeisit?2.Readthiscarefully.3.x+1=2.4.x+y=z.Sentences1and2arenotpropositionsbecausetheyarenotstatements.Sentences3and4arenotpropositionsbecausetheyareneitherturenorfalse,sincethevariablesinthesesentenceshavenotbeenassignedvalues.2022/12/184ExampleConsiderthe2022/12/225Concept陈述句的分类一般命题模糊命题模态命题悖论

地球绕太阳旋转。

100是个大数。下个月要下雨。我在说假话。例题：2022/12/185Concept陈述句的分类一般命题模糊2022/12/226Concept命题的语句形式:

陈述句非命题语句：疑问句命令句感叹句非命题陈述句：悖论语句2022/12/186Concept命题的语句形式:几个经典的悖论:1、哲学家Epimenides（埃庇米尼得斯，克里特哲学家、预言家）:“所有克利特人都在说谎，他们中的一个诗人这么说。”2、理发师悖论:“本人的理发技艺十分高超，誉满全城。我将为本城所有不给自己刮脸的人刮脸，我也只给这些人刮脸。我对各位表示热诚欢迎！”3、苏格拉底悖论：“我只知道一件事，那就是什么都不知道。”2022/12/227Concept几个经典的悖论:2022/12/187Concept2022/12/228二、命题的真值及命题的表示命题真值（TruthValues）的表示：

真：T、1；

假：F、0命题的符号表示：大写英文字母：P、Q、R、…

带下标的大写字母：A1、A2、A3、…

数字：［1］、［2］、［3］、…Concept2022/12/188二、命题的真值及命题的表示Concep2022/12/229命题语句真值确定的几点说明：

1、时间性

2、区域性

3、标准性命题真值间的关系表示：真值表（TruthTable)

Concept2022/12/189命题语句真值确定的几点说明：Conce2022/12/2210Concept三、原子命题与复合命题简单命题(原子命题)：由最简单的陈述句构成的命题(该句再不能分解成更简单的句子了)。通常用大写英文字母表示。例:2是个素数。复合命题(分子命题)：由若干个原子命题构成的命题。例:a>b、b>c、a>c,是由三个原子命题构成的复合命题。2022/12/1810Concept三、原子命题与复合命题2022/12/2211conjuntion1.2联结词复合命题的构成：是用“联结词”将原子命题联结起来构成的。归纳自然语言中的联结词，定义了六个逻辑联结词，分别是：(1)否定“”(2)合取“∧”(3)析取“∨”(4)异或“”(6)等价/双条件“”(5)蕴涵“”2022/12/1811conjuntion1.2联结词2022/12/2212conjunction表示：“…不成立”，“不…”。用于：对一个命题P的否定，写成P，并读成“非P”。P的真值：与P真值相反。一.否定“”例：P：今天是星期五。P：今天不是星期五。PPTFFT2022/12/1812conjunction表示：“…不成2022/12/2213表示：“并且”，“与”,它仅表示逻辑上的“与”,与日常语言中的“与”不同。conjunction二.合取“∧”PQP∧QFFFFTFTFFTTT例：P：小王能唱歌。Q：小王能跳舞。P∧Q：小王能歌善舞。P∧Q的真值为真,当且仅当P和Q的真值均为真。2022/12/1813表示：“并且”，“与”,它仅表示逻辑2022/12/2214

表示“或者”，是可兼取的。conjunction三.析取“∨”

灯泡或者线路有故障。第一节课上数学或者上英语。汽车提前十五或二十分钟到达。可兼或或者排斥或表示近似数例：2022/12/1814表示“或者”，是可兼取的。con2022/12/2215conjunction析取“∨”的真值表PQP∨QFFFFTTTFTTTTP∨Q的真值为F，当且仅当P和Q均为FP:李明在教室。Q:米卢是个好教练。P∨Q:李明在教室或米卢是个好教练。例：2022/12/1815conjunction析取“∨”的真2022/12/2216conjunction例：P:米卢在西安。Q:米卢在北京。PQ:米卢在西安或者米卢在北京。PQ的真值为F，当且仅当P与Q的真值相同PQPQFFFFTTTFTTTF四、异或“”2022/12/1816conjunction例：P:米2022/12/2217异或的另一种表示conjunction

异或是表示两个命题不可能同时都成立。命题“第一节课上数学或者上英语。”可以解释为：“第一节课上数学而没有上英语或者第一节课上英语而没有上数学。”于是有

PQ与(P∧Q)∨(Q∧P)是一样的。实际应用中必须注意“或者”的二义性,注意区别可兼或和排斥或。这里不考虑近似或。2022/12/1817异或的另一种表示conjunctio2022/12/2218五、蕴涵(条件)“”conjunction表示“如果P则Q”单条件,蕴涵P:前提、Q:结论例：P表示：缺少水分。Q表示：植物会死亡。PQ：如果缺少水分，植物就会死亡。PQPQFFTFTTTFFTTT如果2＋3＝5，则今年是丰收年。2022/12/1818五、蕴涵(条件)“”conjunc2022/12/2219注意：“”既表示充分条件也表示必要条件，它决定了哪个作为前件，哪个作为后件。conjunction令：P：天气好。Q：我去公园。1.如果天气好，我就去公园。（充分）2.只要天气好，我就去公园。（充分）3.仅当天气好，我才去公园。（必要）4.只有天气好，我才去公园。（必要）例：命题1、2写成：PQ命题3、4写成：QP2022/12/1819注意：“”既表示充分条件也表示必要2022/12/2220conjunctionFindtheconverseandthecontrapositiveoftheimplication"IftodayisThursday,thenIhaveatesttoday."Solution:Theconverseis"IfIhaveatesttoday,thentodayisThursday."Andthecontrapositiveofthisimplicationis"IfIdonothaveatesttoday,thentodayisnotThursday."2022/12/1820conjunctionFindt2022/12/2221conjunction六、等价(双条件）“”表示“P当且仅当Q”例：P：⊿ABC是等边三角形。Q：⊿ABC是等角三角形。PQ

：⊿ABC是等边三角形当且仅当它是等角三角形。PQPQFFTFTFTFFTTT2022/12/1821conjunction六、等价(双条2022/12/2222Question练习：填空已知P∧Q为T，则P为()，Q为()。已知P∨Q为F，则P为()，Q为()。已知P为F，则P∧Q为()。已知P为T，则P∨Q为()。已知P∨Q为T，且P为F，则Q为()。已知PQ为F，则P为()，Q为()。已知P为F，则PQ为()。已知Q为T，则PQ为()。已知PQ为F，则P为()，Q为()。2022/12/1822Question练习：填空2022/12/2223Question已知P为T，PQ为T，则Q为()。已知Q为T,PQ为T，则P为()。已知PQ为T，P为T,则Q为().已知PQ为F，P为T,则Q为().PP的真值为().PP的真值为()。2022/12/1823Question已知P为T，P2022/12/22241-3命题公式及等价公式一.命题变元

命题常量：即是我们前面所说的命题。例如：“3是素数。”就是命题常量。

命题变元：用大写的英字母如P、Q等表示任何命题。称这些字母为命题变元。

对命题变元作指派(给命题变元一个解释)：将一个命题常量赋值给命题变元的过程，或者是直接赋给命题变元真值“T”或“F”的过程。注意：命题变元本身不是命题，只有给它一个指派，才变成命题。Formula2022/12/18241-3命题公式及等价公式一.命题2022/12/2225二.合式公式

(wff)(wellformedformulas)定义：1.命题变元是命题公式；2.设P是命题公式，则¬P也是命题公式；3.设P、Q是命题公式，则（P∧Q）、（P∨Q）、（P→Q）、（PQ）也是命题公式；4.有限次地使用1、2、3所得到的也是命题公式。Formula2022/12/1825二.合式公式(wff)(we2022/12/2226约定：为方便，最外层括号可以不写，合式公式可以写成：

P∧Q，PR，(P∨Q)∧R如果规定逻辑联接词的优先级：

¬

、∧、∨、→、

则：P∧QR也是合式公式Formula2022/12/1826约定：为方便，最外层括号可以不写，合2022/12/2227三.命题符号化Formula命题符号化的方法

1.首先要明确给定命题的含义。

2.对于复合命题，找联结词，用联结词断句，分解出各个原子命题。

3.设原子命题符号，并用逻辑联结词联结原子命题符号，构成给定命题的符号表达式。2022/12/1827三.命题符号化Formula命题符号2022/12/2228HowcanthefollowingEnglishsentencebetranslatedintoalogicalexpression?"YoucanaccesstheInternetfromcampusonlyifyouareacomputersciencemajororyouarenotafreshman"FormulaSolution:a→(c∨f).2022/12/1828Howcanthefollow2022/12/2229HowcanthefollowingEnglishsentencebetranslatedintoalogicalexpression?

"Youcannotridetherollercoasterifyouareunder4feettallunlessyouareolderthan16yearsold."Solution:(r∧s)→q.Formulaqrs2022/12/1829Howcanthefoll2022/12/2230Formula

说离散数学无用且枯燥无味是不对的。

P：离散数学是有用的。

Q：离散数学是枯燥无味的。该命题可写成：

(P∧Q)

人不犯我，我不犯人；人若犯我，我必犯人。

P：人犯我。Q：我犯人。该命题可写成：(PQ)∧(PQ)

或写成：PQP是Q的必要条件P是Q的充分条件P是Q的充分且必要条件2022/12/1830Formula说离散数学无用且枯燥2022/12/2231四、命题公式的真值表所有公式中的命题变量用指定真值进行指派，即得到一个公式对应的真值。PQPPQ(PQ)∨QTTFTTTFFTTFTTTTFFTFF例：Formula2022/12/1831四、命题公式的真值表所有公式中的命题2022/12/2232说明:设P1，P2,…,Pn为命题公式P中的命题变量，对于命题变元每一种真值指派的可能组合，都能唯一确定P的真值（即有2的n次幂种分布）。为了有序地列出公式的真值表，在对命题变元做指派时，可以按照二进制数的次序列表。Formula2022/12/1832说明:Formula2022/12/2233二进制操作Formula2022/12/1833二进制操作Formula2022/12/2234为了有序地列出A(P1,P2,…,Pn)的真值表，可以将F看成0，将T看成1，按照二进制数00…0,00…01,00…010,…,11…10,11…1(即十进制的0,1,2,….,2n-1)的次序进行指派列真值表。例如，A(P,Q)的真值表可按照如下次序指派：00(F,F)，01(F,T)，10(T,F)，11(T,T)例如，A(P,Q,R)的真值表可按照如下次序指派：000(F,F,F),001(F,F,T),010(F,T,F),011(F,T,T)100(T,F,F),101(T,F,T),110(T,T,F),111(T,T,T)Formula2022/12/1834为了有序地列出A(P1,P2,…,P2022/12/2235例如列出P(QR)的真值表

PQRQRP(QR)000FFFTT001FFTTT010FTFFT011FTTTT100TFFTT101TFTTT110TTFFF111TTTTTFormula2022/12/1835例如列出P(QR)的真值表2022/12/2236观察下面的真值表FormulaPQ¬P∨QPQ（P∧

Q）∨（¬P

∧

¬Q）PQ

FFTTTTFTTTFFTFFFFFTTTTTT在上面的真实表中你是否发现什么问题？¬P∨Q＝P

Q？（P∧

Q）∨（¬P

∧

¬Q）

＝PQ

？2022/12/1836观察下面的真值表FormulaP2022/12/2237AB的定义：A、B是含有命题变元P1,P2,…,

Pn的命题公式，如不论对P1,P2,…,

Pn作任何指派，都使得A和B的真值相同，则称之为A与B等价，记作AB。显然¬P∨QP

Q

（P∧

Q）∨（¬P

∧

¬Q）

PQ

结论：判断两个公式是否等价，更好的方法是当变元数不多时，直接构造两个公式的真值表，看两个真值表是否相等即可。Formula2022/12/1837AB的定义：A、B是含有命题变元P2022/12/2238基本的等价公式

⑴对合律PP⑵幂等律P∨PPP∧PP⑶结合律P∨(Q∨R)(P∨Q)∨RP∧(Q∧R)(P∧Q)∧R⑷交换律P∨QQ∨PP∧QQ∧P⑸分配律P∨(Q∧R)(P∨Q)∧(P∨R)P∧(Q∨R)(P∧Q)∨(P∧R)⑹吸收律P∨(P∧Q)PP∧(P∨Q)P⑺德．摩根定律(P∨Q)P∧Q

(P∧Q)P∨QFormula2022/12/1838基本的等价公式Formula2022/12/2239⑻同一律P∨FPP∧TP⑼零律P∨TTP∧FF⑽互补律P∨PTP∧PF附加：⑾PQP∨Q⑿PQQP⒀PQ(PQ)∧(QP)⒁PQ(P∨Q)∧(P∨Q)⒂PQ(P∧Q)∨(P∧Q)Formula2022/12/1839⑻同一律P∨FP2022/12/2240等价公式(前10个)与集合论的公式比较：

⑴对合律~~AA~A表示A的绝对补集⑵幂等律A∪AAA∩AA⑶结合律A∪(B∪C)(A∪B)∪C；

A∩(B∩C)(A∩B)∩C⑷交换律A∪BB∪AA∩BB∩A⑸分配律A∪(B∩C)(A∪B)∩(A∪C)A∩(B∪C)(A∩B)∪(A∩C)⑹吸收律A∪(A∩B)AA∩(A∪B)A

Formula2022/12/1840等价公式(前10个)与集合论的公式比2022/12/2241⑺德．摩根定律~(A∪B)~A∩~B

~(A∩B)~A∪~B⑻同一律A∪ΦA;A∩EAE表示全集⑼零律A∪EEA∩ΦΦ⑽否定律A∪~AEA∩~AΦ下面通过例题应用等价公式Formula2022/12/1841⑺德．摩根定律~(A∪B)~2022/12/2242Example例１：证明证明P

（QR）P∨（Q∨R）

P（QR）

P∨（QR）P∨（Q∨R）例2：证明德．摩根定律PQ(P∧Q)P∨

Q(P∨

Q)P∧

QFFTTTTFTTTFFTFTTFFTTFFFF证明2022/12/1842Example例１：证明证明P2022/12/2243

(P∧(R∨Q))∨(P∧Q∧R)

P∧((R∨Q)∨(

Q∧R))P∧((R∨Q)∨(Q∨R))P∧TPExample例3：证明(P∧(R∨Q))∨(P∧Q∧R)P结论证明等价公式成立的常用方法：

方法1：真值表。

方法2：等价公式推导。(用置换定律)2022/12/1843(P∧(R∨Q)2022/12/2244置换定律:A是一个命题公式，X是A中的一部分且也是合式公式，如果XY，用Y代替A中的X得到公式B，则AB。满足置换定律的变换称为等价变换。Example例题1.

求证吸收律P∧(P∨Q)P证明

P∧(P∨Q)

(P∨F)∧(P∨Q)(同一律)

P∨(F∧Q)(分配律)

P∨F(零律)

P(同一律)2022/12/1844置换定律:A是一个命题公式，X是A2022/12/2245Example例题2.求证(P∨Q)→(P∧Q)P

证明

(P∨Q)→(P∧Q)

(P∨Q)∨(P∧Q)(公式E11)(P∧Q)∨(P∧Q)(摩根定律)(P∧Q)∨(P∧Q)(对合律)

P∧(Q∨Q)(分配律)

P∧T(互补律)

P(同一律)公式E11：PQP∨Q

2022/12/1845Example例题2.求证(P2022/12/2246例题3.化简(P∧Q)→(P∨(P∨Q))

解原公式(P∧Q)∨((P∨P)∨Q)(E11,结合)(P∧Q)∨(P∨Q)(对合律，幂等律)(P∧Q)∨(Q∨P)(交换律)((P∧Q)∨Q)∨P(结合律)Q∨P(吸收律)公式E11：PQP∨QExample2022/12/1846例题3.化简(P∧Q)→(P∨2022/12/22471-4重言式与重言蕴涵式Formula观察下面真值表：PQ(P∨

Q)∧(P∨

Q)P∨PFFFTFTFTTFFTTTFT可见不论P、Q取值如何，P∨P

的真值总为真，(P∨

Q)∧(P∨

Q)的真值总为假。故称P∨P为重言式(永真式)；称(P∨

Q)∧(P∨

Q)为矛盾式(永假式)。2022/12/18471-4重言式与重言蕴涵式Formu2022/12/2248Definition永真(重言)式（Tautology）公式中的命题变量元论怎样指派，公式对应的真值恒为T。

永假（矛盾）式（Contradiction)公式中的命题变量无论怎样代入，公式对应的真值恒为F。

可满足公式（Satisfaction）公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为T。一般命题公式（Contingency）既不是永真公式也不是永假公式。2022/12/1848Definition永真(重言)式（2022/12/2249Formula重言式的证明方法

方法1：列真值表。

方法2：公式的等价变换，化简成“T”。

方法3：用公式的主析取范式(永真式的主析取范式包含所有的小项)。其中方法2和方法3我们在以后讨论。永真式的性质如果A是永真式，则A是永假式。如果A，B是永真式，则(A∧B)、(A∨B)、(AB)和(AB)也都是永真式。如果A是永真式，则A的置换例式也是永真式。如果用公式X替换命题公式A中的某个变元,

替换后得到的新公式B称为A的置换例式。2022/12/1849Formula重言式的证明方法如果用2022/12/2250公式A：P∨(P∧((PQ)R))用(DE)替换A中P得到A的置换例式B：(DE)∨((DE)∧(((DE)Q)R))如果A是永真式，例如A为P∨P，用

(DE)替换A中P，得到A的置换例式B：(DE)∨(DE)

，显然B也是永真式。结论：如果可以断定给定公式是某个永真式的置换例式的话，则这个公式也是永真式。（这为判定永真式提供了第4种思路）Formula2022/12/1850公式A：P∨(P∧((PQ)R2022/12/2251AB与AB的关系定理：设A、B为两个命题公式，AB当且仅当AB为重言式证明若AB，则无论进行怎样的指派，A、B的真值都相同，即AB为重言式。若AB为重言式，则无论进行怎样的指派，AB的真值都为T，也就是说A和B的真值相同，即AB。Formula2022/12/1851AB与AB的关系定理：设A、B为2022/12/2252重言(永真)蕴涵式Formula1.定义：如果公式AB是重言式，则称A重言(永真)蕴涵B，记作AB，读作A推出B。如(P∧(PQ))Q可记作P∧(PQ))Q注意：AB可以理解成由A可推出B，即由A为真，可以推出B也为真。2.重言(永真)蕴涵式证明方法方法１列真值表。（略）方法２假设前件为真，推出后件也为真。方法３假设后件为假，推出前件也为假。2022/12/1852重言(永真)蕴涵式Formula1.2022/12/2253例：求证

((A∧B)C)∧D∧(C∨D)A∨B证明:设前件((A∧B)C)∧D∧(C∨D)为真。则((A∧B)C)、D、(C∨D)均真，由此可得(A∧B)为T，即A∨B为T。((A∧B)C)∧D∧(C∨D)A∨BD为T，则D为FC∨D为TC为F

((A∧B)C为TA∧B为FFormula2022/12/1853例：求证由此可得(A∧B)为2022/12/2254例：求证

((A∧B)C)∧D∧(C∨D)A∨B证明:

假设后件A∨B为F,则A与B均为T。1.如C为F，则(A∧B)C为F，所以前件

((A∧B)C)∧D∧(C∨D)为F2.如C为T，则⑴若D为T，则D为F，所以前件((A∧B)C)∧D∧(C∨D)为假

⑵若D为F，则C∨D为F，所以前件((A∧B)C)∧D∧(C∨D)为假。((A∧B)C)∧D∧(C∨D)A∨BFormula2022/12/1854例：求证Formula2022/12/22553.重要的重言蕴含式(如教材第43页所示)I1.P∧QP,I2.P∧QQI3.PP∨QI4.QP∨QI5.PPQI6.QPQI7.(PQ)PI8.(PQ)QI9.P,QP∧QI10.P∧(P∨Q)QI11.P∧(PQ)QI12.Q∧(PQ)PI13.(PQ)∧(QR)PRI14.(P∨Q)∧(PR)∧(QR)RI15.AB(A∨C)(B∨C)I16.AB(A∧C)(B∧C)Formula2022/12/18553.重要的重言蕴含式(如教材第43页2022/12/2256等价式与重言蕴含式的关系Formula定理：设P、Q为两个命题公式，PQ当且仅当PQ且QP证明必要性：若PQ，则对于任何指派，P、Q都同真值，故PQ为T，QP为T，即PQ，QP

充分性：若PQ，QP，则说明PQ永真

，QP永真。所以，（PQ）∧（QP）永真，即

PQ为T，PQ为重言式，即PQ2022/12/1856等价式与重言蕴含式的关系Formul2022/12/2257蕴含的性质AB且A为重言式，则B必为重言式若AB且BC，则AC(传递性)若AB且AC，则A(B∧C)

若AB且CB，则(A∨C)B

证明见书P22Formula2022/12/1857蕴含的性质Formula2022/12/2258conjunction1－5其它连接词一、全功能真值表PQC1C2C3C4C5C6C7C8TTTFTTFFTFTFTFTFFTFTFTTFFTTFFTFFTFFFTTFTPQC9C10C11C12C13C14C15C16TTTFTFTFTFTFTFFTFTTFFTTFTFFTFTFFFTTFTFTF↓∨∧↑PQQP2022/12/1858conjunction1－5其它连2022/12/2259二、定义连接词对第8、10、12、14、16列的真值表进行定义如下：

“与非”

↑:

(P∧Q)P↑Q

“或非”

↓:

(P∨Q)P↓Q

“异或”

:

(P∧Q)∨(P∧Q)PQ

逆条件命题

:

(PQ)PQ

conjunction思考：对于任意公式A，是否可找到只包含其中一部分连接词的公式与A等价？2022/12/1859二、定义连接词conjunction2022/12/2260三、极小全功能联结词集合conjunction定义：设S是一个联结词集合，如果任意一个命题公式A都至少存在一个只包含S中联结词的公式与A等价，称S为全功能集。显然，{,∧,∨}就是一个全功能集。从S中任意去掉一个联结词后，得到一个联结词集合S1,至少有一个公式B，不等价于仅包含S1中联结词的任一公式，则称S为极小全功能联结词集合。

可以证明{,∧},{,∨},{↑},{↓}为极小全功能联结词集合2022/12/1860三、极小全功能联结词集合conjun2022/12/2261Dual1-6对偶与范式一、命题公式的对偶性及其对偶处理。限定性命题公式：最多仅含有、∧、∨逻辑联结词的命题公式。命题公式P的对偶公式（Dual）：将P中的

∨换成∧，∧换成∨，T换成F，F换成T（如果存在的话),所的公式称为P的对偶式，记为P*例如：

P与P、Q∧R与Q∨R、(P∨T)∧Q与(P∧F)∨Q分别互为对偶式2022/12/1861Dual1-6对偶与范式一、命题公2022/12/2262

定理：令A(P1,P2,…,Pn)是限定性公式，则A(P1,P2,…,Pn)A*(P1,P2,…,Pn)Dual此定理可反复地使用德-摩根定律得以证明。

验证：令A(P,Q)P∨Q，A*(P,Q)P∧Q

A(P,Q)(P∨Q)A*(P,Q)P∧Q

可见A(P,Q)A*(P,Q)

推论:A(P1,P2,…,Pn)A*(P1,P2,…,Pn)如果把A*看做A，A看做（A*）*，则定理和推论是一回事。2022/12/1862定理：令A(P1,P2,…,2022/12/2263

对偶原理设A、B是限定性命题公式,如果

AB则A*B*Dual因为A(P1,P2,…,Pn)B(P1,P2,…,Pn)故A(P1,P2,…,Pn)B(P1,P2,…,Pn)而A(P1,P2,…,Pn)A*(P1,P2,…,Pn)B(P1,P2,…,Pn)B*(P1,P2,…,Pn)故A*(P1,P2,…,Pn)B*(P1,P2,…,Pn)所以A*(P1,P2,…,Pn)B*(P1,

P2,…,

Pn)证明2022/12/1863对偶原理Dual因为A(P1,P2022/12/2264

对偶原理的验证：

P∨(Q∧R)(P∨Q)∧(P∨R)

AB

P∧(Q∨R)(P∧Q)∨(P∧R)

A*

B*

P∨TT

AB

P∧FF

A*B*Dual2022/12/1864对偶原理的验证：Dual2022/12/2265normalform二、命题公式的标准化----范式1.合取式与析取式合取式(conjunctiveform):

若干个原子命题或其否定的合取。如P、P、P∧Q、P∧Q∧R析取式(disjunctiveform):

若干个原子命题或其否定的析取。如P、P、P∨Q、P∨Q∨R2022/12/1865normalform二、命题公式的2022/12/22662.析取范式与合取范式公式A如果写成如下形式：

A1∨A2∨...∨An(n≥1)其中每个Ai(i=1,2..n)是合取式，称之为A的析取范式。公式A如果写成如下形式：

A1∧A2∧...∧An(n≥1)

其中每个Ai(i=1,2..n)是析取式，称之为A的合取范式。例如，PQ

的析取范式与合取范式：

PQ(P∧Q)∨(P∧Q)----析取范式

PQ(P∨Q)∧(P∨Q)----合取范式normalform2022/12/18662.析取范式与合取范式normal2022/12/22673.析取范式与合取范式的化法

化成限定性公式。

公式E16PQP∨Q

公式E21PQ(P∧Q)∨(P∧Q)

公式E20PQ(PQ)∧(QP)

公式E16PQ(P∨Q)∧(P∨Q)

将否定联结词移到命题变量的前面。

A(P1,P2,…,Pn)A*(P1,P2,…,Pn)(P∨Q)P∧Q、(P∧Q)P∨Q

用分配律、幂等律等公式进行整理，使之成为所要求的形式。

normalform2022/12/18673.析取范式与合取范式的化法norm2022/12/2268例如：求(PQ)R的析取范式与合取范式

(PQ)R((P∨Q)∧(P∨Q))∨R(P∧Q)∨(P∧Q)∨R------析取范式

(PQ)R((P∧Q)∨(P∧Q))∨R((P∨Q)∧(P∨Q))∨R(P∨Q∨R)∧(P∨Q∨R)---合取范式normalform2022/12/1868例如：求(PQ)R的析取范式与合2022/12/22694.主析取范式与主合取范式析取范式与合取范式的局限：标准化但不唯一；能判定永真或永假式但不方便小项定义：在一个有n个命题变元的合取式中，每个变元必出现且仅出现一次，称这个合取式是个小项。例如，有两个变元的小项：

P∧Q、P∧Q、P∧Q、P∧Qnormalform2022/12/18694.主析取范式与主合取范式norm2022/12/2270小项的性质：normalforma).有n个变元，则有2n个小项。

b).每一组指派有且只有一个小项为T。使小项为真的那一组真值指派，就是该小项的编号。上例中记m0,m1,m2,m3分别为：

m0P∧Qm1P∧Q

m2P∧Qm3P∧Q

m3m2m1m0PQP∧QP∧QP∧QP∧Q00FFFFFT01FTFFTF10TFFTFF11TTTFFF2022/12/1870小项的性质：normalform2022/12/2271主析取范式定义

析取范式A1∨A2∨...∨An,,其中每个Ai(i=1,2..n)都是小项，称之为主析取范式。思考：主析取范式与析取范式的区别是什么？主析取范式的写法

方法Ⅰ：列真值表

⑴列出给定公式的真值表。

⑵找出真值表中每个“T”对应的真值指派再对应的小项。

⑶用“∨”联结上述小项，即可。normalform2022/12/1871主析取范式定义normalform2022/12/2272例如求PQ和PQ的主析取范式PQPQPQ00FFTT01FTT

F10TFFF11TTTTPQm0∨m1∨m3

(P∧Q)∨(P∧Q)∨(P∧Q)PQm0∨m3(P∧Q)∨(P∧Q)normalform思考题:永真式的主析取范式是什么样？2022/12/1872例如求PQ和PQ的主析取范式2022/12/2273方法Ⅱ：用公式的等价变换⑴先写出给定公式的析取范式A1∨A2∨...∨An

。⑵为使每个Ai都变成小项，对缺少变元的Ai补全变元，比如缺变元R，就用∧联结永真式(R∨R)形式补R。⑶用分配律等公式加以整理。

PQP∨Q(P∧(Q∨Q))∨((P∨P)∧Q)(P∧Q)∨(P∧Q)∨(P∧Q)∨(P∧Q)(P∧Q)∨(P∧Q)∨(P∧Q)normalform2022/12/1873方法Ⅱ：用公式的等价变换normal2022/12/2274大项定义:在有n个命题变元的析取式中，每个变元必出现且仅出现一次,称之为大项。如，有两个变元的大项及其真值表：

M0

M1M2M3PQP∨QP∨QP∨QP∨Q00FFFTTT01FTTFTT10TFTTFT11TTTTTFnormalform2022/12/1874大项定义:在有n个命题变元的析取式中2022/12/2275大项的性质

a).有n个变元，则有2n个大项。

b).每一组指派有且只有一个大项为F。使大项为假的那一组真值指派，就是该大项的编号。可将各组指派对应的为F的大项分别记作M0,M1,M2,…,M2n-1

。上例中

M0P∨QM1P∨Q

M2

P∨QM3P∨Qnormalform2022/12/1875大项的性质可将各组指派对应的为F的大2022/12/2276主合取范式定义

合取范式A1∧A2∧...∧An,,其中每个Ai(i=1,2..n)都是大项，称之为主合取范式。主合取范式的写法

方法Ⅰ：列真值表⑴列出给定公式的真值表。⑵找出真值表中每个“F”对应的真值指派再对应的大项。⑶用“∧”联结上述大项，即可。normalform2022/12/1876主合取范式定义normalform2022/12/2277例如：求PQ和PQ的主合取范式normalformPQPQPQFFTTFTTFTFFFTTTTPQM2P∨QPQM1∧M2(P∨Q

)∧(P∨Q)2022/12/1877例如：求PQ和PQ的主合取范式2022/12/2278课堂练习：1.已知A(P,Q,R)的真值表如图：求它的主析取和主合取范式。解：小项是m0,m3,m4,m6,m7大项则是M1,M2,M5。2.已知A(P,Q,R)的主析取范式中含有下面小项m1,m3,m5,m7求它的主析取范式和主合取范式。PQRA(P,Q,R)FFFTFFTFFTFFFTTTTFFTTFTFTTFTTTTTQuestion2022/12/1878课堂练习：PQRA(P,2022/12/2279方法Ⅱ：用公式的等价变换⑴先写出给定公式的合取范式

A1∧A2∧...∧An

。⑵为使每个Ai变成大项，对缺少变元的析取式Ai补全变元，比如缺变元R，就用∨联结永假式(R∧R)形式补R。⑶用分配律等公式加以整理。normalform2022/12/1879方法Ⅱ：用公式的等价变换normal2022/12/2280例如：求(PQ)R的主合取范式

(PQ)R(P∨Q)∨R(P∧Q)∨R(P∨R)∧(Q∨R)(P∨(Q∧Q)∨R)∧((P∧P)∨Q∨R)(P∨Q∨R)∧(P∨Q∨R)∧

(P∨Q∨R)∧(P∨Q∨R)normalform2022/12/1880例如：求(PQ)R的主合取范式n2022/12/2281三.范式的应用normalform例1.加法器的设计，有两个n位二进制数a,b相加和为s(s=a+b)，a,b分别写成：

a=anan-1…

ai...a2a1,+b=bnbn-1…

bi...b2b1S=cnSnSn-1…

Si…S2S1其中si是第i位ai、bi及ci-1(ci-1是第i-1位向第i位的进位)的和，显然si是aibi及ci-1的函数,

写成si(ai,bi,ci-1),它与ai,bi,ci-1的关系如下表：2022/12/1881三.范式的应用normalform2022/12/2282ai

bici-1si(ai,bi,ci-1)00001111001100110101010101101001normalform2022/12/1882aibici-1si(ai,bi2022/12/2283在电路逻辑设计中用如下逻辑部件：非门与门或门根据前边的表,列出si(ai,bi,ci-1)的主析取范式：si(ai,bi,ci-1)=(ai∧bi∧ci-1)∨(ai∧bi∧ci-1)∨(ai∧bi∧ci-1)∨(ai∧bi∧ci-1)(在指派001、010、100、111时si为1)下面设计出si(ai,bi,ci-1)的线路图。aba∧baba∨baanormalform2022/12/1883在电路逻辑设计中用如下逻辑部件：aa2022/12/2284si(ai,bi,ci-1)aiaibibici-1ci-1normalformsi(ai,bi,ci-1)=(ai∧bi∧ci-1)∨(ai∧bi∧ci-1)∨(ai∧bi∧ci-1)∨(ai∧bi∧ci-1)2022/12/1884si(ai,bi,ci-1)aia2022/12/2285例2.

安排课表，教语言课的教师希望将课程安排在第一或第三节；教数学课的教师希望将课程安排在第二或第三节；教原理课的教师希望将课程安排在第一或第二节。如何安排课表，使得三位教师都满意。令L1、L2、L3分别表示语言课排在第一、第二、第三节。

M1、M2、M3分别表示数学课排在第一、第二、第三节。

P1、P2、P3分别表示原理课排在第一、第二、第三节。normalform2022/12/1885例2.安排课表，教语言课的教师希望2022/12/2286

三位教师都满意的条件是：(L1∨L3)∧(M2∨M3)∧(P1∨P2)为真。将上式写成析取范式(用分配律)得：((L1∧M2)∨(L1∧M3)∨(L3∧M2)∨(L3∧M3))∧(P1∨P2)(L1∧M2∧P1)∨(L1∧M3∧P1)∨(L3∧M2∧P1)∨(L3∧M3∧P1)∨(L1∧M2∧P2)∨(L1∧M3∧P2)∨(L3∧M2∧P2)∨(L3∧M3∧P2)

可以取(L3∧M2∧P1)、(L1∧M3∧P2)为T，得到两种排法。normalform2022/12/1886三位教师都满意的条件是：no2022/12/2287Reasoning1-7.命题逻辑推理推理推理的过程就是证明永真蕴含式的过程令H1，H2，…，Hn是已知的命题公式(前提)，若有H1∧H2∧....∧Hn

C，则称C是H1，H2，…Hn的有效结论，简称结论。前提集推理规则结论有效结论有效论证2022/12/1887Reasoning1-7.命题逻辑2022/12/2288论证步骤：Reasoning判别有效结论的常用方法真值表法依据AB的概念和定理直接证法间接证法利用P、TCP规则、反证法自然语言描述结论有效？结论成立结论不成立符号化前提结论有效无效2022/12/1888论证步骤：Reasoning判别有效2022/12/2289例1：甲乙两队进行乒乓球比赛，小张上场则小李上场，小李上场则甲队取胜，小张或小李上场了，所以甲队取胜。Reasoning解：(1)命题符号化令P:小张上场；Q:小李上场；R:甲队取胜本例符号化为:(P→Q)∧(Q→R)

∧(P∨Q)R

(2)列真值表（见后页）真值表法2022/12/1889例1：甲乙两队进行乒乓球比赛，小张上2022/12/2290PQRP→QQ→RP∨QFFFTTFFFTTTFFTFTFTFTTTTTTFFFTTTFTFTTTTFTFTTTTTTTReasoning（3）分析结论有效性：由第四行、第八行可知，当前件为真时，结论为真，所以蕴含式成立，结论有效。2022/12/1890PQRP→QQ→RP∨QFFFTTF2022/12/2291规则P(引入前提规则)：在推理过程中，可以随时引入前提。规则T(引入结论规则)：在推理过程中，如果前边有一个或几个公式永真蕴涵公式S，则可将S纳入推理过程中。在推理过程中，还要应用教材43页表1-8.3中的永真蕴涵式I1-I16和表1-8.4中等价公式E1-E22(常用的公式要熟记)推理规则Reasoning2022/12/1891规则P(引入前提规则)：在推理过程中2022/12/22921.直接推理规则P(引入前提规则)：在推理过程中，可以随时引入前提。规则T(引入结论规则)：在推理过程中，如果前边有一个或几个公式永真蕴涵公式S，则可将S纳入推理过程中。Reasoning直接证法推理规则推理过程中，要应用教材43页表1-8.3中的永真蕴涵式I1-I16和表1-8.4中等价公式E1-E22下面请看一些例子。2022/12/18921.直接推理Reasoning直接证2022/12/2293例题2求证P→Q，Q→R，PR证明:

序号前提或结论所用规则从哪几步得到所用公式

(1)PP(2)PQP(3)QT(1)(2)I11

(4)Q→RP(5)RT(3)(4)