第2篇数理逻辑ch3命题逻辑

1、 第第 二二 篇篇 数数 理理 逻逻 辑辑logic（mathematical logic) 是用数学的方法来研究人类推理过程的一门是用数学的方法来研究人类推理过程的一门数学学科。数学学科。又称又称符号逻辑、现代逻辑符号逻辑、现代逻辑。 其显著特征是符号化和形式化，即把逻辑其显著特征是符号化和形式化，即把逻辑所涉及的所涉及的“概念、判断、推理概念、判断、推理”用符号来表用符号来表示，用公理体系来刻划示，用公理体系来刻划, 并基于符号串形式的并基于符号串形式的演算来描述推理过程的一般规律。演算来描述推理过程的一般规律。 第第 3 3 章章 命题逻辑命题逻辑 3-1 命题及其表示法命题及其表示法3

2、-2 联结词联结词3-3 命题公式与翻译命题公式与翻译3-4 真值表与等价公式真值表与等价公式第第3 3章章 命题逻辑命题逻辑3-5 重言式与蕴涵式重言式与蕴涵式3-6 其他联结词其他联结词3-7 对偶与范式对偶与范式3-8 推理理论推理理论第第3 3章章 命题演算及其形式系统命题演算及其形式系统 3-1 3-1 命题及其表示法命题及其表示法 我们把对我们把对确定确定的对象的对象作出判断作出判断的的陈述句陈述句称作称作（propositions or statements） 当判断正确或符合客观实际时，当判断正确或符合客观实际时，称该命题称该命题（True），用），用“T”或或“1”表示；表示

3、；否则称该命题否则称该命题（False），用），用“F”或或“0”表示。表示。要点：要点：确定确定的对象的对象 作出判断作出判断 陈述句陈述句 通常把不含有逻辑联结词的命题通常把不含有逻辑联结词的命题称为称为或或（atoms）（自然语言中的单句自然语言中的单句） 把由原子命题和逻辑联结词共同组成的把由原子命题和逻辑联结词共同组成的命题称为命题称为（compositive propositions or compound statements）（自然语言中的复句自然语言中的复句）。）。命题的符号化（标示符）：命题的符号化（标示符）： 可以用以下两种形式将命题符号化：可以用以下两种形式将命题符号化

4、： . .用（带下标的）大写字母；用（带下标的）大写字母； 例如：例如：P P：今天下雨。：今天下雨。 . .用数字。用数字。 例如：例如：1212：今天下雨。：今天下雨。 上例中的上例中的“P”P”和和“12”12”称为命题标示称为命题标示符。符。（proposition constants） 我们把表示具体命题及表示常命题的我们把表示具体命题及表示常命题的p，q，r，s等与等与f，t统称为统称为。（proposition variable） 是以是以“真、假真、假”或或“1，0”为取值范围的变为取值范围的变元，它未指出符号所表示的具体命题，可以代元，它未指出符号所表示的具体命题，可以代表任

5、意命题表任意命题 。指派指派 当命题变元用一个特定命题取代时，该命当命题变元用一个特定命题取代时，该命题变元才能有确定的真值，从而成为一个命题。题变元才能有确定的真值，从而成为一个命题。称对命题变元进行称对命题变元进行指派指派 对任意给定的命题变元对任意给定的命题变元p1,pn的一种取值的一种取值状况，称为状况，称为或或（assignments） ，用字母用字母 ， 等表示等表示 当当A对取值状况对取值状况 为真时，称指派为真时，称指派 A或或 是是A的成真赋值，记为的成真赋值，记为 (A) = 1；反之称指派反之称指派 A或或 是是A的成假赋值，记为的成假赋值，记为 (A) = 0。 3-2

6、 3-2 联结词联结词否定词否定词“并非并非”合取词合取词“并且并且”析取词析取词“或或” 条件词条件词“如果如果，那么，那么” 双条件词双条件词“当且仅当当且仅当”（negation ）“ ”表示自然表示自然语言中的语言中的“并非并非”（not ）。）。 p p F（0） T（1） T（1） F（0）表表3-2.1 否定词否定词“ ”的意义的意义 “见假为真，见真为假见假为真，见真为假”p读作读作“并非并非p”或或“非非p”。合取合取（ conjunction ）合取联结词合取联结词 “”表示自然语言中的表示自然语言中的 “并且并且”（and ）。）。 3-2.2 合取词合取词“”的意义的意

7、义 p q p q F（0） F（0） T（1） T（1） F（0） T（1） F（0） T（1） F（0） F（0） F（0） T（1）pq读作读作“p并且并且q”或或“p且且q” 见假为假，见假为假，全真为真。全真为真。词（词（disjunction） 取联结词取联结词 “ ”表示自然语言中的表示自然语言中的 “ 或或”（or ）。）。 表表 1-2.3 析取词析取词“”的意义的意义 p q p q F（0） F（0） T（1） T（1） F（0） T（1） F（0） T（1） F（0） T（1） T（1） T（1）见真为真，见真为真，全假为假。全假为假。pq读作读作“p或者或者q”、“p

8、或或q”。词（词（implication) 联结词联结词 “ ”表示自然语言中的表示自然语言中的 “如果如果，那么那么” （ifthen）。）。 表表3-2.4 词词“ ”的意义的意义 p q p q F（0） F（0） T（1） T（1） F（0） T（1） F（0） T（1） T（1） T（1） F（0） T（1）pq中的中的p称为称为，q称为称为 前真后假为假，前真后假为假，其他为真。其他为真。(two-way-implication) 联结词联结词 “ ”表示自然语言中的表示自然语言中的“当且仅当当且仅当”（if and only if）。）。 3-2.5 双向双向词词“ ”的意义的意

9、义 p q p q F（0） F（0） T（1） T（1） F（0） T（1） F（0） T（1） T（1） F（0） F（0） T（1）pq读读作作“p与与q互为条件互为条件”，“p当且仅当当且仅当q”。 相同为真，相同为真，相异为假。相异为假。 定义定义3-3.1 以下四条款规定了以下四条款规定了（proposition formula） 的意义：的意义： 命题常元或命题变元是命题公式，也称命题常元或命题变元是命题公式，也称为原子公式或原子。为原子公式或原子。如果如果A是命题公式，那么是命题公式，那么A也是命题公式。也是命题公式。如果如果A，B是命题公式，那么（是命题公式，那么（AB），）

10、，（AB），（），（AB），（），（AB）也是命题公式。）也是命题公式。只有有限步引用条款（只有有限步引用条款（1）、（）、（2）、）、所组成的符号串是命题公式。所组成的符号串是命题公式。3-3 3-3 命题公式与翻译命题公式与翻译 命题公式外层的括号可以省略；命题公式外层的括号可以省略；、。范例：如下的范例：如下的 ： PQR等价于等价于 ： （PQ）R ）等价于等价于 ： （PQ）R不等价于不等价于 ： P（QR）自然语言的语句用自然语言的语句用 形式化形式化主要是以下几个方面：主要是以下几个方面： 要准确确定原子命题，并将其形式化。要准确确定原子命题，并将其形式化。 要选用恰当的联结词，

11、尤其要善于识别自然语要选用恰当的联结词，尤其要善于识别自然语言中的联结词（有时它们被省略），否定词的位置要言中的联结词（有时它们被省略），否定词的位置要放准确。放准确。 必要必要时可以进行改述，即改变原来的叙述方式，时可以进行改述，即改变原来的叙述方式，但要保证表达意思一致但要保证表达意思一致。 需要的括号不能省略，而可以省略的括号，需要的括号不能省略，而可以省略的括号，在需要提高公式可读性时亦可不省略。在需要提高公式可读性时亦可不省略。 要注意语句的形式化未必是唯一的。要注意语句的形式化未必是唯一的。 自然语言的语句用自然语言的语句用 形式化形式化3-4 3-4 真值表与等价公式真值表与等价

12、公式 定义定义3-4.1（真值表）真值表） 在命题公式在命题公式 对于公式对于公式中分量一切可能的指派组合中分量一切可能的指派组合,公式公式A的取值可能用下表来的取值可能用下表来描述，这个表称为描述，这个表称为（truth table） 。 定义定义3-4.2 （ 等价公式）等价公式） 给定两个给定两个命题公式命题公式A和和B，设设P1，P2， ， Pn为所有出现于为所有出现于A和和B中的原子变元，若中的原子变元，若给给P1，P2， ， Pn任一组真值指派，任一组真值指派，A和和B的真值都相同，的真值都相同，则称则称A和和B是等价的或逻辑相等。记作是等价的或逻辑相等。记作AB 等价证明方法等价

13、证明方法1：可以用真值表验证两个可以用真值表验证两个是否等价。是否等价。 常用的等价等值式常用的等价等值式 E1 AA 双重否定律双重否定律 E2 AAA 幂等律幂等律 E3 AAA 幂等律幂等律 E4 ABBA 交换律交换律 E5 ABBA 交换律交换律 E6 (AB)CA(BC) 结合律结合律 E7 (AB)CA(BC) 结合律结合律 E8 A(BC) (AB)(AC) 分配律分配律 E9 A(BC) (AB)(AC) 分配律分配律 E10 (AB) AB 德摩根律德摩根律 E11 (AB) AB 德摩根律德摩根律 E12 A(AB) A 吸收律吸收律 E13 A(AB) A 吸收律吸收律

14、E14 ABAB E15 A B (AB)(BA)E16 AttE17 AtAE18 AfAE19 AffE20 AAt 排中律排中律E21 AAf 矛盾律矛盾律E22 tf, ft 否定律否定律 E23 ABCA(BC) E24 AB BA 逆否律逆否律E25 (AB)(AB) A1律律0律律 定义定义3-4.3 如果如果X X是是 A的一部分，且的一部分，且X本本身也是一个身也是一个，则称，则称X为公式为公式A的子公式。的子公式。 定理定理3-4.1 （Rule of Replacement ，简记为简记为RR）如果如果X X是是 A的子公式，若的子公式，若X Y，如果将如果将A中的中的X

15、用用Y来置换，所得到的新公式来置换，所得到的新公式B与与公式公式A等价，即等价，即A B。 等价证明方法等价证明方法2：证明思路：证明思路： “讨论指派讨论指派法法” 等价证明方法等价证明方法3： “等价代换法等价代换法”。 定义定义3-5.1 对命题公式对命题公式A，如果对，如果对A中命题变元的一中命题变元的一切指派均弄真切指派均弄真A，则，则A称为称为（tautology），），又称又称. 如果至少有一个指派弄真如果至少有一个指派弄真A，则，则A称为称为（satisfactable formula or contingency）。）。 定义定义3-5.2如果对如果对A中命题变元的一切指派均

16、弄假中命题变元的一切指派均弄假A，则称则称A为为或或（contradiction or absurdity）或或 。3-5 3-5 重言式与蕴涵式重言式与蕴涵式 定理定理3-5.1 任何两个重言式的合取或析取，仍然任何两个重言式的合取或析取，仍然是一个重言式。是一个重言式。 证明思路：证明思路：“讨论指派法讨论指派法”A为为T，B为为T， A与与B析析取（或合取）仍为取（或合取）仍为T， 定理定理3-5.2 一个重言式，对同一分量都用任何一个重言式，对同一分量都用任何Wff置换，其结果仍为一重言式。置换，其结果仍为一重言式。 证明思路：证明思路：“讨论指派法讨论指派法” 真值与分量的指派无关，

17、真值与分量的指派无关，置换后与仍为置换后与仍为T。 定理定理3-5.3 设设A、B是两个是两个Wff，一个重言式，一个重言式， AB当当且仅当且仅当A B为一重言式。为一重言式。 关于关于“当且仅当当且仅当”的证明思路：双向证明法，从的证明思路：双向证明法，从“AB”出发推出出发推出“A B为一重言式为一重言式”；再从；再从“A B为一重言式为一重言式”出发推出出发推出“AB” 。 定义定义3-4.2 （ 等价公式的另一种定义）等价公式的另一种定义）当命题当命题公式公式AB为重言式时，称为重言式时，称A逻辑等价于逻辑等价于B，记为，记为A B，它又称为，它又称为（logically equiv

18、alent or equivalent）。 定义定义3-5.3 当命题公式当命题公式AB为重言式时，称为重言式时，称A逻逻辑蕴涵辑蕴涵B，记为，记为A B，它又称为，它又称为(logically implication)。 定理定理3-5.4 设设P、Q为任意两个命题公式，为任意两个命题公式，PQ的的充分必要条件是充分必要条件是PQ Q且且Q QP P。 证明思路：证明思路： 本定理的结论是本定理的结论是“PQ” 本定理的条件是本定理的条件是“PQ Q且且Q QP P ” 如果能从条件如果能从条件“PQ Q且且Q QP P ”推出结论推出结论“PQ”，说，说明条件是充分的；明条件是充分的； 如

19、果能从结论如果能从结论“PQ”推出条件推出条件“PQ Q且且Q QP P ” ， 说明条件是必要的。说明条件是必要的。 先证必要性：先证必要性：XXXXXX 再证充分性：再证充分性：XXXXXX 关于等价式和蕴涵式的性质：关于等价式和蕴涵式的性质： （1）AB B当且仅当当且仅当 A AB B （2 2）A AB B当且仅当当且仅当 ABAB （3 3）若）若A AB B，则，则B BA A 等价对称性等价对称性 （4 4）若）若A AB B，B BC C，则，则A AC C 等价传递性等价传递性 （5 5）若）若A AB B，则，则BBA A 蕴涵逆否性蕴涵逆否性 （6 6）若）若A AB

20、B，B BC C，则，则A AC C 蕴涵传递性蕴涵传递性 （7 7）若）若A AB B，A AA A，B BB B，则，则A AB B 蕴涵等价蕴涵等价代换代换 （8 8）若）若A AB B，C CB B，则，则ACACB B （9 9）若）若A AB B，A AC C，则，则A ABCBC 设设A为永真式，为永真式，p为为A中命题变元，中命题变元，A(B/p) 表表示将示将A中中p的的出现出现代换为公式代换为公式B后所得后所得的命题公式（称为的命题公式（称为A的一个代入实例），那么的一个代入实例），那么 A(B/p)亦为永真式。亦为永真式。（Rule of Substitution），简记

21、为），简记为RS3-6 3-6 其它联结词其它联结词 3-6.1 异或异或词词“”的意义的意义 F（0） T（1） T（1） F（0） F（0） T（1） F（0） T（1） F（0） F（0） T（1） T（1） p q q pp q读作读作“p异或异或q” 相同为假，相同为假，相异为真。相异为真。异或）异或） 异或联结词的性质：异或联结词的性质： （1） （2）（）（ （3） （ （ ）分配律分配律（4）（）（ （P ） Q（5）（）（ （P ）（6）（）（ P F，FP P，T P R，R ， R ， 且且 R为一矛盾式。为一矛盾式。 表表3-6.2 异或异或词词“ ”的意义的意义 F（

22、0） F（0） T（1） F（0） F（0） T（1） F（0） T（1） F（0） F（0） T（1） T（1） p q q pp q读作读作“p和和q的条件否定的条件否定” 前真后假为真前真后假为真其余为假。其余为假。 （P ） （P ） T（1） T（1） T（1） F（0） F（0） T（1） F（0） T（1） F（0） F（0） T（1） T（1） p q q p全真为假全真为假见假为真。见假为真。 表表3-6.3 与非与非词词“ ”的意义的意义 （P ） 表表3-6.4 或非或非词词“ ”的意义的意义 T（1） T（1） T（1） F（0） F（0） T（1） F（0） T（1）

23、 F（0） F（0） T（1） T（1） p q q p全假为真全假为真见真为假。见真为假。3-7 3-7 对偶与范式对偶与范式 定义定义3-7.1 设给定的命题公式设给定的命题公式A仅含联结词仅含联结词 ，A*为将为将A中符号中符号，t，f分别改换为分别改换为，f，t后所得的公式，那么称后所得的公式，那么称A* *为为A的的（dual）。）。A为为A*的的 定理定理3-7.1 设公式设公式A A和和A A* *中仅含命题变元中仅含命题变元p p1 1,p,pn n，及，及联结词联结词，；则；则 A(pA(p1 1， p p2 2 , p , pn n) ) A A* *(p(p1 1， pp

24、2 2 , p , pn n) ) A(p A(p1 1， pp2 2 , p , pn n) ) A A* *(p(p1 1， p p2 2 , p , pn n) ) 证明思路：利用德摩根定律证明思路：利用德摩根定律 PQ PQ （PQPQ） A A A A* * 推广到推广到p p1 1， p p2 2 , p , pn n 定理定理3-7.2 设公式设公式A A和和B B中仅含命题变元中仅含命题变元p p1 1,p,pn n，如果如果A AB B，则，则A A* *B B* *。 (letters)：指命题常元、变元及它们的否定，：指命题常元、变元及它们的否定，前者又称前者又称，后者则

25、称，后者则称。(disjunctive clauses)：指文字或若干：指文字或若干文字的析取。文字的析取。 (conjunctive clauses)：指文字或若干：指文字或若干文字的合取。文字的合取。(complemental pairs of letters) ：指形如指形如L，L（L为文字）的一对字符。为文字）的一对字符。 定义定义3-7.2 命题公式命题公式A称为公式称为公式A的的（conjunctive normal form）如果如果 A A A为一析取子句或若干析取子句的合取。为一析取子句或若干析取子句的合取。 A形如：形如：A1AA2 2AAn n (n(n 1)1) 定义定

26、义3-7.3命题公式命题公式A称为公式称为公式A的的（disjunctive normal form），如果，如果 A A A为一合取子句或若干合取子句的析取为一合取子句或若干合取子句的析取。 A形如：形如：A1AA2 2AAn n (n (n 1)1)求一个命题公式的合取范式或析取范式的步骤：求一个命题公式的合取范式或析取范式的步骤： . 将公式中的联结词化归成仅含将公式中的联结词化归成仅含 、； . 利用德利用德 . 摩根定律将否定符号摩根定律将否定符号直接内移到各直接内移到各个命题变元之前；个命题变元之前； . 利用分配律、结合律将公式归约为合取范式利用分配律、结合律将公式归约为合取范式

27、或析取范式。或析取范式。定义定义3-7.4 n3-7.4 n个命题变元的合取式，称作个命题变元的合取式，称作布尔合取布尔合取或或小项小项，其中每个变元与它的否定不能同时出现，但，其中每个变元与它的否定不能同时出现，但两者必须出现且仅出现一次。两者必须出现且仅出现一次。 一般来说，一般来说，n n个命题变元共有个命题变元共有2 2n n个小项。个小项。 根据定义可知，没有两个小项是等价的，且每个根据定义可知，没有两个小项是等价的，且每个小项都只对应小项都只对应P和和Q的一组真值指派，使得该小项的的一组真值指派，使得该小项的真值为真值为T。 以上结论可推广到三个以上的变元情况，并且由以上结论可推广

28、到三个以上的变元情况，并且由此可以作出一种编码，使此可以作出一种编码，使n个变元的小项可以很快地个变元的小项可以很快地写出来。写出来。 小项有如下性质：小项有如下性质： . 每一个小项当其真值指派与编码相同时，其每一个小项当其真值指派与编码相同时，其真值为真值为T，在其余，在其余2 2n n -1种真值指派情况下均为种真值指派情况下均为F。 . 任意两个不同小项的合取式永假。任意两个不同小项的合取式永假。 . 全体小项的析取式永为真。全体小项的析取式永为真。 2 2n n -1 mi =m0mm1 1 mm 2 2n n -1 T i=0 定义定义3-7.5 对于给定的对于给定的命题公式命题公

29、式A，如果有一个等，如果有一个等价公式价公式A，它仅由小项的析取所组成，则称它仅由小项的析取所组成，则称A为为A的的（major disjunctive normal form）。）。 一个公式一个公式 定理定理3-7.33-7.3 在真值表中，一个公式的真值为在真值表中，一个公式的真值为T T的指的指派所对应的小项的析取，即为次公式的主析取范式。派所对应的小项的析取，即为次公式的主析取范式。 利用等价公式推演主析取范式的步骤：利用等价公式推演主析取范式的步骤： . 化归为析取范式。化归为析取范式。 . 除去析取范式中所有永假的析取式。除去析取范式中所有永假的析取式。 . 将析取式中重复出现的

30、合取项和相同的变元合将析取式中重复出现的合取项和相同的变元合并。并。 . 对合取项补入没有出现的命题变元，即添加对合取项补入没有出现的命题变元，即添加（P P）式，然后，应用分配律展开公式，再经）式，然后，应用分配律展开公式，再经过整理。过整理。 定义定义3-7.6 n3-7.6 n个命题变元的析取式，称作个命题变元的析取式，称作布尔析布尔析取取或或大项大项，其中每个变元与它的否定不能同时出现，其中每个变元与它的否定不能同时出现，但两者必须出现且仅出现一次。但两者必须出现且仅出现一次。 一般来说，一般来说，n n个命题变元共有个命题变元共有2 2n n个大项。个大项。 大项有如下性质：大项有如

31、下性质： . 每一个大项当其真值指派与编码相同时，其每一个大项当其真值指派与编码相同时，其真值为真值为F，在其余，在其余2 2n n -1种真值指派情况下均为种真值指派情况下均为T。 . 任意两个不同大项的析取式永真。任意两个不同大项的析取式永真。 . 全体大项的合取式永为假。全体大项的合取式永为假。 2 2n n -1 Mi =M0M M1 1 M M 2 2n n -1 F i=0 定义定义3-7.7 对于给定的对于给定的命题公式命题公式A，如果有一个等，如果有一个等价公式价公式A，它仅由大项的合取所组成，则称它仅由大项的合取所组成，则称A为为A的的（major conjunctive n

32、ormal form）。）。 一个公式一个公式 定理定理3-7.43-7.4 在真值表中，一个公式的真值为在真值表中，一个公式的真值为F F的指的指派所对应的大项的合取，即为次公式的主合取范式。派所对应的大项的合取，即为次公式的主合取范式。 利用等价公式推演主合取范式的步骤：利用等价公式推演主合取范式的步骤： . 化归为合取范式。化归为合取范式。 . 除去合取范式中所有永真的合取项。除去合取范式中所有永真的合取项。 . 将合取式中重复出现的析取项和相同的变元合将合取式中重复出现的析取项和相同的变元合并。并。 . 对析取项补入没有出现的命题变元，即添加（对析取项补入没有出现的命题变元，即添加（P

33、 P）式，然后，应用分配律展开公式，再经过整理。）式，然后，应用分配律展开公式，再经过整理。5-1 5-1 命题逻辑推理理论命题逻辑推理理论 定义定义5-1.1 设设A和和C是两个命题公式，当且仅当是两个命题公式，当且仅当AC为一重言式，即为一重言式，即A C，称，称C是是A的有效结论。或的有效结论。或C可由可由A逻辑推出。逻辑推出。 序列序列H1, H2, , Hn和和C是命题公式，当且仅当是命题公式，当且仅当 H1H2Hn C称称C是一组前提是一组前提H1, H2, , Hn的有效结论。或的有效结论。或C可由可由H1, H2, , Hn逻辑推出。逻辑推出。 判别有效结论的过程就是论证过程，

34、论证方法有判别有效结论的过程就是论证过程，论证方法有“真真值表法值表法”、“直接证明法直接证明法”和和“间接证明法间接证明法”。 （1）真值表法）真值表法 （1 1）真值表法）真值表法 设设P1, P2, , Pn 是出现于前提是出现于前提H1, H2, , Hm和结论和结论C中的全部命题变元，假定对中的全部命题变元，假定对P1, P2, , Pn作了全部的真作了全部的真值指派，这样就能对应地确定值指派，这样就能对应地确定H1, H2, , Hm和和C的所有的所有真值，列出这个真值表，即可看出真值，列出这个真值表，即可看出 H1H2Hm C是否成立。是否成立。 因为若从真值表上找出因为若从真值表上找出H1, H2, , Hm真值均为真值均为T的行，的行，对于每一个这样的行，若对于每一个这样的行，若C也有真值也有真值T，则上述蕴涵式成，则上述蕴涵式成立；或者找出立；或者找出C的真值为的真值为F的行，对于每一个这样的行，的行，对于每一个这样的行，H1, H2, , Hm的真值中至少有一个为的真值中至少有一个为F F，则，则上述蕴涵式上述蕴涵式也成立。也成立。 （2 2）直接证明法）直接证明法 直接