离散数学及应用（第3版）课件第二章 命题逻辑

第二章

命题逻辑《离散数学及应用》第二章

命题逻辑逻辑是关于思维形式的科学，所谓思维的逻辑形式是指不同的具体思维内容之间的共同的联系方式。数理逻辑是用数学的方法研究思维的形式结构和规律的学科，它使用符号语言，按照一定的规则，简洁地表达出各种推理的逻辑关系，所以数理逻辑又称符号逻辑，它与计算机科学有着非常密切的联系，是计算机程序设计、人工智能、逻辑设计、机器证明、自动程序设计、计算机辅助设计等计算机理论和应用学科的基础。命题逻辑是数理逻辑中最基础的内容，其以命题为最基本的单位来研究思维的形式结构和规律。2第二章命题逻辑§2.1命题逻辑的基本概念§2.2命题公式及其分类§2.3命题逻辑的等值演算§2.4对偶与范式§2.3.1对偶§2.3.2析取范式和合取范式§2.3.3主范式§2.5命题联结词的完备集§2.6命题逻辑的推理3命题与命题联结词逻辑如何表示？如何“操作”？非真即假的陈述句称为命题（proposition）。一个命题如果是对的或正确的，则称为真命题，其真值为“真”（true），常用T或1表示；一个命题如果是错的或不正确的，则称为假命题，其真值为“假”（false），常用F或0表示。4命题与命题联结词例

判断下列句子哪些是命题，哪些不是这门课程题为“离散数学”。这门“离散数学”讲得好吗？这门“离散数学”讲得真好！

请学习“离散数学”。5是素数。太阳从西方升起。如果明天晴，而且我有空，我就去踢球。天王星上没有生命。x+3>5。本命题是假的。5

XXXXX

命题与命题联结词通常用小写英文字母

p,q,r,…或带有下标的小写字母

p1,p2,p3…来表示命题，称为命题变元或命题变项（propositionalvariables）严格地讲，命题变项与命题不同命题有具体的含意和确定的真值而命题变项只有明确表示某个命题时才有具体的含意和确定的真值命题变项一般只表示一个抽象的命题，其真值可能是T也可能是F但通常也简称命题变项为命题6命题与命题联结词不能再分解的命题称为简单命题（simpleproposition）或原子命题（atomproposition）。一般形式是“.…..是……”由原子命题组合而成的命题称为复合命题（compoundproposition）。例如：

和

e

都是无理数。6和8至少有一个是合数。说刘老师讲课不好是不正确的。不下雨我就去买书。7命题与命题联结词将命题连接起来的方式叫做命题联结词（propositionconnective）或命题运算符（propositionoperator），主要有以下几种：否定词

(not)

p合取词(and) p∧q析取词(or) p∨q异或词

p

q蕴涵词

p

q等价词

p

q8命题与命题联结词设

p

为命题，否定词（negation）“~”是一元联结词~p读作“非p”或“p的否定”。若

p

的真值为真，则

~p

的真值为假；反之，若

p

为假，则

~p

为真。否定联结词的含意相当于自然语言中的“不”、“没有”、“无”、“否定”、“并非”、“取反”等。例用

p

表示命题“3是素数”则

~p

即为命题“3不是素数”9命题与命题联结词设

p,

q

为命题，合取词（conjunction）“∧”是二元联结词p∧q读作“p与q”或“p,

q的合取”当且仅当

p,

q

的真值均为真时，p∧q

的真值为真。合取联结词的含意相当于自然语言中的“p和q”、“p与q”、“p且q”、“p，同时q”、“p并且q”、“p以及q”、“p而且q”、“既p，又q”、“不但p，而且q”、“尽管p，依然q”、“虽然p，但是q”等。10命题与命题联结词例p表示命题“3是素数”q表示命题“5是素数”则“3和5都是素数”可以表示为p∧q11命题与命题联结词设

p,

q

为命题，析取词（disjunction）“∨”是二元联结词p∨q读作“p或q”或“p,

q的析取”当且仅当

p,

q的真值均为假时，p∨q的真值为假。析取联结词的含意相当于自然语言中的“p或者q”、“要么p，要么q”、“不是p，就是q”等。12命题与命题联结词析取联结词∨与自然语言中的“或者”类似但又有所不同。例如：(a)苗苗在看电视或者在吃饭。(b)苗苗今天上午十时在清华大学或者在北京大学。通常称命题(a)中的“或者”为“可兼或”，命题(b)中的“或者”为“不可兼或”。自然语言中的“可兼或”与析取联结词∨相对应，而“不可兼或”与下面介绍的异或联结词相对应。13命题与命题联结词设

p,

q

为命题，异或词（exclusiveor）“

”是二元联结词p

q

读作“p异或q”当且仅当

p,

q

的真值相同时，p

q的真值为假。“异或”也称“不可兼或”。14命题与命题联结词设

p,

q

为命题，蕴涵词（implication）“

”是二元联结词p

q读作“若p则q”当且仅当

p的真值为真、q的真值为假时，p

q的真值为假p称作前提（premise），q称作结论（conclusion）。蕴涵联结词的含意相当于自然语言中的“如果p，则q”、“因为p，所以q”、“只要p，就q”、“只有q，才p”、“仅当q，则p”、“p是q的充分条件”、“q是p的必要条件”、“既然p，那么q”等。15命题与命题联结词例p表示命题“今天晴”q表示命题“苗苗去图书馆”则“因为今天晴，所以苗苗去图书馆了”可以表示为

p

q例p表示命题“2+2=4”q表示命题“北京是中国的首都”则p

q表示“因为2+2=4，所以北京是中国的首都”16命题与命题联结词例对于p

q，当

p

为假时，q

不论为真为假，蕴涵式的真值均为真。“如果周五地震，那么下次课考试”。对于命题

p

q，称命题“q

p”为其逆命题，命题“~p

~q”为其否命题，命题“~q

~p”为其逆否命题。17命题与命题联结词设

p,

q

为命题，等价词（equivalence）“

”是二元联结词p

q读作“p当且仅当q”或“p,q等价”当且仅当

p,

q

的真值相同时，p

q

的真值为真。“等价”也称作“双条件”（biconditional）。等价联结词的含意相当于自然语言中的“p，当且仅当q”、“p是q的充分必要条件”、“p,q含义相同”等。18命题与命题联结词例p表示“3是奇数”q表示“太阳从东方升起”，则命题“3是奇数，当且仅当太阳从东方升起”可符号化为p

q。19命题的符号化把一个用自然语言表述的命题表示为由命题公式的形式，称为命题的符号化，这是进行推理演算的首要步骤。命题的符号化一般经过如下三个步骤：1.找出各原子命题，将原子命题符号化2.

找出命题中各联结词，将联结词符号化3.

将原子命题和联结词组成一个复合命题20命题的符号化例

把下列自然语言命题符号化：说这门课讲得不好是不正确的。p

表示“这门课讲得好”则命题符号化为

~(~p)21命题的符号化例

把下列自然语言命题符号化：

和e都是无理数。p

表示“

是无理数”q

表示“e是无理数”则命题符号化为

p∧q22命题的符号化例

把下列自然语言命题符号化：俞伯牙和钟子期是好朋友。俞伯牙是好朋友

∧钟子期是好朋友俞伯牙

∧钟子期是好朋友Friend(俞伯牙,钟子期)23命题的符号化例

把下列自然语言命题符号化：

属于集合A或者集合B。p表示“

属于集合A”q表示“

属于集合B”它们是可兼或，命题符号化为

p∨q小李生于1978年或者1987年。p表示“小李生于1978年”q表示“小李生于1987年”它们是不可兼或，命题符号化为

p

q24命题的符号化例

把下列自然语言命题符号化：只有在晴天，我才会去公园。p

表示“天气晴”q

表示“我去公园”，则命题符号化为

q

p或者理解为“如果不是晴天我就一定不去公园”，这时命题符号化为

~p

~q只要是晴天，我就会去公园。命题符号化为

p

q25命题的符号化例

把下列自然语言命题符号化：n

是奇数当且仅当

n2

是奇数。p

表示“n是奇数”q

表示“n2是奇数”则命题符号化为

p

q26命题的符号化例

把下列自然语言命题符号化：小李是一名本科生，他的专业是数学或计算机。p

表示“小李是一名本科生”q

表示“小李的专业是数学”r

表示“小李的专业是计算机”各分句之间的关系是合取关系命题符号化为

p∧(q∨r)27命题的符号化把程序语句“IFPTHENQELSER”表达为复合命题(P

Q)∧(

P

R)28这里关心的并不是“Q事实上是不是被执行了”——因为这可能还要受到其他语句的影响；而是“在P发生的情况下Q是否执行”。R的情况也一样，它在事实上可能被其他程序语句所执行，也可能没有，但无论执行与否都不是由P导致的。第二章命题逻辑§2.1命题逻辑的基本概念§2.2命题公式及其分类§2.3命题逻辑的等值演算§2.4对偶与范式§2.3.1对偶§2.3.2析取范式和合取范式§2.3.3主范式§2.5命题联结词的完备集§2.6命题逻辑的推理29命题公式及其分类复合命题是由命题变项、逻辑联结词和括号等符号组成的符号串；但反过来，由这些符号组成的符号串并不一定都是命题：30命题公式及其分类命题逻辑中的命题公式(wellformedformula，简记为wff)递归地定义为：(1) 单个命题变项

p,q,r,…是命题公式；(2) 如果

A

是命题公式，则

(~A)

也是命题公式；(3) 如果

A

和

B

是命题公式，则由逻辑联结词联结

A

和

B

的符号串也是命题公式，如：(A∧B)、(A∨B)、(A

B)、(A

B)等等；(4) 有限次应用(1)-(3)构成的符号串才是命题公式。换言之，只有用命题公式表示的符号串才是命题。命题公式也称为合式公式，简称公式。31命题公式及其分类例(~p)，(~(p∧q))，(p∧(q∨(~r)))都是命题公式而

(p

(∧q))，p

(~p

r

都不是命题公式32命题公式及其分类为简化公式的形式，作如下规定：(1)优先级

,(∧,

∨),

(

,

)(2)公式

(~p)

的括号可以省略，写成

~p(3)整个公式最外层的括号可以省略例1(((

p)∧q)

(q∨p))

p∧q

q∨p例2p∧q∨r不是

命题公式应写作

(p∧q)∨r

或

p∧(q∨r)33命题公式及其分类设

A为命题公式，B

为

A中的一个连续的符号串，且

B

为命题公式，则称

B

为

A的子公式（subformula）。例p∨q、q∨r、p∧(q∨r)

都是公式(p∨q)

(p∧(q∨r))的子公式而

p∧(q、q)

(p

都不是该公式的子公式，因为它们本身不是公式34命题公式及其分类命题公式不是命题，只有当公式中的每一个命题变项都被赋以确定的真值时，公式的真值才被确定，从而成为一个命题。35命题公式及其分类如果一个命题公式

A

含有

n

个命题变项

p1,p2,…,pn，则该公式称为n元命题公式。在A中，对变项组(p1,p2,…,pn)指定的一组确定真值称为该公式的一个真值指派或赋值（assignment）。若指定的一组值使

A的真值为真，则称这组值为

A的成真指派或成真赋值若使

A的真值为假，则称这组值为

A的成假指派或成假赋值36命题公式及其分类例“p取值为T、q取值为F”是~p∧q的一个成假指派“p取值为F、q取值为T”是~p∧q的一个成真指派37命题公式及其分类n（n≥1）元命题公式共有2n个不同的真值指派。在命题变项

p1,p2,…,pn

次序确定的情况下，(p1,p2,…,pn)的一个真值指派可以表示为一个由0和1组成的n位符号串例如一个含命题变项

p1,p2,

p3

的命题公式

A

的一个真值指派表示为101，其含义是p1真值为T，p2真值为F，p3真值为T38命题公式及其分类假设

A

为一个

n

元命题公式，若其所有

2n

个真值指派都是成真指派，则称

A为永真式或重言式（tautology）；若其所有

2n

个真值指派都是成假指派，则称

A为永假式或矛盾式（contradiction）若其至少存在一个成真指派，则称

A为可满足式（satisfiableformula）若

A

至少存在一个成真指派及成假指派，则称

A为非重言的可满足式39命题公式及其分类例

p

p∨q是重言式~p

p是矛盾式~p∧q是非重言式的可满足式40命题公式及其分类重言式一定是可满足式，但反之不真任意两个重言式的析取或合取仍然是重言式任意两个矛盾式的析取或合取仍然是矛盾式41真值表一个命题公式在每种真值指派（即每种命题变项取值的组合）上的值可以直观地用真值表（truthtable）来计算和表示：对于一个

n

元命题公式

A，其真值表的输入端（即最左

n

列）的

2n

行对应于它的

2n个真值指派输出端（即最右一列）对应于命题公式在它的

2n

个真值指派下的真值42真值表为方便构造真值表，特约定如下：(1)命题变项按字典序排列(2)对每个真值指派，以二进制数从小到大或从大到小顺序列出(3)若公式较复杂，可先列出各子公式的真值，最后列出所求公式的真值43真值表各个命题联结词的真值表44pq~pp∧qp∨qp

qp

qp

qTTFTTFTTTFFFTTFFFTTFTTTFFFTFFFTT真值表例列出下述命题的真值表，并给出各公式的成真指派和成假指派：(a)(p∨(p∧q))

(

p

q)(b)

(

p∨q)∧(q∧q)(c)(

p∧q)

(

q∨p)45真值表(a)(p∨(p∧q))

(

p

q)的真值表成真指派为TT、TF、FT和FF，不存在成假指派真值表最后一列全为T，公式为重言式46真值指派子公式真值命题公式真值pqp∧qp∨(p∧q))

p

p

q(p∨(p∧q))

(

p

q)TTTTFTTTFFTFTTFTFFTTTFFFFTFT真值表(b)

(

p∨q)∧(q∧q)

的真值表不存在成真指派，成假指派为TT、TF、FT和FF真值表最后一列全为F，公式为矛盾式47真值指派子公式真值命题公式真值pq

p

p∨q

(

p∨q)q∧q

(

p∨q)∧(q∧q)TTFTFTFTFFFTFFFTTTFTFFFTTFFF真值表(c)(

p∧q)

(

q∨p)

的真值表成真指派为TT、TF和FF，成假指派为FT真值表最后一列中至少有一个T，公式为可满足式48真值指派子公式真值命题公式真值pq

p

p∧q

q

q∨p(

p∧q)

(

q∨p)TTFFFTTTFFFTTTFTTTFFFFFTFTTT第二章命题逻辑§2.1命题逻辑的基本概念§2.2命题公式及其分类§2.3命题逻辑的等值演算§2.4对偶与范式§2.3.1对偶§2.3.2析取范式和合取范式§2.3.3主范式§2.5命题联结词的完备集§2.6命题逻辑的推理49命题逻辑的等值演算设

A，B

为两个命题公式，若

A

B

为一个重言式，则称

A

与

B等值（equivalent）或逻辑等价（logicallyequivalent），记作

A

B，称

A

B

为等值式（equivalence）。(a)“

”并不是一个逻辑联结符，A

B

表示

A,B

有等值关系，而并非命题。(b)设

p1,p2,…,pn是公式

A和公式

B

中出现的全部命题变项。由定义，A,B

等值当且仅当对于命题变项

p1,p2,…,pn的任意一组真值指派，A和

B

的取值均相同。50命题逻辑的等值演算判断两个命题公式是否等值主要有两种方法：真值表法将两个公式的真值表列出，判断输出列是否相同等值演算法由已知的等值式推演出新的等值式等值演算不能直接证明两个公式不等值。证明两个公式不等值的基本思想是找到一个真值指派使一个成真，另一个成假。5152例p∨(p∧q)

p命题逻辑的等值演算Inputspqp∧qp∨(p∧q))

TTTTTFFTFTFFFFFF命题逻辑的等值演算例(p

q)

(

p∨q)53pq

p

qTTTTFFFTTFFTpq

p

p∨qTTFTTFFFFTTTFFTT命题逻辑的等值演算例判断下述3个公式之间的等值关系p

(q

r),(p

q)

r,(p∧q)

r54InputsOutputspqrp

(q

r)(p

q)

r(p∧q)

rTTTTTTTTFFFFTFTTTTTFFTTTFTTTTTFTFTFTFFTTTTFFFTFT命题逻辑的等值演算当命题变项较多时，真值表法的工作量很大而等值演算法则以基本等值式为基础，应用代入规则、置换规则，逐步推演。55命题逻辑的等值演算基本等值式交换律p∨q

q∨p,p∧q

q∧p结合律(p∨q)∨r

p∨(q∨r)(p∧q)∧r

p∧(q∧r)分配律p∨(q∧r)(p∨q)∧(p∨r)p∧(q∨r)(p∧q)∨(p∧r)幂等律p∨p

p,p∧p

p56命题逻辑的等值演算吸收律p∨(p∧q)p,p∧(p∨q)p双重否定律(p)p德·摩根律

(p∨q)

p∧

q

(p∧q)

p∨

q 零律p∨T

T，p∧F

F同一律p∨F

p,p∧T

p57命题逻辑的等值演算排中律（非真即假）

p∨

pT矛盾律（不能既真又假）

p∧

pF蕴涵等值式

(p

q)

(

p∨q)等价等值式

(p

q)

((p

q)∧(q

p)

)58命题逻辑的等值演算定理(代入规则)

假设

A

是一个重言式，对其中所有相同的命题变项都用同一命题公式进行代换，所得到的结果仍为一重言式。重言式的值不依赖于命题变项值的变化。因此，对命题变项以任何公式替换后，得到的仍是重言式59命题逻辑的等值演算例

=p∨(

q∧p

)

p=(s

t)∨(q∧(s

t))

(s

t)60命题逻辑的等值演算定理(置换规则)

设

(A)

是含命题公式

A

的命题公式，

(B)是用命题公式

B

置换了

(A)

中的

A

之后得到的命题公式（不一定是每一处）。

如果

A

B，则

(A)

(B)。6162命题逻辑的等值演算例

((p∨q)∧p)∨(p∧r)

p∨

(p∧r)

p (p∨q)∧p

p命题逻辑的等值演算

代入规则置换规则使用对象任意重言式任一命题公式代换对象任一命题变项任一子公式被代换物任一命题公式任一与代换对象等值的命题公式代换方式代换同一命题变项的所有出现代换子公式的某些出现代换结果仍为重言式与原公式等值6364命题逻辑的等值演算例证明

p

(q

r)

(p∧q)

r证明

p

(q

r)

p∨(

q∨r)

(

p∨

q)∨r

(p∧q)∨r

(p∧q)

r

65命题逻辑的等值演算例证明

(

p∧(

q∧r))∨(q∧r)∨(p∧r)

r证明 (

p∧(

q∧r))∨(q∧r)∨(p∧r)

(

p∧(

q∧r))∨((q∨p)∧r)

((

p∧

q)∧r)∨((q∨p)∧r)

(

(p∨q)∧r)∨((q∨p)∧r)

(

(p∨q)∨(q∨p))∧r

T∧r

r

66命题逻辑的等值演算例证明

((p∨q)∧

(

p∧(

q∨

r)))∨(

p∧

q)∨(

p∧

r)是重言式。证明((p∨q)∧

(

p∧(

q∨

r)))∨(

p∧

q)∨(

p∧

r)

((p∨q)∧(p∨(q∧r)))∨

(p∨q)∨

(p∨r)

((p∨q)∧((p∨q)∧(p∨r)))∨

(p∨q)∨

(p∨r)

((p∨q)∧(p∨r))∨

(p∨q)∨

(p∨r)

((p∨q)∧(p∨r))∨

((p∨q)∧(p∨r))

T

命题逻辑的等值演算例化简语句：“情况并非如此：如果他不来，那么我也不去”解p：他来；q：我去

(

p

q)

p∧q

我去了，而他没来67命题逻辑的等值演算例化简语句：“不得不说如果不是因为他是不得已而为之而且没有造成恶劣后果的话我是不会原谅他的”解p:他这么做q:他造成了恶劣后果r:我原谅他

(

(

p∧

q)

r)

r

p∧

q我原谅他，是因为他这么做了而且没有造成恶劣后果。68命题逻辑的等值演算例程序化简69IfA∧Bthen

IfB∨CthenX

ElseY

EndElse

IfA∧CthenY

ElseX

EndEndIfA∧~B∧CthenYElseXEnd((A∧B)∧(B∨C)

X)

∧((A∧B)∧~(B∨C)

Y)∧(~(A∧B)∧(A∧C)

Y)∧(~(A∧B)∧~(A∧C)

X)

(~(A∧~B∧C)

X)∧(A∧~B∧C

Y)命题逻辑的等值演算例小张或小李是三八红旗手；如果小张是三八红旗手，会告知大家的；如果小李是三八红旗手，那么小赵也是；大家并没有被告知小张是三八红旗手。请问：谁是三八红旗手？解p：小张是三八红旗手q：小李是三八红旗手r：大家被告知小张是三八红旗手s：小赵是三八红旗手(p∨q)∧(p

r)∧(q

s)∧

r

p∧q∧s∧

r70第二章命题逻辑§2.1命题逻辑的基本概念§2.2命题公式及其分类§2.3命题逻辑的等值演算§2.4对偶与范式§2.3.1对偶§2.3.2析取范式和合取范式§2.3.3主范式§2.5命题联结词的完备集§2.6命题逻辑的推理71对偶在基本等值式中，很多都是成对出现p∨p

p，p∧p

p(p∨q)∨r

p∨(q∨r)，

(p∧q)∧r

p∧(q∧r)在仅含有联结词

~,∧,∨

的命题公式

A

中，将∨换成∧、∧换成∨，若包含F和T亦相互取代，所得命题公式称为

A

的对偶式（dual），记

作A

。由对偶式的定义显然有

(A

)

=A，即对偶式是相互的。72对偶例A=p∨(

p∨(q∧

r))A

=p∧(

p∧(q∨

r))73对偶定理1

设

A为一仅含有联结词

~,∧,∨

的

n

元命题公式，p1,p2,…,pn是其命题变项，则~A(p1,p2,…,pn)

A

(~p1,~p2,…,~pn)。（对A中联结词的个数进行归纳证明）推论

设

A为一仅含有联结词

~,∧,∨

的

n

元命题公式，若

A

为重言式，则

A*

必为矛盾式。74对偶定理2（对偶原理）

设

A,B

为两个仅含有联结词

~,∧,∨

的

n

元命题公式，若

A

B

，则

A

B

。证明设

p1,p2,…,pn

是公式

A

和公式

B

中出现的全部命题变项~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)75对偶于是已知

A

B，且

B

是比

A

简单的命题公式，则由对偶原理可直接求出较简单的

B*

与

A*等值。例若

(p∧q)∨(

p∨(

p∨q))

p∨q则

(p∨q)∧(

p∧(

p∧q))

p∧q76第二章命题逻辑§2.1命题逻辑的基本概念§2.2命题公式及其分类§2.3命题逻辑的等值演算§2.4对偶与范式§2.3.1对偶§2.3.2析取范式和合取范式§2.3.3主范式§2.5命题联结词的完备集§2.6命题逻辑的推理77析取范式和合取范式与一个给定的命题公式等值而形式不同的命题公式可以有无穷多个于是，首要的问题就是能否将所有与命题公式

A等值的公式化为某一个统一的规范形式。通过这种规范形式，可以判断任意两个形式上不同的公式是否等值、判断任一公式是否为重言式或矛盾式等78析取范式和合取范式命题变项

p

及其否定式

p统称文字(literal)，且

p

与

p称为互补对。由有限个文字的析取所组成的公式称为析取式（fundamentaldisjunction）由有限个文字的合取所组成的公式称为合取式（fundamentalconjunction）7980例析取式p、

p、p∨q、p∨q∨

q合取式p、

p、p∧q、p∧q∧

p析取范式和合取范式81析取范式和合取范式形如

A1∨A2∨…∨An的公式称为析取范式(disjunctivenormalform,DNF)，其中

Ai

(i=1,…,n)为合取式。给定命题公式

A，与

A

等值的析取范式称作

A的析取范式。形如

A1∧A2∧…∧An的公式称为合取范式(conjunctivenormalform,CNF)，其中

Ai

(i=1,…,n)为析取式。给定命题公式

A，与

A

等值的合取范式称作

A的合取范式。在CNF和DNF中，可能出现的逻辑联结词只有∧,∨,和

。82例析取范式

(

p∧q∧

r)∨(

p∧

q∧

r)∨(p∧q∧

r)(

p∧

r)∨(q∧

r)(p∧

q)∨(

p∧q)合取范式(p∨q)∧(

p∨

q)(

p∨q)∧

r析取范式和合取范式83一个析取范式是矛盾式，当且仅当它的每个合取式都是矛盾式，即每个合取式至少包含一个互补对一个合取范式是重言式，当且仅当它的每个析取式都是重言式，即每个析取式至少包含一个互补对任何析取范式的对偶式为合取范式；任何合取范式的对偶式为析取范式设

B

为

A*的析取范式，则

B*

为

A的合取范式析取范式和合取范式84定理（范式存在定理）

任一命题公式都存在着与之等值的析取范式和合取范式。析取范式和合取范式析取范式和合取范式求范式的步骤：1.利用等值式模式将其它联结词转化成

,∧,∨2.

简化双重否定号，并将所有

写到文字里，使之只作用于命题变项3.

利用分配律，将其最终变成合取范式或析取范式85析取范式和合取范式1.利用等值式模式将其它联结词转化成

,∧,∨：p

q

p∨qp

q

(

p∨q)∧(

q∨p)

(p∧q)∨(

q∧

p)

86872.

简化双重否定号，并将所有

写到文字里，使之只作用于命题变项：

(p)p

(p∨q)

p∧

q

(p∧q)

p∨

q析取范式和合取范式析取范式和合取范式3.

利用分配律，将其最终变成合取范式或析取范式：

p∨(q∧r)

(p∨q)∧(p∨r)

p∧(q∨r)

(p∧q)∨(p∧r)8889例1求

(p∨q)

(p∧q)的析取范式解

(p∨q)

(p∧q)

(

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

(p∨q)∧

(p∧q))

(

p∧

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

p∨

q))

(

p∧

q∧p∧q)∨(p∧

p)∨(p∧

q)∨(q∧

p)∨(q∧

q)

(p∧

q)∨(q∧

p)A

B

(A∧B)∨(

A∧

B)析取范式和合取范式析取范式和合取范式例2求

(p∨q)

(p∧q)的合取范式解

(p∨q)

(p∧q)

(

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

(p∧q)∨

(p∨q))

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

p∨

q)∨(

p∧

q))

(p∨q)∧(

p∨

q)90A

B

(

A∨B)∧(

B∨A)

91析取范式和合取范式定理（范式存在定理）

任一命题公式都存在着与之等值的析取范式和合取范式。

但析取范式和合取范式可能不是惟一的。第二章命题逻辑§2.1命题逻辑的基本概念§2.2命题公式及其分类§2.3命题逻辑的等值演算§2.4对偶与范式§2.3.1对偶§2.3.2析取范式和合取范式§2.3.3主范式§2.5命题联结词的完备集§2.6命题逻辑的推理92极小项与极大项若

n个命题变项

p1,p2,…,pn组成的合取式

q1∧q2∧…∧qn满足

qi=pi或

pi（1

i

n），即：(1)每个命题变项与它的否定式不同时出现，但二者之一必定出现且仅出现一次；(2)第

i个命题变项或其否定出现在从左起的第

i位上，则称合取式

q1∧q2∧…∧qn为极小项（minterm）。93极小项与极大项将命题变项看成1，命题变项的否定看成0，于是每个极小项对应一个二进制数，该二进制数正是该极小项真值为真的指派。将其转换为十进制数

i

，作为下脚标，则该极小项可以表示为

mi

。94

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。极小项与极大项极小项具有如下性质：任一含有

n

个命题变项的公式，所有可能的极小项的个数和该公式的解释个数相同，都是

2n；每个极小项只在一个解释下为真；极小项两两不等值，并且mi∧mj

F

(i≠j)因为其中至少包含一对互补对；恰由

2n

个极小项的析取构成的公式必为重言式。95极小项与极大项若

n

个命题变项

p1,p2,…,pn组成的析取式

q1∨q2∨…∨qn满足

qi

=pi或

pi（1

i

n），即：(1)每个命题变项与它的否定式不同时出现，但二者之一必定出现且仅出现一次；(2)第

i

个命题变项或其否定出现在从左起的第

i

位上，则称析取式

q1∨q2∨…∨qn为极大项（maxterm）。96极小项与极大项如果将命题变项看成0，将其否定看成1，则每一个极大项对应于一个二进制数，该二进制数正是该极大项真值为假的指派。对应的十进制数

i

作为下脚标，则该极大项可以表示为

Mi。97p∨

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，极小项与极大项极大项具有如下性质：任一含有

n

个命题变项的公式，所有可能的极大项的个数和该公式的解释个数相同，都是

2n

。每个极大项只在一个解释下为假。极大项两两不等值，并且Mi∨Mj

T

(i≠j)因为其中至少包含一对互补对。恰由

2n

个极大项的合取构成的公式必为矛盾式。98极小项与极大项极小项和极大项的关系99极小项合取式/析取式对于极小项，•表示∧对于极大项，•表示∨极大项m7111——7

p.

q.

r000——0M0m6110——6

p.

q.

r001——1M1m5101——5

p.

q.

r010——2M2m4100——4

p.

q.

r011——3M3m3011——3

p.

q.

r100——4M4m2010——2

p.

q.

r101——5M5m1001——1

p.

q.

r110——6M6m0000——0

p.

q.

r111——7M7极小项和极大项的关系极小项与极大项pqrm7m6m5m4m3m2m1m0M7M6M5M4M3M2M1M0TTTTFFFFFFFFTTTTTTTTTFFTFFFFFFTFTTTTTTTFTFFTFFFFFTTFTTTTTTFFFFFTFFFFTTTFTTTTFTTFFFFTFFFTTTTFTTTFTFFFFFFTFFTTTTTFTTFFTFFFFFFTFTTTTTTFTFFFFFFFFFFTTTTTTTTF100极小项与极大项定理

设

mi

和

Mi

是由命题变项

p1,p2,…,pn形成的极小项和极大项，则

mi

Mi

。101主范式若由

n

个命题变项构成的析取范式中所有的合取式都是极小项，则称其为主析取范式(fulldisjunctivenormalform)，用

表示。给定命题公式

A

，与

A

等值的主析取范式称作A的主析取范式。即仅由有限个极小项构成的析取范式称为主析取范式。102主范式例在由三个命题变项构成的命题公式中(p∧

q∧

r)∨(p∧q∧

r)∨(p∧q∧r)(p∧q∧r)∨(

p∧

q∧~r)

都是主析取范式(p∧q)∨(

p∧~r)不是主析取范式103主范式求给定命题公式

A的主析取范式的步骤：1.求出

A

的一个析取范式

A’

；2.若

A’

的某合取式

B

中不含命题变项

pi或其否定

pi，则将

B

展成如下形式：B

B∧(pi∨

pi)

(B∧pi)∨(B∧

pi)；3.将重复出现的命题变项、矛盾式及重复出现的极小项都“消去”，如

p∧p用

p

置换，p∧

p用

F置换，mi∨mi用

mi置换；4.将极小项按由小到大的顺序排列，并用Σ

表示之。如

m1∨m2∨m5用

Σ(1,2,5)表示104主范式例求

((p∨q)

r)

p

的主析取范式解原公式的析取范式为

p

∨(q∧

r)用

p∧(

q∨q)∧(

r∨r)置换

p

用

(

p∨p)∧(q∧

r)

置换

(q∧

r)而后——105主范式106((p∨q)

r)

p

p∨(q∧

r)

(p∧(

q∨q)∧(

r∨r))∨((

p∨p)∧(q∧

r))

(p∧

q∧

r)∨(p∧

q∧r)∨(p∧q∧

r)∨(p∧q∧r)∨(

p∧q∧

r)∨(p∧q∧

r)

m4∨m5∨m6∨m7∨m2∨m6

m2∨m4∨m5∨m6∨m7

(2,4,5,6,7)主范式若由

n

个命题变项构成的合取范式中所有的析取式都是极大项，则称其为主合取范式(fullconjunctivenormalform)，用

表示。给定命题公式

A

，与

A

等值的主合取范式称作A的主合取范式。即仅由有限个极大项构成的合取范式称为主合取范式。107主范式求给定命题公式

A

的主合取范式的步骤：1.求出

A

的一个合取范式

A’

；2.若

A’

的某析取式

B

中不含命题变项

pi或其否定

pi，则将

B

展成如下形式：B

B∨(pi∧

pi)

(B∨pi)∧(B∨

pi)；3.将重复出现的命题变项、重言式及重复出现的极大项都“消去”；4.将极大项按由小到大的顺序排列，并用

表示之。如

M1∧M2∧M5

用

(1,2,5)

表示。108109主范式例求

((p∨q)

r)

p

的主合取范式解

((p∨q)

r)

p

(p∨q)∧(p∨

r)

(p∨q∨(r∧

r))∧(p∨(q∧

q)∨

r)

(p∨q∨r)∧(p∨q∨

r)∧(p∨q∨r)∧(p∨

q∨

r)

(p∨q∨r)∧(p∨q∨

r)∧(p∨

q∨

r)

M0∧M1∧M3

(0,1,3)主范式真值表与主范式例

((p∨q)

r)

p

Σ(2,4,5,6,7)110InputsOutputsmpqr((p∨q)

r)

p7TTTT6TTFT5TFTT4TFFT3FTTF2FTFT1FFTF0FFFF111主范式主析取范式和主合取范式设命题公式A中含n个命题变项，且设A的主析取范式中含k个极小项mil,mi2,…,mik，则

A的主析取范式中必含2n

k个极小项，设为mjl,mj2,…,mj2n-k。即

A

mjl

∨mj2

∨…∨mj2n-k

A

A

(mjl

∨mj2

∨…∨mj2n

k

)

mjl∧

mj2∧…∧

mj2n

k

Mjl∧Mj2∧…∧Mj2n

k112主范式由A的主析取范式求主合取范式的步骤(1)求出A的主析取范式中没包含的极小项mj1,mj2,···,mj2n-k

(2)求出与步骤1中极小项下标相同的极大项Mj1,Mj2,···,Mj2n-k

(3)由以上极大项构成的合取式为A的主合取范式113主范式例

((p∨q)

r)

p

m2∨m4∨m5∨m6∨m7

Σ(2,4,5,6,7)

M0∧M1∧M3

(0,1,3)主范式定理（主析取范式定理）

任一含有n个命题变项的公式，都存在唯一的与之等值的且恰仅含这n个命题变项的主析取范式。定理（主合取范式定理）

任一含有n个命题变项的公式，都存在唯一的与之等值的且恰仅含这n个命题变项的主合取范式。114115主范式主析取范式的用途1.判断两命题公式是否等值.2.判断命题公式的类型.3.求命题公式的成真和成假赋值.116主范式1.判断两命题公式是否等值.由于任何命题公式的主析取范式都是唯一的,因而若A

B，说明A与B有相同的主析取范式。反之，若A,B有相同的主析取范式，必有A

B。117主范式2.判断命题公式的类型设A是含n个命题变项的命题公式A为重言式，当且仅当A的主析取范式中含全部2n个极小项A为矛盾式，当且仅当A的主析取范式中不含任何极小项——即为空公式若A的主析取范式中至少含一个极小项，则A是可满足式主范式例判断下列命题公式的类型(1)((p

q)∧p)

q(2)(p

q)∧q解(1)((p

q)∧p)

q

(0,1,2,3)(2)(p

q)∧q

(1,3)由此可知，(1)为重言式，(2)为可满足式

118119主范式

3.求命题公式的成真和成假赋值在上例(2)中(p

q)∧q

(1,3)“FT”、“TT”是成真赋值,“FF”、“TF”是成假赋值主范式例从甲、乙、丙三人中选派人员出国考察，需满足：(1)若甲去，则丙必须去；(2)若乙去，则丙不能去；(3)甲和乙必须去一人且只能去一人。问有几种可能的选派方案？解假设命题

p:派甲去，q:派乙去，r:派丙去(1):p

r，(2):q

r，(3):

(p∧

q)∨(

p∧q)问题转化为求下式的成真指派A=(p

r)∧(q

r)∧((p∧

q)∨(

p∧q))120主范式计算A的主析取范式：(p

r)∧(q

r)∧((p∧

q)∨(

p∧q))

(

p∨r)∧(

q∨

r)∧((p∧

q)∨(

p∧q))

(p∧

q∧r)∨(

p∧q∧

r)可得成真指派为：TFT，FTF。即方案1——派甲与丙去；方案2——派乙去。121第二章命题逻辑§2.1命题逻辑的基本概念§2.2命题公式及其分类§2.3命题逻辑的等值演算§2.4对偶与范式§2.3.1对偶§2.3.2析取范式和合取范式§2.3.3主范式§2.5命题联结词的完备集§2.6命题逻辑的推理122命题联结词的完备集设

C

是一个联结词的集合，如果任何由

n

个命题变项构成的命题公式都存在仅包含

C

中联结词的等值的公式，则称

C

是完备的联结词集合，或说

C

是联结词的完备集

设

C

是一个联结词的集合，其中可由

C

中的其它联结词定义的联结词称作冗余联结词不含有冗余联结词的联结词完备集称作极小完备集123命题联结词的完备集定理如果一个联结词完备集

S1

中的所有联结词都可由一个联结词集合

S2

定义，则

S2也是联结词完备集。定理下述联结词集合都是完备集：(a)S1={

,∨,∧}(b)S2={

,∧}(c)S3={

,∨}(d)S4={

,

}124命题联结词的完备集证明

S1={

,∨,∧}

是完备集任何由

n

个命题变项构成的命题公式都与唯一的一个主析取范式等值，而在主析取范式中仅含联结词

,∨,∧，所以

{

,∨,∧}

是联结词的完备集125命题联结词的完备集证明

S1={

,∨,∧}

是完备集(b)p∨q

(p∨q)

(

p∧

q)，由

S1

是完备集可得

S2={

,∧}

是完备集(c)p∧q

(

p∨

q)，由

S1

是完备集可得

S3={

,∨}

是完备集(d)p∨q

(

p)∨q

p

q，由

S3

是完备集可得

S4={

,

}完备集126命题联结词的完备集在{

,∨,∧}中，∧是冗余联结词在{

,∨,∧}中，∨是冗余联结词联结词集合{∧}不是完备的。证明假设{∧}是完备集，则由联结词完备性的定义有：

p

p1∧p2∧...

pn但当

p,p1,p2,...

pn

都取值为真时，上式左端为假，而右端为真。产生矛盾{

,∧}是联结词的极小完备集127命题联结词的完备集设

p,

q

为命题，与非词（sheffer）“↑”是二元联结词，p↑q读作“p,q

的与非”。当且仅当

p,

q

的真值均为真时，p↑q

的真值为假。简言之，p↑q

(p∧q)设

p,

q

为命题，或非词（pierce）“↓”是二元联结词，p↓q读作“p,q

的或非”。当且仅当

p,

q

的真值均为假时，p↓q的真值为真。简言之，p↓q

(p∨q)128命题联结词的完备集定理S5={

}是联结词完备集S6={

}是联结词完备集证明

p

(p∧p)

p↑p，p∧q

(p∧q)

(p↑q)

(p↑q)↑(p↑q)

p

(p∨p)

p↓pp∨q

(p∨q)

(p↓q)

(p↓q)↓(p↓q)129第二章命题逻辑§2.1命题逻辑的基本概念§2.2命题公式及其分类§2.3命题逻辑的等值演算§2.4对偶与范式§2.3.1对偶§2.3.2析取范式和合取范式§2.3.3主范式§2.5命题联结词的完备集§2.6命题逻辑的推理130命题逻辑的推理逻辑是研究思维结构和规则的科学，推理是逻辑的最终目标。为此，首先应该明确什么样的推理是有效的或正确的。131命题逻辑的推理推理是从前提推出结论的思维过程前提(premise)，或称假设(hypothesis)，是指已知的命题公式

A1,A2…An结论(conclusion)是从前提出发应用推理规则推出的命题公式

B正确的推理或有效的推理即是指

A1∧A2

∧…∧An

B是重言式此时称

B是

A1,A2…An

的逻辑推论或有效结论132命题逻辑的推理解推理问题的基本方法是：1.将命题符号化2.写出前提、结论和推理的形式结构3.对推理形式的正确性进行判断这里考虑的是推理形式结构的有效性，而不是结论的正确性。133命题逻辑的推理判断一个推理形式是否正确，从定义上讲就是判断一个蕴涵式是否是重言式，判定公式类型真值表法等值演算法主析取范式法134命题逻辑的推理例

判断下面推理是否正确：如果三角形的两边相等，则其所对的角相等；一个三角形的两边不相等，所以其所对角不相等。解设

p:三角形的两边相等q:三角形的两边所对的角相等则推理的形式结构为

(p

q)∧

p

q该蕴涵式不是重言式，表明推理不正确，或论证并非有效135命题逻辑的推理采用判定公式类型的方法来判断推理形式的正确与否具有一般性、广泛性的优点，但不足也很明显：不能直观看出由前提A到结论B的推演过程而且也难于推广到谓词逻辑中使用136命题逻辑的推理建立推理演算的证明方法（亦称演绎法）从前提

A1,A2,…,An出发配合使用基本推理公式和几条推理规则逐步推演出结论

B137命题逻辑的推理定理（基本推理公式）以下蕴涵式皆为重言式：(a)附加律

A

(A∨B)

(b)化简律

(A∧B)

A

(c)假言推理/分离式

(A

B)∧A

B

(d)析取三段论

(A∨B)∧

B

A(e)拒取式

(A

B)∧

B

A(f)假言三段论

(A

B)∧(B

C)

(A

C)

138命题逻辑的推理主要的推理规则：(a)前提引入规则在证明的任何步骤上，都可引入前提。(b)结论引入规则在证明的任何步骤上，所证明的结论都可以作为后续证明的前提。(c)代入规则与命题逻辑等值演算中的代入规则相同。(d)置换规则在证明的任何步骤上，命题公式中的任何子命题公式都可以用与之等值的命题公式置换139(AÞB)∧((B∧C)Þr)Þ((A∧C)Þr)是重言式推理理论例:构造下列推理的论证前提：p∨q,p

r,s

t,

s

r,

t结论：q(1)s

t

前提引入(2)

t

前提引入(3)

s (1)(