《离散数学》命题逻辑

第1章命题逻辑

命题逻辑

逻辑是研究推理的科学。

数理逻辑是用数学方法研究推理的形式结构和推理规律的数学学科。由于它使用一套符号来表达各种推理的逻辑关系，因此数理逻辑又称为符号逻辑。从广义上讲，数理逻辑包括集合论、模型论、递归论、证明论和命题演算、谓词演算，但本书只研究两个演算：命题演算和谓词演算两个演算。数理逻辑研究的中心问题是推理，而推理的前提与结论都是表达判断的陈述句，因而表达判断的陈述句构成了推理的基本单位。数理逻辑称之为命题。

第1章命题逻辑一、命题定义1.1

能判断真假的陈述句叫做命题。

该定义有两层含义：

(1)命题是陈述句。其他的语句，如疑问句、祈使句、感叹句均不是命题；

(2)这个陈述句对事物的判断是否符合客观事实是可以给出结论的：不是真（符合客观事实）就是假（不符合客观事实），不能不真也不假，也不能既真又假，所以又称二值逻辑。1.1命题符号化及联结词二、命题的真值命题所表示的判断结果称为命题的真值。⑴真值只取两个值：真（判断与事实相符）或假（判断与事实不符）。通常用1（或字母T）表示真，用0（或字母F）表示假。⑵真命题：真值为真的命题。⑶假命题：真值为假的命题。1.1命题符号化及联结词例6.1.1

判断下列语句是否为命题，并指出其真值。（1）北京是中国的首都。（2）5可以被2整除。（3）2+2=5。（4）请勿吸烟。祈使句（5）乌鸦是黑色的吗？疑问句（6）这个小男孩多勇敢啊！感叹句（7）地球外的星球上存在生物。（8）我正在说谎。悖论注意：一个语句本身是否能分辨真假与我们是否知道它的真假是两回事。也就是说，对于一个句子，有时我们可能无法判定它的真假，但它本身却是有真假的，那么这个语句是命题，否则就不是命题。悖论不是命题。1.1命题符号化及联结词判断一个句子是否为命题1、是否为陈述句2、真值是否唯一X+y>51+101=110真值是否唯一与我们是否知道它的真值是两回事三、命题的分类原子命题（AutomicProposition）：不能再分解为更简单的陈述句的命题；也称简单命题。复合命题（CompoundProposition）：由若干简单命题用联结词联结成的命题。例如：“雪是白的”是原子命题；“昨天下雨，而且打雷”，“如果明天天晴我就去打球或者游泳”都是复合命题。

1.1命题符号化及联结词四、命题的表示引进数学符号来表示命题。常用大写英文字母A,B,…,P,Q或带下标的字母P1,P2,P3,

…,或数字(1),[2],…,等表示命题，称之为命题标识符。例如：

P：罗纳尔多是球星。

Q：5是负数。

P3：明天天气晴。

(2)：太阳从西方升起。皆为符号化的命题，其真值依次为1、0、1或0、0。1.1命题符号化及联结词命题标识符有命题常量、命题变元和原子变元之分。命题常元：真值确定的命题标识符。命题变元：真值不确定，仅表示任意命题的位置标志。原子变元：当命题变元表示原子命题时，该变元称为原子变元如果命题符号P代表命题常元则意味它是某个具体命题的符号化，如果P代表命题变元则意味着它可指代任何具体命题。1.1命题符号化及联结词一、否定联结词“

”（或“

”）否定联结词是一元联结词。相当于日常用语中的“非”，“不”，“无”，“没有”等。

设P为一命题，P的否定是一个新的复合命题,称为P的否定式，记作“

P”，读作“非P”。

P为真当且仅当P为假。

P

P

0

1

1

01.1命题符号化及联结词例6.1.2.P:天津是一个城市.Q:3是偶数.于是:┐P:天津不是一个城市.

┐Q:3不是偶数.例6.1.3.P:苏州处处清洁.Q:这些都是男同学.┐P:苏州不处处清洁(注意,不是处处不清洁).┐Q:这些不都是男同学.1.1命题符号化及联结词二、合取联结词“∧”合取词是二元联结词。相当于自然语言中的“与”、“并且”、“而且”、“也”等。设P,Q为二命题，复合命题“P与Q”记作P∧Q。P∧Q为真当且仅当P和Q同时为真。

PQ

P∧Q

00

0

01

0

10

0

11

11.1命题符号化及联结词例6.1.4.

将下列命题符号化.(1)李平既聪明又用功.(2)李平虽然聪明,但不用功.(3)李平不但聪明,而且用功.(4)李平不是不聪明,而是不用功.解:

设P:李平聪明.Q:李平用功.则(1)P∧Q(2)P∧┐Q(3)P∧Q(4)┐(┐P)∧┐Q注意：不要见到“与”或“和”就使用联结词∧！例如:(1)李敏和李华是姐妹。

(2)李敏和张华是朋友。1.1命题符号化及联结词1.1命题符号化及联结词例6.1.5.

试生成下列命题的合取.(1)P:我们在6-503.Q:今天是星期二.

(2)S：李平在吃饭.R：张明在吃饭.解:(1)P∧Q:我们在6-503且今天是星期二.(2)S∧R:李平与张明在吃饭.三、析取联结词“∨”析取词是二元联结词。相当于自然语言中的“或”、“要么…要么…”等。设P,Q为二命题，复合命题“P或Q”，记作P∨Q。P∨Q为真当且仅当P与Q中至少有一个为真。

PQ

P∨Q

00

0

01

1

10

1

11

1在现代汉语中，“或”有“可兼或”和“排斥或”之分。这里只是“可兼或”。例6.1.6（1）小王爱打球或爱跑步。（可兼或）

设P：小王爱打球。Q：小王爱跑步。则上述命题可符号化为：P∨Q1.1命题符号化及联结词1.1命题符号化及联结词（2）林芳学过英语或法语。（可兼或）设P：林芳学过英语。Q：林芳学过法语。则上述命题可符号化为：P∨Q（3）派小王或小李中的一人去开会。（排斥或）

设P：派小王去开会。Q：派小李去开会。则上述命题可符号化为：(P∧┐Q)∨(┐P∧Q)四、蕴含联结词“

”蕴含词是二元联结词。相当于自然语言中的“若…则…”、“如果…就…”、“只有…才…”。设P,Q为二命题,复合命题“若P则Q”记作P

Q。并称P为前件，Q为后件。P

Q为假当且仅当P为真且Q为假。

PQP

Q

00

1

01

1

10

0

11

11.1命题符号化及联结词例6.1.7

将下列命题符号化。1）天不下雨，则草木枯黄。

P：天下雨。Q：草木枯黄。则原命题可表示为：┐P→Q。2）如果小明学日语，小华学英语，则小芳学德语。

P：小明学日语.Q：小华学英语.R：小芳学德语.则原命题可表示为：(P∧Q)→R3）只要不下雨，我就骑自行车上班。

P：天下雨。Q：我骑自行车上班。则原命题可表示为：┐P→Q。1.1命题符号化及联结词4）只有不下雨，我才骑自行车上班。

P：天下雨。Q：我骑自行车上班。则原命题可表示为：

Q

→┐P。注意:

(1)与自然语言的不同：前件与后件可以没有任何内在联系！

(2)在数学中，“若P则Q”往往表示前件P为真，则后件Q为真的推理关系.但数理逻辑中，当前件P为假时，P→Q的真值为真。1.1命题符号化及联结词“如果p，则q”的不同表述法很多：

若p，就q

只要p，就qp仅当q

只有q

才p

除非q,才p除非q,否则非p，1.1命题符号化及联结词

例：设p:天冷，q:小王穿羽绒服，将下列命题符号化

(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候.注意：

p

q与

p

q

等值（真值相同）p

qp

qp

qp

qq

p

q

pq

pq

p1.1命题符号化及联结词五、等价联结词“

”等价联结词是二元联结词。相当于自然语言中的“等价”、“当且仅当”、“充要条件”等，真值表如右图。

设P,Q为二命题，复合命题“P当且仅当Q”记作P

Q。

P

Q为真当且仅当P，Q真值相同。

PQ

P

Q

00

1

01

0

10

0

11

11.1命题符号化及联结词注：（1）P仅当Q可译为P→QP当Q可译为Q→PP当且仅当Q译为P

Q

（2）命题P

Q所表达的逻辑关系是,P与Q互为充分必要条件,相当于(P

Q)∧(Q

P).

双条件联结词连接的两个命题之间可以没有因果关系。例6.1.8分析下列命题的真值.(1)2+2=4当且仅当3是奇数.(P

Q)P：2+2=4.Q：3是奇数.

(2)2+2=4当且仅当3不是奇数.(P

┐Q)(3)2+2≠4当且仅当3是奇数.(┐P

Q)(4)2+2≠4当且仅当3不是奇数.(┐P

┐Q)1.1命题符号化及联结词5种联结词类似5种运算符，称之为逻辑运算符，有运算的优先级顺序：联结词的优先顺序为：

,

,

,

,;

如果出现的联结词同级，又无括号时，则按从左到右的顺序运算;若遇有括号时，应该先进行括号中的运算。1.1命题符号化及联结词一、概念定义1.3命题公式按下列规则生成：（1）单个命题常项或变项p,q,r,...,0,1是命题的公式；（2）如果α是命题公式，则

α也是命题公式；（3）如果α和β是命题公式，则α

β，α

β，α→β，α

β均是命题公式；（4）只有有限次地利用（1）—（3）形成的符号串才是命题公式。例如：

(P

Q)，P→(P

Q)等都是命题公式，而CP→Q，R→P等不是命题公式。1.2命题公式及分类注:

(1)命题公式也称为合式公式，由命题常项、命题变项、联结词和括弧组成。

(2)如果把公式中的命题变元代以原子命题或复合命题，则该公式便是一个复合命题。因此，对复合命题的研究可化为对命题公式的研究。⑶命题公式一般不是命题,仅当公式中的命题变元用确定的命题代入时，才得到一个命题。其真值依赖于代换变元的那些命题的真值。⑷日常生活中的推理问题是用自然语言描述的，因此要进行推理演算必须先把自然语言符号化（或形式化）成逻辑语言，即命题公式。然后再根据逻辑演算规律进行推理演算。1.2命题公式及分类二、命题符号化(1)分析出各简单命题,将它们符号化;(2)使用合适的联结词,把简单命题逐个的联结起来,组成复合命题的符号化表示.例6.3.2

将下列用自然语言描述的命题符号化。（1）我和他既是弟兄又是同学。解令P：我和他是弟兄；Q：我和他是同学，则该语句可符号化为P∧Q。（2）我和你之间至少有一个要去海南岛。解令P：我去海南岛；Q：你去海南岛，则该语句可符号化为P∨Q。1.2命题公式及分类（3）如果他没来见你，那么他或者是生病了，或者是不在本地。解令P：他来见你；Q：他生病；R：他在本地，则该语句可符号化为¬P→(Q∨¬R)。（4）n是偶数当且仅当它能被2整除。解令P：n是偶数；Q：n能被2整除，则该语句可符号化为P↔Q。1.2命题公式及分类三、公式的解释或赋值设P1,P2,…,Pn是出现在公式G中的全部的命题变元,指定P1,P2,…,Pn的一组真值，则称这组真值为G的一个赋值或解释，记作I。公式G在I下的真值记作TI(G)。若指定的一组值使A的真值为真(假),称这组值为A的成真(假)赋值。例如:对公式(P

Q)∧R，赋值011(即令P=0，Q=1，R=1)为(P

Q)∧R的成真赋值。

赋值011也可记作｛P,Q,

R｝。含有n个命题变元的公式共有2n组不同的赋值。1.2命题公式及分类四、真值表将命题公式G在其所有解释下所取的真值列成一个表,称做命题公式G的真值表。为方便构造真值表，特约定如下：①命题变元按字典序排列。②对每个指派，以二进制数从小到大或从大到小顺序列出。③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。1.2命题公式及分类PQRQ

RP

(Q

R)

(P

(Q

R))000001010011100101110111011101111111011100001000例6.3.1

利用真值表求命题公式

(P→(Q

R))的成真指派和成假指派。1.2命题公式及分类五、命题公式的分类重言式/永真式：若G在所有解释下都是真的，则称G为重言式或永真式。矛盾式/永假式：G在所有解释下都是假的，则称G为称为矛盾式或永假式。可满足式：若G不是恒假的。几点说明

1）G是可满足式的等价定义是：G至少存在一个成真指派。

2）重言式一定是可满足式，但反之不真。1.2命题公式及分类

3）如何利用好真值表来判断公式的类型：①若真值表最后一列全为1，则公式为重言式；②若真值表最后一列全为0，则公式为矛盾式；③若真值表最后一列中至少有一个1，则公式为可满足式。1.2命题公式及分类例6.3.2

判断下列公式的类型。(1)(P∧Q)

Q解令

=(P

Q)

Q

PQP

Q

00011011000111111.2命题公式及分类(2)(Q

P)∧(¬P∧Q)解

令

=(Q

P)

(¬P

Q)

PQQ

P¬P

Q

000110111011010000001.2命题公式及分类(3)(P∨¬Q)

(¬P∧Q∧R)解

令

=(P

¬Q)

(¬P

Q

R)

PQRP

¬Q¬P

Q

R

0000010100111001011101111100111100010000001100001.2命题公式及分类一、公式等值（等价）问题：是否存在两个命题公式G和H，在任意解释下它们的真值都相同？若存在，怎样用已有的概念描述上述现象？解答：存在，比如n=2的命题公式,P

Q与(PQ)在任意解释下均有系统的真值。描述：GH是重言式给这种现象引入一个概念：数学上用〔相等，等价〕，这里用〔等价、等值〕。1.3等值演算定义1.10

设G，H是两个命题公式，若G

H是重言式，则称G与H等价（等值），记作G

H。⑴G

H当且仅当G

H为重言式。⑵

与

是两个完全不同的符号。

不是命题联结词，而是公式间的关系符号，α

β不表示一个公式，即不代表命题，它表示公式α与公式β有等价关系，

是命题联结词，α

β是一个公式，表示某个命题。公式之间的等价关系的特点：自反的对称的传递的1.3等值演算二、公式等价（等值）的判定方法（1)判断两个公式α与β是否等值，用真值表法判断α

β是否为重言式。

例1.7

判断

(P

Q)与

P

Q这两个命题公式是否等值。PQ

(P

Q)

P

Q

(P

Q)

(

P

Q)00011011100010001111这一列可不要1.3等值演算三、公式等价的判定方法（2)根据已知的等价公式,推演出另外一些等价公式的过程称为等值演算.常用的等价公式：（1）双重否定律：α

(

α)

（2-3）等幂律：α

α

α，α

α

α（4-5）交换律：

α

β

β

α，α

β

β

α（6-7）结合律

(α

β)

γ

α

(β

γ)，

(α

β)

γ

α

(β

γ)1.3等值演算（8-9）分配律

α

(β

γ)

(α

β)

(α

γ)（

对

的分配律）

α

(β

γ)

(α

β)

(α

γ)（

对

的分配律）（10-11）德摩根律

(α

β)

α

β，

(α

β)

α

β（12-13）吸收律

α

(α

β)

α，α

(α

β)

α（14-15）零律：α

1

1，α

0

0（16-17）同一律：α

0

α，α

1

α（18）排中律：α

α

1（19）矛盾律：α

α

01.3等值演算（20）蕴含等值式

α

β

α

β(21)等价（双条件）等值式

α

β

(α

β)

(β

α)，

α

β

(α

β)

(

α

β)（22）假言易位

α

β

β

α（23）等价否定等值式

α

β

α

β（24）归谬论

(α

β)

(α

β)

α1.3等值演算等值演算中的置换规则置换：用一个命题公式代换另一个命题公式中的一个子公式。

定理1.1（置换定理）设

(A)是含命题公式A的命题公式，

(B)是用命题公式B置换了

(A)中的A之后的得到的命题公式，如果A

B，则

(A)

(B)。

1.3等值演算例6.4.1

用等值演算法证明

(P

Q)→R

(P→R)

(Q→R)。证明(P

Q)

R

(P

Q)

R（蕴含等值式）

(

P

Q)

R（德摩根律）

(

P

R)

(

Q

R)（分配律）

(P

R)

(

Q

R)（蕴含等值式）

(P

R)

(Q

R)（蕴含等值式）

1.3等值演算例6.4.2

用等值演算法判断下列公式的类型。（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

P)

(

Q

P))

Q

(1

(

Q

P))

Q

(

Q

Q)

P

1

P

1

因此该公式是重言式。1.3等值演算（2）

(P→(P

Q))

R

解

(P

(P

Q))

R

(

P

P

Q)

R

(P

P

Q)

R

0

R

0因此该公式是矛盾式。1.3等值演算（3）P

(((P

Q)

P)→Q)

解P

(((P

Q)

P)

Q)

P

(

((P

Q)

P)

Q)

P

(

((P

P)

(Q

P))

Q)

P

(

(0

(Q

P))

Q)

P

(

Q

P

Q)

P

1

P

从最后结果可以看出该公式既不是重言式，也不是矛盾式，而是可满足式。

1.3等值演算

例6.4.3

设有A，B，C，D四人做百米竞赛，观众甲，乙，丙分别对比赛的名次进行了预测：甲说C第一，B第二；乙说C第二，D第三；丙说A第二，D第四；比赛结束后发现甲，乙，丙每人报告的情况都是各对一半，试问实际名次如何（无并列者）？

1.3等值演算解设Pi，Qi，Ri，Si分别表示A，B，C，D是第i（i=1,2,3,4）名，由于甲，乙，丙每人报告的情况都各对一半，故有下面三个等值式：①(R1

Q2)

(

R1

Q2)

1②(R2

S3)

(

R2

S3)

1③(P2

S4)

(

P2

S4)

1因为重言式的合取仍为重言式，所以①

②

1。即

1

((R1

Q2)

(

R1

Q2))

((R2

S3)

(

R2

S3))

(R1

Q2

R2

S3)

(R1

Q2

R2

S3)

(

R1

Q2

R2

S3)

(

R1

Q2

R2

S3)

1.3等值演算由于C不能既第一又第二，B和C不能并列第二，所以

R1

Q2

R2

S3

0

R1

Q2

R2

S3

0于是得④(R1

Q2

R2

S3)

(

R1

Q2

R2

S3)

1再将③与④合取得③

④

1，即1

((P2

S4)

(

P2

S4))

((R1

Q2

R2

S3)

(

R1

Q2

R2

S3))

(P2

S4

R1

Q2

R2

S3)

(P2

S4

R1

Q2

R2

S3)

(

P2

S4

R1

Q2

R2

S3)

(

P2

S4

R1

Q2

R2

S3)1.3等值演算由于A，B不能同时第二，D不能第三又第四，所以

P2

S4

R1

Q2

R2

S3

0

P2

S4

R1

Q2

R2

S3

0

P2

S4

R1

Q2

R2

S3

0于是可得⑤P2

S4

R1

Q2

R2

S3

1因此C第一，A第二，D第三，B第四。

1.3等值演算四、联结词全功能集前面已经引入了五中联结词，逻辑设计中还常用到其它的一些联结词：异或（排斥或）联结词

与非联结词

或非联结词

在一个形式系统中引入多少联结词好？自然系统中越多越好，应用方便公理系统中越少越好，研究方便一个联结词的集合应该满足什么条件？1.4联结词全功能集对于命题公式，我们关注的是它的真值情况。N个命题变元的命题公式，每个变元有两种赋值情况，共有2N中赋值情况。而每种赋值，又有两种结果，共有

种不同的赋值、取值情况。一个好的方法是，每种赋值、取值情况用一个联结词表示。可以用函数的观点来研究命题公式的变元赋值与最终命题公式的取值之间的关系1.4联结词全功能集定义

称定义域为{00…0,00…1,…,11…1}，值域为{0,1}的函数是n元真值函数，定义域中的元素是长为n的0,1串.

常用F:{0,1}n

{0,1}表示F是n元真值函数.

共有个n元真值函数.例如F:{0,1}2

{0,1}，且F(00)=F(01)=F(11)=0，F(01)=1，则F为一个确定的2元真值函数.1.4联结词全功能集对于任何一个含n个命题变项的命题公式A，都存在惟一的一个n元真值函数F为A的真值表.等值的公式对应的真值函数相同.下表给出所有2元真值函数对应的真值表,每一个含2个命题变项的公式的真值表都可以在下表中找到.

例如：p

q,

p

q,(

p

q)

(

(p

q)

q)等都对应表中的1.4联结词全功能集2元真值函数对应的真值表pq00011011

00000000000011110011001101010101

pq00011011

11111111000011110011001101010101

1.4联结词全功能集pq00011011

00000000000011110011001101010101

pq00011011

11111111000011110011001101010101

1.4联结词全功能集

0

p

q的非

pq

p的非

q异或

qq

p

pp

q

1联结词的全功能集

定义

在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为冗余的联结词，否则称为独立的联结词.例如,在联结词集{

,

,

,

,

}中，由于

p

q

p

q,所以，

为冗余的联结词;类似地，

也是冗余的联结词.又在{

,

,

}中，由于

p

q(p

q)，所以，

是冗余的联结词.类似地，

也是冗余的联结词.1.4联结词全功能集联结词的全功能集(续)定义

设S是一个联结词集合，如果任何n(n

1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词全功能集.说明：若S是联结词全功能集，则任何命题公式都可用S中的联结词表示.

若S1,S2是两个联结词集合，且S1

S2.若S1是全功能集，则S2也是全功能集.

若一个联结词的全功能集中不含冗余的联结词，则称它是极小全功能集。1.4联结词全功能集联结词的全功能集实例(6)S6={

}极小全功能集(7)S8={

}极小全功能集(8){

,

}极小全功能集

(1)S1={

,

,

,

}(2)S2={

,

,

,

,

}

(3)S3={

,

}(4)S4={

,

}(5)S5={

,

}

而{

},{

}等则不是联结词全功能集.

1.4联结词全功能集四、对偶原理定义

如果命题公式α中只出现命题变元、命题常元、命题联结词

、

和

，则称α为限制性命题公式。

定义1.7

在限制性公式α中，将联结词

换成

，将

换成

，将0换成1，将1换成0，所得到的公式称为α的对偶式，记为α*。1.5对偶与范式显然，α和α*互为对偶式。例如，公式

((P

Q)

(

R))与公式

((P

Q)

(

R))互为对偶式。

定理1.2

设A和A*是互为对偶的两个公式，P1,P2,…,Pn是其命题变元，并把A和A*写成函数的形式，则：

A(P1,P2,…,Pn)

A*(

P1,

P2,…,

Pn)A(

P1,

P2,…,

Pn)

A*(P1,P2,…,Pn)

1.5对偶与范式定理1.3（对偶原理）设α(P1,P2,…,Pn)和β(P1,P2,…,Pn)是两个公式，若α

β，则α*

β*。由对偶原理，A为重言式，则A*为矛盾式。如果P

(P

0)

1，则P

(P

0)

01.5对偶与范式一、简单析取（合取）式简单析取式:仅由有限个命题变项及其否定构成的析取式。如p,

q,p

q,p

q

r,…简单合取式:仅由有限个命题变项及其否定构成的合取式。如p,

q,p

q,p

q

r,…注意：（1）一个简单析取式是重言式当且仅当它同时含有某个命题变元及其否定式,如p

p

q。（2）一个简单合取式是矛盾式当且仅当它同时含有某个命题变元及其否定式，如p

p

r。1.5对偶与范式二、析取（合取）范式定义1.19

仅由有限个简单合取式构成的析取式称为析取范式。即：析取范式具有形式α1

α2

…

αn，其中αi(i=1,2,…,n)为简单合取式。命题公式(P

Q)

(

P

Q)是析取范式。定义1.19仅由有限个简单析取式构成的合取式称为合取范式。即：合取范式具有形式α1

α2

…

αn，其中αi(i=1,2,…,n)为简单析取式。

(P

R)

(P

Q

R)

(

P

R)是合取范式。1.5对偶与范式定义

析取范式与合取范式统称为范式。合(析)取范式的对偶式是析(合)取范式.一个析取范式是矛盾式它的每个简单合取式都是矛盾式。一个合取范式是重言式它的每个简单析取式都是重言式。定理1.4（范式存在定理）

任一命题公式都存在着与之等价的析取范式和合取范式。1.5对偶与范式下面给出求任一公式的析取范式和合取范式的步骤:

（1）利用蕴含等值式和等价等值式消去公式中的联结词“→”和“

”；

α→β⇔¬α∨β；

α↔β⇔(α→β)∧(β→α)（2）利用德摩根律和双重否定律将联结词“

”消去或内移到各命题变元之前；

¬(α∨β)⇔¬α∧¬β；¬(α∧β)⇔¬α∨¬β；¬(¬α)⇔α（3）利用分配律、交换律、结合律将公式化为所需要的范式。

¬(A∨B)

¬A∧¬B¬(A∧B)

¬A∨¬B

1.5对偶与范式例1.14

求((P

Q)

R)

P的析取范式和合取范式。解（1）求合取范式((P

Q)

R)

P

(

(P

Q)

R)

P（消去

）

(

(P

Q)

R)

P

((

P

Q)

R)

P（

深入）

((

P

Q)

R)

P

((P

Q)

R)

P

(P

Q

P)

(

R

P)（

对

的分配律）再利用交换律和等幂律得

(P

Q

P)

(

R

P)

(P

Q)

(

R

P)

可见，(P

Q)

(

R

P)也是原公式的合取范式，这说明与某个命题公式等值的合取范式不是惟一的。

1.5对偶与范式（2）析取范式用

对

的分配律就可得到析取范式，即

((P

Q)

R)

P

((P

Q)

R)

P

(P

R)

(Q

R)

P(

对

分配律)

最后结果为原公式的析取范式。利用交换律和吸收律得P

(Q

R)，此公式也是原公式的析取范式，由此可见，与命题公式等价的析取范式也不是惟一的。注意：

(1)单个命题变元既是简单合取式，又是简单析取式；

(2)公式P∧Q∧R既可以看成是合取范式，也可以看成是析取范式1.5对偶与范式例6.5.2：求(P

Q)

R的析取范式与合取范式。解:原式

((P

Q)

R)∧(R

(P

Q))

(┐(P

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

Q))

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

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

((P∨R)∧(┐Q∨R)∧(┐R∨┐P∨Q)(合取范式)

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

(P∧┐Q∧┐R)∨(R∧┐P)∨(R∧Q)(析取范式)1.5对偶与范式

例6.5.2

判别公式((P→Q)

P)→Q是否为重言式或矛盾式。

解

((P

Q)

P)

Q

((

P

Q)

P)

Q

(

P

Q)

P

Q

(P

Q)

P

Q

(P

P

Q)

(

Q

P

Q)

在公式的合取范式中，每一个简单析取式均含有互补对，为重言式，因此原式为重言式。

1.5对偶与范式定义

在含有n个命题变项的简单合取式中，若每个命题变元与其否定不同时存在，而二者之一必须出现且仅出现一次，且第i（1

i

n）个命题变元或其否定出现在左起的第i位上（若命题变元无角标，则按字典顺序），这样的简单合取式为极小项.⑴n个命题变元共可产生2n个不同的极小项，其中每个极小项都有且仅有一个成真指派。(2)在极小项中，将命题变元看成1，命题变元的否定看成0，则每个极小项惟一地对应一个二进制数，若该二进制数对应的十进制数为i，则该极小项记作mi，1.5对偶与范式由三个命题变元P,Q,R共可产生8个极小项，分别为：¬P∧¬Q∧¬R对应000，记为m0¬P∧¬Q∧R对应001，记为m1¬P∧Q∧¬R对应010，记为m2¬P∧Q∧R对应011，记为m3P∧¬Q∧¬R对应100，记为m4P∧¬Q∧R对应101，记为m5P∧Q∧¬R对应110，记为m6P∧Q∧R对应111，记为m71.5对偶与范式定义1.21

设命题公式G中含n个命题变元，如果G的析取范式中的简单合取式都是极小项，则称该析取范式为G的主析取范式。定理

任何命题公式de主析取范都是存在的，并且是唯一的。1.5对偶与范式求公式的主析取范式的步骤：(1)先求析取范式①利用蕴含等值式和等价等值式消去公式中的联结词“→”和“

”；

②利用德摩根律和双重否定律将联结词“

”消去或移到命题变元前；

③利用分配律将公式化为析取范式；

(2)若析取范式的某简单合取式B中不含命题变元Pi,也不含

┐Pi，则添加(Pi

┐Pi),然后应用分配律展开.即

B

B1B

(Pi

┐Pi)(B

Pi)(B

┐Pi).（3)将重复出现的命题变元、重复出现的极小项、矛盾式都消去;如P

P用P代，P

P用0代。(4)将极小项按由小到大的顺序排列，并用

∑(I,j,k)形式表示。1.5对偶与范式例1.15：求((P

Q)

R)P的主析取范式。解:原式

┐(┐(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)

(P∧Q∧R)∨(P∧Q∧┐R)∨(P∧┐Q∧R)∨(P∧┐Q∧┐R)∨(┐P∧Q∧┐R)(主析取范式)

m7∨m6∨m5∨m4∨m2

m2∨m4∨m5∨m6∨m7

∑(2,4,5,6,7)1.5对偶与范式主析取范式与真值表极小项mi的成真赋值为i对应的二进制；依据命题公式主析取范式的极小项，可得到命题公式的成真赋值。由命题公式的主析取范式中没有出现的极小项可确定命题公式的成假赋值。由上可画出真值表反之，可有真值表得到主析取范式真值表的成真赋值决定全部极小项；由极小项得到主析取范式1.5对偶与范式求((P

Q)

R)P的真值表解答：由((P

Q)

R)P∑(2,4,5,6,7)有下表PQR((P

Q)

R)P000000100101011010011011110111111.5对偶与范式例

用真值表法求公式(

P→R)

(P

Q)的主析取范式。PQR

P

RP

Q(

P

R)

(P

Q)000001010011100101110111010111111100001101000011公式所在的列有三个1，它们分别对应于编码001，110，111，因此所求的主析取范式为：m1

m6

m7，即原式

∑(2,6,7)1.5对偶与范式主析取范式的用途(1)求公式的成真赋值和成假赋值例如(p

q)

r

m1

m3

m5

m6

m7，其成真赋值为001,011,101,110,111，其余的赋值000,010,100为成假赋值.(2)判断两个公式是否等值

任何命题公式的主析取范式都是唯一的，因而AB当且仅当A

B有相同的主析取范式。(3)判断公式的类型

设A含n个命题变项，则

A为重言式

A的主析取范式含2n个极小项A为矛盾式

A的主析取范式为0A为非重言式的可满足式

A的主析取范式中至少含一个且不含全部极小项1.5对偶与范式例

用主析取范式判断下述两个公式是否等值：⑴

p

(q

r)与

(p

q)

r⑵

p

(q

r)与

(p

q)

r解

p

(q

r)=m0

m1

m2

m3

m4

m5

m7

(p

q)

r

=m0

m1

m2

m3

m4

m5

m7(p

q)

r

=m1

m3

m4

m5

m7显见，⑴中的两公式等值，而⑵的不等值.

1.5对偶与范式

例

利用求主析取范式的方法判别公式((P→Q)

P)→Q的类型。

解求公式的主析取范式为：

((P

Q)

P)

Q

((

P

Q)

P)

Q

(

P

Q)

P

Q

(P

Q)

P

Q

(P

Q)

(

P

(

Q

Q))

((P

P)

Q)

(

P

Q)

(

P

Q)

(P

Q)

(P

Q)

m0

m1

m2

m3

由于公式的主析取范式包含了所有的极小项，因此原公式为重言式。1.5对偶与范式定义1.22极大项定义

在含有n个命题变元的简单析取式中，若每个命题变元与其否定不同时存在，而二者之一必须出现且仅出现一次，且第i（1

i

n）个命题变元或其否定出现在左起的第i位上（若命题变元无角标，则按字典顺序），这样的简单析取式为极大项.⑴n个命题变元共可产生2n个不同的极大项，其中每个极大项都有且仅有一个成假指派。(2)在极大项中，将命题变元看成0，命题变元的否定看成1，则每个极大项惟一地对应一个二进制数，若该二进制数对应的十进制数为i，则该极大项记作Mi，1.5对偶与范式三个变元P,Q,R可以产生8个极大项，分别为：P∨Q∨R对应000，记为M0P∨Q∨¬R对应001，记为M1P∨¬Q∨R对应010，记为M2P∨¬Q∨¬R对应011，记为M3¬P∨Q∨R对应100，记为M4¬P∨Q∨¬R对应101，记为M5¬P∨¬Q∨R对应110，记为M6¬P∨¬Q∨¬R对应111，记为M71.5对偶与范式定义1.23

设命题公式G中含n个命题变元，如果G的合取范式中的简单析取式都是极大项，则称该合取范式为G的主合取范式。定理

任何命题公式的主合取范都是存在的，并且是唯一的。推演法求主合取范式的步骤：（1）求合取范式A’（2）若A’的某一个简单析取式B中不含某变元pi，也不含

pi，则将B展开成

B

B

0

B

(pi

pi)

(B

pi)

(B

pi)

1.5对偶与范式例

求公式

A=(p

q)

r的主合取范式.(p

q)

r

(p

r)

(q

r)（合取范式）

①

p

r

p

(q

q)

r

(p

q

r)

(p

q

r)

M0

M2,

②q

r

(p

p)

q

r

(p

q

r)

(

p

q

r)

M0

M4③

②,③代入①并排序，得

(p

q)

r

M0

M2

M4

(0,2,4)1.5对偶与范式主合取范式的用途：

(1)求公式的成真赋值和成假赋值.极大项对应成假赋值。缺项对应成真赋值。(2)判断公式的类型

设A含n个命题变项，则

A为重言式

A的主合取范式为1.A为矛盾式

A的主合析取范式含2n个极大项A为非重言式的可满足式

A的主合取范式中至少含一个且不含全部极大项

1.5对偶与范式如何求主合取范式1、真值表法2、推演法3、利用主合取范式与主析取范式之间的关系。设mi和Mi是命题变元P1,P2,…,Pn形成的极小项和极大项，则

mi

Mi，

Mi

mi1.5对偶与范式

先求出主析取范式找出主析取范式中没有的极小项求对应的极大项写主合取范式1.5对偶与范式某公式的主析取范式为：m1

m6

m7，其缺少的极小项有0,m2,m3,m4,m5.则对应的大项为M0,M2,M3,M4,M5,故所求的主合取范式为：M0

M2

M3

M4

M5

，即

(0,2,3,4,5)1.5对偶与范式

总结：矛盾式的主析取范式是空公式，定义它为0，其主合取范式由所有极大项的合取构成；重言式的主合取范式是空公式，定义它为1，其主析取范式必由所有极小项的析取构成。利用一个公式的主范式可以判别这个公式是否为重言式或矛盾式。1.5对偶与范式例6.5.7：求((P

Q)

R)

P的主合取范式。解:原式

┐(┐(P∨Q)∨R)∨P

(P∨Q)∧(┐R∨P

)(合取范式)((P∨Q)∨(R∧┐R

))∧((┐R∨P

)∨(Q∧┐Q))

(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)1.5对偶与范式例6.5.8：求(P

Q)

R的析取范式与合取范式。解:原式

(P∨R)∧(┐Q∨R)∧(┐R∨┐P∨Q)(合取范式)

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

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

)

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

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

)

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

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

)

(主合取范式)

M0∧M2∧M5∧M6

(0,2,5,6)1.5对偶与范式

例6.5.9

利用求主范式的方法判别公式((P→Q)

P)→Q是否为重言式或矛盾式。

解求公式的主析取范式为：

((P

Q)

P)

Q

((

P

Q)

P)

Q

(

P

Q)

P

Q

(P

Q)

P

Q

(P

Q)

(

P

(

Q

Q))

((P

P)

Q)

(

P

Q)

(

P

Q)

(P

Q)

(P

Q)

m0

m1

m2

m3

由于公式的主析取范式包含了所有的极小项，因此原公式为重言式。

1.5对偶与范式当然，利用求主合取范式也可以得到同样的结论，即：

((P

Q)

P)

Q

((

P

Q)

P)

Q

(

P

Q)

P

Q

(P

Q)

P

Q

(P

P

Q)

(

Q

P

Q)

1

1

1

由于公式的主合取范式是一个空公式，因此原公式为重言式。

1.5对偶与范式

例6.5.10

求公式(

P→R)

(P

Q)的主析取范式和主合取范式。

解令

=(

P

R)

(P

Q)

（1）求主合取范式

(P

R)

(

P

Q)

(P

Q)

(P

(Q

Q)

R)

(

P

Q

(R

R))

(P

Q

(R

R))

(P

Q

R)

(P

Q

R)

(

P

Q

R)

(

P

Q

R)

(P

Q

R)

(P

Q

R)

(P

Q

R)

(P

Q

R)

(P

Q

R)

(

P

Q

R)

(

P

Q

R)

M0

M2

M3

M4

M5

此即

的主合取范式1.5对偶与范式

例6.5.17

某单位要在甲，乙，丙三人中选派1～2名出差，选派时需满足如下条件：（1）若甲去，则丙同去；（2）若乙去，则丙不能去；（3）若丙不去，则甲或乙可以去。问有几种选派方案？

解

设P：派甲去出差；Q：派乙去出差；R：派丙去出差。由已知条件可得公式

(P

R)

(Q

R)

(

R

(P

Q))

1.5对偶与范式经过演算可得

(P

R)

(Q

R)

(

R

(P

Q))

(

P

Q

R)

(

P

Q

R)

(P

Q

R)

该公式主析取范式包含3个极小项，因此可知有3种选派方案:①丙去，甲和乙不去；②乙去，甲和丙不去；③甲和丙去，乙不去。1.5对偶与范式一、相关概念前提：已知的命题公式；结论：从前提出发应用推理规则推出的命题公式；推理：从前提推出结论的思维过程。定义1.2.4

若(A1

A2

...

An)

B为重言式，则称A1,A2,...,An推出B的推理正确，B是A1,A2,...,An的逻辑结论或有效结论。称(A1

A2

...

An)

B为由前提A1,A2,...,An推出结论B的推理的形式结构用“A

B”表示A

B是重言式，因而若有前提A1,A2,...,An推出结论B的推理正确，也记作

(A1

A2

...

An)

B。或前提：A1,A2,...,An结论：B注意：“

”不是联结词，“G

H”也不是公式。1.6推理理论判断对立是否正确即为判断条件式是否是重言式，可用真值表法、等值演算法、主析取范式法、构造证明法；当命题变项比较少时，用前3个方法比较方便,此时采用形式结构“A1ÙA2Ù…ÙAk®B”.而在构造证明时，采用如下形式：前提:A1,A2,…,Ak,结论:B例判断下面推理是否正确(1)若今天是1号，则明天是5号.今天是1号.所以明天是5号.解：设p：今天是1号，q：明天是5号.证明的形式结构为:(p®q)Ùp®q

（*）证明（真值表法）真值表略真值表的最后一列全为1，因而(*)是重言式，所以推理真确。（用等值演算法）

(p®q)Ùp®qÛØ((ØpÚq)Ùp)ÚqÛ

ØpÚØqÚq

Û1得证推理正确。（主析取范式）

(p®q)Ùp®qÛ(p

q)Ú

pÚq

(p

q)Ú(

p

(qÚ

q))Ú((pÚ

q)

q)m0Úm1Úm2Úm3Û

(0,1,2,3)可见(*)是重言式，得证推理正确.二、判断推理正确与否的构造证明法注（1）由前提G1,G2,…,Gn

推结论H的推理是否正确与各前提的排列次序无关，因而常把前提中的公式写成集合的形式。注（2）必须把推理的有效性和结论的真实性区别开。据G

H的定义，G为假时G

H为真，G、H都为真时，G

H为真。所以有效的推理不一定产生真实的结论。如果有效的推理中包含假的前提，则结论可能是假；当如果前提为真，则结论一定为真。1.6推理理论

例6.6.1

写出下述推理关系的推理形式。下午小王或去看电影或去游泳。他没去看电影。所以，他去游泳了。

解设P：小王下午去看电影；Q：小王下午去游泳。前提：P

Q，

P

结论：Q

推理形式为:(P

Q)

P

Q

1.6推理理论推理定律（8个,也称基本蕴涵公式）

A

Þ(AÚB)附加律

(AÙB)Þ

A

化简律

(A®B)ÙA

Þ

B

假言推理

(A®B)ÙØB

Þ

ØA

拒取式

(AÚB)ÙØB

Þ

A

析取三段论

(A®B)Ù(B®C)Þ(A®C)假言三段论

(A«B)Ù(B«C)Þ(A«C)等价三段论

(A®B)Ù(C®D)Ù(AÚC)Þ(BÚD)构造性二难6.6公式的蕴涵与形式演绎

构造性证明是一个描述推理过程的命题公式序列，其中的每个命题公式或者是已知的前提，或者是由前面的命题公式应用推理规则得到的结论。推理规则

①前提引入规则－有的书上称为规则P

在推理过程中，可以随时引入已知的前提。

②结论引入规则－有的书上称为规则D

在推理过程中，前面已推出的有效结论（本演绎的中间结论）都可作为后续推理的前提引用。1.6推理理论

③置换规则

在推理过程中，命题公式中的子公式都可以用与之等价的命题公式置换，得到证明的公式序列的另一公式。

④假言推理规则A

B，A|=B⑤附加规则A|=A

B⑥化简规则A

B|=B⑦拒取式规则A

B,

B|=A⑧假言三段论规则A

B,B

C|=A

C⑨析取三段论规则A

B，

B|=A⑩构造性二难规则A

B,C

D,A

C