命题逻辑及命题演算

概述和计算机科学联系和计算机科学联系紧密是计算机科学的支撑学科之一，也是信息科学的数学基础。在计算机理论研究及软硬件开发的各个领域都有广泛的应用。在计算机科学发展的过程中，各种理论问题的研究交错地使用着近代数学中的不同论题，这些论题构成了离散数学。学习离散数学的重要性一个土耳其商人想找一个十分聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出自己头上戴的帽子是什么颜色的。”说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把灯打开。这时，那两个应试者看到商人头上戴的是一顶红帽子，其中一个人便喊道：“我戴的是黑帽子。”请问这个人说得对吗？他是怎么推导出来的呢？要回答这样的问题，实际上就是看由一些诸如“商人戴的是红帽子”这样的前提能否推出“猜出答案的应试者戴的是黑帽子”这样的结论来。这又需要经历如下过程：(1)什么是前提？有哪些前提？(2)结论是什么？(3)根据什么进行推理？(4)怎么进行推理？二、命题与联结词1引例：4是素数；是无理数；大于；大于吗？；5xy5请不要吸烟！定义：命题---具有唯一真值的陈述句。例我正在说假话；2009年的元旦是晴天。真命题---命题的判断结果为真。假命题---命题的判断结果为假。表示方法：命题（），真（1）假（0）。srqp,,,4是素数；是无理数等不能分解成更简单5例的陈述句了，称此种命题为简单命题（原子命题）。否则，某命题是由简单命题通过联结词连接在一起的命题，称之为复合命题。例：2是偶数是不对的；2是偶素数；2或4是素数；如果2是素数，则3也是素数；2是素数当且仅当3也是素数。解：2是偶数；2是素数；4是素数；3是素数。:p:q:r:s非；且；或；如果则；当且仅当。ppqrqsqsqp┐pF（0）T（1）T（1）F（0）“见假为真，见真为假”┐p读作“并非p”或“非p”。(1)否定式：（negation）设P为一命题，P的否定是一个新命题，记作“┐P”。若P为T，┐P为F；若P为F，┐P为T。联结词“┐”表示自然语言中的“并非”（not）。三、联结词（2）合取式：（conjunction）两个命题P和Q的合取是一个复合命题，记作P∧Q。当且仅当P、Q同时为T时，P∧Q为T，其他情况下，P∧Q的真值都是F。合取联结词“∧”表示自然语言中的“并且”。pqp∧qF（0）F（0）T（1）T（1）F（0）T（1）F（0）T（1）F（0）F（0）F（0）T（1）p∧q读作“p并且q”或“p且q”见假为假，全真为真。（3）析取式：两个命题P和Q的析取是一个复合命题，记作P∨Q。当且仅当P、Q同时为F时，P∨Q为F，其他情况下，P∨Q的真值都是T。析取联结词“∨”表示自然语言中的“或”（or）。pqp∨qF（0）F（0）T（1）T（1）F（0）T（1）F（0）T（1）F（0）T（1）T（1）T（1）见真为真，全假为假。p∨q读作“p或者q”、“p或q”。（4）蕴涵式：给定两个命题P和Q，其条件命题是一个复合命题，记作P→Q。当且仅当P的真值为T，Q的真值为F时，P→Q的真值为F，其他情况下，P→Q的真值都是T。条件联结词“→”表示自然语言中的“如果…，那么…”。pqp→qF（0）F（0）T（1）T（1）F（0）T（1）F（0）T（1）T（1）T（1）F（0）T（1）p→q中的p称为条件前件，q称为条件后件前真后假为假，其他为真。（5）等价式：给定两个命题P和Q，其复合命题PQ称作双条件命题。当P和Q的真值相同时，PQ的真值为T，否则，PQ的真值都是F。双条件联结词“”表示自然语言中的“当且仅当”。pqpqF（0）F（0）T（1）T（1）F（0）T（1）F（0）T（1）T（1）F（0）F（0）T（1）pq读作“p与q互为条件”，“p当且仅当q”。相同为真，相异为假。1-1.2复合命题的符号化复合命题的符号化的基本步骤1)找出各个原子命题，并逐个符号化；2)找出各个连接词，符号成相应联结词；3)用联结词将原子命题逐个联结起来；1-1.2复合命题的符号化例将下列命题符号化(1)北京不是村庄P:表示“北京是村庄”┐P:北京不是村庄(2)小王是游泳冠军和百米赛跑冠军P：小王是游泳冠军;Q：小王百米赛跑冠军P∧Q:小王是游泳冠军和百米赛跑冠军1-1.2复合命题的符号化例将下列命题符号化(3)小明或者小华能解够出这道题P：小明能够解出这道题;Q：小华能够解出这道题P∨Q(4)小王或者小李中的一个能够当上班长P：小王能够当上班长;Q：小李能够当上班长((┐P)∧Q)(P∧(┐Q))∨1-1.2复合命题的符号化例将下列命题符号化(5)今夜你若敢去公墓，那么我就咬掉我的鼻子或咬掉我的耳朵P：今夜你敢去公墓。Q：咬掉我的鼻子。R:咬掉我的耳朵P→(Q∨R)1-1.2复合命题的符号化例将下列命题符号化(6)王乐是计算机系的学生，生于1980年或1981年,是三好学生。P：王乐是计算机系的学生。Q：生于1980年。R:生于1981年.S:是三好学生.P∧(Q∨R)∧S四、命题公式及其赋值1.命题常项（命题常元）：简单命题2.命题变项（命题变元）3.合式公式（命题公式）：将命题变元用联结词或圆括号按一定的逻辑关系联结起来的符号串称为合式公式或命题公式。（A，B…）定义：（1）单个命题变项可被称为合式公式；（2）若是合式公式，则也是合式公式；（3）若是合式公式，则也是合式公式；（4）将1-3有限次的联结起来也是合式公式。ABABABABA,,,BA,A注：合式公式的运算规则:,,,,例)())((rrqp五、合式公式的真值引例：qp定义：设是出现在公式中的全部的命题变项，给各指定一个真值，称为对的一个赋值或解释。若指定的一组值使的真值为1，则称这组值为的成真赋值，若使的真值为0，则称这组值为的成假赋值。nppp,,,21nppp,,,21AAAAAA例：利用真值表求的成真赋值和成假赋值rqp练习：（1）（2）（3）rqp)()()(qqpprqqp)(（2）若在它的各种赋值下取值为假，则称为矛盾式或永假式；AA定义：设为任一命题公式.(1)若在它的各种赋值下取值为真，则称为重言式或永真式；AAA（3）若不是矛盾式，则称为可满足式。AA第二章命题逻辑等值演算一、等值式引例：)(qp与qp定义：设是两个命题公式，若构成的等价式为重言式，则称是等值的，记作。BA,BA,BA,BABA练习：1）与)(rqprqp)(2）与rqp)(rqp)(等值演算公式：双重否定律:AA等幂律：AAA,AAA交换律:ABBA,ABBA结合律:(AB)CA(BC)(AB)CA(BC)分配律:A(BC)(AB)(AC)A(BC)(AB)(AC)德·摩根律:(AB)AB(AB)AB吸收律:A(AB)A,A(AB)A零律:A11,A00同一律:A0A,A1A排中律:AA1矛盾律:AA0蕴涵等值式:ABAB等价等值式:AB(AB)(BA)假言易位:ABBA等价否定等值式:ABAB归谬论:(AB)(AB)A注意:A,B,C代表任意的命题公式等值演算的用途一：证明等值式。例1.10验证p(qr)(p∧q)r右(p∧q)∨r蕴涵等值式p∨q∨r德摩根律p∨(q∨r)结合律p∨(qr)蕴涵等值式p(qr)蕴涵等值式注:ABA∨B练习：)()(qpqpp)()()(qpqpqp例证明:p(qr)(pq)r用等值演算不能直接证明两个公式不等值,证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假.方法一真值表法（自己证）方法二观察赋值法.容易看出000,010等是左边的成真赋值，是右边的成假赋值.方法三用等值演算先化简两个公式，再观察例用等值演算法判断下列公式的类型(1)q(pq)解q(pq)q(pq)（蕴涵等值式）q(pq)（德摩根律）p(qq)（交换律，结合律）p0（矛盾律）0（零律）由最后一步可知，该式为矛盾式.(2)(pq)(qp)解(pq)(qp)(pq)(qp)（蕴涵等值式）(pq)(pq)（交换律）1由最后一步可知，该式为重言式.(3)((pq)(pq))r)解((pq)(pq))r)(p(qq))r（分配律）p1r（排中律）pr（同一律）这不是矛盾式，也不是重言式，而是非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.总结：A为矛盾式当且仅当A0A为重言式当且仅当A1说明：演算步骤不惟一,应尽量使演算短些定义文字：命题变项及其否定统称为文字。如：p,q简单析取式：仅有有限个文字组成的析取式。如：p,q,p∨q,p∨q∨r简单合取式：仅有有限个文字组成的合取式。如：p,q,p∧q,p∧q∧r二、析取范式与合取范式命题公式是千变万化的，这给研究命题演算带来困难，这里我们研究如何由一个命题公式化归为一个标准形式的问题，这样命题演算的研究问题就归结为对标准形式的研究问题，这种标准形式就叫范式。析取范式它是这样一种标准形式，在此式内不出现联结词及，否定符号只出现在命题变元前。它是一个析取式，式中的每个析取项是个合取式，每个合取式中只包含命题变元或命题变元的否定。例如p∨(p∧q)∨(q∧r)此式即具有析取范式之形式注意:一个公式的析取范式并不唯一，如p∨(r∧q),可以写成(p∧p)∨(r∧q)合取范式它是这样一种标准形式，在此式内不出现联结词及，否定符号只出现在命题变元前。它是一个合取式，式中的每个合取项是个析取式，每个析取式中只包含命题变元或命题变元的否定。例如p∧(p∨q)∧(q∨r)此式即具有合取范式之形式注意:一个公式的合取范式并不唯一，如p∧(r∨q)可以写成(p∨p)∧(r∨q)定义：析取范式：由有限个简单合取式构成的析取式。如：p∨q,(p∧q)∨(p∧q∧r)合取范式：由有限个简单析取式构成的合取式。如：p∧q,（p∨q）∧（p∨q∨r）范式：析取范式与合取范式统称为范式。设Ai(i=1,2,3,…n)为简单合取式，则A=A1∨A2∨……∨An就是析取范式，而B=A1∧A2∧……∧An就是合取范式。析取范式和合取范式有下列性质：（1）一个析取范式是矛盾式它的每个简单合取式都是矛盾式。（2）一个合取范式是重言式它的每个简单析取式都是重言式。例求下列公式的析取范式与合取范式(1)A=(pq)r解(pq)r(pq)r（消去）pqr（结合律）这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）(2)B=(pq)r解(pq)r(pq)r（消去第一个）(pq)r（消去第二个）(pq)r（否定号内移——德摩根律）这一步已为析取范式（两个简单合取式构成）继续：(pq)r(pr)(qr)（对分配律）这一步得到合取范式（由两个简单析取式构成）求范式的具体步骤：（1）消去对{,∧,∨,}来说冗余的联结词，即{，}。利用下列等值式：AB(A∨B)AB(A∨B)∧(A∨B)（2）否定词的消去或内移。利用下列等值式：AB(A∨B)(A∨B)A∧