离散数学第2版（上篇共上中下3篇）

第1章命题逻辑

Propositional

Logic

(LS)1命题2九个逻辑联结词3命题公式4命题逻辑的等价关系(16个基本等价式)5命题公式的标准化（主范式）6命题逻辑的蕴含关系(9个基本蕴含式)7命题逻辑的推理理论(13个推理规则)数理逻辑

Mathematical(akaSymbolic)Logic也称数学逻辑、符号逻辑用数学方法来从量的侧面来研究推理的规律引入一套符号体系的方法研究符号化、形式化的逻辑演绎规律的数学分支现代数理逻辑的分支[最基本]逻辑演算(命题演算&谓词演算)模型论证明论递归函数论公理化集合论2数理逻辑简史古典／形式逻辑(2000多年的历史)从亚里士多德(公元前384～322)的三段论算起所有人都是要死的,苏格拉底是人,因此,苏格拉底是要死的。分析语言所表达的逻辑维形式但语言中常有含糊不清不易判别的语句引起歧义,甚至争论。命题符号化：数理逻辑最早的萌芽17世纪德国哲学家、数学家G.W.莱布尼兹用数学符号式的“通用语言”来进行思维演算,使人们能够证明思维的正确性,从而避免争论布尔代数19世纪初英国数学家G.布尔一种思维的代数,初步实现了莱布尼兹的部分设想3数理逻辑简史命题演算／命题逻辑(第1章)布尔代数发展为具有逻辑蕴含式的命题演算最简单的公理化的逻辑系统谓词符号化布尔同时代的英国数学家A.德·摩根使数学中的“关系”,“函数”都可以在逻辑命题中出现,加强了逻辑的表现力。谓词演算G.弗雷格等数学家公理化的谓词演算是数理逻辑的基础。4数理逻辑中的语言

5学历类考试MBA(MPA)

【题目】并非小张既高又胖。如果上述断定是真的,那么,下述哪项断定必定是真的?A．小张高但不胖B．小张胖但不高C．小张既不高也不胖D．如果小张高,那么他一定不胖E．如果小张不高,他一定胖6公务员考试行测【题目】某珠宝店失窃,甲、乙、丙、丁四人涉嫌被拘审。四人的口供如下：

甲：案犯是丙。

乙：丁是罪犯。

丙：如果我作案,那么丁是主犯。

丁：作案的不是我。

四个口供中只有一个是假的。如果此断定为真,那么以下哪项是真的？

A．说假话的是甲,作案的是乙。

B．说假话的是丁,作案的是丙和丁。

C．说假话的是乙,作案的是丙。

D．说假话的是丙,作案的是丙。

E．说假话的是甲,作案的是甲。7命题逻辑/命题演算

PropositionalCalculus研究对象命题研究目的推理过程中前提和结论间的形式关系本章介绍命题逻辑的基本知识基本思想方法8学习要点理解并掌握命题、联接词、公式的真值表、公式的赋值、命题公式的类型。熟练运算等价演算、重要等价式、主析取范式、主合取范式。推理证明命题逻辑推理正确性的判断、使用直接证明法、附加前提证明法和归谬法。910§1-1-1命题&真值

Proposition

&

Truth

Value

【命题】能够判明真假的陈述句（Declarative

Sentence）。在命题逻辑中,对命题的成分不再细分,因而命题就成了命题逻辑中最基本也是最小的研究单位。【真值】命题的判断结果。真值只有“真”和“假”两种真值为真时用“T”(或“1”)

表示真值为假时用“F”(或“0”)

表示任何命题的真值都是唯一的。真值为真的命题称为真命题,真命题表达的判断正确。真值为假的命题称为假命题,假命题表达的判断错误。命题1-111【示例】判断以下语句是否为命题,若是命题请给出命题的真值。(1)多美丽的景色呀！(2)你喜欢大学生活吗？(3)请不要在室内吸烟!(4)3+2=5(5)3+2=1(6)x+2=5(7)郑州是河北的省会。(8)中国承办二零零八年奥运会。(9)地球外的星球上也有人类。(10)我在说谎。(11)现在几点了？(12)仔细读书！12§1-1-2原子命题&复合命题【原子命题／简单命题】简单得不能再分解的陈述句。反映了对单一事物的真假判定通常用(带下标的)大写字母或数字表示A、B、C、…P、Q、R、…P：郑州是河北的省会。A1、B2、C3、…P𝑖、Q𝑗、R𝑘、…R1:北京是中国的首都。[12]命题1-113复合命题

Compound

Proposition【定义】原子命题通过逻辑联结词（Logical

Connectives）组合成的新命题。(英国数学家George

Boole)郑州不是河北的省会。郑州不是河北的省会并且北京是中国的首都。明天有雨或有雪。【思考】逻辑联结词如何选取和表示？命题1-114§1-2-1否定联结词

Negation

逻辑联结词1-215§1-2-1否定联结词

采用表格形式可以更直观清晰分析命题P与其否定命题

P的逻辑关系,如下图所示。逻辑联结词1-216P

P1001【示例】马克的PC没运行Linux。解：令P：马克的PC运行的是Linux。则该命题可表示为

P。§1-2-2合取联结词

Conjunction【定义】设P,Q为两个命题,P与Q的合取式,记作P∧Q。复合命题“P并且Q”∧称作合取联结词【规定】P∧Q的真值为真当且仅当P与Q的真值同时为真,否则P∧Q的真值为假。其逻辑关系如下表所示。逻辑联结词1-217PQP∧Q111100010000【示例1】小王能歌善舞。解：令P：小王会唱歌。Q：小王会跳舞。则该命题可表示为P∧Q。通常在自然语言中“并且”、“不但…而且...”、“既…又...”、“又…还…”等均可由合取联结词表示。

【示例2】小王和小张是好朋友。解：该命题可表示为P。【示例3】雪是白色的并且小王会唱歌。(自然语言v.s.数理逻辑)解：令P：雪是白色的。Q：小王会唱歌。则该命题可表示为P∧Q。18命题符号化之练习悟空既用功又聪明。悟空不仅用功而且聪明。悟空虽然聪明,但不用功。悟空与八戒都是三好生。张辉与王丽是同学。解：首先将原子命题符号化：P:悟空用功。Q:悟空聪明。R:悟空是三好学生。S:八戒是三好学生。T:张辉与王丽是同学。(1)到(4)都是复合命题,它们使用的联接词表面看来各不相同,但都是合取联接词,都应符号化为∧。(1)到(4)分别符号化为P∧Q,P∧Q,Q∧¬P

,R∧S。在(5)中,虽然也使用了联接词“与”,但这个联接词是联接该句主语的,而整个句子仍是简单陈述句,所以(5)是原子命题,符号化为T。19§1-2-3析取联结词

Disjunction【定义】设P,Q为两个命题,P与Q的析取式,记作P∨Q。复合命题“P或者Q”∨称作析取联结词【规定】P∨Q的真值为假当且仅当P与Q的真值同时为假,否则P∨Q的真值为真。其逻辑关系如下表所示。逻辑联结词1-220PQP∨Q111101011000【示例1】今天刮风或者下雨。解:令P：今天刮风。Q：今天下雨。则该命题可表示为P∨Q。题中的“或者”是可兼取或(相容或),即析取“∨”。【示例2】第一节课上数学或者上英语。解:

此例中的“或者”是不可兼取或(异或、排斥或),即不可兼析取“⊽”,其表达的含义是“第一节课上数学而没有上英语或者第一节课上英语而没有上数学”。令P：第一节课上数学。Q：第一节课上英语。则该命题可表示为P⊽Q=(

Q∧P)∨(

P∧Q)。21命题符号化之练习张小静爱唱歌或爱听音乐。解先将原子命题符号化。P：张小静爱唱歌。Q：张小静爱听音乐。显然(1)中“或”为相容或,即P与Q可以同时为真,符号化为P˅Q张小静只能挑选202或203房间。解先将原子命题符号化。T：张小静挑选202房间。U：张小静挑选203房间。由题意可知,(2)中“或”应为排斥或。符号化为(T˄

U)˅(

T˄U)。22§1-2-4蕴含联结词

Implication/Conditional

Statement【定义】设P,Q为两个命题,P与Q的蕴含式,记作P→Q。复合命题“如果P那么Q”(或“若P则Q”)→(或⊃)

称作蕴含联结词(也称为“单条件联结词”)P是P→Q的前件（Antecedent）,Q是P→Q的后件（Consequence）P是Q的充分条件,Q是P的必要条件逆命题（Converse）：Q→P否命题（Inverse）：

P→

Q逆否命题（Contrapositive）：

Q→

P【规定】P→Q的真值为假当且仅当P的真值为真同时Q的真值为假,否则P→Q的真值为真。逻辑联结词1-223PQP→Q111100011001使用联接词→时,特别注意以下几点：在自然语言里,特别是在数学中,Q是P的必要条件有许多不同的叙述方式,都应符号化为P→Q。只要P,就Q ifP,thenQ因为P,所以Q P仅当Q PonlyifQ只有Q才P 除非Q才P除非Q,否则非P QunlessP……在自然语言中,“如果P,则Q”中的前件P与后件Q往往具有某种因果联系,而在数理逻辑中,P与Q可以无任何内在联系。在数学或其他自然科学中,“如果P,则Q”往往表达的是前件P为真,后件Q也为真的推理关系。但在数理逻辑中,当P为假时,规定为“善意的推定”，即无论Q是真是假,P→Q均为真。只有P为真Q为假这一种情况,使得复合命题P→Q为假。24【示例1】如果天气持续干旱,植物就会死亡。解:

令P：天气持续干旱。Q：植物会死亡。则该命题可表示为P→Q。【示例2】如果雪是白色的,那么房间里有两盆兰花。解:令P：雪是白色的。Q：房间里有两盆兰花。则该命题可表示为P→Q。25命题符号化之练习如果3+3=6,则雪是白色的。如果3+3≠6,则雪是白色的。如果3+3=6,则雪不是白色的。如果3+3≠6,则雪不是白色的。解令P：3+3=6,P的真值为1.Q：雪是白色的,Q的真值也为1.(1)到(4)的符号化形式分别为P→Q,

P→Q,P→

Q,

P→

Q,这四个复合命题的真值分别为1,1,0,1.26命题符号化之练习以下命题中出现的a是给定的一个正整数：只要a能被4整除,则a一定能被2整除。a能被4整除,仅当a能被2整除。除非a能被2整除,a才能被4整除。除非a能被2整除,否则a不能被4整除。只有a能被2整除,a才能被4整除。只有a能被4整除,a才能被2整除。27解令R：a能被4整除。S：a能被2整除。仔细分析可知,(1)到(5)五个命题均叙述的是a能被2整除是a能被4整除的必要条件,只是在叙述上有所不同,因而都符号化为R→S。而在(6)中,将a能被4整除看成了a能被2整除的必要条件,因而符号化为S→R.总结如果P那么Q：P→Q若P则Q：P→Q因为P所以Q：P→Q只要P就Q：P→QP仅当Q：P→Q只有P才Q：Q→P除非P否则Q：

P→Q或

Q→P28§1-2-5等价联结词

Biconditional／Bi-implication【定义】设P,Q为两个命题,P与Q的等价式,记作P↔Q。复合命题“P当且仅当Q”（P

𝑖𝑓𝑓

Q）↔(或⇆)称作等价联结词(也称为“双条件联结词”)【规定】P↔Q的真值为真当且仅当P与Q的真值相同,否则P↔Q的真值为假。逻辑联结词1-229PQP↔Q111100010001【示例】四边形是平行四边形当且仅当它的对边平行。解:

令P：四边形是平行四边形Q：四边形的对边平行则该命题可表示为P↔Q。30命题符号化之练习31练习答案32逻辑联结词的优先级

Precedence¬最优¬P∧Q(¬P)∧Q∧优于∨P∨Q∧R

P∨(Q∧R)⟶优于⟷P⟷Q⟶R

P⟷(Q⟶R)33§1-3-2命题符号化用符号串来形式化表示命题。命题符号化的步骤：①首先要明确给定命题的含义。②对于复合命题,明确逻辑联结词,用联结词断句,分解出各个原子命题。③设原子命题符号,并用逻辑联结词联结原子命题符号,构成给定命题的符号表达式。命题公式1-334【示例】将下列命题符号化。(1)张辉和王丽都是三好学生。解：令P：张辉是三好学生。Q：王丽是三好学生。则该命题可表示为P∧Q。(2)张辉和王丽是同学。解：令P：张辉和王丽是同学。则该命题可表示为P。(3)张辉或王丽都可以做好这件事情。解：令P：张辉可以做好这件事情。Q：王丽可以做好这件事情。则该命题可表示为P∧Q。(4)校学生会主席是张辉或王丽。解：令P：校学生会主席是张辉。Q：校学生会主席是王丽。则该命题可表示为(P∧Q)∨(

P∧Q)(5)因为雪是白色的,所以2+2=4；解：令P：雪是白色的。Q：2+2=4。则该命题可表示为P→Q(6)如果雪是白色的,那么2+2=4；解：令P：雪是白色的。Q：2+2=4。则该命题可表示为P→Q35(7)只有雪是白色的,才有2+2=4；解：令P：雪是白色的。Q：2+2=4。则该命题可表示为Q→P(8)只要雪不是白色的,就有2+2=4；解：令P：雪是白色的。Q：2+2=4。则该命题可表示为

P→Q(9)除非雪是白色的,否则2+2≠4；解：令P：雪是白色的。Q：2+2=4。则该命题可表示为

P→

Q或Q→P(10)雪是白色的当且仅当2+2=4；解：令P：雪是白色的。Q：2+2=4。则该命题可表示为P↔Q(11)若天不下雨,我就上街；否则在家。解：令P：天下雨。Q：我上街。R：我在家。则该命题可表示为(

P→Q)∧(P→R)。(12)仅当天不下雨且我有时间,才上街。解：令P：天下雨。Q：我有时间。R：我上街。则该命题可表示为R→(

P∧Q)

36思

考

37§1-3-1命题公式的概念

命题公式1-338§1-3-1命题公式的概念【命题公式的伪定义】含有命题变元的断言,即将命题变项用联接词和圆括号按一定的逻辑关系联接起来的符号串此种定义不合适,无法确定命题公式的结构由命题变元、联结词和括号所组成字符串未必都是命题公式，例如：(1)

(𝑝→𝑞)∧

𝑞)(2)

(

𝑝∨𝑞∨(r(3)𝑝→→

𝑞(4)

𝑝𝑞→r命题公式1-339合式公式的递归式定义【原子(命题)公式】单个命题变元(常量)。原子公式不一定是原子变元(常量)【合式公式(Well-FormedFormula,WFF)】简称公式，即由下列规则递归式定义产生的公式：①单个原子公式是合式公式。②若A是一个合式公式,则(

A)也是一个合式公式。③若A、B是合式公式,则(A∧B)、(A∨B)、(A→B)和(A↔B)都是合式公式。④只有有限次使用①、②和③生成的公式才是合式公式。【合式公式的长度】合式公式中的命题标识符、联结词和左右括号的数目。命题公式1-340【示例】说明(𝑞→(𝑞∨r))是合式公式解：(1)

𝑞是合式公式

根据规则①(2)r是合式公式

根据规则①(3)

(𝑞∨r)是合式公式

根据①、②和规则③(4)

(𝑞→(𝑞∨r))是合式公式根据①、③和规则③41关于括号的约定当合式公式比较复杂时,常常使用很多圆括号,为了减少圆括号的使用量,可作以下约定：①规定联结词的优先级由高到低的次序为：

、∧、∨、→、↔

②相同的联结词按从左至右次序计算时,圆括号可省略。③最外层的圆括号可以省略。【示例】(

((𝑝∧𝑞)∨(

r))→((𝑝∨𝑞)∨r))可写成：

(𝑝∧𝑞∨

r)→𝑝∨𝑞∨r有时为了看起来清楚醒目,也常常保留某些原可省去的圆括号。命题公式1-342§1-3-2命题公式的指派

Assignment

命题公式1-343§1-3-3命题公式真值表对于公式中命题变元的每一种可能的真值指派,以及由它们确定出的公式真值所列成的表。命题公式1-344构造真值表的步骤

命题公式1-345【练习】求下列公式的真值表,并求它们的成真赋值和成假赋值。(1)A

=(𝑝∨𝑞)→

𝑟(2)B

=

(𝑞→𝑝)∧𝑞→𝑝(3)C

=

(

𝑝∨𝑞)∧𝑞(4)(

𝑝∧𝑞)→

𝑟(5)(𝑝∧𝑝)↔(𝑞∧𝑞)(6)

(𝑝→𝑝)∧𝑞∧𝑟46§1-3-4命题公式的类型【定义】设A为任一命题公式若A在它的任何赋值下均为真,则称A为重言式或永真式(Tautology);(𝑞→𝑝)∧𝑞→𝑝若A在它的任何赋值下均为假,则称A为矛盾式或永假式(Contradiction);

(

𝑝∨𝑞)∧𝑞若A不是矛盾式,则称A是可满足式(Satisfiable

Compound

Proposition).命题公式1-347可满足式至少存在一个成真赋值重言式是可满足式,但反之不成立若A是非重言式的可满足式，则A至少存在一个成假赋值A

=

(𝑝∨𝑞)

→

𝑟可满足性的应用（课后拓展阅读）数独（离散数学及其应用,P32）48真值表的用途求出公式的全部成真赋值与成假赋值,判断公式的类型若真值表最后一列全为1,则公式为重言式。若真值表最后一列全为0,则公式为矛盾式。若真值表最后一列中至少有一个1,则公式为可满足式。49【示例】确定以下复合命题是否为可满足的。

(𝑝∨𝑞)∧(𝑞∨𝑟)∧(𝑟∨𝑝)当命题变元𝑝、𝑞和𝑟有相同真值时,复合命题为真。

(𝑝∨𝑞∨𝑟)∧(

𝑝∨𝑞∨𝑟)当命题变元𝑝、𝑞和𝑟中至少有一个为真且至少有一个为假时,复合命题为真。(𝑝∨𝑞)∧(𝑞∨𝑟)∧(𝑟∨𝑝)∧(𝑝∨𝑞∨𝑟)∧(

𝑝∨𝑞∨𝑟)此复合命题为真,则①和②同时为真。①为真,三个命题变元有相同真值；②为真,三个变元中至少有一个为真,且至少有一个为假。故矛盾。50公式类型之练习𝑝∨𝑝𝑝∧𝑝𝑝→

(

𝑝)

(𝑝∧𝑞)↔(

𝑝∨𝑞)

(𝑝∨𝑞)↔(

𝑝∧𝑞)

(𝑝→𝑞)↔(

𝑞→

𝑝)

(𝑝→𝑞)∧(𝑞→𝑝)𝑝∧(𝑞∨𝑟)→(𝑝∧𝑞∨𝑝∧𝑟)𝑝∧𝑝→𝑞𝑝∨𝑞→𝑞51重言式矛盾式非重言式的可满足式§1-3-5重言式的性质如果A是重言式,则新公式

A是重言式。如果A,B是重言式,则新公式(A∧B)、(A∨B)、(A→B)和(A↔B)也都是重言式。【代入规则】如果A是重言式,则用任一公式替代A中某个命题变元𝑝的所有出现,得到的新公式B也是重言式。证明：因为重言式对任意指派,其值都是真,与所给的某个命题变元𝑝指派的真值是真还是假无关,因此,用任一公式处处替代A中命题变元𝑝后依旧是永真的。命题公式1-352【示例】求证：(𝑝→𝑞)∨

(𝑝→𝑞)为重言式。证明：由公式𝑟∨

𝑟的真值表可知其为重言式。用公式(𝑝→𝑞)

替代命题变元𝑟所有出现的地方,则得(𝑝→𝑞)∨

(𝑝→𝑞),根据代入规则可知,给定公式是重言式。【注意】若公式(𝑝→𝑞)只替代一个命题变元𝑟,得到(𝑝→𝑞)∨

𝑟,显然它不是重言式,因为这不符合代入规则所要求的处处代入。53重言式的代入规则

用途&不足有助于寻找新的重言式但是其使用前提是必须清楚哪些是已知的重言式,而有很多的公式形式上比较复杂,很难一目了然利用重言式的性质直接来判定例如：公式(𝑝→(𝑞→𝑟))↔(𝑝∧𝑞→𝑟)等价关系提供更加便捷的方法来判定公式命题公式的等价关系1-454§1-4-1等价关系

LogicalEquivalences【定义】A、B是含有命题变元𝑝1、𝑝2、…、𝑝n的命题公式,如果A与B等价,记作A

B或A≡B,并称A

B是等价式,则须满足以下条件：无论对𝑝1、𝑝2、…、𝑝n作任何指派,都使得A和B的真值相同公式A↔B是重言式命题公式间的等价关系1-455【示例】判断下面两个公式是否等价：𝑝→𝑞和

𝑝∨𝑞。解：用真值表法判断𝑝→𝑞↔

𝑝∨𝑞是否为重言式。从真值表可以看出,公式(𝑝→𝑞)↔(

𝑝∨𝑞)永真。根据定义表明:𝑝→𝑞

𝑝∨𝑞。56【注意】↔

v.𝑠.

↔：逻辑联结词,属于目标语言中的符号,出现在命题公式中

：不是逻辑联结词,属于元语言中的符号,表示两个命题公式的一种关系,不属于这两个公式的任何一个公式中的符号。𝑝𝑞𝑝→𝑞

𝑝∨𝑞(𝑝→𝑞)

↔

(

𝑝∨𝑞)00TTT01TTT10FFT11TTT判断𝑝→(𝑞→𝑟)

与

(𝑝∧𝑞)→𝑟是否等价？57111111011111110111011101000001010011100101110111(𝑝∧𝑞)→𝑟𝑝→(𝑞→𝑟)𝑞→𝑟

𝑝𝑞𝑟𝑝∧𝑞00000011结论:𝑝→(𝑞→𝑟)

(𝑝∧𝑞)→𝑟

判断𝑝→(𝑞→𝑟)

与(𝑝→𝑞)→𝑟是否等价？58结论:

𝑝→(𝑞→𝑟)

与(𝑝→𝑞)→𝑟

不等价010111011111110111011101000001010011100101110111(𝑝→𝑞)→𝑟𝑝→(𝑞→𝑟)𝑞→𝑟

𝑝𝑞𝑟𝑝→𝑞11110011§1-4-2

基本等价式用真值表法可以判断任何两个命题公式是否等价,但当命题变项较多时,工作量是很大的。【基本等价式或命题定律】已验证的一组基本且重要的等价式,以此为基础进行公式演算,来判断公式之间是否等价。牢记并能熟练运用基本等价式,是学好数理逻辑的关键之一。命题公式间的等价关系1-459§1-4-2

基本等价式若A和B是任意命题公式,则下列等价关系成立：双重否定律

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命题公式的等价关系1-460DeMorganlawsDistributivelawsCommutativelawsAssociativelawsDoubleNegationlawsIdempotentlaws§1-4-2

基本等价式吸收律

A∨(A∧B)

A A∧(A∨B)

A零律 A∨1

1 A∧0

0同一律 A∨0

A A∧1

A排中律 A∨

A

1 矛盾律

A∧

A

0蕴含等价式

A→B

A∨B 等值等价式 A↔B

(A→B)∧(B→A)假言易位

A→B

B→

A等价否定等值式

A↔B

A↔

B归谬论

(A→B)∧(A→

B)

A命题公式的等价关系1-461AbsorptionlawsNegationlaws思考：对偶观察以上等价式,会发现多数等价式是成对出现的,这种有趣的现象就是对偶性质的反映。【定义】在给定的仅使用联结词

、∧和∨的命题公式A中,若把∧和∨互换,F和T互换而得到一个命题公式A*,则称A*为A的对偶式。【对偶定理】若A和B为两个命题公式,并且A

B,则有A*

B*。利用对偶定理可以扩大等价式的个数,也可减少证明的次数。请你尝试去发现以及证明对偶的相关性质。62§1-4-3置换规则【置换规则】A1是合式公式A的子公式,若A1

B1,将A中的A1用B1替换得到新公式B,则A

B。证明：因为A1

B1,即对于它们的命题变元做任何真值的指派,A1与B1的真值相同,故以B1替换A1后,公式B与A在对其命题变元做相应的任何真值指派,它们的真值亦相同,因此,A

B成立。有了置换规则,就可以用等值演算判断公式的类型。命题公式的等价关系1-463注意区别代入规则V.S.置换规则使用前提代入规则必须面向重言式置换规则面向任意公式被替代的对象代入规则必须是命题变元置换规则可以是命题公式替代对象代入规则的是任意公式置换规则必须是等价式操作范围代入规则必须是处处代入置换规则可部分替换,亦可处处替换64【示例】用等值演算判断公式(𝑝→𝑞)∧𝑝→𝑞的类型。解：(𝑝→𝑞)∧𝑝→𝑞

(

𝑝∨𝑞)∧𝑝→𝑞

(蕴含等价式)

((

𝑝∨𝑞)∧𝑝)∨𝑞

(蕴含等价式)

(

(

𝑝∨𝑞)∨

𝑝)∨𝑞

(德摩根律)

((𝑝∧

𝑞)∨

𝑝)∨𝑞

(德摩根律)

((𝑝∨

𝑝)∧(

𝑞∨

𝑝))∨𝑞

(分配律)

(1∧(

𝑞∨

𝑝))∨𝑞

(排中律)

(

𝑞∨

𝑝)∨𝑞

(同一律)

(

𝑞∨𝑞)∨

𝑝 (交换律,结合律)

1∨

𝑝 (排中律)

1 (零律)

因此(𝑝→𝑞)∧𝑝→𝑞是重言式。65【示例】用等值演算判断公式

(𝑝→(𝑝∨𝑞))∧𝑟的类型。解：

(𝑝→(𝑝∨𝑞))∧𝑟

(

𝑝∨𝑝∨𝑞)∧𝑟

(蕴含等价式,结合律)

(𝑝∧

𝑝∧

𝑞)∧𝑟

(德摩根律)

(0∧

𝑞)∧𝑟

(矛盾律)

0∧𝑟 (零律)0 (零律)因此

(𝑝→(𝑝∨𝑞))∧𝑟是矛盾式。66【示例】用等值演算判断公式𝑝∧(((𝑝∨𝑞)∧

𝑝)→𝑞)的类型。解：𝑝∧(((𝑝∨𝑞)∧

𝑝)→𝑞)

𝑝∧(

((𝑝∨𝑞)∧

𝑝)∨𝑞)

(蕴含等价式)

𝑝∧(

((𝑝∧

𝑝)∨(𝑞∧

𝑝))∨𝑞)

(分配律)

𝑝∧(

(0∨(𝑞∧

𝑝))∨𝑞)

(矛盾律)

𝑝∧(

(𝑞∧

𝑝)

∨𝑞)

(同一律)

𝑝∧((

𝑞∨𝑝)∨𝑞)

(德摩根律,双重否定律)

𝑝∧((

𝑞∨𝑞)∨𝑝)

(交换律,结合律)

𝑝∧(1∨𝑝)

(排中律)

𝑝∧1 (零律)

𝑝 (同一律)因为00,01是成假赋值；10,11是成真赋值,因此公式是可满足式。67等价式之练习求出下列公式的最简等价式：

((𝑝→𝑞)↔(

𝑞→

𝑝))∧r𝑝∨𝑝∨(𝑞∧𝑞)

(𝑝∧(𝑞∧s))∨(

𝑝∧(𝑞∧s))解：

((𝑝→𝑞)↔(

𝑞→

𝑝))∧r

r

𝑝∨𝑝∨(𝑞∧𝑞)

T

(𝑝∧(𝑞∧s))∨(

𝑝∧(𝑞∧s))

𝑞∧s68【示例】用等值演算,化简下列电路。69解：上述电路图可描述为：((𝑝∧𝑞∧r)∨(𝑝∧𝑞∧s))∧((𝑝∧r)∨(𝑝∧s))

((𝑝∧𝑞∧(r∨s))∧(𝑝∧(r∨s))

𝑝∧𝑞∧(r∨s)化简后的电路如下图所示。70【示例】用等值演算,将下面程序结构进行化简。执行X的条件为(A∧B)∨(

A∧B)执行Y的条件为(A∧

B)∨(

A∧

B)71§1-5-1析取范式与合取范式多样的符号形式往往表达的是同一种逻辑内涵根据置换规则,很容易发现一个命题公式经过等值演算,可以变换出若干与之逻辑等价的合式公式。【范式(NormalForm)】使形式多样的合式公式统一化归为一种规范形式的一种标准。命题公式的标准化1-572§1-5-1析取范式与合取范式【文字(Character)】命题变元或命题变元的否定。例如：𝑝,𝑞,

𝑟【简单析取式／子句(Clause)】有限个文字的析取。例如：𝑝∨𝑞,

𝑟∨𝑞。【简单合取式／短语(Phrase)】有限个文字的合取。例如：𝑞∧

𝑝,𝑞∧𝑟∧𝑝。【析取范式(DNF)】有限个短语的析取式。例如：(𝑝∧𝑞)∨(

𝑝∧𝑞)【合取范式(CNF)】有限个子句的合取式。例如：(𝑝∨𝑞)∧(

𝑝∨𝑞)∧(𝑝∨

𝑞∨

𝑟)公式𝑝∨(𝑞∨

𝑟)、

(𝑞∨𝑟)既非析取范式也非合取范式命题公式的标准化1-573§1-5-1析取范式与合取范式【范式存在定理】对于任意命题公式,都存在与其等价的析取范式和合取范式。求范式的方法如下：(1)利用等价公式中的等值等价式和蕴含等价式将公式中的→、↔用联结词

、∧、

∨

来取代。(2)重复使用德摩根律将否定号移到各个命题变元的前端,并消去多余的否定号。(3)重复利用分配律利用∧对∨的分配律求析取范式利用∨对∧的分配律求合取范式命题公式的标准化1-574【示例1】求公式(𝑝→

𝑞)→𝑟的析取范式和合取范式。

(𝑝→

𝑞)→𝑟

(

𝑝∨

𝑞)→𝑟

(消去第一个→)

(

𝑝∨

𝑞)∨𝑟

(消去第二个→)

(𝑝∧𝑞)∨𝑟

(否定号内移-德摩根律)

-析取范式(𝑝∨𝑟)∧(𝑞∨𝑟)

(∨对∧分配律)

-合取范式【示例2】求公式(𝑝↔𝑞)→𝑟的析取范式。

(𝑝↔𝑞)→𝑟

(𝑝↔𝑞)∨𝑟

(消去→)

((

𝑝∨𝑞)∧(𝑝∨

𝑞))∨𝑟

(消去↔)

(𝑝∧

𝑞)∨(

𝑝∧𝑞)∨𝑟

(否定号内移-德摩根律)

-

析取范式【注意】为了清晰和无误,演算中利用交换律,使得每个简单析取式或合取式中命题变项的出现都是按字典顺序,这对下文中求主范式更为重要。75【示例3】求公式(𝑝→𝑞)↔𝑟的析取范式与合取范式。解（1）先求合取范式

(𝑝→𝑞)↔𝑟

(𝑝∨𝑞)↔𝑟 消去→

((𝑝∨𝑞)→𝑟)∧(𝑟→(𝑝∨𝑞)) 消去↔

((𝑝∨𝑞)∨𝑟)∧(𝑟∨𝑝∨𝑞) 消去→

((𝑝∧𝑞)∨𝑟)∧(𝑝∨𝑞∨𝑟) 否定号内移

(𝑝∨𝑟)∧(𝑞∨𝑟)∧(𝑝∨𝑞∨𝑟) 分配律（2）求析取范式：求析取范式与求合取范式的前两步是相同的,只是在利用分配律时有所不同。因而可以用（1）中前四步的结果,接着进行∧对∨分配律演算。

(𝑝→𝑞)↔𝑟

((𝑝∧𝑞)∨𝑟)∧(𝑝∨𝑞∨𝑟)

(𝑝∧𝑞∧𝑝)∨(𝑝∧𝑞∧𝑞)∨(𝑝∧𝑞∧𝑟)∨(𝑟∧𝑝)∨(𝑟∧𝑞)∨(𝑟∧𝑟)

(𝑝∧𝑞∧𝑟)∨(𝑝∧𝑟)∨(𝑞∧𝑟)

76§1-5-2

主析取范式

&

主合取范式范式不唯一性𝑝∨(𝑞∧𝑟)

(𝑝∨𝑞)∧(𝑝∨𝑟)

合取范式

(𝑝∧𝑝)∨(𝑞∧𝑟)

析取范式

𝑝∨(𝑞∧

𝑞)∨(𝑞∧𝑟)

析取范式定义范式的初衷是为多样化的公式提供一种规范化的表达式,但是上述这样的例子恰好说明了范式具有不唯一的表达形式,给研究问题带来了不便。需要进一步定义规则使得合式公式可以成为具有唯一确定形式的规范表达。命题公式的标准化1-577§1-5-2

主析取范式

&

主合取范式【定义】在含有n个命题变项的简单合取式（简单析取式）中,若每个命题变项均以文字的形式在其中出现且仅出现一次,称这样的简单合取式（简单析取式）为极小项（极大项）。【说明】𝑛个命题变项最多有2𝑛个极小项和2𝑛个极大项2𝑛个极小（大）项均互不等值用𝑚𝑖表示第𝑖个极小项,其中𝑖是该极小项成真赋值的十进制表示用M𝑖表示第𝑖个极大项,其中𝑖是该极大项成假赋值的十进制表示极小项：将𝑛个命题变元按字典序排列,并且把命题变元与1对应,命题变元的否定与0对应。极大项：将𝑛个命题变元按字典序排列,并且把命题变元与0对应,命题变元的否定与1对应。命题公式的标准化1-578【示例1】由2个命题变项𝑝和𝑞形成的极小项与极大项79极

小

项极

大

项公

式成真赋值名

称公

式成假赋值名

称

𝑝∧

𝑞00𝑚0𝑝∨𝑞00M0

𝑝∧𝑞01𝑚1𝑝∨

𝑞01M1𝑝∧

𝑞10𝑚2

𝑝∨𝑞10M2𝑝∧𝑞11𝑚3

𝑝∨

𝑞11M3【定理】设𝑚𝑖与M𝑖是命题变项𝑝1,𝑝2,…,𝑝𝑛形成的极小项和极大项,则

𝑚𝑖

M𝑖,M𝑖

𝑚𝑖。

【示例2】由3个命题变项𝑝、𝑞和𝑟形成的极小项与极大项80极

小

项极

大

项公

式成真赋值名

称公

式成假赋值名

称

𝑝∧𝑞∧𝑟000𝑚0𝑝∨𝑞∨𝑟000M0

𝑝∧𝑞∧𝑟001𝑚1𝑝∨𝑞∨𝑟001M1

𝑝∧𝑞∧𝑟010𝑚2𝑝∨𝑞∨𝑟010M2

𝑝∧𝑞∧𝑟011𝑚3𝑝∨𝑞∨𝑟011M3𝑝∧𝑞∧𝑟100𝑚4

𝑝∨𝑞∨𝑟100M4𝑝∧𝑞∧𝑟101𝑚5

𝑝∨𝑞∨𝑟101M5𝑝∧𝑞∧𝑟110𝑚6

𝑝∨𝑞∨𝑟110M6𝑝∧𝑞∧𝑟111𝑚7

𝑝∨𝑞∨𝑟111M7§1-5-2

主析取范式

&

主合取范式【主析取范式】由极小项构成的析取范式【主合取范式】由极大项构成的合取范式下面要讨论的问题是,如何求出与给定公式等价的主析取范式和主合取范式,首先讨论它的存在性和唯一性。【定理】任何命题公式都存在着与之等价的主析取范式和主合取范式,并且是唯一的。命题公式的标准化1-581主范式的求法1

公式化归法先求出公式所对应的析取范式和合取范式；在析取范式的短语和合取范式的子句中重复出现的命题变元,将其等价变换为只出现一次；去掉析取范式中的所有永假式(𝑝∧𝑝),去掉合取范式中所有永真式(𝑝∨𝑝)；用等价式补充缺少的命题变元若析取范式的某一个短语中缺少该命题公式中所规定的命题变元𝑝,则可用公式：(𝑝∨𝑝)∧𝑞⇔𝑞将命题变元𝑝补进去,并利用分配律展开,然后合并相同的短语,此时得到的短语将是标准的极小项。若合取范式的某一个子句中缺少该命题公式中所规定的命题变元𝑝,则可用公式：(𝑝∧𝑝)∨𝑞⇔𝑞将命题变元𝑝补进去,并利用分配律展开,然后合并相同的子句,此时得到的子句将是标准的极大项；利用等幂律将相同的极小项和极大项合并,同时利用交换律进行顺序调整,极小项(极大项)按下标从小到大排列,由此可转换成标准的主析取范式和主合取范式。命题公式的标准化1-582【示例1】求公式A=(𝑝→

𝑞)→𝑟的主析取范式。解：(𝑝→

𝑞)→𝑟

(𝑝∧𝑞)∨𝑟

(析取范式)

(𝑝∧𝑞)∧(

𝑟∨𝑟)∨(

𝑝∨𝑝)∧(

𝑞∨𝑞)∧𝑟

(添加缺少的变元)

(𝑝∧𝑞∧

𝑟)∨(𝑝∧𝑞∧𝑟)∨(

𝑝∧

𝑞∧𝑟)∨(

𝑝∧𝑞∧𝑟)∨(𝑝∧

𝑞∧𝑟)∨(𝑝∧𝑞∧𝑟)

(分配律展开)

𝑚1∨

𝑚3∨

𝑚5∨

𝑚6∨

𝑚7

(合并相同的极小项并排序)

∑1,3,5,6,7 (简化表达)【示例2】求公式A=(𝑝→

𝑞)→𝑟的主合取范式。解：(𝑝→

𝑞)→𝑟

(𝑝∨𝑟)∧(𝑞∨𝑟)

(合取范式)

(𝑝∨(𝑞∧

𝑞)∨𝑟)∧((𝑝∧

𝑝)∨𝑞∨𝑟)

(添加缺少的变元)

(𝑝∨𝑞∨𝑟)∧(𝑝∨

𝑞∨𝑟)∧(𝑝∨𝑞∨𝑟)∧(

𝑝∨𝑞∨𝑟)

M0∧

M2∧

M4

(合并相同的极大项并排序)

∏0,2,4 (简化表达)

83主范式的求法2

真值表法主析(合)取范式的求解步骤列出公式对应的真值表选出公式的真值结果为真(假)的所有的行在这样的每一行中,找到其每一个解释所对应的极小(大)项将这些极小(大)项进行析(合)取即为所得命题公式的标准化1-584【示例1】求解公式A=(𝑝∨𝑞)→

𝑟的主析取范式和主合取范式。(公式A的真值表如下表所示)。85𝑝𝑞𝑟𝑝∨𝑞

𝑟(𝑝∨𝑞)→

𝑟000011001001010111011100100111101100110111111100成真赋值：000,001,010,100,110,所对应的极小项分别为：

𝑝∧𝑞∧𝑟,

𝑝∧𝑞∧𝑟,

𝑝∧𝑞∧𝑟,𝑝∧𝑞∧𝑟,𝑝∧𝑞∧𝑟,主析取范式𝑚0∨𝑚1∨𝑚2∨𝑚4∨𝑚6成假赋值：011,101,111,所对应的极大项分别为：𝑝∨𝑞∨𝑟,

𝑝∨𝑞∨𝑟,

𝑝∨𝑞∨𝑟,主合取范式

M3∧M5∧M7【示例2】学院安排课表,教语言课的教师希望将课程安排在第一或第三节；教数学课的教师希望将课程安排在第二或第三节；教物理课的教师希望将课程安排在第一或第二节。如何安排课表,使得三位教师都满意。解：令L1、L2、L3分别表示语言课排在第一、第二、第三节。

M1、M2、M3分别表示数学课排在第一、第二、第三节。P1、P2、P3分别表示物理课排在第一、第二、第三节。三位教师都满意的条件是：A

(L1∨L3)∧(M2∨M3)∧(P1∨P2

)

为真。(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,暨语言课排在第三节、数学课排在第二节、物理课排在第一节或者语言课排在第一节、数学课排在第三节、物理课排在第二节。86由公式的主析取范式求主合取范式设公式A含有𝑛个命题变元,A的主析取范式含𝑠(0

<𝑠<

2𝑛)个极小项,即A

𝑚𝑖1∨𝑚𝑖2∨…∨𝑚is

,0

≤𝑖𝑗≤

2𝑛-1,𝑗=1,2,…,𝑠。没有出现的极小项为𝑚𝑗1,𝑚𝑗2,…,𝑚𝑗𝑡,(𝑡

=

2𝑛

-𝑠)。它们的下角标的二进制表示为A的成真赋值,因而A的主析取范式为：A

𝑚𝑗1∨𝑚𝑗2∨…∨𝑚𝑗𝑡。由公式的主析取范式,即可求出它的主合取范式。A

A

(𝑚𝑗1∨𝑚𝑗2∨…∨𝑚𝑗𝑡)

𝑚𝑗1∧𝑚𝑗2∧…∧𝑚𝑗𝑡

M𝑗1∧M𝑗2∧…∧M𝑗𝑡87重言式与矛盾式的主合取范式矛盾式无成真赋值,因而矛盾式的主合取范式含2𝑛（𝑛为公式中命题变元的个数）个极大项。矛盾式的主析取范式不含极小项,是空范式,将矛盾式的主析取范式记为0。重言式无成假赋值,因而主合取范式不含任何极大项,是空范式。将重言式的主合取范式记为1.【示例】求命题公式𝑝→(𝑞→𝑝)的主合取范式。解：𝑝→(𝑞→𝑝)的主析取范式为：(𝑝∧𝑞)∨(𝑝∧𝑞)∨(𝑝∧

𝑞)∨(𝑝∧

𝑞)由𝑝→(𝑞→𝑝)对应的所有4个极小项的析取得到。881-5-3主范式的应用求公式的成真成假赋值设公式A含𝑛个命题变项,A的主析取范式有𝑠个极小项,则A有𝑠个成真赋值,它们是极小项下标的二进制表示,其余2𝑛-𝑠个赋值都是成假赋值(𝑝→

𝑞)→𝑟

𝑚1∨𝑚3∨𝑚5∨𝑚6∨𝑚7成真赋值为001,011,101,110,111成假赋值为000,010,100类似地,由主合取范式也立即求出成假赋值和成真赋值.命题公式的标准化1-5891-5-3主范式的应用判断公式的类型（设A含𝑛个命题变项）

A为重言式

A的主析取范式含全部2𝑛个极小项

A的主合取范式不含任何极大项,记为1A为矛盾式

A的主合取范式含全部2𝑛个极大项

A的主析取范式不含任何极小项,记为0A为非重言式的可满足式

A的主析取范式中至少含一个、但不是全部极小项

A的主合取范式中至少含一个、但不是全部极大项命题公式的标准化1-590练习用主析取范式判断公式的类型:A

(𝑝→𝑞)∧

𝑞

B

𝑝→(𝑝∨

𝑞)C

(𝑝∨

𝑞)→𝑟练习答案：A

(

𝑝∨𝑞)∧𝑞

(𝑝∧𝑞)∧𝑞0矛盾式B𝑝∨(𝑝∨𝑞)1𝑚0∨𝑚1∨𝑚2∨𝑚3

重言式C(𝑝∨𝑞)∨𝑟(𝑝∧𝑞)∨𝑟(𝑝∧𝑞∧𝑟)∨(𝑝∧𝑞∧𝑟)∨(𝑝∧𝑞∧𝑟)∨(𝑝∧𝑞∧𝑟)∨(𝑝∧𝑞∧𝑟)∨(𝑝∧𝑞∧𝑟)

𝑚0∨𝑚1∨𝑚3∨𝑚5∨𝑚7

非重言式的可满足式911-5-3主范式的应用判断两个公式是否等价设公式A,B共含有𝑛个命题变元,按𝑛个命题变元求出A与B的主析取范式A’与B’。若A’=B’,则A

B。【示例】用主析取范式判以下每一组公式是否等价⑴𝑝→(𝑞→𝑟)与(𝑝∧𝑞)→𝑟⑵𝑝→(𝑞→𝑟)与(𝑝→𝑞)→𝑟解𝑝→(𝑞→𝑟)=𝑚0∨𝑚1∨𝑚2∨𝑚3∨𝑚4∨𝑚5∨𝑚7(𝑝∧𝑞)→𝑟=𝑚0∨𝑚1∨𝑚2∨𝑚3∨𝑚4∨𝑚5∨𝑚7(𝑝→𝑞)→𝑟=𝑚1∨𝑚3∨𝑚4∨𝑚5∨𝑚7显见,⑴中的两公式等价,而⑵的不等价.命题公式的标准化1-5921-5-3主范式的应用解决实际问题【示例】学校要从A,B,C三人中选派若干人出国考察,需满足下述条件:（1）若A去,则C必须去；（2）若B去,则C不能去；（3）A和B必须去一人且只能去一人。问有几种可能的选派方案?命题公式的标准化1-593解令𝑝:派A去,𝑞:派B去,𝑟:派C去。则三个条件符号化为：(1)𝑝→𝑟,(2)𝑞→

𝑟,(3)(𝑝∧𝑞)∨(

𝑝∧𝑞)。可能的选派方案即求下式的成真赋值

A=(𝑝→𝑟)∧(𝑞→

𝑟)∧((𝑝∧𝑞)∨(

𝑝∧𝑞))求A的主析取范式

A=(𝑝→𝑟)∧(𝑞→

𝑟)∧((𝑝∧𝑞)∨(

𝑝∧𝑞))

(

𝑝∨𝑟)∧(

𝑞∨𝑟)∧((𝑝∧𝑞)∨(

𝑝∧𝑞))

((

𝑝∧𝑞)∨(

𝑝∧𝑟)∨(𝑟∧𝑞)∨(𝑟∧𝑟))分配律∧((𝑝∧𝑞)∨(

𝑝∧𝑞))

((

𝑝∧𝑞)∧(𝑝∧𝑞))∨((

𝑝∧𝑟)∧(𝑝∧𝑞))三对二分配律∨((𝑟∧𝑞)∧(𝑝∧𝑞))∨((

𝑝∧𝑞)∧(

𝑝∧𝑞))∨((

𝑝∧𝑟)∧(

𝑝∧𝑞))∨((𝑟∧𝑞)∧(

𝑝∧𝑞))

(𝑝∧𝑞∧𝑟)∨(𝑝∧𝑞∧𝑟)成真赋值:101,010结论:方案1：派A与C去；方案2：派B去§1-6-1蕴含关系【定义】设A和B是两个命题公式,若A→B是永真式,则称A蕴含B,记作A

B,A

B为蕴含式或永真条件式A为蕴含式的前件或前提B为蕴含式的后件或结论等价式与蕴含式之间的关系A

B的充要条件是A

B且B

A。命题逻辑的蕴含关系1-694§1-6-2证明蕴含关系的方法真值表证明：A→B是重言式。逻辑推演证明前件真推导后件真方法设条件式的前件指派为真,若能推导出后件真值也为真,则条件式是永真式,故蕴含式成立。后件假推导前件假方法设条件式的后件指派为假,若能推导出前件真值也为假,则条件式是永真式,即蕴含式成立。命题逻辑的蕴含关系1-695【示例】求证

𝑞∧(𝑝→𝑞)

𝑝。证明：

①前件真推导后件真方法设

𝑞∧(𝑝→𝑞)为T,则

𝑞,(𝑝→𝑞)皆为T,于是𝑞为F,𝑝→𝑞为T,则必须𝑝为F,故

𝑝为T。②后件假推导前件假方法假定

𝑝为F,则𝑝为T。以下分情况讨论：若𝑞为F,则𝑝→𝑞为F,

𝑞∧(𝑝→𝑞)为F；若𝑞为T,则

𝑞为F,

𝑞∧(𝑝→𝑞)为F,故

𝑞∧(𝑝→𝑞)

𝑝。96§1-6-3基本蕴含式常用的蕴含式如下：1.A

(A∨B)

附加律2.(A∧B)

A化简律3.(A→B)∧A

B假言推理4.(A→B)∧

B

A 拒取式(A∨B)∧

B

A 析取三段论6.(A→B)∧(B→C)

(A→C)

假言三段论7.(A↔B)∧(B↔C)

(A↔C)

等价三段论8.(A→B)∧(C→D)∧(A∨C)

(B∨D)

构造性二难推理(A→B)∧(C→D)∧(

B∨D)

(

A∨C)

破坏性二难推理命题逻辑的蕴含关系1-697§1-7-1论证的有效性数理逻辑的主要任务是用数学的方法来研究数学中的推理。所谓推理是指从前提出发推出结论的思维过程,而前提是已知命题公式集合,结论是从前提出发应用推理规则推出的命题公式。要研究推理就应该给出推理的形式结构,为此,首先应该明确什么样的推理是有效的或正确的。推理也称论证,是指由已知的若干命题得到新命题的思维过程,其中已知命题称为推理的前提或假设,推得的新命题称为推理的结论。命题逻辑要把推理的过程描述为形式化的逻辑演绎规律。命题逻辑的推理理论1-798§1-7-1论证的有效性【定义】设A1,A2,…,A𝑘,B为命题公式,若对于每组赋值,A1∧

A2∧

…∧A𝑘

为假,或当A1∧

A2∧

…∧A𝑘为真时,B也为真,则称由前提A1,A2,…,A𝑘推出结论B的推理是