数字电路课件

1、1-8 1-8 推理理论推理理论目的要求目的要求：1.1.掌握各种不同类型的推理规则掌握各种不同类型的推理规则2.2.熟练掌握逻辑推理证明的不同证明方法的熟练掌握逻辑推理证明的不同证明方法的证明原理、不同的应用场景证明原理、不同的应用场景 1-8 1-8 推理理论推理理论有效结论有效结论（推理的形式结构）（推理的形式结构）推理方法推理方法真值表法；等价（值）演算法；主析取范式法真值表法；等价（值）演算法；主析取范式法构造证明法构造证明法直接证法（直接证法（P P规则；规则；T T规则）规则）间接证法（反证法（归缪法）；间接证法（反证法（归缪法）； CPCP规则）规则）推理证明中常用的推理规则推

2、理证明中常用的推理规则P P规则（前提引入规则）规则（前提引入规则）T T规则（结论引入规则）规则（结论引入规则）CPCP规则（条件证明引入规则）规则（条件证明引入规则）1-8 1-8 推理理论推理理论命题演算的一个主要任务在于提供一种正确的命题演算的一个主要任务在于提供一种正确的思维规律，即思维规律，即推理规则推理规则，应用此规则从一些前，应用此规则从一些前提中推导出一个结论来，这种推导过程称为提中推导出一个结论来，这种推导过程称为演演绎绎或或形式证明形式证明。推理的有效性推理的有效性：是指它的结论是它的前提的合：是指它的结论是它的前提的合符逻辑的结果。符逻辑的结果。1-8 1-8 推理理论

3、推理理论在逻辑学中，把从前提在逻辑学中，把从前提出发，依据公认的推理出发，依据公认的推理规则，规则，推导出一个结论的过程称为推导出一个结论的过程称为有效推理有效推理或或形式证明形式证明。所得的结论叫。所得的结论叫有效结论有效结论。在数理逻辑中，集中研究的是用来从前提导出在数理逻辑中，集中研究的是用来从前提导出结论的结论的推理规则推理规则和和论证原理论证原理。这里最关心的不。这里最关心的不是结论的真实性，而是是结论的真实性，而是推理的有效性推理的有效性。与这些。与这些规则有关的理论称为推理理论。规则有关的理论称为推理理论。1-8 1-8 推理理论推理理论推理：推理：从一个或多个从一个或多个前提前

4、提推出推出结论结论的的思维过程思维过程。 前提：前提：已知的或假定的命题公式（可有多个前提）已知的或假定的命题公式（可有多个前提）结论：结论：从前提出发应用推理规则推出的命题公式。从前提出发应用推理规则推出的命题公式。1-8 1-8 推理理论推理理论定义定义1-8.11-8.1 设设A和和C是两个命题公式，当且仅是两个命题公式，当且仅当当AC为一重言式为一重言式, ,即即AC，称，称C是是A的的有效有效结论结论。或。或C可由可由A逻辑的推出。逻辑的推出。推广到推广到n个前提个前提的情况：的情况：设设H1,H2,Hn，C是命题公式，当且仅当是命题公式，当且仅当H1 H2 Hn C为一重言式，即为

5、一重言式，即H1 H2 Hn C称称C是是一组前提一组前提H1,H2,Hn的的有效结论有效结论。称称H1 H2 Hn C为由前提为由前提H1,H2,Hn推推结论结论C的的推理形式结构推理形式结构。1-8 1-8 推理理论推理理论推理（论证）推理（论证）：判断有效结论（：判断有效结论（判断推理是否判断推理是否正确的正确的）的具体过程）的具体过程 推理方法：推理方法：即即判断有效结论（判断有效结论（判断推理是否正判断推理是否正确）的方法，也就是重言式的证明方法：确）的方法，也就是重言式的证明方法：（1 1）真值表法；）真值表法；（2 2）等价（值）演算法；）等价（值）演算法；（3 3）主析取范式法

6、；）主析取范式法；（4 4）构造证明法）构造证明法(a)直接证法直接证法(b)间接证法间接证法 1-8 1-8 推理理论推理理论例例：判断下面：判断下面推理是否正确推理是否正确（1 1）如果天气凉快，小王就不去游泳。天气）如果天气凉快，小王就不去游泳。天气凉快。所以小王没去游泳。凉快。所以小王没去游泳。（2 2）如果我上街，我一定去新华书店。我没）如果我上街，我一定去新华书店。我没上街，所以我没去新华书店。上街，所以我没去新华书店。解决推理问题的步骤：解决推理问题的步骤：（a a）将命题符号化；）将命题符号化；（b b）写出前提、结论和推理的形式结构；）写出前提、结论和推理的形式结构；（c c

7、）进行判断）进行判断1-8 1-8 推理理论推理理论（1 1）如果天气凉快，小王就不去游泳。天气）如果天气凉快，小王就不去游泳。天气凉快。所以小王没去游泳。凉快。所以小王没去游泳。解解: :（a a）命题符号化）命题符号化P:P:天气凉快天气凉快 Q:Q:小王去游泳。小王去游泳。（b b）前提、结论和推理的形式结构）前提、结论和推理的形式结构前提前提: P: PQ,P结论：结论： Q推理的形式结构推理的形式结构: (P: (PQ) P ) Q1-8 1-8 推理理论推理理论（c c）判断）判断(P(PQ) P ) Q是否为重言式是否为重言式v真值表法：真值表法：P PQ Q Q QP PQ(P

8、(PQ) P 原式原式1 11 10 00 00 01 11 10 01 11 11 11 10 01 10 01 10 01 10 00 01 11 10 01 1真值表的最后一列全为真值表的最后一列全为1，因而是重言，因而是重言式。所以推理正确。式。所以推理正确。1-8 1-8 推理理论推理理论v等值演算法：等值演算法： (P(PQ) P ) Q ( P P Q) P ) Q ( ( P P Q) P Q ( ( P P Q) （ P Q）1所以推理正确。所以推理正确。1-8 1-8 推理理论推理理论主析取范式法：主析取范式法： (PQ) P ) Q ( P Q) P ) Q ( P Q)

9、 P Q (P Q) ( P (Q Q) ( Q (P P) (P Q) ( P Q) ( P Q) ( Q P) ( Q P) (P Q) (P Q ) ( P Q) ( P Q)m11 m10 m01 m00m3 m2 m1 m0所以推理正确。所以推理正确。1-8 1-8 推理理论推理理论（2 2）如果我上街，我一定去新华书店。我没）如果我上街，我一定去新华书店。我没上街，所以我没去新华书店。上街，所以我没去新华书店。解解: :（a a）命题符号化）命题符号化P:P:我上街我上街 Q:Q:我去新华书店。我去新华书店。（b b）前提、结论和推理的形式结构）前提、结论和推理的形式结构前提前提:

10、 P: PQ, P结论：结论： Q推理的形式结构推理的形式结构: (P: (PQ) P ) Q1-8 1-8 推理理论推理理论（c c）判断）判断(P(PQ) P)Q是否为重言式是否为重言式 (PQ) P ) Q ( P Q) P ) Q ( P Q) P Q (P Q) (P (Q Q) ( Q (P P) (P Q) (P Q) (P Q) ( Q P) ( Q P) (P Q) (P Q ) ( P Q)m11 m10 m00m3 m2 m0(P(PQ) P)Q不是重言式，故推理不不是重言式，故推理不正确正确1-8 1-8 推理理论推理理论判断判断推理正确性的构造证明方法：推理正确性的构

11、造证明方法：在推理过程中，如果命题变元较多或前提较多，在推理过程中，如果命题变元较多或前提较多，以上三种方法都不方便，因而引入构造证明方以上三种方法都不方便，因而引入构造证明方法。法。这种方法必须建立在推理定律（重言蕴含式）这种方法必须建立在推理定律（重言蕴含式）的基础之上。的基础之上。证明证明是一个描述推理过程的是一个描述推理过程的命题公式序列命题公式序列，其，其中的每个命题公式，或者是已知的前提，或者中的每个命题公式，或者是已知的前提，或者是由某些前提应用推理规则得到的结论。是由某些前提应用推理规则得到的结论。1-8 1-8 推理理论推理理论证明中常用的推理规则：证明中常用的推理规则：（1

12、 1）P P规则（前提引入规则）：前提在推导过规则（前提引入规则）：前提在推导过程中的任何时候都可以引入程中的任何时候都可以引入（2 2）T T规则（结论引入规则）：在推导中，如规则（结论引入规则）：在推导中，如果有一个或多个公式重言蕴含着公式果有一个或多个公式重言蕴含着公式S S，则公，则公式式S S可以引入推导之中。即可以引入推导之中。即在证明过程中，所在证明过程中，所证明的结论都可以作为后续证明的前提证明的结论都可以作为后续证明的前提。（3 3）置换规则：在证明的任何步骤上，命题）置换规则：在证明的任何步骤上，命题公式的任何子命题公式都可以用与之等价的命公式的任何子命题公式都可以用与之等

13、价的命题公式置换。题公式置换。1-8 1-8 推理理论推理理论常用的蕴含式列表（由推理定律得到的推理规常用的蕴含式列表（由推理定律得到的推理规则）则） 参见课本参见课本P P4343。I1、PQP I2、 PQ Q I3、 PPQ I4、 QPQI5、 ?PPQ I6、 Q PQI7、 ?(PQ) P I8、 ?(PQ)? Q I9、 P,Q PQI10、 ?P,PQ Q I11、 P,PQQ I12、 ?Q,PQ ? P1-8 1-8 推理理论推理理论I13、 PQ,QRPRI14、 PQ, RQ,PR QI15、 PQ(PR)(QR)I16、 PQ (PR)(QR)注：注： H1, H2,

14、 , HnC与与 H1 H2 Hn C含意相同含意相同PQ ? PQ：最重要的等价式：最重要的等价式P(PQ)Q：最重要的蕴含式：最重要的蕴含式PQ ? Q ? P（逆反式）：熟悉此转换（逆反式）：熟悉此转换1-8 1-8 推理理论推理理论常用的等价式列表常用的等价式列表 参见课本参见课本P P4343。E1、 ? ? P P E2、 PQ Q P E3、 PQ Q P E4、(PQ)R P(QR)E5、 (PQ)R P(QR) E6、P（QR）（PQ）（P R） E7、 P（QR）（PQ）（ P R）E8、 ? (PQ ) ? P ? Q1-8 1-8 推理理论推理理论E9、 ? (P Q

15、) ? P ? Q E10、P P P E11、 P P PE12、R（P ? P）RE13、R（P ? P）R E14、R（P ? P）TE15、R（P ? P）FE16、P Q ? P Q 1-8 1-8 推理理论推理理论E17 、 ? (PQ) P ? Q E18、PQ ? Q ? P E19、P(QR) (PQ)R E20、PQ (PQ) (QP)E21、P Q (PQ) (? P ? Q)E22、 ? (P Q) P ? Q1-8 1-8 推理理论推理理论直接直接证明方法：证明方法：由一组前提，利用一些公认的由一组前提，利用一些公认的推理规则，根据已知的等价或蕴含公式，推演推理规则，

16、根据已知的等价或蕴含公式，推演得到有效的结论。得到有效的结论。例例1 证明证明(P Q)(P R)(Q S) S R即即S R是是前提前提P Q，P R,Q S的的有效结论有效结论。（前提、结论已明确给出）（前提、结论已明确给出）分析分析： P QQ S P S S PP R S RS R例例1 1 证明证明( (P Q)(P R)(Q S) S R证法证法1 1：（1 1） P Q P （2 2） P Q T(1)E (条件转化律条件转化律) （3 3） Q S P （4 4） P S T(2)(3) I(假言三段论假言三段论) （5 5） S P T(4)E (条件转化律条件转化律) （6

17、 6） P R P （7 7） S R T(5)(6) I(假言三段论假言三段论) （8 8） S R T(7)E (条件转化律条件转化律) 例例1 1 证明证明( (P Q)(P R)(Q S) S R分析分析：P QS R例例1 1 证明证明( (P Q)(P R)(Q S) S RP Q R QQ R S RP Q S R 证法证法2 2：（1 1） P R P （2 2） P Q R Q T(1)I (前后件附加前后件附加) （3 3） Q S P （4 4） Q R S R T(3)I (前后件附加前后件附加) （5 5） P Q S R T (2)(4)I (假言三段论假言三段论)

18、 （6 6） P Q P （7 7） S R T(5)(6) I(假言推理假言推理) 例例1 1 证明证明( (P Q)(P R)(Q S) S R注：注：推理过程不是唯一的。推理过程不是唯一的。只要严格按照推理规则从而得到有效结论的只要严格按照推理规则从而得到有效结论的推理就是正确的。推理就是正确的。证明过程中不要跳步。证明过程中不要跳步。（跳步在等价公式或（跳步在等价公式或蕴含式的证明中可以使用，但这里不可以）蕴含式的证明中可以使用，但这里不可以）练习题练习题前提：前提：PQ , Q R ,P S , S结论：结论：R1-8 1-8 推理理论推理理论定义定义1-8.2 1-8.2 设公式设

19、公式H1,H2,Hm中的命题变元中的命题变元为为P1,P2,Pn，对于，对于P1,P2,Pn的一些真值指的一些真值指派，如果能使派，如果能使H1 H2 Hm的真值为的真值为T，则称公式则称公式H1,H2,Hm是是相容的相容的。如果对于如果对于P1,P2,Pn的每一组真值指派使得的每一组真值指派使得H1 H2 Hm的真值均为的真值均为F，则称公式，则称公式H1,H2,Hm是是不相容的不相容的。1-8 1-8 推理理论推理理论间接证明方法之一（归缪法，反证法）：间接证明方法之一（归缪法，反证法）：设有一组前提设有一组前提H1,H2,Hm，要推出结论，要推出结论C，即证即证H1 H2 Hm C记作：

20、记作：S C,即证即证S C为永真，为永真，或证或证 C S为永真，或证为永真，或证C S永真，永真，故要证故要证 C S永假。永假。即即只要证明只要证明H1,H2,Hm及及 C是是不相容的。不相容的。只需将只需将 C作为附加前提作为附加前提能推出矛盾来即可能推出矛盾来即可分析分析：PQPQ Q R QQ Q例例2 2 证明证明(PQ) (QR) P（附加前提）附加前提）（矛盾）（矛盾）例例2 2 证明证明(PQ) (QR) P证明：证明： （1 1）P Q P （2）P P(附加前提附加前提) （3） (QR) P （4） Q R T(3)E(德摩根律德摩根律) （5）Q T(1)(2)I

21、(假言推理假言推理) （6） Q T(4)I(化简式化简式) （7）Q Q（矛盾）（矛盾） T(5)(6)I分析分析：P Q (S R) R S R S Q例例3 3 用归缪法证明用归缪法证明( (P Q)(P R)(Q S) S R（附加前提）附加前提）（矛盾）（矛盾）Q SP PPP R P例例3 3 用归缪法证明用归缪法证明( (P Q)(P R)(Q S) S R证明：证明： （1 1） (S R) P (附加前提附加前提) （2） S R T(1)E(德摩根律德摩根律) （3） S T(2)I （4） R T(2)I （5） Q S P （6） Q T(3)(5)I （7） P R

22、P （8） P T(4)(7)I 例例3 3 用归缪法证明用归缪法证明( (P Q)(P R)(Q S) S R证明证明(续续)： （9） P Q P （10） PT(6)(9)I （11） P P （矛盾）（矛盾）T(8)(10)I例例3 3 用归缪法证明用归缪法证明( (P Q)(P R)(Q S) S R证明：证明： （1 1） (S R) P (附加前提附加前提) （2） S R T(1)E(德摩根律德摩根律) （3） P Q P （4） P Q T(3)E(条件转化律条件转化律) （5） Q S P （6） P S T(4)(5)I(假言三段论假言三段论（7 7） S P T(6)E

23、(条件转化律条件转化律)（8） ( S R) (P R) T(7)I(前后件附加前后件附加)（9） P R T(2)(8)I(假言推理假言推理)（10）P R P（11） P R T(10)E(条件转化律条件转化律)（12） (P R) T(11)E(德摩根律德摩根律)（13） (P R) (P R) （矛盾）（矛盾） T(9)(12)I练习题：练习题：前提：前提：P Q , R Q , R S结论：结论： P1-8 1-8 推理理论推理理论间接证明方法之二间接证明方法之二 : :CP规则规则要证要证H1 H2 Hm （ R C）设设H1 H2 Hm 为为S ，即证，即证S ( (R C)或或

24、S ( R C)即证即证S ( R C)为永真式为永真式因为因为S ( R C) S ( R C) ( S R) C (S R) C(S R) C所以，若将所以，若将R作为附加前提，如有作为附加前提，如有(S R) C，即证得即证得S ( (R C)由由(S R) C，证得，证得S ( (R C)，称为称为CP规则规则。分析分析：SP S P例例4 4 证明证明P ( ( Q R)， S P，Q S R（附加前提）附加前提）RP ( ( Q R)Q RQ例例4 4 证明证明P ( ( Q R)， S P，Q S R证明：证明： （1 1）S P (附加前提附加前提) （2） S P P （3）

25、 P T(1)(2)I(析取三段论析取三段论) （4） P ( ( Q R) P （5） Q R T(3)(4) I(假言推理假言推理) （6） Q P （7） R T(5)(6) I(假言推理假言推理) （8） S R CP练习题：练习题：前提：前提：(P Q)( R S), (S V) U结论：结论：P U综合例题综合例题根据下列条件构造推理的证明。根据下列条件构造推理的证明。 (1) 或者天晴，或者下雨。或者天晴，或者下雨。(2) 如果天晴，我就去看电影。如果天晴，我就去看电影。(3) 如果我去看电影，我就不看书。如果我去看电影，我就不看书。结论：如果我在看书则天在下雨。结论：如果我在看

26、书则天在下雨。和命题翻译结合的推理题目和命题翻译结合的推理题目（前提、结论未明确给出（前提、结论未明确给出,需需要自己构造。要自己构造。)综合例题综合例题设设 M：天晴。：天晴。 Q：下雨。：下雨。S：我去看电影。：我去看电影。 R：我看书。：我看书。前提前提: (1) (M Q) (2) M S (3) S R结论：结论： R Q详细证明参见课本详细证明参见课本P46例题例题6。综合练习综合练习如果考试及格，那我高兴。若我高兴，那么我饭量如果考试及格，那我高兴。若我高兴，那么我饭量增加。我的饭量减少，所以我考试没有及格。试对增加。我的饭量减少，所以我考试没有及格。试对上述论证构造证明。上述论

27、证构造证明。解：解：设设P P：我考试及格：我考试及格 Q Q：我高兴。：我高兴。 R R：我饭量增加。此论证可表为：我饭量增加。此论证可表为 PQPQ，QRQR，R R PP （1 1）PQ PQ P P （2 2）QRQR P P （3 3） RRP P （4 4） QQT(2)(3)IT(2)(3)I （5)5) PPT(1)(4)IT(1)(4)I综合练习综合练习符号化并推证结论是否有效：符号化并推证结论是否有效：为庆祝九七香港回归，足坛四支劲旅举行友谊为庆祝九七香港回归，足坛四支劲旅举行友谊比赛。已知情况如下，问结论是否有效？比赛。已知情况如下，问结论是否有效？前提：前提：1). 1

28、). 若大连获得冠军，则北京或上海获得亚军。若大连获得冠军，则北京或上海获得亚军。2). 2). 若上海获得亚军，则大连不能获得冠军。若上海获得亚军，则大连不能获得冠军。3). 3). 若延边获得亚军，则北京不能获得亚军。若延边获得亚军，则北京不能获得亚军。4). 4). 最后大连获得冠军。最后大连获得冠军。 结论：结论：5). 5). 延边没有获得亚军。延边没有获得亚军。命题符号：命题符号： A A：大连获得冠军：大连获得冠军 B B：北京获得亚军：北京获得亚军 C C：上海获得亚军：上海获得亚军 D D：延边获得亚军：延边获得亚军 以上四句话成为四个命题以上四句话成为四个命题vA B CvC Av D B(1)A证明证明(A B C)(C A)(D B)AD综合练习综合练习综合练习综合练习符号化并推证结论：符号化并推证结论：若厂方拒绝增加工资，则罢工不会停止，除非若厂方拒绝增加工资，则罢工不会停止，除非罢工超过一年并且工厂经理辞职。罢工超过一年并且工厂经理辞职。 问：如果问：如果厂方拒绝增加工资，而罢工又刚刚开始，罢工厂方拒绝增加工资，而罢工又刚刚开始，罢工是否能停止是否能停止? ?命题符号：命题符号： A A：厂方拒绝增加工资厂方拒绝增加工资 B B：罢工不会停止罢工不会停止 C C：罢工超过