离散数学(第1.6-1.7)陈瑜

1、陈瑜陈瑜Email：2022年年4月月20日星期三日星期三2022-4-202022-4-20计算机学院计算机学院2 2/156/156主要内容主要内容n 1.1.命题公式的蕴涵命题公式的蕴涵 1)1)九类蕴涵关系九类蕴涵关系 2)2)蕴涵关系的基本性质蕴涵关系的基本性质n 2.2.推理的基本概念和推理形式推理的基本概念和推理形式n 3.3.推理规则推理规则 1)P1)P规则规则 2)T2)T规则规则 3)CP3)CP规则规则2022-4-202022-4-20计算机学院计算机学院3 3/156/1561 16 6 命题公式的蕴涵命题公式的蕴涵n 定义定义1.181.18 设设A A和和B B

2、是两个合适公式，如果在是两个合适公式，如果在任何任何解释解释下，下，A A取值取值1 1时时B B也也取值取值1 1，则称公式，则称公式A A蕴涵蕴涵公公式式B B，并记，并记A A B B。（A A取取0 0时的情况不考虑）时的情况不考虑）n 定理定理1.11: 1.11: A AB B 当且仅当当且仅当 ABAB为永真式。为永真式。 注意：蕴含和条件联结词注意：蕴含和条件联结词是完全不同的。是完全不同的。 1)1)是命题联结词，是命题联结词，ABAB是一个命题公式；是一个命题公式； 2)2)是公式间关系符，是公式间关系符，A AB B不是一个命题公不是一个命题公 式，仅表示式，仅表示A A

3、，B B间的蕴含关系。间的蕴含关系。2022-4-202022-4-20计算机学院计算机学院4 4/156/1561 16 6 命题公式的蕴涵命题公式的蕴涵n 定义定义1.181.18 设设A A和和B B是两个合适公式，如果在任何是两个合适公式，如果在任何解释下，解释下，A A取值取值1 1时时B B也也取值取值1 1，则称公式，则称公式A A蕴涵公蕴涵公式式B B，并记，并记A A B B。（A A取取0 0时的情况不考虑）时的情况不考虑）n 定理定理1.11: 1.11: A AB B 当且仅当当且仅当 ABAB为永真式。为永真式。 注意：蕴含和条件联结词注意：蕴含和条件联结词是完全不同

4、的。是完全不同的。 1)1)是命题联结词，是命题联结词，ABAB是一个命题公式；是一个命题公式； 2)2)是公式间关系符，是公式间关系符，A AB B不是一个命题公不是一个命题公 式，仅表示式，仅表示A A，B B间的蕴含关系。间的蕴含关系。2022-4-202022-4-20计算机学院计算机学院5 5/156/1561 16 6 命题公式的蕴涵命题公式的蕴涵n 定义定义1.18 1.18 设A和B是两个合适公式，如果在任何解释下，A取值1时B也取值1，则称公式A蕴涵公式B，并记A B。n 定理定理1.11:1.11: A AB B 当且仅当当且仅当 ABAB为永真式。为永真式。 注意：蕴含和

5、条件联结词注意：蕴含和条件联结词是完全不同的。是完全不同的。 1)1)是命题联结词，是命题联结词，ABAB是一个命题公式；是一个命题公式； 2)2)是公式间关系符，是公式间关系符，A AB B不是一个命题公不是一个命题公 式，仅表示式，仅表示A A，B B间的蕴含关系。间的蕴含关系。2022-4-202022-4-20计算机学院计算机学院6 6/156/1561 16 6 命题公式的蕴涵命题公式的蕴涵n 定义定义1.18 1.18 设A和B是两个合适公式，如果在任何解释下，A取值1时B也取值1，则称公式A蕴涵公式B，并记A B。n 定理定理1.11: 1.11: A AB B 当且仅当当且仅当

6、 ABAB为永真式。为永真式。 注意：蕴含和条件联结词注意：蕴含和条件联结词是完全不同的。是完全不同的。 1)1)是命题联结词，是命题联结词，ABAB是一个命题公式；是一个命题公式； 2)2)是公式间关系符，是公式间关系符，A AB B不是一个命题公不是一个命题公 式，仅表示式，仅表示A A，B B间的蕴含关系。间的蕴含关系。注意注意区别：区别：定义定义1.12设设G、H是是公式，公式，如果在任意解释下，如果在任意解释下，G与与H的的真值相同真值相同，则称，则称公式公式G、H是等价的是等价的 ，记作记作GH。定理定理1.3公式公式G、H等价的等价的充分必要条件充分必要条件是公式是公式 GH是永

7、真是永真公式。公式。 2022-4-202022-4-20计算机学院计算机学院7 7/156/1561 16 6 命题公式的蕴涵命题公式的蕴涵n 定义定义1.181.18 设A和B是两个合适公式，如果在任何解释下，A取值1时B也取值1，则称公式A蕴涵公式B，并记A B。n 定理定理1.11:1.11: AB 当且仅当 AB为永真式。 注意：蕴含和条件联结词注意：蕴含和条件联结词是完全不同的。是完全不同的。 1)1)是命题联结词，是命题联结词，ABAB是一个命题公式；是一个命题公式； 2)2)是公式间关系符，是公式间关系符，A AB B不是一个命题公不是一个命题公 式，仅表示式，仅表示A A，B

8、 B间的蕴含关系。间的蕴含关系。2022-4-202022-4-20计算机学院计算机学院8 8/156/156证明证明n定理定理1.11:1.11: AB 当且仅当 AB为永真式。证：证： 1)1)因因A AB B，由蕴涵定义知：，由蕴涵定义知：A A取取1 1，B B也取也取1 1。此。此时，由时，由运算规则知运算规则知ABAB取取1 1。此外，。此外，A A若为若为0 0， ABAB也必取也必取1 1。因此，。因此， ABAB为永真式。为永真式。 2)2)如果如果ABAB为永真式，那么为永真式，那么A A取取1 1时必有时必有B B也取也取1 1，从而从而A AB B。（注：此处由假设（注

9、：此处由假设“ABAB为永真式为永真式”也可得出也可得出A A取取0 0时，时，B B取取0 0或或1 1，ABAB也为也为1 1的结果，的结果，但根据蕴涵定义，我们不需要判断此情况。）但根据蕴涵定义，我们不需要判断此情况。）根据前提假设，此处B只可能取12022-4-202022-4-20计算机学院计算机学院9 9/156/156蕴含关系的性质蕴含关系的性质n 自反性自反性 A A A An 反对称性，如果反对称性，如果A A B B，且且B B A A，则必有：，则必有： A A B Bn A A B B 且且A A为永真式，则为永真式，则B B必为永真式必为永真式n 传递性，如果传递性，

10、如果A A B B，B B C C，则，则A A C Cn 如如A A B B，A A C C，则，则A A BC BCn 如如A A C C，B B C C，则，则AB AB C C2022-4-202022-4-20计算机学院计算机学院1010/156/156蕴含关系的性质蕴含关系的性质n 自反性自反性 A A A An 反对称性，如果反对称性，如果A A B B，且，且B B A A，则必有：，则必有： A A B Bn A A B B 且且A A为永真式，则为永真式，则B B必为永真式必为永真式n 传递性，如果传递性，如果A A B B，B B C C，则，则A A C Cn 如如A

11、A B B，A A C C，则，则A A BC BCn 如如A A C C，B B C C，则，则AB AB C C2022-4-202022-4-20计算机学院计算机学院1111/156/156蕴含关系的性质蕴含关系的性质n 自反性自反性 A A A An 反对称性，如果反对称性，如果A A B B，且且B B A A，则必有：，则必有： A A B Bn A A B B 且且A A为永真式，则为永真式，则B B必为永真式必为永真式n 传递性，如果传递性，如果A A B B，B B C C，则，则A A C Cn 如如A A B B，A A C C，则，则A A BC BCn 如如A A C

12、 C，B B C C，则，则AB AB C C2022-4-202022-4-20计算机学院计算机学院1212/156/156蕴含关系的性质蕴含关系的性质n 自反性自反性 A A A An 反对称性，如果反对称性，如果A A B B，且，且B B A A，则必有：，则必有： A A B Bn A A B B 且且A A为永真式，则为永真式，则B B必为永真式必为永真式n 传递性，如果传递性，如果A A B B，B B C C，则，则A A C Cn 如如A A B B，A A C C，则，则A A BC BCn 如如A A C C，B B C C，则，则AB AB C C 以上三个性质根据定义

13、和定理以上三个性质根据定义和定理1.111.11是很容是很容易证明的（这些证明作为课外练习），下面我易证明的（这些证明作为课外练习），下面我们来证明另外五个重要性质。们来证明另外五个重要性质。 2022-4-202022-4-20计算机学院计算机学院1313/156/156蕴含关系的性质蕴含关系的性质n 自反性自反性 A A A An 反对称性，如果反对称性，如果A A B B，且，且B B A A，则必有：，则必有： A A B Bn A A B B 且且A A为永真式，则为永真式，则B B必为永真式必为永真式n 传递性，如果传递性，如果A A B B，B B C C，则，则A A C Cn

14、 如如A A B B，A A C C，则，则A A BC BCn 如如A A C C，B B C C，则，则AB AB C C2022-4-202022-4-20计算机学院计算机学院1414/156/156蕴含关系的性质蕴含关系的性质n 自反性自反性 A A A An 反对称性，如果反对称性，如果A A B B，且，且B B A A，则必有：，则必有： A A B Bn A A B B 且且A A为永真式，则为永真式，则B B必为永真式必为永真式n 传递性，如果传递性，如果A A B B，B B C C，则，则A A C Cn 如如A A B B，A A C C，则，则A A BC BCn 如

15、如A A C C，B B C C，则，则AB AB C C 证明：证明： 由已知条件由已知条件A A B B 且且 B B C C，可知，可知: : (AB)(AB)(BC )(BC )应该是永真式；再根据假言三段论，应该是永真式；再根据假言三段论，应有应有(AB)(BC )(AB)(BC ) AC AC ；再根据性质；再根据性质3 3， ACAC也必是永真式，即也必是永真式，即A A C C 。 2022-4-202022-4-20计算机学院计算机学院1515/156/156蕴含关系的性质蕴含关系的性质n 自反性自反性 A A A An 反对称性，如果反对称性，如果A A B B，且，且B

16、B A A，则必有：，则必有： A A B Bn A A B B 且且A A为永真式，则为永真式，则B B必为永真式必为永真式n 传递性，如果传递性，如果A A B B，B B C C，则，则A A C Cn 如如A A B B，A A C C，则，则A A BC BCn 如如A A C C，B B C C，则，则AB AB C C2022-4-202022-4-20计算机学院计算机学院1616/156/156蕴含关系的性质蕴含关系的性质n 自反性自反性 A A A An 反对称性，如果反对称性，如果A A B B，且，且B B A A，则必有：，则必有： A A B Bn A A B B 且

17、且A A为永真式，则为永真式，则B B必为永真式必为永真式n 传递性，如果传递性，如果A A B B，B B C C，则，则A A C Cn 如如A A B B，A A C C，则，则A A BC BCn 如如A A C C，B B C C，则，则AB AB C C 证明：证明： 由已知条件由已知条件A AB B且且A AC C，可知，可知: AB: AB和和ACAC都是永都是永真式，于是真式，于是(AB)(AC )(AB)(AC )也是永真式。也是永真式。 但，但，(AB)(AC)(AB)(AC)( (AB)AB)( (AC)AC)AA( (BC) BC) A(BC) A(BC) ；所以；所

18、以A(BC)A(BC)是永真式，是永真式，即即A A BC BC 。 2022-4-202022-4-20计算机学院计算机学院1717/156/156蕴含关系的性质蕴含关系的性质n 自反性自反性 A A A An 反对称性，如果反对称性，如果A A B B，且，且B B A A，则必有：，则必有： A A B Bn A A B B 且且A A为永真式，则为永真式，则B B必为永真式必为永真式n 传递性，如果传递性，如果A A B B，B B C C，则，则A A C Cn 如如A A B B，A A C C，则，则A A BC BCn 如如A A C C，B B C C，则，则AB AB C

19、C 证明：证明： 由已知条件由已知条件A AB B且且A AC C，可知，可知: AB: AB和和ACAC都是永都是永真式，于是真式，于是(AB)(AC )(AB)(AC )也是永真式。也是永真式。 但，但，(AB)(AC)(AB)(AC)( (AB)AB)( (AC)AC)AA( (BC) BC) A(BC) A(BC) ；所以；所以A(BC)A(BC)是永真式，是永真式，即即A A BC BC 。 从证明过程看，性质从证明过程看，性质5 5反过来也反过来也对，即由对，即由 A BC可知：可知： A B，A C2022-4-202022-4-20计算机学院计算机学院1818/156/156蕴

20、含关系的性质蕴含关系的性质n 自反性自反性 A A A An 反对称性，如果反对称性，如果A A B B，且，且B B A A，则必有：，则必有： A A B Bn A A B B 且且A A为永真式，则为永真式，则B B必为永真式必为永真式n 传递性，如果传递性，如果A A B B，B B C C，则，则A A C Cn 如如A A B B，A A C C，则，则A A BC BCn 如如A A C C，B B C C，则，则AB AB C C2022-4-202022-4-20计算机学院计算机学院1919/156/156蕴含关系的性质蕴含关系的性质n 自反性自反性 A A A An 反对称

21、性，如果反对称性，如果A A B B，且，且B B A A，则必有：，则必有： A A B Bn A A B B 且且A A为永真式，则为永真式，则B B必为永真式必为永真式n 传递性，如果传递性，如果A A B B，B B C C，则，则A A C Cn 如如A A B B，A A C C，则，则A A BC BCn 如如A A C C，B B C C，则，则AB AB C C 证明：证明： 由由A AC C且且B BC C知道（知道（A AC C）（B BC C）是永真式；进一）是永真式；进一步步可变换可变换为永真式为永真式(AB(AB）C C，即，即ABABC C。 2022-4-202

22、022-4-20计算机学院计算机学院2020/156/156蕴含关系的性质蕴含关系的性质n AB AB C C 当且仅当当且仅当 A A BC BC 该性质是推理演绎中该性质是推理演绎中CPCP规则的基础规则的基础n A A B, iff A B, iff AB B是矛盾式是矛盾式 该性质是反证法的基础该性质是反证法的基础n 定理定理1-6.2:A1-6.2:AB iff B iff B BA A 该定理提供了逆向思维的基础该定理提供了逆向思维的基础2022-4-202022-4-20计算机学院计算机学院2121/156/156蕴含关系的性质蕴含关系的性质n AB AB C C 当且仅当当且仅

23、当 A A BC BC 该性质是推理演绎中该性质是推理演绎中CPCP规则的基础规则的基础n A A B, iff A B, iff AB B是矛盾式是矛盾式 该性质是反证法的基础该性质是反证法的基础n 定理定理1-5.2:A1-5.2:AB iff B iff B BA A 该定理提供了逆向思维的基础该定理提供了逆向思维的基础 证明：证明： 先设先设ABABC C，由定理，由定理1.111.11，ABABC C是永真式；但是是永真式；但是ABABC CAABCBC AA（B BC C）A A（B BC C），），于是于是A A（B BC C）是永真式，即有）是永真式，即有A AB BC C。

24、其次，设其次，设A AB BC C，则，则A A（B BC C）是永真式，即）是永真式，即ABABC C是永真式，从而是永真式，从而ABABC C。 2022-4-202022-4-20计算机学院计算机学院2222/156/156蕴含关系的性质蕴含关系的性质n AB AB C C 当且仅当当且仅当 A A BC BC 该性质是推理演绎中该性质是推理演绎中CPCP规则的基础规则的基础n A A B, iff A B, iff AB B是矛盾式是矛盾式 该性质是反证法的基础该性质是反证法的基础n 定理定理1-6.2:A1-6.2:AB iff B iff B BA A 该定理提供了逆向思维的基础该

25、定理提供了逆向思维的基础2022-4-202022-4-20计算机学院计算机学院2323/156/156蕴含关系的性质蕴含关系的性质n AB AB C C 当且仅当当且仅当 A A BC BC 该性质是推理演绎中该性质是推理演绎中CPCP规则的基础规则的基础n A A B, iff A B, iff AB B是矛盾式是矛盾式 该性质是反证法的基础该性质是反证法的基础n 定理定理1-5.2:A1-5.2:AB iff B iff B BA A 该定理提供了逆向思维的基础该定理提供了逆向思维的基础 证明：证明： 当当A AB B时，时，A AB B是永真式，所以（是永真式，所以（A AB B）是矛

26、盾式，）是矛盾式，即即AAB B是矛盾式。是矛盾式。 反之，当反之，当AAB B是矛盾式时。（是矛盾式时。（AAB B）是永真式，）是永真式，从而导致从而导致A AB B。 2022-4-202022-4-20计算机学院计算机学院2424/156/156蕴含关系的性质蕴含关系的性质n AB C iff A BC 该性质是推理演绎中CP规则的基础n A B, iff AB是矛盾式 该性质是反证法的基础n 定理定理1.12:1.12:A AB iff B iff B BA A （证明略）（证明略） 该定理提供了逆向思维的基础该定理提供了逆向思维的基础2022-4-202022-4-20计算机学院计

27、算机学院2525/156/156基本蕴含（关系）式（蕴含定律）基本蕴含（关系）式（蕴含定律）n I I1 1：P PPQ PQ ， Q QPQ PQ P PPQ PQ ， Q QPQ PQ 扩充法则扩充法则( (析取引入律析取引入律) )n I I2 2：PQ PQ P P ， PQPQQ Q （PQPQ）P P ，（，（PQPQ）Q Q 化简化简法则法则( (合取消去律合取消去律) )n I I3 3：P P（PQPQ） Q Q 假言推论（分离规则）假言推论（分离规则）n I I4 4：Q Q（PQPQ） P P 否定式假言推论（拒取式）否定式假言推论（拒取式）2022-4-202022-4

28、-20计算机学院计算机学院2626/156/156基本蕴含（关系）式（蕴含定律）基本蕴含（关系）式（蕴含定律）n I I1 1：PPQ ， QPQ PPQ ， QPQ 扩充法则(析取引入律)n I I2 2：PQ PQ P P ， PQPQQ Q （PQPQ）P P ，（，（PQPQ）Q Q 化简化简法则法则( (合取消去律合取消去律) )n I I3 3：P P（PQPQ） Q Q 假言推论（分离规则）假言推论（分离规则）n I I4 4：Q Q（PQPQ） P P 否定式假言推论（拒取式）否定式假言推论（拒取式）2022-4-202022-4-20计算机学院计算机学院2727/156/15

29、6基本蕴含（关系）式（蕴含定律）基本蕴含（关系）式（蕴含定律）n I I1 1：PPQ ， QPQ PPQ ， QPQ 扩充法则(析取引入律)n I I2 2：PQ P ， PQQ （PQ）P ，（PQ）Q 化简法则(合取消去律)n I I3 3：P P（PQPQ） Q Q 假言推论（分离规则）假言推论（分离规则）n I I4 4：Q Q（PQPQ） P P 否定式假言推论（拒取式）否定式假言推论（拒取式）2022-4-202022-4-20计算机学院计算机学院2828/156/156基本蕴含（关系）式（蕴含定律）基本蕴含（关系）式（蕴含定律）n I I1 1：PPQ ， QPQ PPQ ，

30、QPQ 扩充法则(析取引入律)n I I2 2：PQ P ， PQQ （PQ）P ，（PQ）Q 化简法则(合取消去律)n I I3 3：P（PQ） Q 假言推论（分离规则）n I I4 4：Q Q（PQPQ） P P 否定式假言推论（拒取式）否定式假言推论（拒取式）2022-4-202022-4-20计算机学院计算机学院2929/156/156基本蕴含（关系）式（蕴含定律）基本蕴含（关系）式（蕴含定律）n I I5 5：PP（PQPQ） Q Q 析取三段论（选言三段论）析取三段论（选言三段论）n I I6 6：（：（PQPQ）（QRQR） PRPR 假言（前提条件）三段论假言（前提条件）三段论

31、n I I7 7：（PQPQ）（PRPR）（QRQR） R R 二难推论二难推论n I I8 8：（：（PQPQ）（RSRS）（PRPR）（QSQS）n I I9 9：（：（P PQ Q）（Q QR R） P PR Rn I I1010：（：（PQPQ）（PRPR） QRQR 归结原理归结原理2022-4-202022-4-20计算机学院计算机学院3030/156/156基本蕴含（关系）式（蕴含定律）基本蕴含（关系）式（蕴含定律）n I I5 5：P（PQ） Q 析取三段论（选言三段论）n I I6 6：（：（PQPQ）（QRQR） PRPR 假言（前提条件）三段论假言（前提条件）三段论n I

32、 I7 7：（PQPQ）（PRPR）（QRQR） R R 二难推论二难推论n I I8 8：（：（PQPQ）（RSRS）（PRPR）（QSQS）n I I9 9：（：（P PQ Q）（Q QR R） P PR Rn I I1010：（：（PQPQ）（PRPR） QRQR 归结原理归结原理2022-4-202022-4-20计算机学院计算机学院3131/156/156基本蕴含（关系）式（蕴含定律）基本蕴含（关系）式（蕴含定律）n I I5 5：P（PQ） Q 析取三段论（选言三段论）n I I6 6：（PQ）（QR） PR 假言（前提条件）三段论n I I7 7：（PQPQ）（PRPR）（QRQ

33、R） R R 二难推论二难推论n I I8 8：（：（PQPQ）（RSRS）（PRPR）（QSQS）n I I9 9：（：（P PQ Q）（Q QR R） P PR Rn I I1010：（：（PQPQ）（PRPR） QRQR 归结原理归结原理2022-4-202022-4-20计算机学院计算机学院3232/156/156基本蕴含（关系）式（蕴含定律）基本蕴含（关系）式（蕴含定律）n I I5 5：P（PQ） Q 析取三段论（选言三段论）n I I6 6：（PQ）（QR） PR 假言（前提条件）三段论n I I7 7：（PQ）（PR）（QR） R 二难推论n I I8 8：（：（PQPQ）（R

34、SRS）（PRPR）（QSQS）n I I9 9：（：（P PQ Q）（Q QR R） P PR Rn I I1010：（：（PQPQ）（PRPR） QRQR 归结原理归结原理2022-4-202022-4-20计算机学院计算机学院3333/156/156基本蕴含（关系）式（蕴含定律）基本蕴含（关系）式（蕴含定律）n I I5 5：P（PQ） Q 析取三段论（选言三段论）n I I6 6：（PQ）（QR） PR 假言（前提条件）三段论n I I7 7：（PQ）（PR）（QR） R 二难推论n I I8 8：（PQ）（RS）（PR）（QS）n I I9 9：（：（P PQ Q）（Q QR R）

35、P PR Rn I I1010：（：（PQPQ）（PRPR） QRQR 归结原理归结原理2022-4-202022-4-20计算机学院计算机学院3434/156/156基本蕴含（关系）式（蕴含定律）基本蕴含（关系）式（蕴含定律）n I I5 5：P（PQ） Q 析取三段论（选言三段论）n I I6 6：（PQ）（QR） PR 假言（前提条件）三段论n I I7 7：（PQ）（PR）（QR） R 二难推论n I I8 8：（PQ）（RS）（PR）（QS）n I I9 9：（PQ）（QR） PRn I I1010：（：（PQPQ）（PRPR） QRQR 归结原理归结原理2022-4-202022-

36、4-20计算机学院计算机学院3535/156/156例例6.1:6.1:考虑以下语句，并将其前提和结论符号化。考虑以下语句，并将其前提和结论符号化。n 1).1).前提：前提： 1. 1. 如果明天天晴，我们准备外出旅游。如果明天天晴，我们准备外出旅游。PQPQ 2 2明天的确天晴。明天的确天晴。P P 结论：我们外出旅游。结论：我们外出旅游。 Q Q 上述例子可描述为：上述例子可描述为：PQPQ，P PQ Q( (分离规则分离规则) )n 2)2)、前提：、前提： 1. 1. 如果一个人如果一个人比较懒，则他学不好离散数学。比较懒，则他学不好离散数学。 PQ PQ 2. 2. 如果一个人如果

37、一个人学不好离散数学学不好离散数学，则他，则他拿不到好成绩。拿不到好成绩。 QRQR 结论：结论： 如果一个人比较懒则拿不到好成绩。则拿不到好成绩。PRPR 上述例子可描述为：上述例子可描述为：PQPQ，QRQRPRPR( (假言三段论假言三段论) )2022-4-202022-4-20计算机学院计算机学院3636/156/156例例6.1:6.1:考虑以下语句，并将其前提和结论符号化。考虑以下语句，并将其前提和结论符号化。n 1).1).前提：前提： 1. 1. 如果明天天晴，我们准备外出旅游。如果明天天晴，我们准备外出旅游。PQPQ 2 2明天的确天晴。明天的确天晴。P P 结论：我们外出

38、旅游。结论：我们外出旅游。 Q Q 上述例子可描述为：上述例子可描述为：PQPQ，P PQ Q( (分离规则分离规则) )n 2)2)、前提：、前提： 1. 1. 如果一个人如果一个人比较懒，则他学不好离散数学。比较懒，则他学不好离散数学。 PQ PQ 2. 2. 如果一个人如果一个人学不好离散数学学不好离散数学，则他，则他拿不到好成绩。拿不到好成绩。 QRQR 结论：结论： 如果一个人比较懒则拿不到好成绩。则拿不到好成绩。PRPR 上述例子可描述为：上述例子可描述为：PQPQ，QRQRPRPR( (假言三段论假言三段论) )2022-4-202022-4-20计算机学院计算机学院3737/1

39、56/156例例6.1:6.1:考虑以下语句，并将其前提和结论符号化。考虑以下语句，并将其前提和结论符号化。n 1).1).前提：前提： 1. 1. 如果明天天晴，我们准备外出旅游。如果明天天晴，我们准备外出旅游。PQPQ 2 2明天的确天晴。明天的确天晴。P P 结论：我们外出旅游。结论：我们外出旅游。 Q Q 上述例子可描述为：上述例子可描述为：PQPQ，P PQ Q( (分离规则分离规则) )n 2)2)、前提：、前提： 1. 1. 如果一个人如果一个人比较懒，则他学不好离散数学。比较懒，则他学不好离散数学。 PQ PQ 2. 2. 如果一个人如果一个人学不好离散数学学不好离散数学，则他

40、，则他拿不到好成绩。拿不到好成绩。 QRQR 结论：结论： 如果一个人比较懒则拿不到好成绩。则拿不到好成绩。PRPR 上述例子可描述为：上述例子可描述为：PQPQ，QRQRPRPR( (假言三段论假言三段论) )2022-4-202022-4-20计算机学院计算机学院3838/156/156例例6.1:6.1:考虑以下语句，并将其前提和结论符号化。考虑以下语句，并将其前提和结论符号化。n1)、前提：1. 如果明天天晴，我们准备外出旅游。 PQ2明天的确天晴。P 结论：我们外出旅游。 Q 上述例子可描述为：PQ，PQ(分离规则)n 2)2)、前提：、前提： 1. 1. 如果一个人如果一个人比较懒

41、，则他学不好离散数学。比较懒，则他学不好离散数学。 PQ PQ 2. 2. 如果一个人如果一个人学不好离散数学学不好离散数学，则他，则他拿不到好成拿不到好成绩。绩。QRQR 结论：结论： 如果一个人如果一个人比较懒则拿不到好成绩。比较懒则拿不到好成绩。PRPR 上述例子可描述为：上述例子可描述为：PQPQ，QRQRPRPR( (假言三段论假言三段论) )2022-4-202022-4-20计算机学院计算机学院3939/156/156例例6.1:6.1:考虑以下语句，并将其前提和结论符号化。考虑以下语句，并将其前提和结论符号化。n1)、前提：1. 如果明天天晴，我们准备外出旅游。 PQ2明天的确

42、天晴。P 结论：我们外出旅游。 Q 上述例子可描述为：PQ，PQ(分离规则)n 2)2)、前提：、前提： 1. 1. 如果一个人如果一个人比较懒，则他学不好离散数学。比较懒，则他学不好离散数学。 PQPQ 2. 2. 如果一个人如果一个人学不好离散数学学不好离散数学，则他，则他拿不到好成拿不到好成绩。绩。QRQR 结论：结论： 如果一个人如果一个人比较懒则拿不到好成绩。比较懒则拿不到好成绩。PRPR 上述例子可描述为：上述例子可描述为：PQPQ，QRQRPRPR( (假言三段论假言三段论) )2022-4-202022-4-20计算机学院计算机学院4040/156/156例例6.1:6.1:考

43、虑以下语句，并将其前提和结论符号化。考虑以下语句，并将其前提和结论符号化。n1)、前提：1. 如果明天天晴，我们准备外出旅游。 PQ2明天的确天晴。P 结论：我们外出旅游。 Q 上述例子可描述为：PQ，PQ(分离规则)n 2)2)、前提：前提： 1. 1. 如果一个人如果一个人比较懒，则他学不好离散数学。比较懒，则他学不好离散数学。 PQ PQ 2. 2. 如果一个人如果一个人学不好离散数学学不好离散数学，则他，则他拿不到好成拿不到好成绩。绩。QRQR 结论：结论： 如果一个人如果一个人比较懒则拿不到好成绩。比较懒则拿不到好成绩。PRPR 上述例子可描述为：上述例子可描述为：PQPQ，QRQR

44、PRPR( (假言三段论假言三段论) )2022-4-202022-4-20计算机学院计算机学院4141/156/156例例6.1(6.1(续续1)1)n 3)3) 某女子在某日晚归家途中被杀害，据多方调查确证，某女子在某日晚归家途中被杀害，据多方调查确证，凶手必为王某或张某，但后又查证，作案之晚王某在工凶手必为王某或张某，但后又查证，作案之晚王某在工厂值夜班，没有外出。根据上述案情可得前提如下：厂值夜班，没有外出。根据上述案情可得前提如下： 前提：前提： 1. 1.凶手为王某或凶手为王某或张某。张某。PQPQ 2. 2.如果王某是凶手，则他在作案当晚必外出。如果王某是凶手，则他在作案当晚必外

45、出。PRPR 3. 3.王某案发之晚并未外出。王某案发之晚并未外出。 R R 结论：结论：张某是凶手。张某是凶手。 Q Q 则上述例子可描述为：则上述例子可描述为：PRPR，R RP P( (拒取式拒取式) )PQPQ，P PQ Q( (选言三段论选言三段论) )2022-4-202022-4-20计算机学院计算机学院4242/156/156例例6.1(6.1(续续1)1)n 3)3) 某女子在某日晚归家途中被杀害，据多方调查确证，某女子在某日晚归家途中被杀害，据多方调查确证，凶手必为王某或张某，但后又查证，作案之晚王某在工凶手必为王某或张某，但后又查证，作案之晚王某在工厂值夜班，没有外出。根

46、据上述案情可得前提如下：厂值夜班，没有外出。根据上述案情可得前提如下： 前提：前提： 1.1.凶手为王某或凶手为王某或张某。张某。PQPQ 2.2.如果王某是凶手，则他在作案当晚必外出。如果王某是凶手，则他在作案当晚必外出。PRPR 3.3.王某案发之晚并未外出。王某案发之晚并未外出。 R R 结论：结论：张某是凶手。张某是凶手。 Q Q 则上述例子可描述为：则上述例子可描述为：PRPR，R RP P( (拒取式拒取式) )PQPQ，P PQ Q( (选言三段论选言三段论) )2022-4-202022-4-20计算机学院计算机学院4343/156/156例例6.1(6.1(续续1)1)n 3

47、)3) 某女子在某日晚归家途中被杀害，据多方调查确证，某女子在某日晚归家途中被杀害，据多方调查确证，凶手必为王某或张某，但后又查证，作案之晚王某在工凶手必为王某或张某，但后又查证，作案之晚王某在工厂值夜班，没有外出。根据上述案情可得前提如下：厂值夜班，没有外出。根据上述案情可得前提如下： 前提：前提： 1.1.凶手为王某或凶手为王某或张某。张某。PQPQ 2.2.如果王某是凶手，则他在作案当晚必外出。如果王某是凶手，则他在作案当晚必外出。PRPR 3.3.王某案发之晚并未外出。王某案发之晚并未外出。 R R 结论：结论：张某是凶手。张某是凶手。 Q Q 则上述例子可描述为：则上述例子可描述为：

48、PRPR，R RP P( (拒取式拒取式) )PQPQ，P PQ Q( (选言三段论选言三段论) )2022-4-202022-4-20计算机学院计算机学院4444/156/156例例6.1(6.1(续续1)1)n 3)3) 某女子在某日晚归家途中被杀害，据多方调查确证，某女子在某日晚归家途中被杀害，据多方调查确证，凶手必为王某或张某，但后又查证，作案之晚王某在工凶手必为王某或张某，但后又查证，作案之晚王某在工厂值夜班，没有外出。根据上述案情可得前提如下：厂值夜班，没有外出。根据上述案情可得前提如下： 前提：前提： 1. 1.凶手为王某或凶手为王某或张某。张某。PQPQ 2. 2.如果王某是凶

49、手，则他在作案当晚必外出。如果王某是凶手，则他在作案当晚必外出。PRPR 3. 3.王某案发之晚并未外出。王某案发之晚并未外出。 R R 结论：结论：张某是凶手。张某是凶手。 Q Q 则上述例子可描述为：则上述例子可描述为：PRPR，R RP P( (拒取式拒取式) )PQPQ，P PQ Q( (选言三段论选言三段论) )2022-4-202022-4-20计算机学院计算机学院4545/156/156例例6.1(6.1(续续1)1)n 3)3) 某女子在某日晚归家途中被杀害，据多方调查确证，某女子在某日晚归家途中被杀害，据多方调查确证，凶手必为王某或张某，但后又查证，作案之晚王某在工凶手必为王

50、某或张某，但后又查证，作案之晚王某在工厂值夜班，没有外出。根据上述案情可得前提如下：厂值夜班，没有外出。根据上述案情可得前提如下： 前提：前提： 1. 1.凶手为王某或凶手为王某或张某。张某。PQPQ 2. 2.如果王某是凶手，则他在作案当晚必外出。如果王某是凶手，则他在作案当晚必外出。PRPR 3. 3.王某案发之晚并未外出。王某案发之晚并未外出。 R R 结论：结论：张某是凶手。张某是凶手。 Q Q 则上述例子可描述为：则上述例子可描述为：PRPR，R RP P( (拒取式拒取式) )PQPQ，P PQ Q( (选言三段论选言三段论) )前面学习的基本蕴含关系式一定要熟记！前面学习的基本蕴

51、含关系式一定要熟记！2022-4-202022-4-20计算机学院计算机学院4646/156/156例例6.1(6.1(续续2)2)n 4)4) 前提：前提：1.1.如果某同学为省二级以上运动员，则他将被大学录取。如果某同学为省二级以上运动员，则他将被大学录取。PRPR2.2.如果某同学高考总分在如果某同学高考总分在560560分以上，则将被大学录取。分以上，则将被大学录取。QRQR3.3.某同学高考总分在某同学高考总分在560560分以上或者是省二级运动员。分以上或者是省二级运动员。PQPQ 结论：结论：该同学被大学录取。该同学被大学录取。R R 则上述例子可描述为：则上述例子可描述为：PQ

52、PQ，PRPR，QRQRR R( (二难推论二难推论) )2022-4-202022-4-20计算机学院计算机学院4747/156/156例例6.1(6.1(续续2)2)n 4)4) 前提：前提：1.1.如果某同学为省二级以上运动员，则他将被大学录取。如果某同学为省二级以上运动员，则他将被大学录取。PRPR2.2.如果某同学高考总分在如果某同学高考总分在560560分以上，则将被大学录取。分以上，则将被大学录取。QRQR3.3.某同学高考总分在某同学高考总分在560560分以上或者是省二级运动员。分以上或者是省二级运动员。PQPQ 结论：结论：该同学被大学录取。该同学被大学录取。R R 则上述

53、例子可描述为：则上述例子可描述为：PQPQ，PRPR，QRQRR R( (二难推论二难推论) )2022-4-202022-4-20计算机学院计算机学院4848/156/156例例6.1(6.1(续续2)2)n 4)4) 前提：前提：1.1.如果某同学为省二级以上运动员，则他将被大学录取。如果某同学为省二级以上运动员，则他将被大学录取。PRPR2.2.如果某同学高考总分在如果某同学高考总分在560560分以上，则将被大学录取。分以上，则将被大学录取。QRQR3.3.某同学高考总分在某同学高考总分在560560分以上或者是省二级运动员。分以上或者是省二级运动员。PQPQ 结论：该同学被大学录取。

54、结论：该同学被大学录取。R R 则上述例子可描述为：则上述例子可描述为：PQPQ，PRPR，QRQRR R( (二难推论二难推论) )2022-4-202022-4-20计算机学院计算机学院4949/156/156命题逻辑的推理命题逻辑的推理2022-4-202022-4-20计算机学院计算机学院5050/156/1561 17 7 命题逻辑的推理方法命题逻辑的推理方法n 命题演算的一个主要任务在于提供一种正确的命题演算的一个主要任务在于提供一种正确的思维规律，即思维规律，即推理规则推理规则，应用此规则从一些前，应用此规则从一些前提中推导出一个结论来，这种推导过程称为提中推导出一个结论来，这种

55、推导过程称为演演绎绎或或形式证明形式证明。n 定义定义1.191.19 设设G G1 1,G,G2 2, ,G,Gn n, ,H H是公式是公式, ,如果如果 G G1 1,G,G2 2, ,G,Gn nH H ( (G G1 1G G2 2G Gn n H)H)， 称称H H是是前提前提G G1 1,G,G2 2, ,G,Gn n 的逻辑结果的逻辑结果（有效结（有效结论）论）2022-4-202022-4-20计算机学院计算机学院5151/156/1561 17 7 命题逻辑的推理方法命题逻辑的推理方法n 命题演算的一个主要任务在于提供一种正确的思维规律，即推理规则，应用此规则从一些前提中推

56、导出一个结论来，这种推导过程称为演绎或形式证明。n 定义定义1.191.19 设设G G1 1,G,G2 2, ,G,Gn n, ,H H是公式是公式, ,如果如果 G G1 1,G,G2 2, ,G,Gn nH H ( (或表示为：或表示为：G G1 1G G2 2G Gn n H)H)， 称称H H是是前提前提G G1 1,G,G2 2, ,G,Gn n 的的逻辑结果逻辑结果（有效结有效结论论），也可以说由），也可以说由G G1 1,G,G2 2, ,G,Gn n 推出结论推出结论H H。2022-4-202022-4-20计算机学院计算机学院5252/156/156n定义定义1.201.

57、20 设设G G是由一组命题公式组成的集合，如果存在命题公是由一组命题公式组成的集合，如果存在命题公式的有限序列：式的有限序列： H H1 1，H H2 2，H Hn n（=H=H） 其中，其中，H Hi i或者是或者是G G中的中的某个公式某个公式，或者是前面的某些，或者是前面的某些H Hj j（jiji）的）的有效结论有效结论，则称公式，则称公式H H是是G G的的逻辑结果（有效逻辑结果（有效结论），结论），或者称由或者称由G G演绎演绎出结论出结论H H来。来。n定理定理公式公式H H是是公式公式集合集合G GGG1 1,G,G2 2, , ,G Gn n 的逻辑的逻辑结结果当果当且仅当

58、且仅当G G1 1GG2 2GGn nH H为永真公式。为永真公式。 在更一般意义上，我们有下述定义：在更一般意义上，我们有下述定义：2022-4-202022-4-20计算机学院计算机学院5353/156/156n定义1.20 设G是由一组命题公式组成的集合，如果存在命题公式的有限序列： H1，H2，Hn（=H） 其中，Hi或者是G中的某个公式，或者是前面的某些Hj（ji）的有效结论，则称公式H是G的逻辑结果（有效结论），或者称由G演绎出结论H来。n定理定理公式公式H H是是公式公式集合集合G GGG1 1,G,G2 2, , ,G Gn n 的逻辑的逻辑结结果果当当且仅当且仅当G G1 1

59、GG2 2GGn nH H为永真公式。为永真公式。 在更一般意义上，我们有下述定义：在更一般意义上，我们有下述定义：2022-4-202022-4-20计算机学院计算机学院5454/156/156解释解释 这里需要特别注意的是：这里需要特别注意的是：推理的有效性和结论的真实推理的有效性和结论的真实性是不同的，有效的推理不一定产生真实的结论性是不同的，有效的推理不一定产生真实的结论；而；而产生真实结论的推理过程未必是有效的，产生真实结论的推理过程未必是有效的，因为有效的因为有效的推理中可能包含为推理中可能包含为“假假”的前提，的前提，而无效的推理却可而无效的推理却可能包含为能包含为“真真”的前提

60、。的前提。 由此可见，推理的有效性是一回事，前提与结论的真由此可见，推理的有效性是一回事，前提与结论的真实与否是另一回事。所谓推理有效，指的是它的结论实与否是另一回事。所谓推理有效，指的是它的结论是它的前提的合乎逻辑的结果。也即，如果它的前提是它的前提的合乎逻辑的结果。也即，如果它的前提都为真，那么所得的结论也必然为真，而并不是要求都为真，那么所得的结论也必然为真，而并不是要求前提或结论一定为真或为假，如果推理是有效的话，前提或结论一定为真或为假，如果推理是有效的话，那么不可能它的前提都为真时，而它的结论为假。那么不可能它的前提都为真时，而它的结论为假。2022-4-202022-4-20计算