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

1、,第二篇数理逻辑,逻辑学（logic）是一门研究思维形式及思维规律的科学。数理逻辑（mathematicallogic)是用数学的方法来研究人类推理过程的一门数学学科。,数理逻辑又称符号逻辑、现代逻辑。,其显著特征是符号化和形式化，即把逻辑所涉及的“概念、判断、推理”用符号来表示，用公理体系来刻划,并基于符号串形式的演算来描述推理过程的一般规律。,第3章命题逻辑,3-1命题及其表示法,3-2联结词,3-3命题公式与翻译,3-4真值表与等价公式,第3章命题逻辑,3-5重言式与蕴涵式,3-6其他联结词,3-7对偶与范式,3-8推理理论,第3章命题演算及其形式系统,3-1命题及其表示法,我们把对确定

2、的对象作出判断的陈述句称作命题（propositionsorstatements）,当判断正确或符合客观实际时，称该命题真（True），用“T”或“1”表示；否则称该命题假（False），用“F”或“0”表示。要点：确定的对象作出判断陈述句,通常把不含有逻辑联结词的命题称为原子命题或原子（atoms）（自然语言中的单句）,把由原子命题和逻辑联结词共同组成的命题称为复合命题（compositivepropositionsorcompoundstatements）（自然语言中的复句）。,命题的符号化（标示符）：可以用以下两种形式将命题符号化：.用（带下标的）大写字母；例如：P：今天下雨。.用数字。

3、例如：12：今天下雨。上例中的“P”和“12”称为命题标示符。,命题常元（propositionconstants）我们把表示具体命题及表示常命题的p，q，r，s等与f，t统称为命题常元。,命题变元（propositionvariable）是以“真、假”或“1，0”为取值范围的变元，它未指出符号所表示的具体命题，可以代表任意命题。,指派当命题变元用一个特定命题取代时，该命题变元才能有确定的真值，从而成为一个命题。称对命题变元进行指派,对任意给定的命题变元p1,pn的一种取值状况，称为指派或赋值（assignments），用字母，等表示,当A对取值状况为真时，称指派弄真A或是A的成真赋值，记为(

4、A)=1；反之称指派弄假A或是A的成假赋值，记为(A)=0。,3-2联结词,否定词“并非”,合取词“并且”,析取词“或”,条件词“如果，那么”,双条件词“当且仅当”,(1)否定（negation）定义3-2.1设P为一命题，P的否定是一个新命题，记作“P”。若P为T，P为F；若P为F，P为T。联结词“”表示自然语言中的“并非”（not）。,表3-2.1否定词“”的意义,“见假为真，见真为假”p读作“并非p”或“非p”。,（2）合取（conjunction）定义3-2.2两个命题P和Q的合取是一个复合命题，记作PQ。当且仅当P、Q同时为T时，PQ为T，其他情况下，PQ的真值都是F。合取联结词“”

5、表示自然语言中的“并且”（and）。,3-2.2合取词“”的意义,pq读作“p并且q”或“p且q”,见假为假，全真为真。,（3）析取词（disjunction）定义3-2.3两个命题P和Q的析取是一个复合命题，记作PQ。当且仅当P、Q同时为F时，PQ为F，其他情况下，PQ的真值都是T。析取联结词“”表示自然语言中的“或”（or）。,表1-2.3析取词“”的意义,见真为真，全假为假。,pq读作“p或者q”、“p或q”。,（4）条件词（implication)定义3-2.4给定两个命题P和Q，其条件命题是一个复合命题，记作PQ。当且仅当P的真值为T，Q的真值为F时，PQ的真值为F，其他情况下，PQ

6、的真值都是T。条件联结词“”表示自然语言中的“如果，那么”（ifthen）。,表3-2.4条件词“”的意义,pq中的p称为条件前件，q称为条件后件,前真后假为假，其他为真。,（5）双条件(two-way-implication)定义3-2.5给定两个命题P和Q，其复合命题PQ称作双条件命题。当P和Q的真值相同时，PQ的真值为T，否则，PQ的真值都是F。双条件联结词“”表示自然语言中的“当且仅当”（ifandonlyif）。,3-2.5双向条件词“”的意义,pq读作“p与q互为条件”，“p当且仅当q”。,相同为真，相异为假。,定义3-3.1以下四条款规定了命题公式（propositionform

7、ula）的意义：,（1）单个命题常元或命题变元是命题公式，也称为原子公式或原子。（2）如果A是命题公式，那么A也是命题公式。（3）如果A，B是命题公式，那么（AB），（AB），（AB），（AB）也是命题公式。（4）只有有限步引用条款（1）、（2）、（3）所组成的符号串是命题公式。命题公式又称为合式公式Wff（Wellformedformula）Wff的正例和反例见其他书上表述。,3-3命题公式与翻译,联结词的优先级命题公式外层的括号可以省略；联结词的优先级：、。利用加括号的方法可以提高优先级。范例：如下的Wff：PQR等价于Wff：（PQ）R）等价于Wff：（PQ）R不等价于Wff：P（QR）

8、,自然语言的语句用Wff形式化主要是以下几个方面：,要准确确定原子命题，并将其形式化。,要选用恰当的联结词，尤其要善于识别自然语言中的联结词（有时它们被省略），否定词的位置要放准确。,必要时可以进行改述，即改变原来的叙述方式，但要保证表达意思一致。,需要的括号不能省略，而可以省略的括号，在需要提高公式可读性时亦可不省略。,要注意语句的形式化未必是唯一的。自然语言的语句用Wff形式化的例子可见其他书上表述。,3-4真值表与等价公式,定义3-4.1（真值表）在命题公式Wff中，对于公式中分量一切可能的指派组合,公式A的取值可能用下表来描述，这个表称为真指表（truthtable）。,定义3-4.2

9、（等价公式）给定两个命题公式A和B，设P1，P2，Pn为所有出现于A和B中的原子变元，若给P1，P2，Pn任一组真值指派，A和B的真值都相同，则称A和B是等价的或逻辑相等。记作AB等价证明方法1：可以用真值表验证两个Wff是否等价。,常用的等价等值式E1AA双重否定律E2AAA幂等律E3AAA幂等律E4ABBA交换律E5ABBA交换律E6(AB)CA(BC)结合律E7(AB)CA(BC)结合律E8A(BC)(AB)(AC)分配律E9A(BC)(AB)(AC)分配律E10(AB)AB德摩根律E11(AB)AB德摩根律E12A(AB)A吸收律E13A(AB)A吸收律,E14ABABE15AB(AB

10、)(BA)E16AttE17AtAE18AfAE19AffE20AAt排中律E21AAf矛盾律E22tf,ft否定律E23ABCA(BC)E24ABBA逆否律E25(AB)(AB)A,1律,0律,定义3-4.3如果X是WffA的一部分，且X本身也是一个Wff，则称X为公式A的子公式。定理3-4.1（替换原理RuleofReplacement，简记为RR）如果X是WffA的子公式，若XY，如果将A中的X用Y来置换，所得到的新公式B与公式A等价，即AB。等价证明方法2：证明思路：“讨论指派法”等价证明方法3：“等价代换法”。,定义3-5.1对命题公式A，如果对A中命题变元的一切指派均弄真A，则A称

11、为重言式（tautology），又称永真式.,如果至少有一个指派弄真A，则A称为可满足式（satisfactableformulaorcontingency）。,定义3-5.2如果对A中命题变元的一切指派均弄假A，则称A为不可满足式或矛盾式（contradictionorabsurdity）或永假式。,3-5重言式与蕴涵式,定理3-5.1任何两个重言式的合取或析取，仍然是一个重言式。证明思路：“讨论指派法”A为T，B为T，A与B析取（或合取）仍为T，定理3-5.2一个重言式，对同一分量都用任何Wff置换，其结果仍为一重言式。证明思路：“讨论指派法”真值与分量的指派无关，置换后与仍为T。定理3-

12、5.3设A、B是两个Wff，一个重言式，AB当且仅当AB为一重言式。关于“当且仅当”的证明思路：双向证明法，从“AB”出发推出“AB为一重言式”；再从“AB为一重言式”出发推出“AB”。,定义3-4.2（等价公式的另一种定义）当命题公式AB为重言式时，称A逻辑等价于B，记为AB，它又称为逻辑等价式（logicallyequivalentorequivalent）。,定义3-5.3当命题公式AB为重言式时，称A逻辑蕴涵B，记为AB，它又称为逻辑蕴涵式(logicallyimplication)。,定理3-5.4设P、Q为任意两个命题公式，PQ的充分必要条件是PQ且QP。证明思路：本定理的结论是“

13、PQ”本定理的条件是“PQ且QP”如果能从条件“PQ且QP”推出结论“PQ”，说明条件是充分的；如果能从结论“PQ”推出条件“PQ且QP”，说明条件是必要的。先证必要性：XXXXXX再证充分性：XXXXXX,关于等价式和蕴涵式的性质：（1）AB当且仅当AB（2）AB当且仅当AB（3）若AB，则BA等价对称性（4）若AB，BC，则AC等价传递性（5）若AB，则BA蕴涵逆否性（6）若AB，BC，则AC蕴涵传递性（7）若AB，AA，BB，则AB蕴涵等价代换（8）若AB，CB，则ACB（9）若AB，AC，则ABC,设A为永真式，p为A中命题变元，A(B/p)表示将A中p的所有出现全部代换为公式B后所得

14、的命题公式（称为A的一个代入实例），那么A(B/p)亦为永真式。,代入原理（RuleofSubstitution），简记为RS,3-6其它联结词,3-6.1异或词“”的意义,pq读作“p异或q”,相同为假，相异为真。,（1）不可兼析取（异或）定义3-6.1两个命题公式P和Q的不可兼析取是一个新命题公式，记作PQ。当且仅当P、Q真值不同时，PQ为T，其他情况下的真值都是F。,异或联结词的性质：（1）PQPQ交换律（2）（PQ）RP（QR）结合律（3）P（QR）（PQ）（PR）分配律（4）（PQ）（PQ）（PQ）（5）（PQ）（PQ）（6）（PP）F，FPP，TPP定理3-6.1设P、Q和R为命题

15、公式，如果PQR，则PRQ，QRP，且PQR为一矛盾式。证明思路利用性质（6）。,表3-6.2异或词“”的意义,pq读作“p和q的条件否定”,前真后假为真其余为假。,（2）条件否定定义3-6.2设P和Q是两个命题公式，P和Q的条件否定是一个新命题公式，记作PQ。当且仅当P的真值为T，Q的真值为F时，PQ为T，其他情况下的真值都是F。根据此定义，可知PQ（PQ）,（3）与非定义3-6.3设P和Q是两个命题公式，P和Q的与非是一个新命题公式，记作PQ。当且仅当P和Q的真值都为T时，PQ为F，其他情况下PQ的真值都是T。根据此定义，可知PQ（PQ）PQ的3个性质见P-26页。,全真为假见假为真。,表

16、3-6.3与非词“”的意义,（4）或非定义3-6.4设P和Q是两个命题公式，P和Q的或非是一个新命题公式，记作PQ。当且仅当P和Q的真值都为F时，PQ为T，其他情况下PQ的真值都是F。根据此定义，可知PQ（PQ）PQ的性质与联结词性质留给大家自己推算。,表3-6.4或非词“”的意义,全假为真见真为假。,3-7对偶与范式,定义3-7.1设给定的命题公式A仅含联结词，A*为将A中符号，t，f分别改换为，f，t后所得的公式，那么称A*为A的对偶式（dual）。显然，A也为A*的对偶式。,定理3-7.1设公式A和A*中仅含命题变元p1,pn，及联结词，；则A(p1，p2,pn)A*(p1，p2,pn)

17、A(p1，p2,pn)A*(p1，p2,pn)证明思路：利用德摩根定律PQ（PQ）AA*推广到p1，p2,pn,定理3-7.2设公式A和B中仅含命题变元p1,pn，如果AB，则A*B*。,文字(letters)：指命题常元、变元及它们的否定，前者又称正文字，后者则称负文字。,析取子句(disjunctiveclauses)：指文字或若干文字的析取。,合取子句(conjunctiveclauses)：指文字或若干文字的合取。,互补文字对(complementalpairsofletters)：指形如L，L（L为文字）的一对字符。,定义3-7.2命题公式A称为公式A的合取范式（conjunctiv

18、enormalform）如果（1）AA（2）A为一析取子句或若干析取子句的合取。A形如：A1A2An(n1),定义3-7.3命题公式A称为公式A的析取范式（disjunctivenormalform），如果（1）AA（2）A为一合取子句或若干合取子句的析取。A形如：A1A2An(n1),求一个命题公式的合取范式或析取范式的步骤：.将公式中的联结词化归成仅含、；.利用德.摩根定律将否定符号直接内移到各个命题变元之前；.利用分配律、结合律将公式归约为合取范式或析取范式。定义3-7.4n个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时出现，但两者必须出现且仅出现一次。一般来说，

19、n个命题变元共有2n个小项。,根据定义可知，没有两个小项是等价的，且每个小项都只对应P和Q的一组真值指派，使得该小项的真值为T。以上结论可推广到三个以上的变元情况，并且由此可以作出一种编码，使n个变元的小项可以很快地写出来。小项有如下性质：.每一个小项当其真值指派与编码相同时，其真值为T，在其余2n-1种真值指派情况下均为F。.任意两个不同小项的合取式永假。.全体小项的析取式永为真。2n-1mi=m0m1m2n-1Ti=0,定义3-7.5对于给定的命题公式A，如果有一个等价公式A，它仅由小项的析取所组成，则称A为A的主析取范式（majordisjunctivenormalform）。一个公式主

20、析取范式可以构成真值表的方法写出。定理3-7.3在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为次公式的主析取范式。利用等价公式推演主析取范式的步骤：.化归为析取范式。.除去析取范式中所有永假的析取式。.将析取式中重复出现的合取项和相同的变元合并。.对合取项补入没有出现的命题变元，即添加（PP）式，然后，应用分配律展开公式，再经过整理。,定义3-7.6n个命题变元的析取式，称作布尔析取或大项，其中每个变元与它的否定不能同时出现，但两者必须出现且仅出现一次。一般来说，n个命题变元共有2n个大项。大项有如下性质：.每一个大项当其真值指派与编码相同时，其真值为F，在其余2n-1种真值指派

21、情况下均为T。.任意两个不同大项的析取式永真。.全体大项的合取式永为假。2n-1Mi=M0M1M2n-1Fi=0,定义3-7.7对于给定的命题公式A，如果有一个等价公式A，它仅由大项的合取所组成，则称A为A的主合取范式（majorconjunctivenormalform）。一个公式主合取范式可以构成真值表的方法写出。定理3-7.4在真值表中，一个公式的真值为F的指派所对应的大项的合取，即为次公式的主合取范式。利用等价公式推演主合取范式的步骤：.化归为合取范式。.除去合取范式中所有永真的合取项。.将合取式中重复出现的析取项和相同的变元合并。.对析取项补入没有出现的命题变元，即添加（PP）式，然后，应用分配律展开公式，再经过整理。,5-1命题逻辑推理理论,定义5-1.1设A和C是两个命题公式，当且仅当AC为一重言式，即AC，称C是A的有效结论。或C可由A逻辑推出。序列H1,H2,Hn和C是命题公式，当且仅当H1H2HnC称C是一组前提H1,H2,Hn的有效结论。或C可由H1,H2,Hn逻辑推出。判别有效结论的过程就是论证过程，论证方法有“真值表法”、“直接证明法”和“间接证明法”。（1）真值表法,（1）真值表法设P1,P2,Pn是出现于前提H1,H2,Hm和结论C中的全部命题