命题逻辑的基本概念

《命题逻辑的基本概念》由会员分享，可在线阅读，更多相关《命题逻辑的基本概念（20页珍藏版）》请在装配图网上搜索。

1、命题逻辑的基本概念 第一节命题一、什么是命题 命题是一个非真即假（不可兼）的陈述句。有两层意思，首先命题是一个陈述句，而命令 句、疑问句和感叹句都不是命题。其次是说这个陈述句所表达的内容可决定是真还是假，而且 不是真的就是假的，不能不真又不假，也不能又真又假。凡与事实相符的陈述句为真语句，而 与事实不符的陈述句为假语句。这就是说，一个命题具有两种可能的取值（又称真值）为真或 为假，又只能取其一。通常用大写字母T表示真值为真，用F表示真值为假，有时也可分别 用 1 和 0 表示它们。因为只有两种取值，所以这样的命题逻辑称为二值逻辑。我们把以这种非真必假的命题作为研究对象的逻辑称为古典逻辑，但也有

2、人反对关于命题的这 种观点，认为存在既不真也不假的命题，例如：直觉主义逻辑、多值逻辑等。聶举例举例说明命题概念：1. 雪是白的”。是一个陈述句，可决定真值，显然其真值为真，或说为T,所以是一个命题。2. 雪是黑的”。是一个陈述句，可决定真值，显然其真值为假，或说为F,所以是一个命题。3. 好大的雪啊！不是陈述句，不是命题。4. 一个偶数可表示成两个素数之和（哥德巴赫猜想）。是命题，或为真或为假，只不过当今尚不知 其是真命题还是假命题。5. 1+101=110。这是一个数学表达式，相当于一个陈述句，可以叙述为1 加 101 等110，这个句子 所表达的内容在十进制范围中真值为假，而在二进制范围中

3、真值为真。可见这个命题的真值还与所讨论问 题的范围有关。哥举例举例：下列句子都是命题（1） 8 小于 12。（2）8 大于 12。（3）21 世纪末，人类将住在月球。（4）任何一个大于5 的偶数可表成两个素数的和。（1）显然为命题，它陈述了一个事实。 （2）表示了一个错误的判断，故为假，又是一个陈述句，故 为命题。（3）也是命题，虽然现在还不知道真假，但到 21 世纪末，就能知其真假，故它是不为真必为假 的一个陈述句，即为命题。（4）是不知真假的一个陈述句，但不知不等于不存在，这句话要么为真， 要么为假，只是不知道而已，故也为一个命题。谊举例举例：下列句子不是命题。（1）8大于12吗？（2）请

4、勿吸烟。（3）X 大于 Y。（4）本页这一行的这句话是假话。（1）是一个疑问句，不是陈述句。（2）是一个祈使句。（3）是一个不能确定其真假的句子，它可能 为真，也可能为假，从而不为命题。在判断一个语句是否是命题时，从语法上就是看他是否是陈述句。但 值得注意的是，这里所说的陈述句不包括那些自指谓的语句。如（4）这个语句，它的结论是对自身而言 的，就是所谓自指谓的。这种自指谓的语句往往会产生自相矛盾的结论，即所谓的悖论。如上面这句话， 如果承认它是真的，由于本页这一行中没有别的话，所以必须承认它是假的；另一方面，如果承认它是假 的，这刚好就是这句话所说的，所以又必须承认它是真的。因此这句话本身包含

5、了悖论。我们在判断一个 语句是否是命题时把这种语句排除在命题之外。二、命题变项为了对命题作逻辑演算，采用数学手法将命题符号化（形式化）是十分重要的。我们约定用 大写字母表示命题，如以P表示雪是白的，Q表示北京是中国的首都等等。当P表示任一命 题时， P 就称为命题变项（变元）。有些文献中，用小写拉丁字母表示命题变量：p, q, r，而用大写字母代表具体的、确 指的命题： P， Q， R， ，本书在不发生混淆的地方有时也用大写字母代表命题变量。命题与命题变项含义是不同的，命题指具体的陈述句，是有确定的真值，而命题变项的真值不定，只 当将某个具体命题代入命题变项时，命题变项化为命题，方可确定其真值

6、。命题与命题变项象初等数学中 常量与变量的关系一样。如5是一个常量，是一个确定的数字，而x是一个变量，赋给它一个什么值它就 代表什么值，即x的值是不定的。初等数学的运算规则中对常量与变量的处理原则是相同的，同样在命题 逻辑的演算中，命题与命题变项的处理原则也是相同的。因此，除在概念上要区分命题与命题变项外，在 逻辑演算中就不再区分它们了。三、简单命题和复合命题简单命题又称原子命题，它是不包含任何的与、或、非一类联结词的命题。如1.1.1中所举 的命题例子都是简单命题。这样的命题是不可再分割了，如再分割就不是命题了。而像命题雪 是白的而且1 + 1 = 2，就不是简单命题，它可以分割为雪是白的以

7、及1+1=2两个简单命题, 联结词是而且。在简单命题中，尽管常有主语和谓语，但我们不去加以分割，是将简单命题作 为一个不可分的整体看待，进而作命题演算。在谓词逻辑里，才对命题中的主谓结构进行深入分 析。仅只限于简单命题的讨论，除分别讨论真值外，再没有可研究的内容了。而命题逻辑所讨论 的正是多个命题联结而成的复合命题的规律性。把一个或几个简单命题用联结词（如与、或、非） 联结所构成的新的命题称为复合命题，也称为分子命题。复合命题自然也是陈述句，其真值依赖 于构成这复合命题的各简单命题的真值以及联结词，从而复合命题有确定的真值。 张三学英语 和李四学日语就是一个复合命题，由简单命题张三学英语李四学

8、日语 经联结词和联结而 成，这两个简单命题真值均为真时，这复合命题方为真。在数理逻辑里，仅仅把命题看成是一个可取真或可取假的陈述句，所关心的并不是这些具体 的陈述句的真值究竟为什么或在什么环境下是真还是假，这是有关学科本身研究的问题，而逻辑关心的仅是命题可以被赋予真或假这样的可能性，以及规定了真值后怎样与其他命题发生联系的 问题。不能分解成更简单的命题的组合的命题称为简单命题。而像下面这样的命题：（1）期中考试，张三没有考及格。（2）期中考试，张三和李四都考及格了。（3）期中考试，张三和李四中有人考 90 分。（4）张三能考90分，那么李四也能考90 分。（5）张三能考90分当且仅当李四也能考

9、90 分。它们都是由简单命题通过加上诸如：不是，或者，而且，如果那么.，当且仅当等这样一些否定词或连词得到的。这些词称为联结词。由联结词连接的命题称为复合命题。第二节 命题连接词及真值表联结词可将命题联结起来构成复杂的命题，命题逻辑联结词的引入是十分重要的，其作用相当于初等数学里的实数集上定义的+、一、X、等运算符。通过联结词便可定义新的命题，从而使命题逻辑的内容变得丰富起来，我们要讨论的仅只是复合命题的真值，可由组成它的相应命题的真值所确定。值得注意的是逻辑联结词 与日常自然用语中的有关联结词的共同点和不同点。下面介绍五个常用的逻辑联结词：、A、V、f 联结词分为两类。一类是由此联结词构成的

10、复合命题的真假完全由构成它的简单命题的真假决定，这种联结词 叫做真值联结词。例如，张三和李四都考了 90 分。若张三考了 90 分， 李四考了 90 分都真，则原命题真，若这两个命题有一个假，则原命题假。所以和是个真值联结词。另一类是由此联结词构成的复合命题的真假不完全由构成它的简单命题的真假来确定，例 如：（1）清华大学是中国最好的大学之一，促使许多有志学子前来求学。（2）珠穆朗玛峰最高，促使许多有志学子来清华求学。这两个命题都是用联结词促使来连接的，但前者为真，后者却为假了。在古典逻辑中，我们只 讨论真值联结词，即复合命题的真假完全由构成它的简单命题的真假来确定。一、否定词一1否定词1 是

11、个一元联结词。一个命题P加上否定词就形成了一个新的命题，记作r P,这个新命题是命题的否定，读作非P。规定，若命题P的真值为真，那么1P的真值就为假。若P的真值为假，那么P的真值就为真。r P与P间的真值关系，常常使用称作真值表的一种表格来表示， 见图 1.2.1也可将图121看作是对P的定义。它表明了P的真值如何依赖于P的真值。真值表描述了命题之间的真值关系，很直观，当命题变项的个数不多时，也很容易建 立，所以真值表是命题逻辑里研究真值关系的重要工具。图 1.2.1P1001例1：昨天张三去看球赛了。这命题以p表示，于是昨天张三没有去看球赛，这新命题便 可以一1 p表示了。若昨天张三去看球赛

12、了，命题p是真的，那么新命题p必然是假的。反之，若命题p是假的, 那么P就是真的这符合图121的描述。例 2： Q： 今天是星期三。一Q：今天不是星期三。然而Q不能理解为今天是星期四”，因为今天是星期三的否定，并不一定必是星期四， 还可能是星期五、星期六。在这种情况下，要注意否定词的含义是否定被否定命题的全部， 而不是一部分。我们来看下面的例子：（1）塑料不是金属。（Q）（2）塑料是金属。（Q）对于上面的（1）句究竟算不算简单命题，有不同的看法，在有些文献中认为，简单命题中 不应该含有联结词，因此它不应当算简单命题，然而也有人认为，在人们发现塑料之初，对它的 性质还不够了解时，命题（1）也是一

13、种肯定的判断，虽然这种肯定是通过否定的方式加以表达 的。这个问题我们不去争论。重要的是，如果命题（1）用Q表示，那么命题（2）就应该用Q表示。二、合取词八合取词人是个二元命题联结词。将两个命题P、Q联结起来，构成一个新的命 题PAQ，读作P、Q的合取，也可读作P与Q。这个新命题的真值与构成它的命题P、 Q 的真值间的关系, 由合取词真值表图1.2.2 来规定。图122指出，只有当两个命题变项P = T, Q = T时方可PAQ =T,而P、Q只要 有一为F则PAQ = F。这样看来，PAQ可用来表示日常用语P与Q,或P并且Q。日常自然用语中说， 这台机器质量很好，但是很贵，这句话的含义是说同一

14、台 机器质量很好而且很贵。若用P表示这台机器量很好”，用Q表示这台机器很贵， 那么这句话的逻辑表示就是PAQ。尽管这句话里出现的联结词是但是”。总之，合 取词有与、 并且的含义，但逻辑联结词是自然用语中联结词的抽象，两者并不是 等同的，这是需注意的。在进行命题的形式化时，不能见到和，与就用A。例如，李文与李武是兄 弟， 王芳和陈兰是好朋友，这两个命题中分别有和及与字，可是它们都是简单 命题而不是复合命题，因而，分别符号化 P， Q 即可。图 1.2.2PQPAQFFFFTFTFF例 3: P: 教室里有 10 名女同学。Q: 教室里有 15 名男同学。不难看出，命题教室里有10名女同学与15名

15、男同学”，便可由PAQ来描述了。 例 4: A: 今天下雨了。B: 教室里有 100张桌子。可知AAB就是命题今天下雨了并且教室里有100张桌子P、Q、A、B都是简单命题，通过合取词A,得到了复合命题PAQ, AAB。复合命题通过A 还可得到复合命题的复合命题。日常自然用语里的联结词和、 与、 并且，一般是表示两种同类有关事物的并列关系的（如 例 3）。而在逻辑语言中仅考虑命题与命题之间的形式关系或说是逻辑内容，并不顾及日常自然 用语中是否有此说法。这样A同与、并且又不能等同视之。例4在日常自然用语句，因A, B毫无联系，然而在数理逻辑中AAB是可以讨论的。上面这一点是我们需要着重指出的。我们

16、现在只考虑命题与命题之间的形式关系，而不顾及 语句的含义，正如我们在研究语法规则时，只考虑句子的形式，而不考虑句子的意义。三、析取词V析取词V是个二元命题联结词。将两个命题P、Q联结起来，构成一个新的命题 PVQ，读作P、Q的析取，也读作P或Q。这个新命题的真值与构成它的命题P、Q 的真值间的关系，由析取词真值表图123来规定。图123指出，当P、Q有一取值为T时,PVQ便为T。仅当P、Q均取F值时,PVQ 方为F。这就是析取词的定义,PVQ可用来表示自然用语P或Q。4 图 1.2.3例 5: P: 今天刮风。Q: 今天下雨。命题今天刮风或者下雨便可由PVQ来描述了。例 6: A: 2 小于

17、3 。B: 雪是黑的。AVB就是命题2小于3或者雪是黑的”。由于2小于3是真的，所以AVB必取值为真，尽 管雪是黑的这命题取假。同样需注意析取词用或的异同。在自然语言中的或具有二义性，有时表示的是相容性或，有时表示的是不相容性或（即排 斥或）。例如：（1）张三或者李四考了 90 分。（2）第一节课上数学课或者上英语课。在（1）中，张三和李四可能都考了90 分，张三和李四中只要有一个考了90 分，则命题（1） 为真，若张三和李四都考了 90分，（1）当然为真。在（2）中，第一节课不能既上数学又上英 语，因此，若第一节课上英语和第一节课上数学两个命题都真，（2）就不为真了。这样两种用法出现了歧义，

18、这就是自然语言的意思不确定性。因此，在将命题进行形式化的 时候，我们就需要格外注意。例如，对于上例中的第二句，我们就不能简单的符号化为 PVQ， 而应该采用另外的形式，例如可以写为1 q）vCpaq）o四、蕴涵词f蕴涵词也是个二元命题联结词。将两个命题P、Q联结起来，构成一个新的 命题PQ，读作如果P则Q,或读作P蕴涵Q,如果P那么Q,其中P称前件（前项、 条件）， Q 称后件（后项、结论）。规定只有当P为T而Q为F时,PQ = F。而P = F、Q任意，或P = T、Q = T 时PQ均取值为T。真值表见图124。引入-的目的是希望用来描述命题间的推理，表示因果关系。图 1.2.4说明了:P

19、Q = T下，若P = T必有Q = T，而不会出现Q = F，这表明PQ体现了 P是 Q 成立的充分条件。PQ = T 下,若P = F可有Q = T，这表明PQ体现了 P不必是Q成立的必要 条件。使用P-Q能描述推理。即P-Q为真时，只要P为真必有Q真，而不能出现P 真而Q假就够了。至于P为假时,Q取真取假，并不违背P为真时Q必真。从而仍可 规定P为假时,P-Q取真。这当然只是对P-Q的一种说明，而从逻辑上说，本可按 真值表定义PQ,可不必涉及具体含义。另外，当P = F时对PQ真值的不同定义 方式将给推理的讨论带来不同的表示形式， 也是允许的。图125是PVQ的真值表，显然图124同12

20、5是相同的，在P、Q的所有取值下,PQ同一1 PVQ都有相同的真值，于是可记作PQ = 一1 PVQ（真值相同的等值命题以等号联结）。这也说明-可由一1、V来表示，从逻辑上 看如果P则Q同非P或Q是等同的两个命题。蕴涵词-与自然用语如果.那么.有一致的一面，可表示因果关系。然而 P、Q是无关的命题时，逻辑上允许讨论PQ。并且P = F则PQ = T,这在自然用 语中是不大使用的。图 1.2.4FQFTQFFTFTTP-Q真假值的这种取法也有人为因素，表现在：（1）根据P-Q真假值取法的定义可以看出，若P为假，不论Q是否为真，则P-Q为真。I我们来看命题如果月亮从西边出来，则太阳也从西边出来。由

21、定义这是一个真命题，但这使人感到有点不自然，既然月亮不会从西边出来，我们完全可 以认为这个命题毫无用处或毫无意义。但是，我们感兴趣的主要是（数学）推理和证明的方法， 在这种情况下，命题P-Q真的意义在于我们能从P真推出Q真，而没有必要追求从P假能推 出什么来。例如，关于整数的如下命题：对某个实数n如果n 2,那么n2 4。这是个真命题，而无须考虑命题变项取什么值。（2）蕴涵词可以连接两个以上意义毫不相干的命题，只要前件和后件满足P?Q为真的定义 所规定的条件，我们便可说P-Q为真。P-Q真假的这种规定也引起了争论。例如：如果地球停止了转动，则大熊猫产在中国。但注意到，我们关心的是推理，关心能否

22、从P真推出Q真，关心各命题之间实际意义是否 有联系。I 图 1.2.5PQ-CPVQFFT五、双条件词双条件词同样是个二元命题联结词。将两个命题P、Q联结起来构成新命 题P Q，读作P当且仅当Q,或读作P等值Q。这个新命题的真值与P、Q真值间 的关系, 由双条件词的真值表图1.2.6 来规定。图126指出，只有当两个命题P、Q的真值相同或说P = Q时,PQ的真值方 为T。而当P、Q的真值不同时,PQ = F。若建立(PQ)人(QP)的真值表，就可发现(PQ)人(QP)和卩Q有相同的 真值，于是(PQ)人(QP) = P Q图 1.2.6PQ POQFFTFTFTFF例 9: P: ABC 是

23、等腰三角形Q:AABC中有两个角相等命题就是AABC是等腰三角形当且仅当厶ABC中有两个角相等。显然就这个例子而言PQ = To六、总结所定义的五个结词是数理逻辑中最基本最常用的逻辑运算。一元二元联结词还有多 个，此外还有三元以至更多元的联结词，因其极少使用，况且又都可由这五个基本 联结词表示出来，所以无需一一定义了。 联结词是由命题定义新命题的基本方法。命题逻辑的许多问题都可化成是计算复合命题的真假值问题，真值表方法是极为有 力的工具，是应十分重视和经常使用的。 由联结词构成新命题的真值表中，对仅由两个变元 P、Q 构成的新命题 A 而言, 每个 变元有 T、F 两种取值, 从而 P、Q 共

24、有四种可能的取值, 对应于真值表中的四行, 每 一行下命题A都有确定的真值。对P、Q的每组真值组合（如P = T, Q = F）或说真值 指派，都称作命题A的一个解释。一般地说，当命题A依赖于命题P，P到A的1n真值表就有2n行，每一行对应着P1,，P的每组真值都称作命题A的一个解释。A1n有2n个解释，命题的解释用符号I表示。由于数理逻辑是采用数学的符号化的方法来研究命题间最一般的真值规律的，而不 涉及判断一个命题本身如何取真取假，抛开命题的具体含义，而是抽象形式地讨论 逻辑关系，这就导致了数理逻辑中所讨论的命题与自然用语的差异。联结词A、V、一同构成计算机的与门、或门和非门电路是相对应的。

25、从而命题逻 辑是计算机硬件电路的表示、分析和设计的重要工具。也正是数理逻辑应用于实际 特别是应用于计算机学科推动了数理逻辑的发展。_此外，五个联结词在不同的书中会采用不同的符号。如一1 P可以P或卩表示,PAQ 以PQ表示,PVQ以P + Q表示,PQ以P = Q表示,P Q以P=Q表示。阅读时 应注意不同的表示方式。在这里我们要强调两点：（1）上述五个真假联结词来源于日常使用的相应的词汇，我们的规定与它们的实际含义在 很大程度上是一致的，但由于自然语言的歧义性，期间并不完全一致。在以后的使用中，以上联 结词组成的复合命题的真假值一定要根据这五个联结词的定义去理解，而不能根据日常语言的意 义去

26、理解。（2）在今后我们主要关心的是命题间的真假值的关系，而不讨论命题的内容。第三节合式公式命题公式是命题逻辑讨论的对象，而由命题变项使用联结词可构成任意多的复 合命题，如一PAQ, PAQVR, P一1 Q等。问题是它们是否都有意义呢？只有一 个联结词的命题一1 P, PAQ, PQ当然是有意义的。由两个联结词构成的命题 PAQVR至少意义不明确，是先作PAQ再对R做V,还是先作QVR再对P作A呢？ 1 PAQ也有同样的问题。解决运算次序是容易的，可像初等代数那样使用括号的 办法, 在逻辑运算中也常使用圆括号来区分运算的先后次序。这样由命题变项、命题 联结词和圆括号便组成了命题逻辑的全部符号。

27、进一步的问题是建立一个一般的原 则以便生成所有的合法的命题公式，并能识别什么样的符号串是合法的（有意义的)？合式公式(简记为Wff)的定义：1. 简单命题是合式公式。2. 如果A是合式公式，那么1 A也是合式公式。3. 如果A、B是合式公式，那么(AAB), (AVB), (AB)和(A B)是合式公式。4. 当且仅当经过有限次地使用1.2.3所组成的符号串才是合式公式。 这个定义给出了建立合式公式的一般原则，也给出了识别一个符号串是否是合式公式的原则。这是递归(归纳)的定义。在定义中使用了所要定义的概念，如在2和3中都 出现了所要定义的合式公式字样，其次是定义中规定了初始情形，如 1 中指明

28、了已 知的简单命题是合式公式。条件4说明了哪些不是合式公式，而1、 2和3说明不了这一点。 依定义，若判断一个公式是否为合式公式，必然要层层解脱回归到简单命题方 可判定。(PAQ), (P(PAQ),(PQ)人(QR)(PR)都是合式公式。而PVQV, (PQ)( AQ), (PQ 都不是合式公式, 没有意义, 我们不讨论。在实际使用中，为了减少圆括号的数量，可以引入一些约定，如规定联结词优 先级的办法，可按一1 , V,A,，的排列次序安排优先的级别，多个同一联 结词按从左到右的优先次序。这样，在书写合式公式时，可以省去部分或全部圆括 号。通常采用省略一部分又保留一部分括号的办法，这样选择就

29、给公式的阅读带来 方便。如(P(QVR)可写成 P(QVR)或 PQVRo(P(PR)可写成 P(PR)。命题演算中只讨论合式公式, 为方便起见, 将合式公式就称作公式。由此定义的4易知，任一合式公式必为下列6种形式之一：命题变元、A、 (AAB), (AVB), (AB)和(AB)。例如，下列符号串都是合式公式：一1 Q，PA_1Q，CP)VQ，PVCP)，(PA P)(一P(PVR)。若合式公式P中含有n个不同的命题变元，则说P是n元合式公式。合式公式代表了所有命题， n 元合式公式表示此命题由 n 个简单命题复合而成， 此命题的真假就由这n个简单命题的真假完全确定。怎样表示命题形式的真假

30、值呢？ 我们给出如下定义。设P为一个合式公式，P中出现的所有命题变项都在p，P2，Pn中，对序列 (P, P2，Pn)指定的任一真假值序列0, t2，tn)称为P的关于P, P2， Pn 的一个指派(assignment)或解释(其中 t.=T 或 F, iN, Un)。若 P, P2， Pn的一个指派使P为真，则称此指派为P的一个成真指派；若P, P2，Pn的一个指派使P为假，则称此指派为P的一个成假指派。由定义可得：P关于P的成真指派为F,成假指派为T。PAQ关于P、Q的成真指派为(T,T),成假指派为(T,F) , (F,T), (F,F)。 PVQ关于P、Q的成真指派为(T,T), (

31、T,F) , (F,T),成假指派为(F,F)。 同时我们也不难给出A-B和 LB的成真和成假指派。这样，我们在这里也就可以给出真值表的确切定义，即合式公式在所有可能的 指派下所取值列成的表成为真值表。在后面我们统一用解释这个词，而不是上面的指派第四节重言式一、定义命题公式中有一类重言式。如果一个公式，对于它的任一解释I下其 真值都为真，就称为重言式(永真式)。如pv1 P是一个重言式。显然由V、A、-和 联结的重言式仍是重言式。一个公式，如有某个解释I0,在I0下该公式真值为真，则称这公式是 可满足的。PVQ当取I0 = (T, F)即P = T, Q = F时便有PVQ = T,所以是 可

32、满足的。重言式当然是可满足的。另一类公式是矛盾式(永假式或不可满足的)。如果一个公式，对于 它的任一解释I下真值都是假，便称是矛盾式。如PA P就是矛盾式。不难看出这三类公式间有如下关系:1. 公式A永真，当且仅当一1 A永假。2. 公式A可满足，当且仅当1 A非永真。3. 不是可满足的公式必永假。4. 不是永假的公式必可满足。举例：证明P-(Q-(PAQ)是重言式证明：构造它的真值表，用来看是否在它的任一解释I下其真值都为真。PQ(PAQ)(Q-(PAQ)P-(Q-(PAQ)FFFTTTFFTTFTFFTTTTTT故P(Q(P A Q)是一个重言式。由于任何公式中包含的变元个数总是有限的，所

33、以其真值解释也只有有限多个， 故真值表总可以做出。而公式为何种公式可以从真值表看出，因此，对任何公式 都可判定它是何种公式，亦即命题逻辑的判定问题是可解的。二、代入规则A是一个公式，对A使用代入规则得公式B,若A是重言式，则B也 是重言式。为保证重言式经代入规则仍得到保持， 要求:1. 公式中被代换的只能是命题变元(原子命题)， 而不能是复合命题。2. 对公式中某命题变项施以代入，必须对该公式中出现的所有同一命 题变项代换同一公式。(RaS)如可用(RAS)来代换某公式中的P,记作,而不能反过来将公式中的(RAS)以P代之。这一要求可以代数的例子来说明，如对(a + b)2 = a2 + 2a

34、b + b2可以a = cd代入，仍会保持等式成立。而若将a + b以cd代入，结果左端得(cd)2, 而右端无法代入cd,不能保持等式成立了。一般地说，公式A经代入规则可得任一公式，而仅当A是重言式时，代入后方 得保持。(R vS)如A = P厂P,作代入*/得B = 一一Q仍是重言式。若将P以Q代之得B = PVQ(这不是代入，违反了规定(2)不是重言式了)。 在第三章公理系统中，代入规则视作重要的推理规则经常使用。例题举例：使用代入规则证明重言式。例1:判断(RVS) V-1 (RVS)为重言式。因PV_1P为重言式，作代入便得(RVS) V-1 (RVS)。依据代入规则，这公式必是重言

35、式。例 2：判断(RVS)人(RVS)(PVQ)(PVQ)为重言式. 不难验证(AA(AB)B是重言式，便 M(R V S) A (RV S)(PVQ)(P V Q)是重言式。简单自然语言的形式化所介绍的五个联结词及其与自然用语的联系和区别，为自然语句的形 式化作了准备。一些推理问题的描述，常是以自然语句来表示的，需首先 把自然语句形式化成逻辑语言，即以符号表示的逻辑公式，然后根据逻辑 演算规律进行推理演算。这一节讨论自然语句的形式化。形式化过程。先要引入一些命题符号P、Q、用来表示自然语句中所出现的简 单命题，进而依自然语句通过联结词将这些命题符号联结起来，以形成表示自然语 句的合式公式。这

36、个过程要注意自然语句中某些联结词的逻辑含义。一、简单自然语句的形式化1. 北京不是村庄。令P表示北京是村庄，于是1可表示为P。2. 李明既聪明又用功。令P表示李明聪明，Q表示李明用功”，于是2可表示为PAQ。3血是有理数的话2近也是有理数。令P表示是有理数，Q表示是有理数”，于是3可表示为PQ。二、较复杂自然语句的形式化需注意的是逻辑联结词是从自然语句中提炼抽象出来的，它仅保留了逻辑内容，而把自然语句所表达的主观因素、心理因素以及文艺修辞方面的因素全部撇开了，从而命题联结词只表达了自然语句的一种客观性质。又由于自然语句本身并不严谨，常有二义性，自然会出现同一自然语句的不等价的逻辑描述，其根由在

37、于人们对同一自然语句的不同理解。例 1: 张三与李四是表兄弟。 这是普通的自然用语，它是一个命题，令以 R 表示, 若形式地规定: P: 张三是表兄弟。Q: 李四是表兄弟。那么R = PAQo显然，这样的形式化是错误的。原因很简单。张三是表兄弟，李四是表兄弟 都不是命题。实际上张三与李四是表兄弟才是一个命题，而且是一个简单命题。这 例子说明自然语句中的与不一定都能用合取词来表达。例 2 ：张三或李四都能做这件事。这句话中的或不一定就用析取词来表示，应允许有的人把这命题的内容理解 为：张三能做这件事而且李四也能做这件事，这样，这句话便可以PAQ的形式表示 了。例 3: 给了三个命题A: 今晚我在

38、家里看电视。B: 今晚我去体育场看球赛。C: 今晚我在家里看电视或去体育场看球赛。问题是C与AVB是否表达的是同一命题呢？回答是否定的。因为C同A、B的真值关系应由图 1.5.1 给出第六节波兰表达式数理逻辑也谓之符号逻辑。自然对一个公式如何以符号描述是给以关 注的，像括号的使用，联结词的中辍、前辍、后辍形式的选择，都直接影 响着同一公式描述和计算的复杂程度。若用计算机来识别、计算、处理逻 辑公式，不同的表示方法会带来不同的效率。一、计算机识别括号的过程合式公式的定义中使用的是联结词的中辍表示，又引入括号以便区分 运算次序，这些都是人们常用的方法。计算机识别处理这样表示的公式的方法，需反复自左

39、向右，自右向左的扫描。如对公式(PV(QAR) V(SAT)真值的计算过程, 开始从左向右扫描，至发现第一个右半括号为止， 便返回至最近的左半括号，得部分公式(QAR)方可计算真值。随后又向右 扫描，至发现第二个右半括号，便返回至第二个左半括号，于是得部分公 式(PV(QAR)并计算真值，重复这个过程直至计算结束。如图161所示 的扫描过程123.67。这种多次重复扫描, 显然是有浪费的，从而降低了机器的使用效率。 追溯这种重复扫描的原因并不在于使用了括号，而在于公式的中辍表示方 法。图 1.6.1公式中的运算符是否非要括号才能定义呢？若一个式子中同时使用两种或两种 以上的运算符放置方式时，无

40、论怎样对运算符的优先级进行规定，括号都不能完全 避免。例如：对数运算符log是前置运算符，阶乘运算符!是后置运算符，而对式子 logn!来说，对于不同的运算优先级，它可以有两种不同的含义，分别为log(n!)和 (logn)!。但无论是规定log的优先级大于!还是!的优先级大于log，都只能表示其中之 一，而另一个则必须使用括号。因此，我们可以采用下面的思维方式：将中置、后置全部换成前置或将中置、前置全部换成后置。这样，便可不使用 任何括号。二、波兰式一般地说，使用联结词构成公式有三种方式，中辍式如PVQ,前辍式 如VPQ,后辍式如PQV。前缀式用于逻辑学是由波兰的数理逻辑学家J. Lukas

41、iewicz提出的， 称之为波兰表示式。如将公式PV(QAR)AS)的这种中辍表示化成波兰式，可由内层括号逐步向外层脱开(或由外层向里逐层脱开)的办法。如图 1.6.2以波兰式表达的公式，由计算机识别处理的过程，当自右向右扫描时 可以一次完成，避免了重复扫描。同样后辍表示(逆波兰式)也有同样的 优点，而且自左向右一次扫描(看起来更合理)使可识别处理一个公式， 很是方便，常为计算机的程序系统所采用，只不过这种表示的公式，人们 阅读起来不大习惯。由外向里：举例：中置变前置 PV(QVR)AS)由里向外：PV(CQVK)AS)PVCVQRAS)PVAVQRSPVC(QVR)AS)VP(CQVR)AS

42、)VPACQVR) SVPAVQRSVPAVQRS叢例题【本章小结】【本章小结】数理逻辑是用数学方法研究逻辑的学科。它的核心内容为命题逻辑和谓词逻 辑。本章是命题逻辑的基础知识，主要涉及命题逻辑的基本结构以及自然语言的形 式化方法。本章中通过命题概念引出简单命题，再通过 5个常用的命题联结词构成新的复合命 题，从而构成命题逻辑的理论基础。由5 个常用的命题联结词所定义的运算是数理逻辑中最基本最常用的逻辑运 算。本章详细介绍了这5 个命题联结词的定义与真值表，并举例说明了它们的使用 方法。其中否定词属一元联结词，其它几个均为二元联结词。联结词是由已有命题 定义新命题的基本方法，是命题逻辑中最基本

43、的内容之一。参见 5 个常用的命题逻 辑联结词列表。命题逻辑中的许多问题都可以化为计算复合命题的真假值问题，因而真值表 方法是命题逻辑中一个极为有力的工具。由命题公式列写真值表以及下一章将介绍 的由真值表列写命题公式，都是学习命题逻辑需要熟练掌握的基本功。联结词AV、同构成计算机的与门、或门和非门电路是相对应的。下一章 中还要讲到的实际中常用的与非门和或非门电路则对应着与非和或非联结词。从而 命题逻辑是计算机硬件电路的表示、分析和设计的重要工具。也正是数理逻辑应用 于实际特别是应用于计算机学科推动了数理逻辑的发展。自然语句的形式化是研究命题逻辑的一个基本出发点和归宿。本章在引入命 题联接词后，

44、对自然语句的形式化方法进行了介绍，不论是简单自然语句还是较复 杂的自然语句，都需要注意自然语言与命题逻辑符号表示的特点与差别。【课后习题】1. P,Q为两个命题，当且仅当时，PAQ的真值为1,当且仅当时，PVQ的值为0。(1.2节)2. P, Q为两个命题，当且仅当时，P-Q的真值为0。(1.2节)3. 两个重言式的析取为，一个重言式与一个矛盾式的析取为。(1.4 节)1. 下面联结词不具有交换律的是( ) 。 (1.2节)(A B) AC) VD)2. 下面语句是真命题的为()。(1.1 节)(A) 我正在说谎(B) 如果1 + 1 = 2，则雪是黑色的(C) 如果1 + 1 = 3，则雪是

45、黑色的( D )吃饭了吗？3. 合式公式(PA(P-Q) Q 是()。(1.4 节)(A) 矛盾式(B) 蕴涵式(C) 重言式( D )等价式4. 下列合式公式中， ()是重言式。(1.4节)(A) (PQ)人(Qf P)(B) (PAQ)P(C) (PVQ)(D) (PVQ)A(PVQ)5下列合式公式中，()不是重言式。(1.4 节)(A) Q(PVQ)(B) (PAQ)P(C) (PAQ)A(PVQ)(D) (PVQ) (PQ)6重言式的否定为()。(1.4 节)(A) 重言式(B) 矛盾式(C) 可满足式(D) 蕴涵式7.合式公式P (QP)为()。(1.4节)(A) 重言式(B) 可满足式(C) 矛盾式( D )等值式