e书联盟好书下载www.book118.com 1.2.3析取词V 析取可”是个儿命趣联结时.办称析取符号.将个命题1.Q联结起米，构成·个 新的命题PVQ,读作P.Q的析取、也作：或Q.这个新命题的红值与构成它的命题， Q的班竹间的关系、山析取词更值表米战定.划】.2.、示. ..指出，当'N有·取值为T.VQ使 , 为1.仪当P.位均取F值成·1Q方为上.这就是析取 i可的定义·Q可来表小示自然用语P戏Q. 例5P:今天刮风. Q:今犬下相. 刻1.么. 命题“今天刮风或苔下雨”使由PVQ来描述了. 例6：2小于3. 书：了是黑的 .1V乃就是命题“2小于3或者雪是黑的”.山于2于3是鱼的、所以VH必取值为 〔、尽悴“·是黑的”这命题假 同样品注意新取词同“域”的异同. 1.2.4蕴涵词→ 瓴诉词“·”也是个元命题联结词，亦称推断符号.将两个命题P,Q联结起来，构成 个新的命题P→Q、读竹如果P则Q.或读作P蕴函Q,如果P挪么，其中P称前件 (前项、条件)，Q称行件（后项、站论）. 规定1有当P为T而Q为I时.+Q=F.而P-FQ任意，或P=T、Q二1时. 良均取值为T,其值表见图」.2.4. 引人·的廿的是希望用来描述命题问的推理，表示因 PQ P-Q 果关系.实际」图1,2.1说明了： T (Q=T下.若P=T必有Q-T,而不会出现 F Q·F、这长明Q休现了P是Q成寸的充分茶件. 「T 1?-《一T下，若P=F可有Q=T,这表明P→ 图1.2.4 体现了”不必是父成立的必要条件. 使Q能描述推理.即1？Q为真时，只要P为真必有Q真，而不能现P真而 Q假就够了.乍了”为假时，？取真取假，并不违背P为真时Q必舆.从而仍可规定为 假时，PQ取真.这当然只是对P→Q的一种说明·而从逻辑上说，本可按真值表定义 ”Q,训不必涉及其体含义.另外、当”二上刖对P→Q真值的不问定义方式将给推理的 时论带米不的表示形式，也是允许的. 图i.2.5儿·VQ的真偵表、成然图1.之.同1.之.5是相同的、在P,Q的所有取值 下.’Q问·VQ都有利同的4值.5是可记作 -( (Q立俏的筝伯偷题以等号联结 ·5·
e书联盟好书下载www.book118.com
e书联盟好书下载www.book118.com 这也说明→可出一·V来表示，从逻#上看“如果P则Q”同“非P或Q”是等同的两个 命题. PQPV父 蕴涵词→与自然用语“如果…那么…”有·敛的一面， T 可表示因果关系.然而P,Q是无关的命题时，逻辑上允许讨论 11 T TF P→Q.并且P=F则P+Q=T,这在自然用语中是不大使 T 用的. 图1.2.5 例7P:n一3(n为整数) Q:n2>9 命题P-Q表示“如果n>3那么n2>9”,分析P+Q的真值、 （1)P一Q=T,例如，n=4>3,有n2=16>9,这符合事实P→Q=T,正是我 们所期望的可用PQ表示P,Q间的因果关系，这时规定P→Q=T是自然的. (2)P=T,Q=F,例如，n>3而n2<9这是不会成立的，也可用P+Q表示P,Q 间的因果关系是不成立的，自然规定P→Q=F (3)P=F而Q=F或T.例如， n=2<3有n2=4<9 1=-4<3有n2=16>9 由于前提条件n>3不成立，而n2>9成立与否并不重要，都不违反对自然用语“如果>3 那么n2>9”成立的肯定.于是刀=F时可规定P→Q=T.当然在肯定了(1)，(2)的情况 下，对P=F时P→Q的值另作规定也是可以的，同样不违反自然语句“如果…那么 …”可以用P→Q来描述.总之，对P→Q的这种说明是可接受的，但也不是说只有这样 的解释才是合理的. 例8P:2+2=5 Q:雪是黑的 P→Q就是命题“如果2+2=5，那么雪是黑的”，从蔬涵词的定义看，由于2十2= 5是不成立的或说P取F值，不管Q取真取假都有P*Q=T. 联结词→，较”、V、A难于理解，然而它在逻辑中用于表示因果关系，因而又是最有用的. 1.2.5双条件词+ 双条件词“一”同样是个二元命题联结词，亦称等价符号.将两个命题P,Q联结起来构 成新命题PQ,读作P当且仅当Q,或读作P等价于Q.这个新命题的真值与P,Q真值 间的关系，由双条件词的真值表来规定，如图1.2.6所示. 图1.2.6指出，只有当两个命题P,Q的真值相同或说P= P Q P+Q Q时，PQ的真值方为T.而当P,Q的真值不同时，P一Q=F. F T 若建立(P+Q)A(Q+P)的真值表，就可发现(P→Q)A T F (Q→P)和P一Q有相同的真值，于是 (P+Q)A(Q*P）=P→Q 图1.2.6 例9P:△AB('是等腰三角形 Q:△ABC中有两个角相等 ·6·
e书联盟好书下载www.book118.com
e书联盟好书下载www.book118.com 命题'一Q就是“入AB(,'是等腰角形出且仅当△ABC中有两个角相等”.显然就这 个例子而言PQ=T, 1.2.6总结 由五个联结词所定义的运算是数理逻辑中最基本，最常用的逻辑运算，·元二元联结词 还有多个，此外还有二元以至多元的联结词，因其极少使用，况且义都可由这五个基木联结 词表示出米，所以无需一一定义了. 联结词是由命题定义新命题的基本方法. 命题逻辑的许多问题都可化成是计算复合命题的真假值问题，真值表方法是极为有力 的工其，是应十分重视和经常使用的， 由联结词构成新命题的真值表中，对仅由两个变元P,Q构成的新命题A而言，每个变 元有T,F两种取值，从而P,Q共有四种可能的取值，对应于真值表中的四行，每一下命 题A都有确定的真值.对P,Q的每组真值组合（如P一T,Q二F)或说真值指派，都称作 命题A的·个解释.一般地说、当命题A依赖于命题P,…,Pn时，则由P,·,P,到A的 真侑表就有2行，每一行对应着P,…,P的一组真值，在这组真值下，A的真值随之而 定，P,…,P。的每组真值都称作命题A的一个解释，A有2”个解释，命题的解释用符号【 表不。 由丁数理逻辑是采用数学的符号化的方法来研究命题间最一般的真值规律的，而不涉 及判断个命题本身如何取真取假，不顾命题的具体含义，而是抽象地、形式地讨论逻辑关 系，这就导致了数理逻辑中所讨论的命题与自然用语的差异. 联结词A、V、一同构城计算机的与门、或门和非门电路是相对应的，从而命题逻是 计算机硬件电路的表示、分析和设计的重要工具.也正是数理逻辑应用于实际，特别是应用 于计算机学科推动了其自身的发展. 1.3合式公式 命题公式是命题逻辑讨论的对象，而由命题变项使用联结词可构成任意多的复合命题， 如一PAQ,PAQVR,P→“Q等.它们是否都有意义呢？只有一个联结词的命题·P, PAQ、'+Q当然是有意义的.由两个联结词构成的命题PAQVR至少意义不明确，是先 作1”∧Q再对R作V,还是先作QVR再对P作∧呢？一PAQ也有同样的问题.解决运算 次序是容易的，可像初等代数那样使用括号的办法，在逻辑运算中也常使用圆括号来区分 运算的先后次序，这样由命题变项，命题联结词和圆括号便组成了命题逻辑的全部符号.进 ·步的问题是建立一般的原则以便生成所有的合法的命题公式，并能识别什么样的符号审 是合法的（有意义的）？ 合式公式（简记为Wf)的定义： (1)简单命题是合式公式， (2)如果A是合式公式·那么A也是合式公式， (3)如果A,B是合式公式，那么(.1AB).(AVB).(A→B)和(A+B)是合式公式. 。74
e书联盟好书下载www.book118.com
e书联盟好书下载www.book118.com (4)当且仅当经过有限次地使用(1)，(2)，(3)所组成的符号串才是合式公式， 这个定义给出了建立合式公式的一般原则，也给出了识别一个符号串是否是合式公式 的原则. 这是递归（归纳）的定义.在定义中使用了所要定义的概念，如在(2)和(3)中都出现了所 要定义的合武公式字样；其次是定义中规定了初始情形，如(1)中指明了已知的简单命题是 合式公式. 条件(4)说明了哪些不是合式公式，而(1)，(2)，(3)说明不了这一点. 依定义，若判断一个公式是否为合式公式，必然要层层解脱回归到简单命题方可判定， (PAQ),(P+(PAQ),((P→Q)A(Q→R))→(P→R)都是合式公式.而PVQ V,(P→Q)→(AQ),(P+Q都不是合式公式，因为没有意义，我们不讨论. 在实际使用中，为了减少圆括号的数量，可以引人-一些约定，如规定联结词优先级的办 法，可按“，八，V,→，+的排列次序安排优先的级别，多个同一联结词按从左到右的优先 次序.这样，在书写合式公式时，可以省去部分或全部圆括号，通常采用省略一部分又保留一 部分括号的办法，这样选择就给公式的阅读带来方便，如 (P(QVR)》可写成P→(QVR)或P+QVR. (P*(P+R))可写成P→(P→R). 命题演算中只讨论合式公式，为方便起见，将合式公式就称作公式. 1.4重言式 1.4.1定义 命题公式中有一类重言式，如果一个公式，对于它的任一解释I下其真值都为真，就称 为重言式（永真式）.如PV一P是一个重言式. 显然由V、八、*和+联结的重言式仍是重言式. 一个公式，如有某个解释I,在I。下该公式真值为真，则称这公式是可满足的.如PV Q当取I。=(T,F)即P=T,Q=F时便有PVQ=T,所以是可满足的.重言式当然是 可满足的 另一类公式是矛盾式（永假式或不可满足的）.如果一个公式，对于它的任一解释1下真 值都是假，便称是矛盾式，如P八一P就是矛盾式、 不难看出这三类公式间有如下关系： (1)公式A永真，当且仅当A永假. (2)公式A可满足，当且仅当一A非永真 (3)不是可满足的公式必永假. (4)不是水假的公式必可满足. 1.4.2代入规则 A是一个公武，对A使用代人规则得公式B,若A是重言式，则B也是重言式， 8
e书联盟好书下载www.book118.com
e书联盟好书下载www.book118.com 为保证重白式经代入规则仍得到保持，要求： (1)公式中被代换的贝能足命题变元（原子命题），而不能是复合命题. P 如可用(RAS)来代换某公式中的P,记作(RA),而不能反过来将公式中的(RAS) 以P代之. 这·要求可以代数的例子米说明，如对 (u一h)-4+2ah-b 可用a一d代入，仍会保持等式成立.而若将6用(d代入，结果左端得(d)°，而右端 无法代入d,不能保持等式成立了. (2)对公式中某命题变项施以代入，必须对该公式中出现的所有同一命题变项代换同 -…公武 ·般地说，公式A经代入规则可得任一公式，而仅当A是重言式时，代入后方得保持. 如A二PVP.作代入二6得B=-QV-Q仍是重言式若将一P以Q代之得 B=PVQ(这不是代入，违反了规定(2)不是重言式了 在第3章公理系统中，代入规则视作重要的推理规则经常使用. 可使用代入规则证明重言式， 例1判断(RVS)V(RVS)为重言式. 因PV一P为重言式，作代入RV便得(RVS)V(RVS).依据代人规则，这公 式必是重言式， 例2判断(RVS)A(RVS)→(PVQ))→(PVQ)为重言式. A B 不难验证(AA(A+B)B是重言式，作代入(RVS)'PVQ),便知 (RVS)A(RVS)→(PVQ))→(PVQ) 是重言式， 1.5命题形式化 前面所介绍的五个联结词及其与白然用语的联系和区别，为自然语句的形式化作了准 备.·些推理问题的描述，常是以自然语句来表示的，需首先把自然语句形式化成逻辑语言， 即以符号表示的逻辑公式，然后根据逻辑演算规律进行推理演算.这一节讨论自然语句的形 式化. 形式化过程.先要引入·些命题符号P,Q,…用来表示自然语句中所出现的简单命题， 进而依自然语句通过联结词将这些命题符号联结起来，以形成表示自然语句的合式公式，这 个过程要注意自然语句中某些联结词的逻辑含义， 1.5.1简单自然语句的形式化 (们)北京不是村庄. 令P表示“北京是村庄”.下是(1)可表小为一P. ·9·
e书联盟好书下载www.book118.com