《离散数学》课件：2-命题逻辑

第二章

命题逻辑

第二章

命题逻辑2.1

命题以及逻辑联结词

2.2

命题公式

2.3

命题公式的等价关系和蕴涵关系

2.4

范式2.5

命题逻辑在二值逻辑器件

和语句逻辑中的应用

2.1命题以及逻辑联结词

2.1.1命题

所谓命题是指一句有真假意义的话。例如：上海是中国最大的城市 今天是星期二 所有素数都是奇数 1+1=2命题用大写英文字母P，Q，…，P1，P2，…，表示。

如果一个命题是真的，就说它的真值是1；

如果一个命题是假的，就说它的真值是0。

也用“1”代表一个抽象的真命题，用“0”代表一个抽象的假命题。

定义2.1.1设P是一个命题，命题“P是不对的”称为P的否定，记以P，读作非P。P是真的当且仅当P是假的。例如：

P：吉大是中国最大的大学。P：吉大不是中国最大的大学。定义2.1.2设P，Q是两个命题，命题“P或者Q”称为P，Q的析取，记以PQ，读作P或Q。规定PQ是真的当且仅当P，Q中至少有一个是真的。例如：

P：今天下雨，Q：今天刮风， PQ：今天下雨或者刮风。定义2.1.3设P，Q是两个命题，命题“P并且Q”称为P，Q的合取，记以PQ，读作P且Q。规定PQ是真的当且仅当P和Q都是真的。例如，P：22=5，Q：雪是黑的，

PQ：22=5并且雪是黑的。

定义2.1.4设P，Q是两个命题，命题“如果P，则Q”称为P蕴涵Q，记以PQ。规定，PQ是假的当且仅当P是真的而Q是假的。例如，P：f(x)是可微的，Q：f(x)是连续的，

PQ：若f(x)是可微的，则f(x)是连续的。由定义知，如果P是假命题，则不管Q是什么命题，命题“如果P，则Q”在命题逻辑中都被认为是真命题。例如，P：22=5，Q：雪是黑的，

于是，命题“如果22=5，则雪是黑的”是真命题。定义2.1.5设P，Q是两个命题，命题“P当且仅当Q”称为P等价Q，记以PQ。规定，PQ是真的当且仅当P，Q或者都是真的，或者都是假的。例如， P：a2+b2=a2，

Q：b=0，

PQ：a2+b2=a2当且仅当b=0。例2.1.1

如果你走路时看书，那么你会成为近视眼。令P：你走路；Q：你看书；R：你会成为近视眼。于是，上述语句可表示为（PQ）R。

例2.1.2

除非他以书面或口头的方式正式通知我，否则我不参加明天的会议。

令P：他书面通知我；Q：他口头通知我；R：我参加明天的会议。

于是，上述语句可表示为(PQ)R。

例2.1.3

设P，Q，R的意义如下：

P：苹果是甜的；Q：苹果是红的；

R：我买苹果。

试用日常语言复述下述复合命题：

(1)(PQ)R (2)(PQ)R解：(1)如果苹果甜且红，那么我买。(2)我没买苹果，因为苹果不甜也不红。2.2命题公式

§2.2.1公式我们用大写的英文字母P，Q，R，…等代表一个抽象的命题，或称为命题符号。定义2.2.1命题符号称为原子。例如，Q，S，…等都是原子。定义2.2.2

命题公式命题逻辑中的公式，是如下定义的一个符号串： (1) 原子是公式；

(2) 0、1是公式；

(3) 若G，H是公式，则(G)，(GH)， (GH)，(GH)，(GH)是公式； (4) 所有公式都是有限次使用(1)，(2)，(3)

得到的符号串。规定：公式(G)的括号可以省略，写成G。整个公式的最外层括号可以省略。五种逻辑联结词的优先级按如下次序递增： ，，，，例如，我们写符号串

PQRQSR

就意味着是如下公式： ((P(QR))(Q((S)R)))§2.2.2解释

定义2.2.3设G是命题公式，A1,…,An是出现在G中的所有原子。指定A1,…,An的一组真值，则这组真值称为G的一个解释。设G是公式，I是G的一个解释，显然，G在I下有真值，通常记为TI(G)。

例

G=PQ，设解释I，I’如下：

I： I’：

则TI(G)=1，TI’(G)=0PQ

11

PQ

10

定义2.2.4公式G在其所有可能的解释下所取真值的表，称为G的真值表。显然，有n个不同原子的公式，共有2n个解释。

例：G=(PQ)R，其真值表如下：

PQRG00010011010101111001101111001111

若公式G中出现的所有原子为A1，…，An，有时我们用{m1，…，mn}表示G的一个解释I，其中

例如，上例公式G的真值表中第二个解释就可以记为{P，Q，R}定义2.2.5公式G称为恒真的(或有效的)，如果G在它的所有解释下都是真的；

公式G称为恒假的(或不可满足的)，如果G在它的所有解释下都是假的；公式G称为可满足的，如果它不是恒假的。考虑G1=

(P→Q)→P，G2=(P→Q)P，G3=PP。从真值表可以看出G1对所有解释具有“真”值，公式G3对所有解释具有“假”值，而G2具有“真”和“假”值。PQG1PQG2PG30010000001101110101100111111G是恒真的当且仅当G是恒假的。G是可满足的当且仅当至少有一个解释I，使G在I下为真。若G是恒真的，则G是可满足的；反之不对。如果公式G在解释I下是真的，则称I满足G；

如果G在解释I下是假的，则称I弄假G。在逻辑研究和计算机推理以及决策判断中，人们对于所研究的命题，最关心的莫过于“真”、“假”问题，所以恒真公式在数理逻辑研究中占有特殊且重要的地位。判定问题能否给出一个可行方法，对任意的公式，判定其是否是恒真公式。因为一个命题公式的解释的数目是有穷的，所以命题逻辑的判定问题是可解的(可判定的，可计算的)，亦即，命题公式的恒真，恒假性是可判定的。§2.3 命题公式的等价关系

和蕴涵关系

§2.3.1公式的等价定义2.3.1公式G，H说是等价的，记以G=H，如果G，H在其任意解释I下，其真值相同。显然，公式G，H等价的充要条件是公式GH是恒真的。基本等价式1) (GH)=(GH)(HG)；2) (GH)=(GH)；3) GG=G，GG=G； (等幂律)4)

GH=HG，GH=HG； (交换律)5)

G(HS)=(GH)S，

G(HS)=(GH)S； (结合律)基本等价式6) G(GH)=G，G(GH)=G； (吸收律)7)

G(HS)=(GH)(GS)，

G(HS)=(GH)(GS)； (分配律)8)

G0=G，G1=G； (同一律)9)

G0=0，G1=1； (零一律)10)

(GH)=GH，

(GH)=GH。 (摩根律)从上述众多的等价公式可以看出，每一个命题公式的表达式是不唯一的，这种不唯一性使得人们在进行逻辑推理时可以有千变万化的方式，即对于一个公式G，可根据如上等价公式，在等价的意义下，对其进行推演，从而得到G的各种等价形式。经验表明，自觉的使用逻辑规律和不自觉的使用是完全不一样的，熟悉这些规律可以使我们的思维正确而敏锐。定义2.3.2完备集设Q是逻辑运算符号集合，若所有逻辑运算都能由Q中元素表示出来，而Q的任意真子集无此性质，则称Q是一个完备集。可以证明，{，}，{，}都是完备集。

定义2.3.3与非式设P，Q是两个命题，命题“P与Q的否定”称为P与Q的与非式，记作PQ。“”称作与非联结词。PQ为真当且仅当P，Q不同时为真。由定义可知：

PQ=(PQ)。

定义2.3.4或非式设P，Q是两个命题，命题“P或Q的否定”称为P与Q的或非式，记作PQ，

称作或非联结词。PQ为真当且仅当P，Q同时为假。由定义可知：

PQ=(PQ){}是完备集下面我们来说明{}是完备集。

P=PPPQ=(PP)(QQ)PQ=(PQ)(PQ)读者可以自己证明{}也是完备集。

§2.3.2公式的蕴涵

逻辑的一个重要功能是研究推理。固然，依靠等价关系可以进行推理。但是，进行推理时，不必一定要依靠等价关系，只需是蕴涵关系就可以了。例如，若三角形等腰，则两底角相等，

这个三角形等腰，

所以，这个三角形两底角相等。又如，若行列式两行成比例，则行列式值为0，

这个行列式两行成比例，

所以，这个行列式值为0。上面两个例子的推理关系涵义不同，但依据的推理规则相同，推理形式为：

若P则Q，P，所以Q。

推理的正确性与命题P，Q涵义无关，只决定于逻辑形式，命题逻辑中用公式表示命题，命题间演绎推理关系，反映为公式间逻辑蕴涵关系。定义2.3.5蕴涵设G，H是两个公式。称H是G的逻辑结果(或称G蕴涵H)，当且仅当对G，H的任意解释I，如果I满足G，则I也满足H，记作GH。注意：符号“”和“=”一样，它们都不是逻辑联结词，因此，G=H，GH也都不是公式。

是一种部分序关系。公式G蕴涵公式H的充要条件是：公式GH是恒真的。例如：(PQ)P，(PQ)Q定义2.3.6设G1,…,Gn，H是公式。称H是G1,…,Gn的逻辑结果(或称G1,…,Gn共同蕴涵H)，当且仅当公式G1…

Gn蕴涵H。显然，公式H是G1,…,Gn的逻辑结果的充要条件是：公式((G1…

Gn)H)是恒真的。例如，P，PQ共同蕴涵Q。

定理2.3.1如果H1，…，Hm，P共同蕴涵公式Q，则H1，…，Hm共同蕴涵公式PQ。例如，因为公式PQ，QR，P共同蕴涵R，所以PQ，QR共同蕴涵PR。

定理2.3.1证明：因为(H1…HmP)Q，所以公式(H1…HmP)Q是恒真的。利用下面的基本等价公式：

P1(P2P3)=(P1P2)P3于是，(H1…HmP)Q=(H1…Hm)(PQ)。故(H1…Hm)(PQ)是恒真的。所以H1，…，Hm共同蕴涵PQ。§2.3.3演绎

定义2.3.7设S是一个命题公式的集合(前提集合)。从S推出公式G的一个演绎是公式的一个有限序列：

G1,G2,…,Gk

其中，Gi或者属于S，或者是某些

Gj

(j<i)的逻辑结果。

并且

Gk就是G。我们称公式G为此演绎的逻辑结果，或称从S演绎出G。

有时也记为SG。

例设S={PQ，QR，PM，M}则下面的公式序列:

M，PM，P，PQ，Q，QR，R

就是从S推出R的一个演绎。引理设G，H1，H2是公式。如果G蕴涵H1，G蕴涵H2，则G蕴涵H1H2。证明：任取G，H1，H2的一个解释I。

若I满足G，由假设知，I满足

H1，I满足H2，故I满足

H1H2。由I的任意性，所以G(H1H2)。

定理2.3.2设S是公式集合，G是一个公式。于是，从S演绎出G的充要条件是G是S的逻辑结果。证明：必要性，设从S演绎出G，令

G1，…，Gk

是这个演绎。对任意Gi(i=1，…，k)，往证Gi

是S的逻辑结果。对i用归纳法:(1)当i=1时，因G1S，显然,G1

…G1

是恒真公式，故SG1

，即

G1

是S的逻辑结果。

(2)设i<n时，命题成立。(3)当i=n时，若GnS，则S

Gn，归纳法完成。若Gn是某些Gj(j<n)的逻辑结果，不妨设

(Gj1

…Gjh)Gn(1)

其中j1，…，jh都小于n。

由归纳假设知，SGjm，m=1，…，h。由引理知：S(Gji

…Gjh)(2)

根据(1)，(2)式及蕴涵关系的传递性，得

S

Gn

即Gn是S的逻辑结果，归纳完成。

充分性，若G是S的逻辑结果，由演绎的定义知，G是如下演绎：

G1，…，Gk，G的逻辑结果，其中

G1

，…，Gk

是S中所有公式。

定理2.3.3设S是前提公式集合，G，H是两个公式。如果从S∪{G}可演绎出H，则从S可演绎出GH。证明：因为从S∪{G}可演绎出H，由定理2.3.2知，H是S∪{G}的逻辑结果。亦即

(G1

…Gk

G)H

其中G1，…，Gk

是S中所有公式。

由定理2.3.1知：

(G1

…Gk)(GH)

即GH是S的逻辑结果，再由定理2.3.2知，从S可演绎出GH。

基本蕴涵式

PQPPQQPPQQPQP(PQ)Q(PQ)(PQ)P基本蕴涵式

(PQ)QP，QPQP，PQQP，PQQQ，PQPPQ，QRPRPQ，PR，QRR§2.3.4公式蕴涵的证明方法真值表法；证GH是恒真公式；利用一些基本等价式及蕴涵式进行推导；任取解释I，若I满足G，往证I满足H；反证法，设结论假，往证前提假。§2.3.4公式蕴涵的证明方法若给出前提集合S={G1，…，Gk}，公式G，证明SG有如下两种方法：

1.G1

…Gk

G

2.形式演绎法形式演绎法根据一些基本等价式和基本蕴涵式，从S出发，演绎出G，在演绎过程中遵循以下三条规则：规则1.可随便使用前提。(根据演绎定义)规则2.可随便使用前面演绎出的某些公式的逻辑结果。(根据演绎的定义)规则3.

如果需要演绎出的公式是PQ的形式，则我们可将P做为附加前提使用，而力图去演绎出Q。(根据定理2.3.3)。

例2.3.1证明{(PQ)，(PR)，(QS)}SR

PQ 规则1

PQ 规则2，根据1 QS 规则1 PS 规则2，根据2，3 SP 规则2，根据4 PR 规则1 SR 规则2，根据5，6 SR 规则2，根据7。

例2.3.2证明{P(QS)，RP，Q}RS RP 规则1 R 规则3 P 规则2，根据1，2 P(QS) 规则1 QS 规则2，根据3，4 Q 规则1 S 规则2，根据5，6 RS 规则3，根据2，7例2.3.3若厂方拒绝增加工资，则罢工不会停止，除非罢工超过一年并且工厂经理辞职。问：如果厂方拒绝增加工资，而罢工又刚刚开始，罢工是否能停止?令 P：厂方拒绝增加工资；

Q：罢工停止；

R：工厂经理辞职；

S：

罢工超过一年。

于是， G1：(P(RS))Q G2：P G3：S H：Q我们要证明：H是{G1，G2，G3}的逻辑结果。1.

S 规则12.

SR 规则2，根据13.

(RS) 规则2，根据24.

P 规则15.

P(RS) 规则2，根据3，46.(P(RS))Q 规则17.

Q 规则2，根据5，6亦即，罢工不会停止。§2.4范式

§2.4.1析取范式和合取范式定义2.4.1原子或原子的否定称为文字。

例如，P，P是文字。定义2.4.2

有限个文字的析取式称为一个子句；

有限个文字的合取式称为一个短语。特别，一个文字既可称为是一个子句，也可称为是一个短语。例如，P，PQ，PQ是子句，P，PQ，PQ是短语。

定义2.4.3析取范式、合取范式有限个短语的析取式称为析取范式；

有限个子句的合取式称为合取范式。特别，一个文字既可称为是一个合取范式，也可称为是一个析取范式。一个子句，一个短语既可看做是合取范式，也可看做是析取范式。例如，P，PQ，PQ，(PQ)(PQ)是析取范式。

P，PQ，PQ，(PQ)(PR)是合取范式。

定理2.4.1对于任意命题公式，都存在等价于它的析取范式和合取范式。

证明：对于公式G，通过如下算法即可得出等价于G的范式：步1.使用基本等价式，将G中的逻辑联结词， 删除。步2.使用(H)=H和摩根律，将G中所有的否 定号都放在原子之前。

步3.

反复使用分配律，即可得到等价于G的范 式。

例：

G =(P(QR))S

=(P(QR))S =P(QR)S =P(QR)S……………. (析取范式) =P(QR)(S(QQ)) =P(QR)(SQ)(SQ)(析取范式) =(PS)(QR) =(PSQ)(PSR)……

(合取范式)

§2.4.2主析取范式和主合取范式

定义2.4.4设P1,…,Pn是n个不同原子，一个短语（子句）如果恰好包含所有这n个原子或其否定，且其排列顺序与P1,…,Pn的顺序一致，则称此短语（子句）为关于P1,…,Pn的一个极小（大）项。显然，共有2n个不同的极小（大）项。

例如，对原子P，Q，R而言，PQR，PQR，PQR都是极小项，但是，P，PQ不是极小项，而PQ对原子P，Q而言是极小项。

显然，对于n个原子P1,…,Pn而言，其不同的解释共有2n个，对于P1,…,Pn的任一个极小项m，2n个解释中，有且只有一个解释使m取1值。例如，对P，Q，R而言，PQR是极小项，解释{P，Q，R}使该极小项取1值，其他解释都使该极小项取0值。如果将真值1，0看做是数，则每一个解释对应一个n位二进制数。假设使极小项m取1值的解释对应的二进制数为i，今后将m记为mi。

例:对P，Q，R而言，PQR是极小项，解释(0，1，0)使该极小项取1值，解释(0，1，0)对应的二进制数是2，于是PQR记为m2。

对P，Q，R而言，8个极小项与其对应的解释如下：

极小项

解释

记法

PQR000m0

PQR001m1

PQR010m2

PQR011m3

PQR100m4

PQR101m5

PQR110m6

PQR111m7

一般地，对P1,…,Pn而言，2n个极小项为定义2.4.5主析取范式设命题公式G中所有不同原子为P1,…,Pn，如果G的某个析取范式G’中的每一个短语，都是关于P1,…,Pn的一个极小项，则称G’为G的主析取范式。

恒假公式的主析取范式用0表示。

定理2.4.2对于命题公式G，都存在等价于它的主析取范式。

证明：由定理2.4.1知，存在析取范式G’，使得G=G’。设G中所有不同原子为P1,…,Pn，对于G’中每一个短语Gi’进行检查，如果Gi’不是关于P1,…,Pn的极小项，则Gi’中必然缺少原子Pj1,…,Pjk。因为：于是将G’中非极小项Gi’化成了一些极小项之析取。对G’中其他非极小项也做如上处理，最后得等价于G的主析取范式G*。

例求G=(RP)(Q(PR))主析取范式。

解：

G =(RP)(Q(PR)) =(RP)(QP)(QR) =(PR)(QP)(QR) =((PR)(QQ))((QP)(RR))( (QR)(PP)) =(PQR)(PQR)(PQR)(P QR)求G=(PQ)(PR)(QR)主析取范式。

PQRG0

00000110

10001111000101011011111G的主析取范式为(PQR)(PQR)(PQR)(PQR)例于是，G的主析取范式为(PQR)(PQR)(PQR)(PQR)证明真值表法的正确性对于公式G，用这种方法写出主析取范式G’，若解释I使G取1值，而在I下取1值的唯一极小项写在G’中，故G’也取1值，若I使G取0值，而在I下取1的唯一极小项不在G’中且I弄假其它所有极小项，故G’取0值，所以G’是与G等价的主析取范式。

定理2.4.3设公式G，H是关于原子P1,…,Pn的两个主析取范式。如果G，H不完全相同，则G，H不等价。证明：因为G，H不完全相同，所以或者G中有一个极小项不在H中；

或者反之。不妨设极小项mi

在G中而不在H中。

于是根据极小项的性质，二进制数i所对应的关于P1,…,Pn的解释Ii使mi取1值，从而使公式G取1值。

Ii使所有不是mi的极小项取0值，从而使公式H取0值。

故G，H不等价。

定理2.4.4对于任意公式G，存在唯一一个与G等价的主析取范式。

§2.4.3恒真恒假性的判定

引理短语是恒假的当且仅当至少有一个原子及其否定(也称互补对)同时在此短语中出现。证明：充分性，若有一个原子P及其否定P同时出现在短语中，则此短语有形式： PP…显然，不管是什么解释I，PP在I下取0值，于是此短语在I下取0值，故此短语恒假。必要性，若短语恒假，而任意原子及其否定均不同时在短语中出现。那么，取这样的解释I：指定带有否定号的原子取0值，不带否定号的原子取1值，显然，此短语在这个解释I下取1值，与此短语恒假矛盾。定理2.4.5命题公式G是恒假的当且仅当在等价于它的析取范式中，每个短语均至少包含一个原子及其否定。证明：设G的析取范式如下：

G=G1…Gn

其中Gi是短语，i=1，…，n。

显然，公式G恒假的充要条件是每个Gi恒假。再根据引理，此定理结论显然成立。例2.4.1

判断公式G=(PQ)(QR)(RP)是否恒假?解：

G=(PQ)(QR)(RP)

=(PQ)(QR)(RP)

=((PQ)(QQ)(PR)(QR))(RP)

=(PQR)(QQR)(