命题逻辑的基本概念.docx

命题逻辑的基本概念 第一节 命题一、什么是命题命题是一个非真即假（不可兼）的陈述句。有两层意思，首先命题是一个陈述句，而命令句、疑问句和感叹句都不是命题。其次是说这个陈述句所表达的内容可决定是真还是假，而且不是真的就是假的，不能不真又不假，也不能又真又假。凡与事实相符的陈述句为真语句，而与事实不符的陈述句为假语句。这就是说，一个命题具有两种可能的取值（又称真值）为真或为假，又只能取其一。通常用大写字母T表示真值为真，用F表示真值为假，有时也可分别用1和0表示它们。因为只有两种取值，所以这样的命题逻辑称为二值逻辑。我们把以这种非真必假的命题作为研究对象的逻辑称为古典逻辑，但也有人反对关于命题的这种观点，认为存在既不真也不假的命题，例如：直觉主义逻辑、多值逻辑等。 举例举例说明命题概念：1. 雪是白的。是一个陈述句，可决定真值，显然其真值为真，或说为T，所以是一个命题。2. 雪是黑的。是一个陈述句，可决定真值，显然其真值为假，或说为F，所以是一个命题。3. 好大的雪啊！不是陈述句，不是命题。4. 一个偶数可表示成两个素数之和（哥德巴赫猜想）。是命题，或为真或为假，只不过当今尚不知其是真命题还是假命题。5. 1+101=110。这是一个数学表达式，相当于一个陈述句，可以叙述为1加101等110，这个句子所表达的内容在十进制范围中真值为假，而在二进制范围中真值为真。可见这个命题的真值还与所讨论问题的范围有关。 举例举例：下列句子都是命题（1） 8小于12。（2） 8大于12。（3） 21世纪末，人类将住在月球。（4） 任何一个大于5的偶数可表成两个素数的和。（1）显然为命题，它陈述了一个事实。（2）表示了一个错误的判断，故为假，又是一个陈述句，故为命题。（3）也是命题，虽然现在还不知道真假，但到21世纪末，就能知其真假，故它是不为真必为假的一个陈述句，即为命题。（4）是不知真假的一个陈述句，但不知不等于不存在，这句话要么为真，要么为假，只是不知道而已，故也为一个命题。 举例举例：下列句子不是命题。（1） 8大于12吗？（2） 请勿吸烟。（3） X大于Y。（4） 本页这一行的这句话是假话。（1）是一个疑问句，不是陈述句。（2）是一个祈使句。（3）是一个不能确定其真假的句子，它可能为真，也可能为假，从而不为命题。在判断一个语句是否是命题时，从语法上就是看他是否是陈述句。但值得注意的是，这里所说的陈述句不包括那些自指谓的语句。如（4）这个语句，它的结论是对自身而言的，就是所谓自指谓的。这种自指谓的语句往往会产生自相矛盾的结论，即所谓的悖论。如上面这句话，如果承认它是真的，由于本页这一行中没有别的话，所以必须承认它是假的；另一方面，如果承认它是假的，这刚好就是这句话所说的，所以又必须承认它是真的。因此这句话本身包含了悖论。我们在判断一个语句是否是命题时把这种语句排除在命题之外。 二、 命题变项为了对命题作逻辑演算，采用数学手法将命题符号化（形式化）是十分重要的。我们约定用大写字母表示命题，如以P表示雪是白的，Q表示北京是中国的首都等等。当P表示任一命题时，P就称为命题变项（变元）。有些文献中，用小写拉丁字母表示命题变量：p，q，r，而用大写字母代表具体的、确指的命题：P，Q，R，本书在不发生混淆的地方有时也用大写字母代表命题变量。 命题与命题变项含义是不同的，命题指具体的陈述句，是有确定的真值，而命题变项的真值不定，只当将某个具体命题代入命题变项时，命题变项化为命题，方可确定其真值。命题与命题变项象初等数学中常量与变量的关系一样。如5是一个常量，是一个确定的数字，而x是一个变量，赋给它一个什么值它就代表什么值，即x的值是不定的。初等数学的运算规则中对常量与变量的处理原则是相同的，同样在命题逻辑的演算中，命题与命题变项的处理原则也是相同的。因此，除在概念上要区分命题与命题变项外，在逻辑演算中就不再区分它们了。三、 简单命题和复合命题简单命题又称原子命题，它是不包含任何的与、或、非一类联结词的命题。如1.1.1中所举的命题例子都是简单命题。这样的命题是不可再分割了，如再分割就不是命题了。而像命题雪是白的而且1 + 1 = 2，就不是简单命题，它可以分割为雪是白的以及1+1=2两个简单命题,联结词是而且。在简单命题中，尽管常有主语和谓语，但我们不去加以分割，是将简单命题作为一个不可分的整体看待，进而作命题演算。在谓词逻辑里，才对命题中的主谓结构进行深入分析。仅只限于简单命题的讨论，除分别讨论真值外，再没有可研究的内容了。而命题逻辑所讨论的正是多个命题联结而成的复合命题的规律性。把一个或几个简单命题用联结词（如与、或、非）联结所构成的新的命题称为复合命题，也称为分子命题。复合命题自然也是陈述句，其真值依赖于构成这复合命题的各简单命题的真值以及联结词，从而复合命题有确定的真值。张三学英语和李四学日语就是一个复合命题，由简单命题张三学英语李四学日语 经联结词和联结而成，这两个简单命题真值均为真时，这复合命题方为真。在数理逻辑里，仅仅把命题看成是一个可取真或可取假的陈述句，所关心的并不是这些具体的陈述句的真值究竟为什么或在什么环境下是真还是假，这是有关学科本身研究的问题，而逻辑关心的仅是命题可以被赋予真或假这样的可能性，以及规定了真值后怎样与其他命题发生联系的问题。 不能分解成更简单的命题的组合的命题称为简单命题。而像下面这样的命题：（1） 期中考试，张三没有考及格。（2） 期中考试，张三和李四都考及格了。（3） 期中考试，张三和李四中有人考90分。（4） 张三能考90分，那么李四也能考90分。（5） 张三能考90分当且仅当李四也能考90分。它们都是由简单命题通过加上诸如：不是，或者，而且，如果那么，当且仅当等这样一些否定词或连词得到的。这些词称为联结词。由联结词连接的命题称为复合命题。第二节 命题连接词及真值表联结词可将命题联结起来构成复杂的命题，命题逻辑联结词的引入是十分重要的，其作用相当于初等数学里的实数集上定义的、等运算符。通过联结词便可定义新的命题，从而使命题逻辑的内容变得丰富起来，我们要讨论的仅只是复合命题的真值，可由组成它的相应命题的真值所确定。值得注意的是逻辑联结词与日常自然用语中的有关联结词的共同点和不同点。下面介绍五个常用的逻辑联结词：、联结词分为两类。一类是由此联结词构成的复合命题的真假完全由构成它的简单命题的真假决定，这种联结词叫做真值联结词。例如，张三和李四都考了90分。若张三考了90分，李四考了90分都真，则原命题真，若这两个命题有一个假，则原命题假。所以和是个真值联结词。另一类是由此联结词构成的复合命题的真假不完全由构成它的简单命题的真假来确定，例如：（1） 清华大学是中国最好的大学之一，促使许多有志学子前来求学。（2） 珠穆朗玛峰最高，促使许多有志学子来清华求学。这两个命题都是用联结词促使来连接的，但前者为真，后者却为假了。在古典逻辑中，我们只讨论真值联结词，即复合命题的真假完全由构成它的简单命题的真假来确定。一、 否定词否定词是个一元联结词。一个命题P加上否定词就形成了一个新的命题，记作P，这个新命题是命题的否定，读作非P。规定，若命题P的真值为真，那么P的真值就为假。若P的真值为假, 那么P 的真值就为真。P 与P间的真值关系, 常常使用称作真值表的一种表格来表示, 见图1.2.1也可将图1.2.1看作是对P的定义。它表明了P的真值如何依赖于P的真值。真值表描述了命题之间的真值关系，很直观，当命题变项的个数不多时，也很容易建立，所以真值表是命题逻辑里研究真值关系的重要工具。 图1.2.1 例题例1: 昨天张三去看球赛了。这命题以P表示，于是昨天张三没有去看球赛，这新命题便可以P表示了。若昨天张三去看球赛了，命题P是真的，那么新命题P必然是假的。反之，若命题P是假的，那么P就是真的.这符合图1.2.1的描述。例题例2: Q: 今天是星期三。Q: 今天不是星期三。然而Q不能理解为今天是星期四，因为今天是星期三的否定，并不一定必是星期四，还可能是星期五、星期六。在这种情况下，要注意否定词的含义是否定被否定命题的全部，而不是一部分。我们来看下面的例子：（1） 塑料不是金属。（Q）（2） 塑料是金属。（Q）对于上面的（1）句究竟算不算简单命题，有不同的看法，在有些文献中认为，简单命题中不应该含有联结词，因此它不应当算简单命题，然而也有人认为，在人们发现塑料之初，对它的性质还不够了解时，命题（1）也是一种肯定的判断，虽然这种肯定是通过否定的方式加以表达的。这个问题我们不去争论。重要的是，如果命题（1）用Q表示，那么命题（2）就应该用Q表示。二、 合取词合取词是个二元命题联结词。将两个命题P、Q联结起来，构成一个新的命题PQ, 读作P、Q的合取, 也可读作P与Q。这个新命题的真值与构成它的命题P、Q的真值间的关系, 由合取词真值表图1.2.2来规定。图1.2.2指出, 只有当两个命题变项P = T, Q = T时方可PQ =T, 而P、Q只要有一为F则PQ = F。这样看来，PQ可用来表示日常用语P与Q, 或P并且Q。日常自然用语中说，这台机器质量很好，但是很贵，这句话的含义是说同一台机器质量很好而且很贵。若用P表示这台机器量很好，用Q表示这台机器很贵，那么这句话的逻辑表示就是PQ。尽管这句话里出现的联结词是但是。总之，合取词有与、并且的含义，但逻辑联结词是自然用语中联结词的抽象，两者并不是等同的，这是需注意的。在进行命题的形式化时，不能见到和，与就用。例如，李文与李武是兄弟，王芳和陈兰是好朋友，这两个命题中分别有和及与字，可是它们都是简单命题而不是复合命题，因而，分别符号化P，Q即可。 图1.2.2 例题例3: P: 教室里有10名女同学。Q: 教室里有15名男同学。不难看出,命题教室里有10名女同学与15名男同学，便可由PQ来描述了。例4: A: 今天下雨了。B: 教室里有100张桌子。可知AB就是命题今天下雨了并且教室里有100张桌子.P、Q、A、B都是简单命题, 通过合取词, 得到了复合命题PQ, AB。复合命题通过还可得到复合命题的复合命题。日常自然用语里的联结词和、与、并且，一般是表示两种同类有关事物的并列关系的（如例3）。而在逻辑语言中仅考虑命题与命题之间的形式关系或说是逻辑内容，并不顾及日常自然用语中是否有此说法。这样同与、并且又不能等同视之。例4在日常自然用语句，因A, B毫无联系，然而在数理逻辑中AB是可以讨论的。上面这一点是我们需要着重指出的。我们现在只考虑命题与命题之间的形式关系，而不顾及语句的含义，正如我们在研究语法规则时，只考虑句子的形式，而不考虑句子的意义。 三、 析取词析取词是个二元命题联结词。将两个命题P、Q联结起来,构成一个新的命题PQ, 读作P、Q的析取, 也读作P或Q。这个新命题的真值与构成它的命题P、Q的真值间的关系, 由析取词真值表图1.2.3来规定。图1.2.3指出, 当P、Q有一取值为T时, PQ便为T。仅当P、Q均取F值时, PQ方为F。这就是析取词的定义, PQ可用来表示自然用语P或Q。图1.2.3 例题例5: P: 今天刮风。Q: 今天下雨。命题今天刮风或者下雨便可由PQ来描述了。例题例6: A: 2小于3。B: 雪是黑的。AB就是命题2小于3或者雪是黑的。由于2小于3是真的, 所以AB必取值为真, 尽管雪是黑的这命题取假。同样需注意析取词用或的异同。在自然语言中的或具有二义性，有时表示的是相容性或，有时表示的是不相容性或（即排斥或）。例如：（1） 张三或者李四考了90分。（2） 第一节课上数学课或者上英语课。在（1）中，张三和李四可能都考了90分，张三和李四中只要有一个考了90分，则命题（1）为真，若张三和李四都考了90分，（1）当然为真。在（2）中，第一节课不能既上数学又上英语，因此，若第一节课上英语和第一节课上数学两个命题都真，（2）就不为真了。这样两种用法出现了歧义，这就是自然语言的意思不确定性。因此，在将命题进行形式化的时候，我们就需要格外注意。例如，对于上例中的第二句，我们就不能简单的符号化为PQ，而应该采用另外的形式，例如可以写为(PQ)(PQ)。四、 蕴涵词蕴涵词也是个二元命题联结词。将两个命题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。真值表见图1.2.4。引入的目的是希望用来描述命题间的推理, 表示因果关系。图1.2.4说明了: PQ = T下, 若P = T必有Q = T, 而不会出现Q = F, 这表明PQ体现了P是Q成立的充分条件。PQ = T下, 若P = F可有Q = T, 这表明PQ体现了P不必是Q成立的必要条件。使用PQ能描述推理。即PQ为真时, 只要P为真必有Q真, 而不能出现P真而Q假就够了。至于P为假时, Q取真取假, 并不违背P为真时Q必真。从而仍可规定P为假时, PQ取真。这当然只是对PQ的一种说明, 而从逻辑上说, 本可按真值表定义PQ, 可不必涉及具体含义。另外, 当P = F时对PQ真值的不同定义方式将给推理的讨论带来不同的表示形式, 也是允许的。图1.2.5是PQ的真值表, 显然图1.2.4同1.2.5是相同的, 在P、Q的所有取值下, PQ同PQ都有相同的真值, 于是可记作 PQ = PQ(真值相同的等值命题以等号联结)。这也说明可由、来表示, 从逻辑上看如果P则Q同非P或Q是等同的两个命题。蕴涵词与自然用语如果那么有一致的一面，可表示因果关系。然而P、Q是无关的命题时,逻辑上允许讨论PQ。并且P = F则PQ = T, 这在自然用语中是不大使用的。图1.2.4 PQ真假值的这种取法也有人为因素，表现在：（1） 根据PQ真假值取法的定义可以看出，若P为假，不论Q是否为真，则PQ为真。我们来看命题如果月亮从西边出来，则太阳也从西边出来。由定义这是一个真命题，但这使人感到有点不自然，既然月亮不会从西边出来，我们完全可以认为这个命题毫无用处或毫无意义。但是，我们感兴趣的主要是（数学）推理和证明的方法，在这种情况下，命题PQ真的意义在于我们能从P真推出Q真，而没有必要追求从P假能推出什么来。例如，关于整数的如下命题：对某个实数n，如果n 2，那么n2 4。这是个真命题，而无须考虑命题变项取什么值。（2） 蕴涵词可以连接两个以上意义毫不相干的命题，只要前件和后件满足P?Q为真的定义所规定的条件，我们便可说PQ为真。PQ真假的这种规定也引起了争论。例如：如果地球停止了转动，则大熊猫产在中国。但注意到，我们关心的是推理，关心能否从P真推出Q真，关心各命题之间实际意义是否有联系。图1.2.5 五、 双条件词双条件词同样是个二元命题联结词。将两个命题P、Q联结起来构成新命题PQ, 读作P当且仅当Q, 或读作P等值Q。这个新命题的真值与P、Q真值间的关系, 由双条件词的真值表图1.2.6来规定。图1.2.6指出, 只有当两个命题P、Q的真值相同或说P = Q时, PQ的真值方为T。而当P、Q的真值不同时, PQ = F。若建立(PQ)(QP)的真值表, 就可发现(PQ)(QP)和PQ有相同的真值, 于是(PQ)(QP) = PQ图1.2.6 例题例9: P: ABC是等腰三角形Q:ABC中有两个角相等命题PQ就是ABC是等腰三角形当且仅当ABC中有两个角相等。显然就这个例子而言PQ = T。六、 总结所定义的五个结词是数理逻辑中最基本最常用的逻辑运算。一元二元联结词还有多个，此外还有三元以至更多元的联结词，因其极少使用，况且又都可由这五个基本联结词表示出来，所以无需一一定义了。联结词是由命题定义新命题的基本方法。命题逻辑的许多问题都可化成是计算复合命题的真假值问题，真值表方法是极为有力的工具，是应十分重视和经常使用的。由联结词构成新命题的真值表中，对仅由两个变元P、Q构成的新命题A而言, 每个变元有T、F两种取值, 从而P、Q共有四种可能的取值, 对应于真值表中的四行, 每一行下命题A都有确定的真值。对P、Q的每组真值组合(如P = T, Q = F)或说真值指派, 都称作命题A的一个解释。一般地说, 当命题A依赖于命题P1, , Pn到A的真值表就有2n行, 每一行对应着P1, , Pn的每组真值都称作命题A的一个解释。A有2n个解释, 命题的解释用符号I表示。由于数理逻辑是采用数学的符号化的方法来研究命题间最一般的真值规律的，而不涉及判断一个命题本身如何取真取假，抛开命题的具体含义，而是抽象形式地讨论逻辑关系，这就导致了数理逻辑中所讨论的命题与自然用语的差异。联结词、同构成计算机的与门、或门和非门电路是相对应的。从而命题逻辑是计算机硬件电路的表示、分析和设计的重要工具。也正是数理逻辑应用于实际特别是应用于计算机学科推动了数理逻辑的发展。此外，五个联结词在不同的书中会采用不同的符号。如P可以P或表示, PQ以PQ表示, PQ以P + Q表示, PQ以PQ表示, PQ以PQ表示。阅读时应注意不同的表示方式。在这里我们要强调两点：（1） 上述五个真假联结词来源于日常使用的相应的词汇，我们的规定与它们的实际含义在很大程度上是一致的，但由于自然语言的歧义性，期间并不完全一致。在以后的使用中，以上联结词组成的复合命题的真假值一定要根据这五个联结词的定义去理解，而不能根据日常语言的意义去理解。（2） 在今后我们主要关心的是命题间的真假值的关系，而不讨论命题的内容。第三节 合式公式命题公式是命题逻辑讨论的对象，而由命题变项使用联结词可构成任意多的复合命题，如PQ, PQR, PQ等。问题是它们是否都有意义呢？只有一个联结词的命题P, PQ, PQ当然是有意义的。由两个联结词构成的命题PQR至少意义不明确, 是先作PQ再对R做, 还是先作QR再对P作呢? PQ也有同样的问题。解决运算次序是容易的, 可像初等代数那样使用括号的办法, 在逻辑运算中也常使用圆括号来区分运算的先后次序。这样由命题变项、命题联结词和圆括号便组成了命题逻辑的全部符号。进一步的问题是建立一个一般的原则以便生成所有的合法的命题公式，并能识别什么样的符号串是合法的（有意义的）？合式公式（简记为Wff）的定义：1. 简单命题是合式公式。2. 如果A是合式公式, 那么A也是合式公式。3. 如果A、B是合式公式, 那么(AB), (AB), (AB)和(AB)是合式公式。4. 当且仅当经过有限次地使用1.2.3所组成的符号串才是合式公式。这个定义给出了建立合式公式的一般原则，也给出了识别一个符号串是否是合式公式的原则。这是递归（归纳）的定义。在定义中使用了所要定义的概念，如在2和3中都出现了所要定义的合式公式字样，其次是定义中规定了初始情形，如1中指明了已知的简单命题是合式公式。条件4说明了哪些不是合式公式，而1、2和3说明不了这一点。依定义，若判断一个公式是否为合式公式，必然要层层解脱回归到简单命题方可判定。(PQ), (P(PQ),(PQ)(QR)(PR)都是合式公式。而PQ, (PQ)( Q), (PQ都不是合式公式, 没有意义, 我们不讨论。在实际使用中，为了减少圆括号的数量，可以引入一些约定，如规定联结词优先级的办法，可按，的排列次序安排优先的级别，多个同一联结词按从左到右的优先次序。这样，在书写合式公式时，可以省去部分或全部圆括号。通常采用省略一部分又保留一部分括号的办法，这样选择就给公式的阅读带来方便。如(P(QR)可写成P(QR)或PQR。(P(PR)可写成P(PR)。命题演算中只讨论合式公式, 为方便起见, 将合式公式就称作公式。由此定义的4易知，任一合式公式必为下列6种形式之一：命题变元、A 、(AB), (AB), (AB)和(AB)。例如，下列符号串都是合式公式：Q，PQ，(P)Q，P(P)，(PP)(P(PR)。若合式公式P中含有n个不同的命题变元，则说P是n元合式公式。合式公式代表了所有命题，n元合式公式表示此命题由n个简单命题复合而成，此命题的真假就由这n个简单命题的真假完全确定。怎样表示命题形式的真假值呢？我们给出如下定义。设P为一个合式公式，P中出现的所有命题变项都在p1，p2，pn中，对序列（p1，p2，pn）指定的任一真假值序列（t1，t2，tn）称为P的关于p1，p2，pn的一个指派（assignment）或解释（其中ti=T或F，iN，1in）。若p1，p2，pn的一个指派使P为真，则称此指派为P的一个成真指派；若p1，p2，pn的一个指派使P为假，则称此指派为P的一个成假指派。由定义可得：P关于P的成真指派为F，成假指派为T。PQ关于P、Q的成真指派为（T,T），成假指派为（T,F）,（F,T），（F,F）。PQ关于P、Q的成真指派为（T,T），（T,F）,（F,T），成假指派为（F,F）。同时我们也不难给出AB和AB的成真和成假指派。这样，我们在这里也就可以给出真值表的确切定义，即合式公式在所有可能的指派下所取值列成的表成为真值表。在后面我们统一用解释这个词，而不是上面的指派第四节 重言式一、 定义命题公式中有一类重言式。如果一个公式，对于它的任一解释I下其真值都为真，就称为重言式（永真式）。如PP是一个重言式。显然由、和联结的重言式仍是重言式。一个公式，如有某个解释I0, 在I0下该公式真值为真, 则称这公式是可满足的。PQ当取I0 = (T, F)即P = T, Q = F时便有PQ = T, 所以是可满足的。重言式当然是可满足的。另一类公式是矛盾式（永假式或不可满足的）。如果一个公式，对于它的任一解释I下真值都是假，便称是矛盾式。如PP就是矛盾式。不难看出这三类公式间有如下关系:1. 公式A永真， 当且仅当A永假。2. 公式A可满足, 当且仅当A非永真。3. 不是可满足的公式必永假。4. 不是永假的公式必可满足。例题举例：证明P(Q(PQ)是重言式证明：构造它的真值表，用来看是否在它的任一解释I下其真值都为真。PQ(PQ)(Q(PQ)P(Q(PQ)FFFTTTFFTTFTFFTTTTTT故P(Q(PQ)是一个重言式。由于任何公式中包含的变元个数总是有限的，所以其真值解释也只有有限多个，故真值表总可以做出。而公式为何种公式可以从真值表看出，因此，对任何公式都可判定它是何种公式，亦即命题逻辑的判定问题是可解的。二、 代入规则A是一个公式, 对A使用代入规则得公式B, 若A是重言式, 则B也是重言式。为保证重言式经代入规则仍得到保持, 要求: 1. 公式中被代换的只能是命题变元（原子命题）, 而不能是复合命题。2. 对公式中某命题变项施以代入，必须对该公式中出现的所有同一命题变项代换同一公式。如可用(RS)来代换某公式中的P, 记作 , 而不能反过来将公式中的(RS)以P代之。这一要求可以代数的例子来说明，如对(a + b)2 = a2 + 2ab + b2可以a = cd代入，仍会保持等式成立。而若将a + b以cd代入，结果左端得(cd)2，而右端无法代入cd，不能保持等式成立了。一般地说，公式A经代入规则可得任一公式, 而仅当A是重言式时, 代入后方得保持。如 A = PP, 作代入 得 B = QQ 仍是重言式。若将P以Q代之得B = PQ(这不是代入, 违反了规定(2)不是重言式了)。在第三章公理系统中，代入规则视作重要的推理规则经常使用。例题举例：使用代入规则证明重言式。例1: 判断(RS) (RS)为重言式。因 PP为重言式, 作代入 便得(RS) (RS)。依据代入规则,这公式必是重言式。例题例2： 判断(RS)(RS)(PQ)(PQ)为重言式.不难验证(A(AB)B是重言式, 作代入便知(RS)(RS)(PQ)(PQ)是重言式。简单自然语言的形式化所介绍的五个联结词及其与自然用语的联系和区别，为自然语句的形式化作了准备。一些推理问题的描述，常是以自然语句来表示的，需首先把自然语句形式化成逻辑语言，即以符号表示的逻辑公式，然后根据逻辑演算规律进行推理演算。这一节讨论自然语句的形式化。形式化过程。先要引入一些命题符号P、Q、用来表示自然语句中所出现的简单命题，进而依自然语句通过联结词将这些命题符号联结起来，以形成表示自然语句的合式公式。这个过程要注意自然语句中某些联结词的逻辑含义。一、 简单自然语句的形式化1. 北京不是村庄。令P表示北京是村庄，于是1可表示为P。2. 李明既聪明又用功。令P表示李明聪明，Q表示李明用功，于是2可表示为PQ。3.是有理数的话,也是有理数。令P表示是有理数，Q表示是有理数，于是3可表示为PQ。二、 较复杂自然语句的形式化需注意的是逻辑联结词是从自然语句中提炼抽象出来的，它仅保留了逻辑内容，而把自然语句所表达的主观因素、心理因素以及文艺修辞方面的因素全部撇开了，从而命题联结词只表达了自然语句的一种客观性质。又由于自然语句本身并不严谨，常有二义性，自然会出现同一自然语句的不等价的逻辑描述，其根由在于人们对同一自然语句的不同理解。例题例1: 张三与李四是表兄弟。这是普通的自然用语，它是一个命题，令以R表示, 若形式地规定: P: 张三是表兄弟。Q: 李四是表兄弟。那么 R = PQ。显然，这样的形式化是错误的。原因很简单。张三是表兄弟，李四是表兄弟都不是命题。实际上张三与李四是表兄弟才是一个命题，而且是一个简单命题。这例子说明自然语句中的与不一定都能用合取词来表达。例题例2：张三或李四都能做这件事。这句话中的或不一定就用析取词来表示，应允许有的人把这命题的内容理解为：张三能做这件事而且李四也能做这件事，这样，这句话便可以PQ的形式表示了。例题例3: 给了三个命题A: 今晚我在家里看电视。B: 今晚我去体育场看球赛。C: 今晚我在家里看电视或去体育场看球赛。问题是C与AB是否表达的是同一命题呢? 回答是否定的。因为C同A、B的真值关系应由图1.5.1给出第六节 波兰表达式数理逻辑也谓之符号逻辑。自然对一个公式如何以符号描述是给以关注的，像括号的使用，联结词的中辍、前辍、后辍形式的选择，都直接影响着同一公式描述和计算的复杂程度。若用计算机来识别、计算、处理逻辑公式，不同的表示方法会带来不同的效率。一、 计算机识别括号的过程合式公式的定义中使用的是联结词的中辍表示，又引入括号以便区分运算次序，这些都是人们常用的方法。计算机识别处理这样表示的公式的方法，需反复自左向右，自右向左的扫描。如对公式(P(QR) (ST)真值的计算过程, 开始从左向右扫描，至发现第一个右半括号为止，便返回至最近的左半括号，得部分公式(QR)方可计算真值。随后又向右扫描，至发现第二个右半括号，便返回至第二个左半括号，于是得部分公式(P(QR)并计算真值，重复这个过程直至计算结束。如图1.6.1所示的扫描过程12367。这种多次重复扫描, 显然是有浪费的，从而降低了机器的使用效率。追溯这种重复扫描的原因并不在于使用了括号，而在于公式的中辍表示方法。图1.6.1 公式中的运算符是否非要括号才能定义呢？若一个式子中同时使用两种或两种以上的运算符放置方式时，无论怎样对运算符的优先级进行规定，括号都不能完全避免。例如：对数运算符log是前置运算符，阶乘运算符!是后置运算符，而对式子logn!来说，对于不同的运算优先级，它可以有两种不同的含义，分别为log(n!)和(logn)!。但无论是规定log的优先级大于!还是!的优先级大于log，都只能表示其中之一，而另一个则必须使用括号。因此，我们可以采用下面的思维方式：将中置、后置全部换成前置或将中置、前置全部换成后置。这样，便可不使用任何括号。 二、波兰式一般地说，使用联结词构成公式有三种方式，中辍式如PQ, 前辍式如PQ, 后辍式如PQ。前缀式用于逻辑学是由波兰的数理逻辑学家J. Lukasiewicz提出的, 称之为波兰表示式。如将公式P(QR)S)的这种中辍表示化成波兰式，可由内层括号逐步向外层脱开（或由外层向里逐层脱开）的办法。如图1.6.2以波兰式表达的公式，由计算机识别处理的过程，当自右向右扫描时可以一次完成，避免