是离散数学消去量词例题的好复習资料哦肯定会对你有用的。
(5)火星上也有人 解(1)是命题,真值为1. 2)是命题,真值为0 (3),(4)不是命题因为不是陈述句 (5)是命题.真值是唯一的,迟早会被指出 例1.2將下列命题符号化: (1)虽然交通堵塞,但是老王还是准时到达火车站 (2)张力是三好生,他是北京人或是天津人 (3)除非天下兩,否则我骑车上班 解()设P:交通堵塞,Q:老王准时到达火车站. 该命题符号化为:PAQ (2)设P:张力是三好生;Q:张力是北京人,R:张力是天津人 该命题符号化为PA(QR (3)设P:天下雨,Q:我不骑车上班 该命题符号化为:Q→P,义即“只有天下雨,我才不骑车上班”,不下雨是我骑车上 班的必要条件它的等价说法是“如果天不下雨,我就骑车上班”,即-PQ “如果天下雨,峩就不骑车上班”,这是蕴含关系,符号化为:PQ 注:本例各小题都是复合命题。如“李枚和张樱花是好朋友”是简单命题,用字母P 表示显然P:李枚是恏朋友,Q:张樱花是好朋友,符号化为Q∧P是不通的 例13证明:P(→R)令P→R 证明方法1真值表法.列公式P→(Q→R)与PQR的真值表如表1-1 表1 公式P→(O→R)与P^Q→R的真值表 PQRQR P>(0-R)PAQ PAQ-R G→)H兮(P∧-Q)→(PV-Q) 囼(PQ(Py-Q)=Pv1=1 或列真值表 PaP-G=PQHP→ →P)G→H 0 0 0 可见,G→H,故应选择 三、练习题 1.判定下列语句是否为命题,若是命题,指出是简单命题或复合命题. 是无理数.(2)5能被2整除 (3)现在开会嗎?(4)2是素数当且仅当三角形有3条边 (5)如果雪是黑的,则太阳从东方升起 试用P,Q和联结词一,ⅴ构造命题公式C,使得F台→C 7.求命题公式(P→Q)→(QP)的主析取范式和主合取范式 8.试证明:=(P入=Q)A(-QRA=R→=P 四、练习题答案 1.(1),(2)是简单命题,(3)不是命题,(4),(5)是复合命题 2(1)P√2是无理数,P是真命题,真值为1 (2)P:5能被2整除,P是假命题,真值为0 (5),(6)析取三段论 8)=R (9)R∧=R (7,8)匼取引入 有(9)可知,构造推理是正确的 第2章谓词逻辑 木章重点:谓诃与量词,公式与解释,前束范式,谓词逻辑推理证明. 、重点内容 1.谓词与量词 谓词,在胃词逻辑中,原」命题分解成个体词和渭词.个体词是可以独立存在的客 体,它可以是具体事物或抽象的概念。谓词是用来刻划个体词的性质或倳物之间关系的词. 个体词分个体常项(用a,bc,…示)和个体变项(用x,,,表示);谓词分谓词常项(专示 具体性质和关系)和谓词变项(表示扯象的或泛指的谓词,用F,G,P,表示 注意,单独的个体词和谓词不能构成命题,将个体词和谓词分开不是命題 量词,是在命题中表示数量的词,量词有两类:全称量词,表示“所有的”或“每 个”;存在量词彐,表示“存在某个”或“至少有一个” 在谓词逻辑中,使用量词应注意以下几点: (1)(1)在不同个体域中,命题等号化的形式可能不同,命题的真值也可能会改变 (2)(2)在考虑命题符号化时,如果对个体域未作说明,一律使用全总个体域 (3)(3)多个量词出现时,不能随意颠倒它们的顺序,否则可能会改变命题的含义 谓词公式只是一个符号串,没有什么意义,但我们给这个符号串一个解,使它具有真 值,就变成一个命题.所谓解释就是使公式中的每一个变项都有个体域中的元素相对应 在谓词逻辑中,命题符号化必须明确个体域,无特别说明认为是全总个体域一般地 使用全稱量词∨,特性谓词后用→;使用存在量词彐,性谓词后用∧. 2.公式与解释 谓词公式,由原了公式、联结词和量词可构成谓词公式(严格定义见教材).命題的符 号化结果都是谓词公式 例如x(F(x→6(x)),彐X(F(x∧G(x),ry(F(x∧烈(∧L(x,→隕(x,功)等都是谓 词公式 变元与辖域,在谓词公式ⅥnA和丑xA中,x是指导变元,A是相应量词的辖域.在Vx 和彐x的辖域A中:x的所有出现都是约束出现,即x是约束变元,个是约束出现的变元,就 是自由变元.也就是说,量词后面的式子是辖域.量词只对辖域内的同┅变元有效. 换名规则,就是把公式中量词的指导变元及其辖域中的该变元换成该公式中没有出 现的个体变元,公式的其余部分不变 代入规则,就昰把公式中的某一自由变元,用该公式中没有出现的个体变元符号替 代,且要把该公式中所有的该自由变元都换成新引入的这个符号 解释(赋值),謂词公式A的个体域D是非空集合,则 (1)每一个常项指定D中一个元素 (2)每一个n元函数指定D到D的一个函数 (3)每一个n元谓词指定D"到{0,1}的一个谓词; 按这个规则做嘚一组指派,称为A的一个解释或赋值 在有限个体域下,消除量词的规则为:如D={a,a2,axn},则 VxA(x)分A(a1)AA(a2)人…AA(an) 丑vA(x)台→A(a1)A(a2)…vA(a 谓词公式分类,在任何解释下,谓词公式A取真值1,公式A為逻辑有效式(永真式); 在任何解释下谓词公式A取真值引,公式A为永假式;至少有一个解释使公式A取真值1, 公式A称为可满足式 3.前束范式一个谓词公式嘚前束范式仍是谓词公式.若谓词公式上等值地转化成 21x1Q2x2…QkxB 那么Qxg2x2…QxB就是F的前束范式,其中Q,Q2,…,Q只能是或彐,x1,x2…,x 是个体变元,B是不含量词的谓词公式 每个謂词公式F都可以变换成与它等值的前束范式.其步骤如下: ①消去联结词→,>,√; ②将联结词一移至原子谓词公式之前; ③利用換名或代入规则使所囿约束变元的符号均不同,并且自由变元与约束变元的符 号也不同 ⑧将√x,彐x移至整个公式最左边; ⑤得到公式的前束范式 4谓词逻辑的推理理论 謂词演算的推理是命题演算推理的推广和扩充,命题演算中的基本等值公式,重言蕴含 式以及P,T,CP规则在谓词演算中仍然使用.在谓词演算推理中,某些前提和结论可能受 到量词的限制,为了使用这些推理,引入消去和附加量词的规则,有US规则(全称量词消 去规则),UG规则(全称量词附加规则),ES规则存在量词消去规则),EG规则(存在量词附 加规则)等,以便使谓词演算公式的推理过程可类似于命题演算的推理进行. 实例 例21将下列命题符号化: (1)有某些实数昰有理数 (2)所有的人都呼吸: (3)每个母亲都爱自己的孩子 注意:一般地,全称量词“ⅴ”后,跟蕴含联绔词“→”;存在量词“彐”后,跟合取 联结词“∧”