命题逻辑的基本概念.ppt

《命题逻辑的基本概念.ppt》由会员分享，可在线阅读，更多相关《命题逻辑的基本概念.ppt（55页珍藏版）》请在三一办公上搜索。

1、1,鸣谢 黄林鹏 教授,2,第1章 命题逻辑的基本概念,命题逻辑研究的是命题的推理演算命题逻辑的基本概念命题联结词合式公式、重言式自然语句的形式化,3,命题逻辑的基本概念,命题是一个非真即假(不可兼)的陈述句有两层意思，首先命题是一个陈述句，而命令句、疑问句和感叹句都不是命题其次是说这个陈述句所表达的内容可决定是真还是假，而且不是真的就是假的，不能不真又不假，也不能又真又假凡与事实相符的陈述句为真浯句，而与事实不符的陈述句为假语句这说是说，一个命题具有两种可能的取值(又称真值)，为真或为假，并且只能取其一通常用大写字母T表示真值为真，用F表示真值为假因为只有两种取值，所以这样的命题逻辑称为二值

2、逻辑,4,举例说明,(1)“雪是白的”命题，(2)“雪是黑的”命题(3)“好大的雪啊”不是陈述句，不是命题(4)“一个偶数可表示成两个素数之和”是命题，或为真或为假，只不过当今尚不知其是真命题还是假命题(5)“1+10l110”这是一个数学表达式，相当于一个陈述句，可以叙述为“1加101等于110，这个句子所表达的内容在十进制范围中真值为假，而在二进制范围中真值为真可见，这个命题的真值与所讨论问题的范围有关,5,命题变项,为了对命题作逻辑演算，采用数学手法将命题符号化(形式化)是十分重要的约定用大写字母表示命题，如以户表示“雪是白的”，Q表示“北京是中国的首都”等当P表示任一命题时，P就称为命

3、题变项(变元)命题与命题变项含义是不同的，命题指具体的陈述句，是有确定的真值，而命题变项的真值不定，只当将某个具体命题代入命题变项时，命题变项化为命题，方可确定其真值，命题与命题变项像初等数学中常量与变量的关系一样如5是一个常量，是一个确定的数字，而x是一个变量，赋给它一个什么值它就代表什么值，即x的值是不定的,6,简单命题和复合命题,简单命题又称原子命题，它是不包含任何的与、或、非一类联结词的命题如111中所举的命题例子都是简单命题这样的命题不可再分割，如再分割就不是命题了而像命题“雪是白的而且l+l2”，就不是简单命题，它可以分割为“雪是白的”以及“1十12”两个简单命题，联结词是“而且”

4、在简单命题中，尽管常有主语和谓语，但我们不去加以分割，是将简单命题作为一个不可分的整体来看待，进而作命题演算在谓词逻辑里，才对命题中的主谓结构进行深入分析,7,复合命题,把一个或几个简单命题用联结词(如与、或、非)联结所构成的新的命题称为复合命题复合命题自然也是陈述句，其真值依赖于构成该复合命题的各简单命题的真值以及联结词，从而复合命题有确定的真值如“张三学英语和李四学日语”就是一个复合命题，由简单命题“张三学英语”“李四学日语”经联结词“和”联结而成，这两个简单命题真值均为真时，该复合命题方为真命题逻辑所讨论的是多个命题联结而成的复合命题的规律性,8,内容/形式,在数理逻辑里，仅仅把命题看成

5、是一个可取真或可取假的陈述句，所关心的并不是这些具体的陈述句的真值究竟为什么或在什么环境下是真还是假，这是有关学科本身研究的问题，而逻辑关心的仅是命题可以被赋予真或假这样的可能性，以及规定了真值后怎样与其他命题发生联系,9,命题联结词及真值表,联结词可将命题联结起来构成复杂的命题，命题逻辑联结词的引入是十分重要的，其作用相当于初等数学里在实数集上定义的十、一、等运算符通过联结词便可定义新的命题，从而使命题逻辑的内容变得丰富起来，复合命题的真值可由组成它的简单命题的真值所确定值得注意的是逻辑联结词与日常自然用语中的有关联结词的共同点和不同点,10,常用的逻辑联结词,否定词“”是个一元联结词，亦称

6、否定符号一个命题P加上否定词就形成了一个新的命题，记作 P，这个新命题是命题的否定，读作非P 否定词的真值规定如下：若命题P的真值为真，那么 P的真值就为假；若P的真值为假，那么 P的真值就为真 P与P间的真值关系，常常使用称作真值表的一种表格来表示.,11,P的定义,真值表,真值表表明了P的真值如何依赖于P的真值真值表描述了命题之间的真值关系，很直观.真值表是命题逻辑里研究真值关系的重要工具,12,例1,“昨天张三去看球赛了”该命题以P表示，于是“昨天张三没有去看球赛”，该新命题便可用P表示 若昨天张三去看球赛了，命题P是真的，那么新命题P必然是假的反之，若命题P是假的，那么P就是真的,13

7、,例2,Q：今天是星期三 Q：今天不是星期三 然而 Q不能理解为“今天是星期四”，因为“今天是星期三”的否定，并不一定必是星期四，还可能是星期五、星期六,14,合取词,合取词是个二元命题联结词，亦称合取符号将两个命题P，Q联结起来，构成一个新的命题PQ，读作P Q的合取，也可读作P与Q这个新命题的真值与构成它的命题P，Q的真值间的关系，由合取词真值表来规定,15,合取词真值表,只有当两个命题变项PT，Q=T时方有 PQ T，而P，Q只要有一为F，则PQ=FPQ可用来表示日常用语P与Q，或P并且Q,16,例3,P：教室里有10名女同学 Q：教室里有15名男同学 不难看出，命题PQ:“教室里有10

8、名女同学与15名男同学”,17,例4,A：今天下雨了B：教室里有100张桌子。可知AB就是命题“今天下雨了并且教室里有100张桌子”,18,注意,日常自然用语里的联结词“和”、“与”、“并且”，一般是表示两种同类有关事物的并列关系而在逻辑语言中仅考虑命题与命题之间的形式关系并不顾及日常自然用语中是否有此说法这样，“”同“与”、“并且”又不能等同视之 日常自然用语中说，“这台机器质量很好，但是很贵”，这句话的含义是说同一台机器质量很好而且很贵若用P表示“这台机器质量很好”，用Q表示“这台机器很贵”，那么这句话的逻辑表示就是PQ，尽管这句话里出现的联结词是“但是”总之，合取词有“与”、“并且”的含

9、义，逻辑联结词是自然用语中联结词的抽象，两者并不等同，这是需注意的,19,析取词,析取词“”是个二元命题联结词。将两个命题P、Q联结起来,构成一个新的命题PQ,读作P、Q的析取,也读作P或Q。这个新命题的真值与构成它的命题P、Q的真值间的关系,20,析取词真值表,当P、Q有一取值为T时,PQ便为T。仅当P、Q均取F值时,PQ方为F。这就是析取词的定义,PQ可用来表示自然用语P或Q。,21,例,例5:P:今天刮风。Q:今天下雨。命题“今天刮风或者下雨”便可由PQ来描述了。例6:A:2小于3。B:雪是黑的。AB就是命题“2小于3或者雪是黑的”。由于2小于3是真的,所以AB必取值为真,尽管“雪是黑的

10、”这命题取假。,22,蕴涵词,蕴涵词“”也是个二元命题联结词。将两个命题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。,23,真值表,PQ=T下,若P=T必有Q=T,而不会出现Q=F,这表明PQ体现了P是Q成立的充分条件。PQ=T下,若P=F可有Q=T,这表明PQ体现了P不必是Q成立的必要条件。,24,因果关系,引入的目的是希望用来描述命题间的推理,表示因果关系。使用PQ能描述推理。即PQ为真时,只要P为真必有Q真,

11、而不能出现P真而Q假就够了。至于P为假时,Q取真取假,并不违背P为真时Q必真。从而仍可规定P为假时,PQ取真。当P=F时对PQ真值的不同定义方式将给推理的讨论带来不同的表示形式,也是允许的。,25,PQ=PQ,在P、Q的所有取值下,PQ同PQ都有相同的真值:PQ=PQ(真值相同的等值命题以等号联结)。这也说明可由、来表示,从逻辑上看“如果P则Q”同“非P或Q”是等同的两个命题。,26,如果那么,蕴涵词与自然用语“如果那么”有一致的一面，可表示因果关系。然而P、Q是无关的命题时,逻辑上允许讨论PQ。并且P=F则PQ=T,这在自然用语中是不大使用的。,27,例7:,P:n 3(n为整数)Q:n2

12、9命题PQ表示“如果n 3那么n2 9”,分析PQ的真值。1.P=Q=T。这时如n=4 3,有n2=16 9,这符合事实 PQ=T,正是我们所期望的可以PQ表示P、Q间的因果关系,这时规定P T是自然的。2.P=T,Q=F。如n 3而 n2 9 由于前提条件n 3不成立，而n2 9成立与否并不重要，都不违反对自然用语“如果n 3那么n2 9”成立的肯定。于是 P=F时可规定P Q=T。当然在肯定了1,2的情况下,对P=F时PQ的值另作规定也是可以的,同样不违反自然语句“如果那么”可以用PQ来描述。总之，对PQ的这种说明是可接受的,但也不是说仅只有这样的解释才是合理的。,28,例8:,P:2+2

13、=5 Q:雪是黑的PQ就是命题“如果2+2=5,那么雪是黑的”。从蕴涵词的定义看，由2+2=5是不成立的或说P取F值,不管Q取真取假都有PQ=T。,29,双条件词,30,(PQ)(QP)=PQ,只有当两个命题P、Q的真值相同或说P=Q时,PQ的真值方为T。而当P、Q的真值不同时,PQ=F。若建立(PQ)(QP)的真值表,就可发现(PQ)(QP)和PQ有相同的真值,于是(PQ)(QP)=PQ,31,例9,P:ABC是等腰三角形Q:ABC中有两个角相等命题PQ就是“ABC是等腰三角形当且仅当ABC中有两个角相等”。显然就这个例子而言PQ=T。,32,总结,定义的五个联结词是数理逻辑中最基本最常用的

14、逻辑运算。一元二元联结词还有多个，此外还有三元以至更多元的联结词，因其极少使用，况且又都可由这五个基本联结词表示出来，所以无需一一定义了。联结词是由命题定义新命题的基本方法。命题逻辑的许多问题都可化成是计算复合命题的真假值问题，真值表方法是极为有力的工具，是应十分重视和经常使用的。,33,总结,由联结词构成新命题的真值表中，对仅由两个变元P、Q构成的新命题A而言,每个变元有T、F两种取值,从而P、Q共有四种可能的取值,对应于真值表中的四行,每一行下命题A都有确定的真值。对P、Q的每组真值组合(如P=T,Q=F)或说真值指派,都称作命题A的一个解释。一般地说,当命题A依赖于命题P1,Pn到A的真

15、值表就有2n行,每一行对应着P1,Pn的每组真值都称作命题A的一个解释。A有2n个解释,命题的解释用符号I表示。,34,总结,由于数理逻辑是采用数学的符号化的方法来研究命题间最一般的真值规律的，而不涉及判断一个命题本身如何取真取假，抛开命题的具体含义，而是抽象形式地讨论逻辑关系，这就导致了数理逻辑中所讨论的命题与自然用语的差异。联结词、同构成计算机的与门、或门和非门电路是相对应的。从而命题逻辑是计算机硬件电路的表示、分析和设计的重要工具。也正是数理逻辑应用于实际特别是应用于计算机学科推动了数理逻辑的发展。,35,不同的符号,五个联结词在不同的书中会采用不同的符号。如P可以以P表示,PQ以PQ表

16、示,PQ以P+Q表示,PQ以PQ表示,PQ以PQ表示。阅读时应注意不同的表示方式。,36,1.3 合式公式,命题公式是命题逻辑讨论的对象，而由命题变项使用联结词可构成任意多的复合命题，如PQ,PQR,PQ等。问题是它们是否都有意义呢？只有一个联结词的命题P,PQ,PQ当然是有意义的。由两个联结词构成的命题PQR至少意义不明确,是先作PQ再对R做,还是先作QR再对P作呢?P Q也有同样的问题。解决运算次序是容易的,可象初等代数那样使用括号的办法,在逻辑运算中也常使用圆括号来区分运算的先后次序。这样由命题变项、命题联结词和圆括号便组成了命题逻辑的全部符号。进一步的问题是建立一个一般的原则以便生成所

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

18、不了这一点。,38,判断一个公式是否为合式公式,依定义，若判断一个公式是否为合式公式，必然要层层解脱回归到简单命题方可判定。(PQ),(P(PQ),(PQ)(QR)(PR)是合式公式。而PQ,(PQ)(Q),(PQ都不是合式公式。,39,约定,为了减少圆括号的数量，可以引入一些约定，如规定联结词优先级的办法，可按，的排列次序安排优先的级别，多个同一联结词按从左到右的优先次序。这样，在书写合式公式时，可以省去部分或全部圆括号。通常采用省略一部分又保留一部分括号的办法，这样选择就给公式的阅读带来方便。如(P(QR)可写成P(QR)或PQR。(P(PR)可写成P(PR)。命题演算中只讨论合式公式,将

19、合式公式就称作公式。,40,1.4 重言式/可满足式/矛盾式,如果一个公式，对于任一解释I其值都为真，就称为重言式（永真式）。如PP是一个重言式。由、和联结的重言式仍是重言式。一个公式，如在某个解释I0下值为真,则称它是可满足的。如PQ，当取I0=(T,F)，即P=T,Q=F时便有PQ=T,所以是可满足的。重言式当然是可满足的。矛盾式（永假式或不可满足式）：如果一个公式，对于任一解释I值都是假的，便称是矛盾式。如PP就是矛盾式。,41,三类公式间关系,1.公式A永真，当且仅当永假。2.公式A可满足,当且仅当A非永真。3.不是可满足的公式必永假。4.不是永假的公式必可满足。,42,1.4.2 代

20、入规则,A是一个公式,对A使用代入规则得公式B,若A是重言式,则B也是重言式。为保证重言式经代入规则仍得到保持,要求:,43,1.公式中被代换的只能是命题变元(原子命题),而不能是复合命题。如可用(RS)来代换某公式中的P,而不能反过来将公式中的(RS)以P代之。这一要求可以以代数的例子来说明，如对(a+b)2=a2+2ab+b2 可以a=cd代入，仍会保持等式成立。而若将a+b以cd代入，结果左端得(cd)2，而右端无法代入cd，不能保持等式成立了。,44,2.对公式中某命题变项施以代入，必须对该公式中出现的所有同一命题变项代换以同一公式。如A=PP,P以 Q代之得 B=QQ 仍是重言式。若

21、将P以Q代替得B=PQ不是重言式了,45,使用代入规则证明重言式,例1:判断(RS)(RS)为重言式。因PP为重言式,P以(RS)代入得(RS)(RS)。依据代入规则,这公式必是重言式。例2：判断(RS)(RS)(PQ)(PQ)为重言式.不难验证(A(AB)B是重言式,A 以RS代入，B 以PQ代入得(RS)(RS)(PQ)(PQ)是重言式。,46,1.5 命题形式化,一些推理问题的描述，常是以自然语句来表示的，需首先把自然语句形式化成逻辑语言，即以符号表示的逻辑公式，然后根据逻辑演算规律进行推理演算。先要引入一些命题符号P、Q、用来表示自然语句中所出现的简单命题，进而依自然语句通过联结词将这

22、些命题符号联结起来，以形成表示自然语句的合式公式。,47,1.5.1 简单自然语句的形式化,1.北京不是村庄。令P表示“北京是村庄”，于是1可表示为P。2.李明既聪明又用功。令P表示“李明聪明”，Q表示“李明用功”，于是2可表示为PQ。3.2是有理数的话,22也是有理数。令P表示“2是有理数”，Q表示“22是有理数”，于是3可表示为PQ。,48,1.5.2 较复杂自然语句的形式化,需注意的是逻辑联结词是从自然语句中提炼抽象出来的，它仅保留了逻辑内容，而把自然语句所表达的主观因素、心理因素以及文艺修辞方面的因素全部撇开了，从而命题联结词只表达了自然语句的一种客观性质。又由于自然语句本身并不严谨，

23、常有二义性，自然会出现同一自然语句的不等价的逻辑描述，其根由在于人们对同一自然语句的不同理解。,49,例1:张三与李四是表兄弟。这是普通的自然用语，它是一个命题，令以R表示,若形式地规定:P:张三是表兄弟。Q:李四是表兄弟。那么R=PQ。显然，这样的形式化是错误的。原因很简单。“张三是表兄弟”，“李四是表兄弟”都不是命题。实际上“张三与李四是表兄弟”才是一个命题，而且是一个简单命题。这例子说明自然语句中的“与”不一定都能用合取词来表达。,50,例2：张三或李四都能做这件事。这句话中的“或”不一定就用析取词来表示，应允许有的人把这命题的内容理解为：张三能做这件事而且李四也能做这件事，这样，这句话

24、便可以PQ的形式表示了。,51,例3:给了三个命题,A:今晚我在家里看电视。B:今晚我去体育场看球赛。C:今晚我在家里看电视或去体育场看球赛。问题是C与AB是否表达的是同一命题呢?,52,否。因为C同A、B的真值关系为,53,异或(不可兼或),这表的前三行很容易理解，而第四行是说今晚我在家看电视，又去体育场看球赛。显然对同一个人来说这是不可能的，从而这时C的真值为F。这就说明了C与AB逻辑上是并不相等的。即C中出现的“或”不能以“”来表示。C同A,B的逻辑关系,常称为异或(不可兼或),以 表示,有C=A B不难验证 C=(AB)(AB),54,例4:今天我上班,除非今天我病了,以P表示今天我病了,Q表示今天我上班,例4是个因果关系,意思是如果今天我不病,那么我上班,所以可描述成PQ。,55,作业,P12 1(2,4,6,8)4(2,4,6)5(2,4,6,8)6(2),