1、概述和计算机科学联系概述和计算机科学联系 n和计算机科学联系紧密是计算机科学的支撑学科之一，也是信息科学的数学基础。在计算机理论研究及软硬件开发的各个领域都有广泛的应用。在计算机科学发展的过程中，各种理论问题的研究交错地使用着近代数学中的不同论题，这些论题构成了离散数学。学习离散数学的重要性学习离散数学的重要性 一个土耳其商人想找一个十分聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后
2、，请你们尽快说出自己头上戴的帽子是什么颜色的。”说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把灯打开。这时，那两个应试者看到商人头上戴的是一顶红帽子，其中一个人便喊道：“我戴的是黑帽子。” 请问这个人说得对吗？他是怎么推导出来的呢？ 要回答这样的问题，实际上就是看由一些诸如“商人戴的是红帽子”这样的前提能否推出“猜出答案的应试者戴的是黑帽子”这样的结论来。这又需要经历如下过程： (1) 什么是前提？有哪些前提？ (2) 结论是什么？ (3) 根据什么进行推理？ (4) 怎么进行推理？ 二、命题与联结词二、命题与联结词1 引例引例：4是素数是素数
3、； 是无理数；是无理数；大于大于 ；大于大于 吗？；吗？； 5xy5请不要吸烟！请不要吸烟！定义：命题定义：命题-具有唯一真值的陈述句。具有唯一真值的陈述句。n例 我正在说假话； 2009年的元旦是晴天。 真命题真命题-命题的判断结果为真。命题的判断结果为真。假命题假命题-命题的判断结果为假。命题的判断结果为假。表示方法：命题（表示方法：命题（ ），真（），真（1）假（假（0）。）。srqp,4是素数是素数； 是无理数等不能分解成更简单是无理数等不能分解成更简单5例例的陈述句了，称此种命题为的陈述句了，称此种命题为简单命题（原子简单命题（原子命题）命题）。否则，某命题是由简单命题通过联结词连接
4、在否则，某命题是由简单命题通过联结词连接在一起的命题，称之为一起的命题，称之为复合命题复合命题。例：例： 2是偶数是不对的；是偶数是不对的；2是偶素数；是偶素数；2或或4是是素数；如果素数；如果2是素数，则是素数，则3也是素数；也是素数；2是素数是素数当且仅当当且仅当3也是素数。也是素数。解：解： 2是偶数；是偶数； 2是素数；是素数； 4是素数；是素数； 3是素数。是素数。:p:q:r:s非非 ； 且且 ； 或或 ；如果；如果 则则 ； 当且仅当当且仅当 。ppqrqsqsq p p F（0） T（1） T（1） F（0）“见假为真，见真为假见假为真，见真为假”p读作读作“并非并非p”或或“
5、非非p”。（negationnegation ）“ “ ” ”表示自然语表示自然语言中的言中的“并非并非”（not not ）。）。 三、联结词三、联结词合取式合取式：（ conjunction conjunction ）合取联结词合取联结词“”“”表示自然语言表示自然语言 中的中的 “ “并且并且” ” 。 p q p q F（0） F（0） T（1） T（1） F（0） T（1） F（0） T（1） F（0） F（0） F（0） T（1）pq读作读作“p并且并且q”或或“p且且q” 见假为假，见假为假，全真为真。全真为真。式式： 取联结词取联结词 “ “ ” ”表示自然语言中的表示自然语言
6、中的 “ “ 或或”（or or ）。）。 p q p q F（0） F（0） T（1） T（1） F（0） T（1） F（0） T（1） F（0） T（1） T（1） T（1）见真为真，见真为真，全假为假。全假为假。pq读作读作“p或者或者q”、“p或或q”。 联结词联结词 “ ” ”表示自然语言中的表示自然语言中的“如果如果，那么，那么”。 p q p q F（0） F（0） T（1） T（1） F（0） T（1） F（0） T（1） T（1） T（1） F（0） T（1）pq中的中的p称为称为，q称为称为 前真后假为假，前真后假为假，其他为真。其他为真。： 联结词联结词 “ ”表示自然语
7、言中的表示自然语言中的“当且仅当当且仅当”。 p q p q F（0） F（0） T（1） T（1） F（0） T（1） F（0） T（1） T（1） F（0） F（0） T（1）pq读读作作“p与与q互为条件互为条件”，“p当且仅当当且仅当q”。 相同为真，相同为真，相异为假。相异为假。1-1.2 复合命题的符号化n复合命题的符号化的基本步骤1) 找出各个原子命题，并逐个符号化；2) 找出各个连接词，符号成相应联结词；3) 用联结词将原子命题逐个联结起来； 1-1.2 复合命题的符号化n例 将下列命题符号化 (1)北京不是村庄P: 表示“北京是村庄”P:北京不是村庄(2)小王是游泳冠军和百米
8、赛跑冠军P：小王是游泳冠军;Q：小王百米赛跑冠军PQ: 小王是游泳冠军和百米赛跑冠军1-1.2 复合命题的符号化n例 将下列命题符号化 (3)小明或者小华能解够出这道题P：小明能够解出这道题;Q：小华能够解出这道题PQ(4)小王或者小李中的一个能够当上班长P：小王能够当上班长;Q：小李能够当上班长(P)Q)(P(Q)1-1.2 复合命题的符号化n例 将下列命题符号化 (5) 今夜你若敢去公墓，那么我就咬掉我的鼻子或咬掉我的耳朵P：今夜你敢去公墓。Q：咬掉我的鼻子。R: 咬掉我的耳朵 P (QR)1-1.2 复合命题的符号化n例 将下列命题符号化 (6) 王乐是计算机系的学生，生于1980年或1
9、981年,是三好学生。P：王乐是计算机系的学生。Q：生于1980年。R: 生于1981年. S: 是三好学生.P(QR)S四、命题公式及其赋值四、命题公式及其赋值1.命题常项（命题常元）：简单命题命题常项（命题常元）：简单命题2.命题变项（命题变元）命题变项（命题变元） 3.合式公式（命题公式）：将命题变元用联合式公式（命题公式）：将命题变元用联结词或圆括号按一定的逻辑关系联结起来的符结词或圆括号按一定的逻辑关系联结起来的符号串称为合式公式或命题公式。（号串称为合式公式或命题公式。（A，B）定义：定义：（1）单个命题变项可被称为合式公式；单个命题变项可被称为合式公式；（2）若若 是合式公式，则
10、是合式公式，则 也是合式公式；也是合式公式；（3）若若 是合式公式，则是合式公式，则 也是合式公式；也是合式公式；（4）将将1-3有限次的联结起来也是合式公式。有限次的联结起来也是合式公式。ABABABABA,BA,A注：合式公式的运算规则注：合式公式的运算规则:,例例)()(rrqp五、合式公式的真值五、合式公式的真值引例引例：qp定义定义：设：设 是出现在公式是出现在公式 中的全中的全 部的命题变项，给部的命题变项，给 各指定一个真值各指定一个真值，称为对，称为对 的一个赋值或解释。若指定的一组的一个赋值或解释。若指定的一组值使值使 的真值为的真值为1，则称这组值为，则称这组值为 的成真赋
11、的成真赋值，若使值，若使 的真值为的真值为0，则称这组值为，则称这组值为 的成的成假赋值。假赋值。 nppp,21nppp,21AAAAAA例：利用真值表求例：利用真值表求 的成真赋值和成假赋值的成真赋值和成假赋值rqp练习：练习：（1）（2）（3）rqp)()()(qqpprqqp)(（2）若）若 在它的各种赋值下取值为假，则称在它的各种赋值下取值为假，则称 为为矛盾式矛盾式或永假式；或永假式；AA定义定义：设：设 为任一命题公式为任一命题公式.(1)若若 在它的各种赋值下取值为真，则称在它的各种赋值下取值为真，则称 为为重言式重言式或永真式；或永真式；AAA （3）若）若 不是矛盾式，则称
12、不是矛盾式，则称 为为可满足式可满足式。AA第二章第二章 命题逻辑等值演算命题逻辑等值演算一、等值式一、等值式引例：引例：)(qp与与qp 定义：设定义：设 是两个命题公式，若是两个命题公式，若 构成构成的等价式的等价式 为重言式，则称为重言式，则称 是等值的，记是等值的，记作作 。BA,BA,BA,BABA练习练习：1） 与与 )(rqprqp )(2） 与与 rqp )(rqp )(等值演算公式：等值演算公式：双重否定律双重否定律 : AA等幂律：等幂律： A AA, A AA交换律交换律: A BB A, A BB A结合律结合律: (A B) CA (B C) (A B) CA (B
13、C)分配律分配律: A (B C)(A B) (A C) A (B C) (A B) (A C)德德摩根律摩根律 : (A B)AB (A B)AB吸收律吸收律: A (A B)A, A (A B)A零律零律: A 11, A 00 同一律同一律: A 0A, A 1A排中律排中律: AA1矛盾律矛盾律: AA0蕴涵等值式蕴涵等值式: ABA B等价等值式等价等值式: AB(AB) (BA)假言易位假言易位: ABBA等价否定等值式等价否定等值式: ABAB归谬论归谬论: (AB) (AB) A注意注意:A,B,C代表任意的命题公式代表任意的命题公式等值演算的用途一：证明等值式。等值演算的用途
14、一：证明等值式。例例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 AB 练习：练习：)()(qpqpp)()()(qpqpqp例例 证明证明: p (q r) (p q) r 用等值演算不能直接证明两个公式不等值用等值演算不能直接证明两个公式不等值,证证明两个公式不等值的基本思想是找到一个赋值明两个公式不等值的基本思想是找到一个赋值使一个成真使一个成真,另一个成假另一个成假. 方法一方法一
15、真值表法（自己证）真值表法（自己证） 方法二方法二 观察赋值法观察赋值法. 容易看出容易看出000, 010等是左等是左 边的成真赋值，是右边的成假赋值边的成真赋值，是右边的成假赋值. 方法三方法三 用等值演算先化简两个公式，再观用等值演算先化简两个公式，再观 察察例例 用等值演算法判断下列公式的类型用等值演算法判断下列公式的类型(1) q(pq) 解解 q(pq) q( p q) （蕴涵等值式）（蕴涵等值式） q (pq) （德摩根律）（德摩根律） p (qq) （交换律，结合律）（交换律，结合律） p 0 （矛盾律）（矛盾律） 0 （零律）（零律）由最后一步可知，该式为矛盾式由最后一步可知
16、，该式为矛盾式. (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是它是
17、它的成假赋值的成假赋值.总结：总结：A A为矛盾式当且仅当为矛盾式当且仅当A A0 0 A A为重言式当且仅当为重言式当且仅当A A1 1说明：演算步骤不惟一说明：演算步骤不惟一, ,应尽量使演算短些应尽量使演算短些定义定义文字：命题变项及其否定统称为文字。文字：命题变项及其否定统称为文字。 如：如：p , q简单析取式：仅有有限个文字组成的析取式。简单析取式：仅有有限个文字组成的析取式。 如：如：p , q , p q , p q r简单合取式：仅有有限个文字组成的合取式。简单合取式：仅有有限个文字组成的合取式。 如：如：p , q , p q , p q r二、析取范式与合取范式二、析取范
18、式与合取范式 命题公式是千变万化的，这给研究命题演算带来困难，这命题公式是千变万化的，这给研究命题演算带来困难，这里我们研究如何由一个命题公式化归为一个标准形式的问题，里我们研究如何由一个命题公式化归为一个标准形式的问题，这样命题演算的研究问题就归结为对标准形式的研究问题，这这样命题演算的研究问题就归结为对标准形式的研究问题，这种标准形式就叫种标准形式就叫范式范式。 析取范式析取范式 它是这样一种标准形式，在此式内不出现联结词它是这样一种标准形式，在此式内不出现联结词及及，否定符号只出现在命题变元前。它是一个析取式，式，否定符号只出现在命题变元前。它是一个析取式，式中的每个析取项是个合取式，每
19、个合取式中只包含命题变元或中的每个析取项是个合取式，每个合取式中只包含命题变元或命题变元的否定。命题变元的否定。 例如例如 p (p q) ( (q r) 此式即具有析取范式之形式此式即具有析取范式之形式注意注意:一个公式的析取范式并不唯一，如一个公式的析取范式并不唯一，如p (r q),可以写成可以写成(p p )(r q) 合取范式合取范式 它是这样一种标准形式，在此式内不出现联结词它是这样一种标准形式，在此式内不出现联结词及及，否定符号只出现在命题变元前。它是一个合，否定符号只出现在命题变元前。它是一个合取式，式中的每个合取项是个析取式，每个析取式中取式，式中的每个合取项是个析取式，每个
20、析取式中只包含命题变元或命题变元的否定。只包含命题变元或命题变元的否定。 例如例如 p (pq) ( (q r) 此式即具有合取范式之形式此式即具有合取范式之形式注意注意:一个公式的合取范式并不唯一，一个公式的合取范式并不唯一， 如如 p ( (r q) 可以写成可以写成(p p) (r q) 定义：定义：析取范式：析取范式：由有限个简单合取式构成的析取式。由有限个简单合取式构成的析取式。 如：如：p q , (p q) (p q r)合取范式合取范式：由有限个简单析取式构成的合取式。：由有限个简单析取式构成的合取式。 如：如：p q ,（p q）（ p qr）范式范式：析取范式与合取范式统称
21、为范式。：析取范式与合取范式统称为范式。设设Ai(i=1,2,3,n)为简单合取式，则为简单合取式，则A=A1 A2 An 就是析取范式，就是析取范式，而而B=A1 A2 An 就是合取范式。就是合取范式。析取范式和合取范式有下列性质：析取范式和合取范式有下列性质： （1）一个析取范式是矛盾式）一个析取范式是矛盾式它的每个简单合它的每个简单合取式都是矛盾式。取式都是矛盾式。（2）一个合取范式是重言式）一个合取范式是重言式它的每个简单析它的每个简单析取式都是重言式。取式都是重言式。例例 求下列公式的析取范式与合取范式求下列公式的析取范式与合取范式(1) A=(pq)r解解 (pq)r ( pq)
22、r （消去（消去） pqr （结合律）（结合律） 这既是这既是A的析取范式（由的析取范式（由3个简单合取式组成的析取式），个简单合取式组成的析取式），又是又是A的合取范式（由一个简单析取式组成的合取式）的合取范式（由一个简单析取式组成的合取式）(2) B=(pq)r解解 (pq)r ( pq)r （消去第一个（消去第一个） ( pq) r （消去第二个（消去第二个） (p q) r （否定号内移（否定号内移德摩根律）德摩根律）这一步已为析取范式（两个简单合取式构成）这一步已为析取范式（两个简单合取式构成）继续：继续： (p q) r (p r) (q r) （ 对对 分配律）分配律）这一步得到
23、合取范式（由两个简单析取式构成）这一步得到合取范式（由两个简单析取式构成）求范式的具体步骤：求范式的具体步骤：（1）消去对）消去对 , ,来说冗余的联结词来说冗余的联结词 ，即，即 ， 。利用下列等值式：。利用下列等值式： A B ( A B) A B ( A B) (A B)（2）否定词的消去或内移。）否定词的消去或内移。 利用下列等值式：利用下列等值式： A B ( A B) ( A B) A B ( A B) A B（3）利用分配律：）利用分配律： C ( AB) （CA）（C B） C ( AB ) （CA）（C B）(3) 求求( ( p q)(p r)的析取范式。的析取范式。解：解
24、：( ( p q) (p r) ( (p q) ( p r) (p q) p) ) (p q) r) ) (p p)(q p) )(p r)(qr) ) ( (q p)( (p r)(q r) (4) 求求( (p q)(pr)的析取的析取/合取范式。合取范式。解解: (1) 求求析取范式析取范式 ( (p q) (p r) ( ( p q) ( p r ) p q ( p r ) (4) 求求( (p q)(pr)的析取的析取/合取范式。合取范式。解：解：(2) 求求合取取范式合取取范式 ( (p q) (p r) ( ( p q) ( p r ) ( p r ) ( ( p q) (p r
25、) p) ) q (p p) ( p r) ) q ( (p pq )( pr q ) (合取范式合取范式) 定义定义 在含有在含有n个命题变项的简单合取式个命题变项的简单合取式( (简单析取式简单析取式) )中，若中，若每个命题变项均以文字的形式在其中出现且仅出现一每个命题变项均以文字的形式在其中出现且仅出现一次，而且第次，而且第i（1 i n）个文字出现在左起第）个文字出现在左起第i位上，称位上，称这样的简单合取式（简单析取式）为这样的简单合取式（简单析取式）为 极小项（极大项）极小项（极大项）.由由p, q两个命题变项形成的极小项与极大项两个命题变项形成的极小项与极大项 公式公式 成真赋
26、值成真赋值名称名称 公式公式 成假赋值成假赋值名称名称 p q p q p q p q0 0 0 1 1 0 1 1 m0m1m2m3 p q p q p q p q 0 0 0 1 1 0 1 1 M0M1M2M3 极小项极小项 极大项极大项 由由p, q, r三个命题变项形成的极小项与极大项三个命题变项形成的极小项与极大项 极小项极小项 极大项极大项 公式公式 成真成真赋值赋值名称名称 公式公式 成假成假赋值赋值名称名称 p q r p q r p q r p q rp q rp q rp q rp q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1m0
27、m1m2m3m4m5m6m7p q r p q r p q r p q r p q r p q r p q r p q r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1M0M1M2M3M4M5M6M7 极小项与极大项关系极小项与极大项关系 设设mi和和Mi是命题变项是命题变项p1 ， p2 ， pn形成的形成的极小项和极大项，则极小项和极大项，则 mi Mi ， Mi mi定义定义设由设由n个命题变项构成的析（合）取范式中所个命题变项构成的析（合）取范式中所有的简单合（析）取式都是极小（大）项，有的简单合（析）取式都是极小（大）项，则称该析（合）取范式为主析
28、（合）取范式。则称该析（合）取范式为主析（合）取范式。由不同最小项所组成的析取式称为主析取范式由不同最小项所组成的析取式称为主析取范式由不同最大项所组成的合取式称为主合取范式由不同最大项所组成的合取式称为主合取范式 求求( ( p q) (p r)的主析取范式。的主析取范式。 ( ( p q) (p r) ( (q p) ( (p r)(q r) (析取范式析取范式) (pr)(q q)()( pq)(r r) ) ( qr) (p p ) ) ( (p qr) ( (p q r) ( pq r) ( pq r ) (主析取范式主析取范式) m2 m3m5 m7 用等值演算法求公式的主范式的步
29、骤：用等值演算法求公式的主范式的步骤： (1) 先求析取范式（合取范式）先求析取范式（合取范式） (2) 将不是极小项（极大项）的简单合取式将不是极小项（极大项）的简单合取式 （简单析取式）化成与之等值的若干个极小（简单析取式）化成与之等值的若干个极小 项的析取（极大项的合取），需要利用同一项的析取（极大项的合取），需要利用同一 律（零律）、排中律（矛盾律）、分配律、律（零律）、排中律（矛盾律）、分配律、 幂等律等幂等律等. (3) 极小项（极大项）用名称极小项（极大项）用名称mi（Mi）表示，）表示， 并按角标从小到大顺序排序并按角标从小到大顺序排序. 例例 求求( ( p q) (p r)
30、的主合取范式。的主合取范式。解法解法1： P q r p p q p r ( ( p q) (p r) 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 0 1 0 1 0 1 1 1 1 1 0 0 1 0 0 1 1 1 0 1 1 1解法解法2：( ( p q) (p r) ( (pq) ( p r) (合取范式合取范式) (p q) (r r ) ) ( p r) (q q ) ) (p q r ) ( (p q r ) )( pq r) ( ( p q r) ) ( (p q r ) ( (p q r )( ( pq r) ( ( p q r) (主合取范式主合取范式) M0M1M4 M6
