数理逻辑（mathematicallogic）是用数学方法研究人类推理过程的一门数学学科。5.1命题及联结词5.1命题及联结词定义5.1.1定义5.1.2例如，P：22=5，Q：雪是黑的，PQ：22=5并且雪是黑的。定义5.1.3定义5.1.3例如，P：小李爱唱歌。Q：小李爱跳舞。PQ：小李爱唱歌或跳舞。定义5.1.4例如，P：f(x)是可微的，Q：f(x)是连续的，PQ：若f(x)是可微的，则f(x)是连续的。定义5.1.5例如，P：a2+b2=a2，Q：b=0，PQ：a2+b2=a2当且仅当b=0。例例例5.2命题公式及公式的等值和蕴含关系一、命题公式规定：定义2设A是命题公式，P1,…,Pn是出现在A中的所有命题变元。对P1,…,Pn指定一组真值，则这组真值称为A的一个赋值或指派。（assignments）成真指派成假指派设A为命题公式：A（P1,…,Pn）称为n元命题公式。有n个不同原子的公式，共有2n个不同的真值指派。A在其所有可能的真值指派下所取真值的表，称为G的真值表。（truthtable）p语句的形式化定义3：对命题公式A，如果对A中命题变元的一切指派均为真，则A称为重言式（tautology），又称永真式.我们常把重言式记为1,把矛盾式记为0例:用真值表判断下列公式的类型.(1)(PQ)PQ(PQ)Q(PQ)RPPP二、命题公式的等值式二、命题公式的等值式几点说明：1、定义中，A,B,均为元语言符号2、A或B中可能有哑元出现.例如(pq)((pq)(rr))r为左边公式的哑元.3、用真值表可检查两个公式是否等值请验证：p(qr)(pq)rp(qr)不与(pq)r等值例1判断下列各组公式是否等值:(1)p(qr)与(pq)r(2)p(qr)与(pq)r二、命题公式的等值式基本等值式基本等值式等值演算与置换规则等值演算与置换规则等值演算与置换规则等值演算的应用举例证明两个公式不等值例3证明p(qr)与(pq)r不等值证方法一真值表法,见例1(2)方法二观察法.观察到000,010是左边的成真赋值，是右边的成假赋值方法三先用等值演算化简公式，然后再观察p(qr)pqr(pq)r(pq)r(pq)r更容易看出前面的两个赋值分别是左边的成真赋值和右边的成假赋值判断公式类型:A为矛盾式当且仅当A0A为重言式当且仅当A1例4用等值演算法判断下列公式的类型(1)q(pq)(2)(pq)(qp)(3)((pq)(pq))r)(1)q(pq)判断公式类型三、公式的蕴含关系上面两个例子的推理关系涵义不同，但依据的推理规则相同，推理形式为：若P则Q，P，所以Q。推理的正确性与命题P，Q涵义无关，只决定于逻辑形式，命题逻辑中用公式表示命题，命题间演绎推理关系，反映为公式间逻辑蕴含关系。定义5（蕴含）设A，B，C是命题公式，则：（1）自反性：AA（2）反对称性：若AB，BA，则AB（3）传递性：若AB，且BC，则AC基本蕴涵式基本蕴涵式公式蕴涵的证明方法5.3对偶与范式一、对偶定理1：设公式A中仅含命题变元p1,…,pn，及联结词┐，∧，∨，A*为A的对偶，那么┐A(p1,…,pn)A*(┐p1,…,┐pn)对偶原理5.4命题演算的推理规则定义1设A1,A2,…,An,B为命题公式.如果A1A2…AnB为重言式,则称B为由前提A1,A2,…,An推出的有效结论.说明判断推理是否有效,就是判断A1A2…AnB是否重言式即A1A2…AnB所以判断推理是否有效的方法:1、真值表法2、等值演算法3、蕴含演算法4、主析取范式法推理实例推理实例推理实例推理定律形式证明法例例2构造下面推理的证明：若明天是星期一或星期三，我明天就有课.若我明天有课，今天必备课.我今天没备课.所以，明天不是星期一、也不是星期三.解(1)设命题并符号化设p：明天是星期一，q：明天是星期三，r：我明天有课，s：我今天备课直接证明法前提：(pq)r,rs,s结论：pq证明:(((pq)r)(rs)s)(pq)(((pq)r)(rs)s)(pq)((pq)r)(rs)s)(pq)((pr)(qr)(rs))(pq)(pr)r(qr)rs)(pq)(prqrs)(pq)(prqr