离散数学耿素云
等都可以符号化为∧请看下例【例1.3】将下列命题符号化(1)张路既聪明又用功(2)张路不仅聪明,而且用功(3}张路虽然不太聪明,但他很用功(4)张路不是不聪明,而是不用功(5)肖颖和李莉都是北大的学生6)张芳与陈敏是好朋友(7)姜文相姜武是兄弟解设p:张路聪明,q:张路用功.(1)到(4)分别符号化为p∧q,p∧q,pAqp)A=4.在这4个复合命题中都使用了联结词∧.至丁说它们的真值,均应由P,q的真值而定在(5)中设p:肖颖是北大学生,q:陈敏是北大学生.复合命题(5)符号化为pAq.(6),7)两命题均为简单命题,因而分别符号化为p和q即可定义L.3设p,q为任意命题复合命题“b或q称作p与q的析取式,记作pVq.V称为析取联结词为岸?的逻辑关系为p与q中至少一个成立,因而pVq为真当且仅当p与q中至少一个在例12(3)中,设p:2是素数,g:4是素数则pVq表示2或4是素数由于p的真值为1,所以pVq的真值为1.骊在(8)中,设r:6是素数,s:8是素数,庄予r,s的真值均为0,所以rVs的真值为0析取联结词的逻辑关系是明确的,但自然语言中的“或”具有二义性,用“或”联结的命题,有时具有相容性,有时又具有排斥性,因而在使用联结词∨时要注意区分请看下例【例1.4】将下面命题符号化(1)谢丹生于1972年或1973年(2)吕小洲学过德语或法语(3)派老王或老李中的一人去上海开会解本例中,(1),(3)中的或是排斥的,面(2)中的或是相容的因而(2)可符号化为p￥q其中p表示目小洲学过德语,q表示吕小洲学过法語只有吕小洲既没学过德语,也没学过法谮时,比命题才是假的其他情况下均为真.在(1)中,设r谢丹生于1972年,:谢丹生于19乃3年,r,s的联合真值情况有且仅有3种情况:同假;r真,5假;r假,s真,不会出现同真的情况,因而可以符号化为rs.rs为真当且仅当r,s中一个为真另一个为假.在(3)中,设t:派老王到海开会,u:派老李到上海开会,t认的联合真值情况有4种:同真同假,真一假(两种情况).如果也符号化为Vx,就叫能派2人去开会,因帕不能符号化为tV4.可以使用多个联结词符号化为(tA-n)y(→t∧n)此复合命题为真当且仅当p,q中一个为真,一个为假,它很准确地表达了(3)的含义定义14设p,g为二命题复合命题“如果p则q"称作p与q的蕴涵式,记作p→q称p是蕴涵式的前件,q是蕴涵式的后件→称作蕴涵联结词p→q的逻辑关系是,q是p的必要条件,或p是q的充分条件、Pq为假当且仅当p为真且q为假在使用瘟涵联结词→时,应注意以下几点t.在自然语言里,特别是在数学中,g是p的必要条件有不同的叙述方式,如“只要就“p仅当q”“只有q才p”等都可以符号化为p→q的形式2.在自然语言里,“如果p则q”中的p与q往往有某种内在联系,而在数理逻辑里,p与q不一定有什么内在联系3.在数学和其他自然科学中,“如果p则q”往往表示的是前件为真,后件为真的推理关系.但在数理逻辑中,当p为假时,p→q为真在下例中,这3意注意事项郡有所体现,请注总区分【例1.5】将下列命题符号化(1)若3+3=6,则地球是运动的(2)若3|3≠6,则地球是运动的(3)若3+3=6,则地球是静比不动的.(4)若3+3≠6,则地球是静止不动的(5)只要a是4的倍数,a就是2的倍数(6)a是4的倍数,仅当a是2的倍数(7)除非a是2的倍数,a才能是4的倍数(8)除非a是2的倍数,否则a不是4的倍数(9)具有a是2的倍数,a才能是4的倍数(10)只有a是4的倍数,a才能是2的倍数解生(1)-(4)中,令护:3+3=6,9:地球是话动的,在这,p与q显然没有什么内在联系,但仍可以组成蕴涵式蕴涵式分别为p→q,一p→q,p“-9p-9桌值分别为1,1,0,1,在(5)(10)中,令r:a是4的倍数,:a是2的倍数(5)-(9)均叙还的是a是2的倍数是a是4的倍数的必要条件,因而都符号化为r→s.r,s的真值均可为0或1.但是当r的真值为1时的真值必定为1,因而蕴涵式rs不会出现前件真后件假的情况.于是,r→s的真值为1而在(10)中,将a是4的倍数看成∫a是2的倍数的必要条件,因而应符号化为s→r.因为可能出现s为真,r为假的情况,所以s→r的真值为0.比较(5)和(10),注意这里的“要”和“只有”是有区别的,在符号化时一定要注意定义15设p,q为命题复合命题“p当且仅当q"称作与q的等份式记作p“q+称作等价联结词力艹q的逻辑关系是P与q互为充分必要条件pq刈真当且仅当p与q的真值相间【例1.6将下列命题符号化,并求其真值(1)2+3=5当且仅当2是无理数(2)2+3=5当且仅当2不是无理数(3)2+3≠5当且仅当2是无理数(4)2+3≠5当且仅当2不是无理数(5)O1,(2两圆约面积相等当且仅当它们的半径相等6}A,B两角相等当且仅当它们是同位角(7)杜明是四川人坐且仅当沈荣生1970年解在(1)-(4)中,设p:2+3=5、9:√2是无理数(1)-(4)分别符号化为p*,pq.一pq,p-q由于p,q的真值郡是1,丙而pq与p*-g两边的命题真值相同所以它们的真值均为1.而p-9与pq两边命题的真值均相异,因而它们的真值为为0在(5)中,设p:O1,O2两圆面积相等,g:O1,O2两圆半径相等命题符号化为p→q,p与g的真值要由O1,O2的具体情况而定,但p,q的真值相同(同真或同假),因而pq的真值为1.府在(6)中,若设p:A,B两角相等,q:A,B是同位角,命题也符号化为ptq.但是p,q的真值可以不同,因而p*q的真值要由p,q的具伭情况而定类似地,(7)的真值也要根据具体憤况而定以上定义了5种联结词,组成一个联结词集,A,∨,→,,其中一是一元联结词符,其余的都是二元朕结词符,有时也称它们是逻辑运算符.可以规定这些运算符的优先级本书中规定它们优先级的顺序为-,∧,Ⅴ,→,←.如果出现的联词符同级,又无括号时,按从左到右顺序进行运算;若遇有括号时,先进行括号中的运算如,p→qAx*与(p(qAt)表达相同的逻辑关系,而pxA;·s,(P*q)∧p*5,(p→9)A(→*)表达的是互不相同的逻辑关乐【例1.7】将下列命题符号化并求真值(1)如果3是合数,则4是素数,并且如果4是素数,则它不能被2整除(2)如果2-3>5当且仅当5是全数,则/2和/3都是有理数解(1)设p:3是合数,q;4是素数,r:4能被2整除,则p,q,r的真值分别为0,0,1.命题符号化为(pg)A(q→-r),容易计算出它的真值为1(2)设p:2+3>5,q:5是合数,:2是有理数,5:3是有理数它们的真值分别为0,00,0命题符号化为(p+g)→(rAs),它的前件真值为1,后件真值为0,所以它的真值为012命题公式与赋值在上节中,用p,q,r…表示确定的简单命题,通常称p,q,r…为命题常项或命题常元,将p,q、r…用},A,V,,屮的某些联结词符按一定的逻辑关系联结起来就是复合命题的符号化形式简单命题和复合命题都有确定的真值.然而,在数理翌辑中不仅要研究具体的逻辑关系,而更主要的是研究抽象的逻辑关系.首先应对简单命题进行抽象称真值可以变化的简单陈述句为命题查项或命题变元,也用p,q,x…表示其实,命题变项p,q:r…均为取值或1的变量.pq,r…表示的是常项还是变项应由F下文确定成该注意的是,命题变呗不是命题将命题常项和命魎变用联结词和圆括号按一定逻辑关系联结起来的符号串称为合式公式,当使用联结词集{,A,,,|时,合式公式定义如下定义1.6(1)单个的命题变项(或常项)是合式公式(2}若A是合式公式,则(A)也悬合式公式;(3)若A,B是合式公式,则(AAB),(A∨B),(A+B),(A…B)是合式公式(4)只有角限次地应用(1)-3)形成然符号串才是合式公式合式公式也称为命题公式简称公式在合式公式的定义中,引进了A,胃等符号,它们代表任意的公式在本书中以后出现的A,B等符号也均代表任意的公式,不再说明另外,为方便起见,(A)、(AAB)等的外层括号均可以省去根据定义,((pAq)Ⅵr)→5,如→(g→),(pVq)Ar等都是合式公式,而pAq户AqAr)→等均不是合式公式为了讨论公式的真值变化情况,首先绘出公式层次的定义定义1.7(1)若A是单个的命颊变项或常项,则称A为0层合式(2)称A是n+1(n≥0)层公式是指下列诸情况之一:3A=-B,B是n层公式;②A=B∧C,其中B,C分别为i层和;层公式,且n=mx(,j);A=BVC,其中B,C的层次同②④A=B→C,其中BC的层次何②;⑤A=B*C,其中B,C的层次同②;易知,((-"p→q)Ar)Vs与(pA-qAr)Vs)→(pV?Vr)分别为4层和5层公式在合式公式中,由于有命题变项出现,因而公式的真值是不确定的,当将公式中出现的全部变项都解释成具体的命题之后,公式就成了真值确定的复合命魎了【例18】给出卜面公式两种不同的解释,一种解释使它为真,一种解释使它为假.分式为解(1)将力解释成2是偶数,q解释成3是偶数,r解释成2+3是偶数显然,p,q,r的真值分别为I,0,0,故(pVq)r的真值为0(2)中,q的解释同(1),将r解释成2+3为奇数,则(pvq)→r的真值为1.般情况下,设公式A中含n个命题变硕,将每个命题变项都指定确定的真值或1,称为对A的赋值或解释严格定义如下定义18设p1:p2,…p是出现在公式A中的全部命,变项,绔pp2,…p各指定个真值,称为对A的一个薰值或解释.若指定的…组值使A的值为1,则称这组值为A的成真值若使A的值为0,则称这组值为A的成假值本书中,含η个命题变项的命题公式的赋值形式做如下规定(1)设A中含的命题变項为p1,p2…p赋值α1a2…an(a;为0或1)是指p1=a1p2Prft(2)若出现在A中的命题变项为户,q,r…,赋值a12…是指p=21,q=2……,即按字典顺序狱值例如,在公式(→1∧血人(pA一2A中,011(1=0,p2=1,=1),101(11,2=0,p3-1)都是成真赋值其余的斌值都是式假赋值在公式(pA一q)→r中,011(p0,g=1,r=1)为成真赋值,100(p=1,=0,rm0)为成假赋值含n(n≥1}命题变项的公式A共有2”个狱值将公式A在所有赋值之下取值情况列成表,称为A的真值变构造真值表的具体步骤如下:(1)找出公式中所含的全部命变项1;内2…,pn(若无下角标就按字典顺字给出),列出所有可能的赋值(2n个);(2)按从低到高的顺序写出各层次;(3)对应各斌值,计算公式各层次的值直到最后计算出公式的值【例1.]求下列命题公式的真值表)(p∧一q)r2)(p(qVp)〉vr3)一(p→q)∧q∧r解变1.1(pA-9)r的真值丧p望r1户A-q(p∧一g)000阝1011101000豪12{p→(qp})r的J值V p(Qvpp→(qⅤp))Yr00000104101011100t丧1,3-(p→q)AqAr的真值豪pP即(p→qAn{p→q)AqAr00t01〔0」0010U101ll10表1.1—1.3都是按构造舆值表的步骤一步一步地写出的,这样构造真值表不容易出锴如果比较熟练有些层次可不列出.由真值表可以看出,公式(1)的8个赋值中,除了100是成7假赋值外,其余的都是成真賦值.而(2)无成假赋值.(3〉无成真赋值根据公式在各种赋值下的取值情况,可将命题公式分为3类,定义如下定义1.9设A为一命题公式(1)若A在它的各种赋值下取值均为真,则称A为重言式或永真式;(2)若A在它的各种赋值取值均为假,则称A为矛盾式永假式;(3)若A不是矛盾式,则称A是可满足式由定义可以看出,重言式是可满足式,但反之不真用真值表可以判断公式的类型;若真值表的最后一列全为1,则公式为重言式;若最后一列全为则公式为矛盾式;若最后一列既有1又有0,则公式为非重言式的可满足式在例1.9中,(1为可满足式,(2)为重言式,当然也是可满足的,(3)是矛盾式用真值表判断公式的类型方法简单易行,但当命题变项较多时,计算量人在下两节中还要介绍其他方法3等值演算给定n个命题变项,按合式公式的形成规则可以形成无穷无尽多的命题公式,但在这些无穷无尽的公式中,有些其有相同的真值表这些公式的真值表的最后一列以有有限种不同的情况例如,n=2时,p,∨q,(pA一q),(p→9)∧(p∨p)…,表面看来,它们具有不同的形式,但它们的真值是相同的即在4个财值00,01,10,11下,均有相同的真值,也就是它们的真值表的最后列是相同的,对于任意的含p,q两个命题变项的公式来说,在以上4个赋值的每个赋值下,公式只能取值0或1,因而2个命题变项共叮产生22=16种不同的取值情况.一般地,n个命题变项以能兰成2个真值不同的公式.这就存在着如何判断哪些公式具有相同真值的问题了设公式A,B均含命题变项p1,p2:…,pn若A,B具勻相同的真值,则A…B的真值总为1,即A→B为重言式下面给出A与序真值相的严格定义定义1.10设A,B为二命题公式,若等价式A→B为重言式,则称A与B是等值的,记作A台B在定义中,要注意符号“兮”不是联结词符,它是A与B等值的一种记法.千万不能将灬或<}与些混为谈例1.10】用真值表法判断下面二公式是酉等值fq→p)与pAq解用真值表法判断一(q→p){pAq)是否为重言式,见表1.414一(q→p*→Aq)的真值爱PPq→p)+(PA001110000由于真值表的最后一列全为1,所以(p)(pAq)是重音式,即“(q→p)句(,pAq)从表14不难看出,(qp)(bAg}为重言式,当且仅当在各个赋值下(q→p)与(→pAq)的真值均相同于是真值表最后·列可省去【例1.1】判断下列各组公式是等值1)→(q→p)与(Aq(p*q)→r与〔pA解用简化真值表法解此题1】)由表1.5可以看出,p(qr)与(pAg)→r的真值表相同,因而它们是等值的,即(9=r)o(PA9)-r表1.5P4p Ap"{q→r))P凸g)-一00010010101001111D011100L O I11D1(2)从表1.6可以看出,000与010使得(p+q)→;写(pAq)→r的真值不同,因而(p→q)→r
用户评论
