离散数学 - opencomcn

1、 第一章第一章 命题逻辑命题逻辑 这章是以“命题”为中心 主要讨论： 命题的表示、命题的演算 命题演算中的公式，及其应用 命题逻辑推理1-1. 命题与命题的真值 本节主要讨论三个问题： 命题的概念 命题的真值 原子命题与复合命题一. 命题的概念 statement命题命题 是一个能确定是真的或是假的判断。是一个能确定是真的或是假的判断。 （判断都是用陈述句表示）（判断都是用陈述句表示）例例1-1.1 判定下面这些句子哪些是命题。判定下面这些句子哪些是命题。 2是个素数。是个素数。 雪是黑色的。雪是黑色的。 2010年人类将到达火星。年人类将到达火星。 如果如果 ab且且bc，则，则ac 。(a

2、、b、c是确定实数是确定实数) x+yb、bc、ac) 构成的复合命题。构成的复合命题。1-2 联结词 connectives 复合命题的构成：是用复合命题的构成：是用“联结词联结词”将原将原子命题联结起来构成的。子命题联结起来构成的。 归纳自然语言中的联结词，定义了六个归纳自然语言中的联结词，定义了六个逻辑联结词，分别是：逻辑联结词，分别是： (1) 否定否定“ ” (2) 合取合取“” (5) 蕴涵蕴涵“” (6) 等价等价“”(3) 析取析取“” (4) 异或异或“ ”一. 否定“” negation表示：表示：“不成立不成立”，“不不”。用于：对一个命题用于：对一个命题p的否定，写成的

3、否定，写成 p，并，并读成读成“非非p”。 p的真值：与的真值：与p真值相反。真值相反。 例例1-2.1 p：2是素数。是素数。 p：2不是素数不是素数。p pt ff t二. 合取“”conjunction表示：表示：“并且并且”、“不但不但而且而且.”、“既既又又 .”、“尽管尽管还还 ”例例1-2.2 p：小王能唱歌。：小王能唱歌。 q：小王能跳舞。：小王能跳舞。pq：小王能歌善舞。：小王能歌善舞。 pq读成读成p合取合取q。pq的真值为的真值为真真，当且，当且 仅当仅当p和和q的真值均为的真值均为真真。p q pqf f ff t ft f ft t t三. 析取“”、异或“ ” 表示

4、表示“或者或者” “或者或者”有有二义性二义性，看下面两个例子：，看下面两个例子： 例例1-2.3. 灯泡灯泡或者或者线路有故障。线路有故障。 例例1-2.4. 第一节课上数学第一节课上数学或者或者上英语。上英语。例例3中的中的或者或者是是可兼取的或可兼取的或。即。即析取析取“”例例4中的中的或者或者是是不可兼取的或不可兼取的或，也称之为，也称之为异异或或、排斥或排斥或。即。即“ ”。1. 1. 析取析取“” ” disjunctiondisjunctionp：灯泡有故障。：灯泡有故障。 q：线路有故障。：线路有故障。例例3中的复合命题可中的复合命题可 表示为：表示为：pq，读，读 成成p析取

5、析取q。pq的真值为的真值为f，当，当 且仅当且仅当p与与q均为均为f。p q pqf f ff t tt f tt t t2. 2. 异或异或“ “ ” ” exclusive orexclusive orp：第一节上数学：第一节上数学。q：第一节上英语。：第一节上英语。例例4中的复合命题中的复合命题 f f ff t tt f tt t fp q p q当且仅当当且仅当p与与q的的真值相同真值相同。p q的真值为的真值为f，可写成可写成p q，读，读成成p异或异或q。3.“3.“异或异或”的另一种表示的另一种表示 异或异或是表示两个命题是表示两个命题不可能同时都成立。不可能同时都成立。 命

6、题命题“第一节课上数学第一节课上数学或者或者上英语。上英语。”可以解可以解释为：释为： “第一节课上数学而没有上英语第一节课上数学而没有上英语或者或者第一节课第一节课上英语而没有上数学。上英语而没有上数学。” 于是有于是有 实际应用中必须注意实际应用中必须注意“或者或者”的二义性。的二义性。p q 与与 (p q)(q p ) 是一样的。是一样的。四.条件(蕴涵)“” conditional (implication)implication) 表示表示“如果如果 ，则，则 ”，“只要只要 ，就，就 ”, “只有只有 , 才才” , “ . , 仅当仅当 ” 例例1-2.5： p表示：缺少水分。

7、表示：缺少水分。 q表示：植物会死亡。表示：植物会死亡。 pq：如果：如果缺少水分缺少水分，植物就会死亡植物就会死亡。 pq：也称之为蕴涵式，读成：也称之为蕴涵式，读成“p蕴涵蕴涵 q”，“如果如果p则则q”。也说成。也说成p是是pq 的的 前件，前件，q是是pq的后件。还可以说的后件。还可以说p是是q的的 充分条件充分条件，q是是p的的必要条件必要条件。 关于充分条件和必要条件的说明：关于充分条件和必要条件的说明： 充分条件充分条件：就是只要条件成立，结论就成立，：就是只要条件成立，结论就成立，则该条件就是则该条件就是充分条件充分条件。 上例中，上例中，“缺少水分缺少水分”就是就是“植物会死

8、亡植物会死亡”的充分条件。在自然语言中表示充分条件的词的充分条件。在自然语言中表示充分条件的词有有 ： 如果如果 则则 ，只要，只要 就就，若，若则则 必要条件必要条件：就是如果该条件不成立，那么结论：就是如果该条件不成立，那么结论就不成立就不成立, 则该条件就是则该条件就是必要条件必要条件。 上例中，上例中，“植物死亡植物死亡”就是就是“缺少水分缺少水分”的必的必要条件要条件(植物未死亡，一定不缺少水分植物未死亡，一定不缺少水分)。 在自然语言中表示必要条件的词有在自然语言中表示必要条件的词有 ： 只有只有 才才 ； 仅当仅当， ; , 仅当仅当。 pq的真值：的真值： pq的真值为假，当且

9、仅当的真值为假，当且仅当p为真，为真，q为为假。假。注意注意：当前件：当前件p为假时，为假时， pq为为t。 p q pq小王借钱不还小王借钱不还 我替他还我替他还 （我给小王担保）（我给小王担保） f f t f t t t f f t t t 举例：举例：令：令：p：天气好。：天气好。 q：我去公园。：我去公园。1.如果天气好，我就去公园。如果天气好，我就去公园。2.只要天气好，我就去公园。只要天气好，我就去公园。3.天气好，我就去公园。天气好，我就去公园。4.仅当天气好，我才去公园。仅当天气好，我才去公园。5.只有天气好，我才去公园。只有天气好，我才去公园。6.我去公园，仅当天气好。我去

10、公园，仅当天气好。pqqp可见可见“”既表示充分条件（即前件是后件的充分既表示充分条件（即前件是后件的充分条件）；也表示必要条件（即后件是前件的必要条条件）；也表示必要条件（即后件是前件的必要条件）。这一点要特别注意件）。这一点要特别注意!它决定了哪个作为前它决定了哪个作为前件，哪个作为后件。件，哪个作为后件。五.双条件 (等价）“” “ ” biconditional (equivalence) 表示表示“当且仅当当且仅当”、“充分且必要充分且必要” 例例1-2.6： p：abc是等边三角形。是等边三角形。 q：abc是等角三角形。是等角三角形。 pq ：abc是等边三角形是等边三角形当且仅

11、当当且仅当 它它是等角三角形。是等角三角形。 p q pq f f t f t f t f f t t t pq的真值：的真值： pq的真值为真，当且仅当的真值为真，当且仅当p与与q的真的真值相同。值相同。本节小结：本节小结： 要熟练掌握这六个联结词在自然语言中要熟练掌握这六个联结词在自然语言中所表示的含义以及它们的真值表的定义。所表示的含义以及它们的真值表的定义。 p q pq pq pq pq f f f f f t t f t f t t t f t f f t t f ft t t t f t tp q 特别要注意特别要注意“或者或者”的二义性，即要区的二义性，即要区分给定的分给定的“

12、或或”是是“可兼取的或可兼取的或”还是还是“不可兼取的或不可兼取的或”。 特别要注意特别要注意“”的用法，它既表示的用法，它既表示“充分条件充分条件”也表示也表示“必要条件必要条件”，即要，即要弄清哪个作为前件，哪个作为后件。弄清哪个作为前件，哪个作为后件。 下面做练习下面做练习 练习练习：填空：填空 已知已知pq为为t，则，则p为为( )，q为为( )。 已知已知pq为为f，则，则p为为( )，q为为( )。 已知已知p为为f，则，则pq为为( )。 已知已知p为为t，则，则pq为为( )。 已知已知pq为为t，且，且p为为f ，则，则q为为( )。 已知已知pq为为f，则，则p为为( )，

13、q为为( )。 已知已知p为为f，则，则pq为为( )。 已知已知q为为t，则，则pq为为( )。 已知已知 pq为为f，则，则p为为( )， q为为( )。 已知已知p为为t， pq为为t，则，则q为为( )。 已知已知 q为为t, pq为为t，则，则p为为( )。 已知已知pq为为t，p为为t , 则则q为为( )。 已知已知pq为为f，p为为t , 则则q为为( )。 pp 的真值为的真值为( )。 pp 的真值的真值为为( )。1-3 命题公式及命题符号化一一.常值命题与命题变元常值命题与命题变元 常值命题常值命题：即是我们前面所说的命题。它是有即是我们前面所说的命题。它是有具体含义具

14、体含义 (真值真值)的。例如：的。例如：“3是素数。是素数。”就是就是常值命题。常值命题。 命题变元命题变元：用大写的英字母如用大写的英字母如p、q等表示任何等表示任何命题。称这些字母为命题变元。命题。称这些字母为命题变元。 对命题变元作对命题变元作指派指派(给命题变元一个给命题变元一个解释解释)：将：将一个常值命题赋予命题变元的过程，或者是直接一个常值命题赋予命题变元的过程，或者是直接赋给命题变元真值赋给命题变元真值“t”或或“f”的过程。的过程。 注意注意：命题变元本身不是命题，只有给它一个：命题变元本身不是命题，只有给它一个解释，才变成命题。解释，才变成命题。二.合式公式 ( wff )

15、 (well formed formulas)1.定义：定义： 单个命题变元是个合式公式。单个命题变元是个合式公式。 若若a是合式公式，则是合式公式，则 a是合式公式。是合式公式。 若若a和和b是是合式公式，则合式公式，则(ab)， (ab)， (ab)和和(ab)都是合式公式。都是合式公式。 当且仅当有限次地应用当且仅当有限次地应用，所得到的所得到的 含有命题变元、联结词和括号的符号串是含有命题变元、联结词和括号的符号串是合合 式公式式公式。 注意这个定义是递归的。注意这个定义是递归的。(1)是递归的基础，是递归的基础，由由(1)开始，使用规则开始，使用规则(2)(3) ，可以得到任意的合，

16、可以得到任意的合式公式。式公式。 这里所谓的合式公式可以解释为合法的这里所谓的合式公式可以解释为合法的命题公式之意，也称之为命题公式之意，也称之为命题公式命题公式，有时，有时也简称也简称公式公式。 下面的式子不是合式公式：下面的式子不是合式公式： pq， pr， pqr 下面的式子才是合式公式：下面的式子才是合式公式： (pq)，( pr)，(pq)r) 按照按照合式公式定义最外层括号必须写。合式公式定义最外层括号必须写。 约定约定：为方便，最外层括号可以不写。：为方便，最外层括号可以不写。 上面的合式公式可以写成：上面的合式公式可以写成： pq， pr，(pq)r2. 命题公式的命题公式的真

17、值表真值表 (truth table) 一个命题公式不是复合命题，所以它没一个命题公式不是复合命题，所以它没有真值，但是给其中的所有命题变元作指有真值，但是给其中的所有命题变元作指派以后它就有了真值。可以以表的形式反派以后它就有了真值。可以以表的形式反应它的真值情况，例如命题应它的真值情况，例如命题 公式公式 ( pq)q 的真值表如下所示：的真值表如下所示：p q p pq ( pq)qf f t f f f t t t tt f f t tt t f t t 由于对每个命题变元可以有两个真值由于对每个命题变元可以有两个真值(t,f)被指被指派，所以有派，所以有n个命题变元的命题公式个命题变

18、元的命题公式 a(p1,p2,pn) 的真值表有的真值表有2n行。行。 为为有序地有序地列出列出a(p1,p2,pn)的真值表，可将的真值表，可将f看看成成0、t看成看成1，按，按二进制数次序列表。二进制数次序列表。 如如a(p,q)的真值表可按照如下次序指派：的真值表可按照如下次序指派： 00(ff)，01(ft)，10(tf)，11(tt) 如如a(p,q,r)的真值表可按照如下次序指派：的真值表可按照如下次序指派： 0 1 2 3 4 5 6 7000 001 010 011 100 101 110 111fff fft ftf ftt tff tft ttf ttt a(p1,p2,p

19、n)的真值表，按照的真值表，按照二进制数二进制数000 0001 00010 1 10 111 0 1 2 2n -2 2n -1 即按照十进制的即按照十进制的0，1，2，. ，2n -1的次序的次序进行指派列真值表。进行指派列真值表。 例如列出例如列出p(qr)的真值表的真值表 p q r qr p(qr)000 f f f001 f f t010 f t f011 f t t100 t f f101 t f t110 t t f111 t t tttttftttttttfftt三三.命题符号化命题符号化 所谓命题符号化，就是用命题公式的符所谓命题符号化，就是用命题公式的符号串来表示给定的命

20、题。号串来表示给定的命题。 命题符号化的方法命题符号化的方法 1.首先要明确给定命题的含义。首先要明确给定命题的含义。 2.对于复合命题，找联结词，用联结词对于复合命题，找联结词，用联结词 断句，分解出各个原子命题。断句，分解出各个原子命题。 3.设原子命题符号，并用逻辑联结词联设原子命题符号，并用逻辑联结词联结原子命题符号，构成给定命题的符号表结原子命题符号，构成给定命题的符号表达式。达式。例例1.说离散数学无用且枯燥无味是不对的。说离散数学无用且枯燥无味是不对的。 p：离散数学是有用的。：离散数学是有用的。 q：离散数学是枯燥无味的。：离散数学是枯燥无味的。 该命题可写成：该命题可写成：

21、( pq)例例2.如果小张与小王都不去，则小李去。如果小张与小王都不去，则小李去。 p：小张去。：小张去。 q：小王去。：小王去。 r：小李去。：小李去。 该命题可写成：该命题可写成： ( p q)r 如果小张与小王不都去，则小李去。如果小张与小王不都去，则小李去。 该命题可写成：该命题可写成： (pq)r 也可以写成：也可以写成： ( p q)r例例3. 仅当仅当天不下雨且我有时间，才上街。天不下雨且我有时间，才上街。 p：天下雨。：天下雨。q：我有时间。：我有时间。r：我上街。：我上街。 分析分析：由于：由于“仅当仅当”是表示是表示“必要条件必要条件”的，既的，既“天不下雨且我有时间天不下

22、雨且我有时间”，是，是“我上我上街街”的必要条件。所以的必要条件。所以 该命题可写成：该命题可写成： r( pq) 例例4.人不犯我，我不犯人；人若犯我，我人不犯我，我不犯人；人若犯我，我必犯人。必犯人。 p：人犯我。：人犯我。q：我犯人。：我犯人。 该命题可写成：该命题可写成：( pq)(pq) p是是q的充分条件的充分条件p是是q的必要条件的必要条件p是是q的充分且必要条件的充分且必要条件或写成： pq例例5 .若天不下雨，我就上街；否则在家。若天不下雨，我就上街；否则在家。 p：天下雨。天下雨。q ：我上街。：我上街。r：我在家。：我在家。 该命题可写成：该命题可写成： ( pq)(p

23、r). 注意注意：中间的联结词一定是：中间的联结词一定是“”，而不是，而不是 因为原命题表示：因为原命题表示：“天不下雨时我做什么天不下雨时我做什么，天天下下雨我又做什么雨我又做什么”的的两种作法，两种作法，其中有一种作法是假其中有一种作法是假的，则我说的就是假话，所以中间的联结词一定是的，则我说的就是假话，所以中间的联结词一定是“ ”。 如果写成如果写成 ( pq)(p r)，就表明，就表明两种作法两种作法都都是假的时候，我说的才是假话。这显然不对是假的时候，我说的才是假话。这显然不对。“”，也不是，也不是“ ”。 实际上实际上, 公式公式( pq)(p r) 的真值总是的真值总是真真的。的

24、。 因为当因为当p为为t时，时， ( pq)为为t， 当当p为为f时，时， (pr)为为t，所以所以( pq)(p r) 的真值总是真的。而例的真值总是真的。而例5中命中命题的真值不是总是真的。题的真值不是总是真的。此时此话是假话，虽然此时此话是假话，虽然( pq) 是是f，而，而(p r)的真值的真值是是“t”。于是。于是若写成若写成( pq) (p r)：则表示两种作法一个是：则表示两种作法一个是表达式表达式 ( pq) (p r) 的真值却是的真值却是“t”。所以这个表达式也不对所以这个表达式也不对。真真 , 另一个是假时，才是真的。另一个是假时，才是真的。例如例如当当p为为f，q为为f

25、时，即天没下雨而我没上街。时，即天没下雨而我没上街。 本节重点掌握：本节重点掌握： 列命题公式的真值表列命题公式的真值表 将给定命题符号化将给定命题符号化 作业题：作业题： 第第8页：（页：（3） 第第12页：（页：（5）、（）、（7） 第第17页：（页：（1）a)、d)1-4 重言式与重言蕴涵式 tautology, tautological implications一一.重言式重言式(永真式永真式)与矛盾式与矛盾式(永假式永假式)1.例子例子 p pp pp f t f t t f 可见不论可见不论p取什么真值取什么真值 pp 的真值总是为真，的真值总是为真， pp的真值总是为假。故称的真

26、值总是为假。故称 pp为重言式为重言式(永永真式真式)，称，称 pp为矛盾式为矛盾式(永假式永假式)。2 .重言式重言式(矛盾式矛盾式)定义定义 a(p1,p2,pn) 是含有命题变元是含有命题变元p1,p2, pn的的命题公式，如不论对命题公式，如不论对p1, p2 , , pn作任何指派作任何指派,都使得都使得a(p1,p2, pn) 为为真真(假假)，则称之为，则称之为重言重言式式(矛盾式矛盾式), 也称之为也称之为永真式永真式 (永假式永假式)。3.重言式的证明方法重言式的证明方法 方法方法1：列真值表。：列真值表。 方法方法2：公式的等价变换，化简成：公式的等价变换，化简成“t”。

27、方法方法3：用公式的主析取范式。：用公式的主析取范式。 其中方法其中方法2 和方法和方法3 我们在以后讨论。我们在以后讨论。方法方法1. 列真值表。列真值表。 例如，证明例如，证明 (p(pq)q 为重言式。为重言式。 p q pq p(pq) (p(pq)q f f t f t f t t f t t f f f t t t t t t 永真式的真值表的最后一列全是永真式的真值表的最后一列全是“t”。4. 永真式的性质永真式的性质 1) 如果如果a是永真式，则是永真式，则 a是永假式。是永假式。 2) 如果如果a，b是永真式，则是永真式，则(ab)、(ab)、(ab)和和(ab)也都是永真式

28、。也都是永真式。 3) 如果如果a是永真式，则是永真式，则a的置换例式也是永真式。的置换例式也是永真式。 置换例式置换例式： a(p1,p2,pn) 是含有命题变元是含有命题变元p1,p2, pn的命题公式，如果用合式公式的命题公式，如果用合式公式x替换某替换某个个pi(如果如果pi在在a(p1,p2,pn) 中多处出现，则各处中多处出现，则各处均用均用x替换替换 )，其余变元不变，替换后得到新的公，其余变元不变，替换后得到新的公式式b，则称，则称b是是a(p1,p2,pn) 的置换例式。的置换例式。 例如例如： 公式公式a：p( p(pq)r) 用用(de)替换替换a中中p得到得到a的置换例

29、式的置换例式 b： (de)( (de)(de)q)r) 如果如果a是永真式，例如是永真式，例如a为为 pp，用用 (de)替换替换a中中p，得到，得到a的置换例式的置换例式 b： (de)(de) ， 显然显然b也是永真式。也是永真式。 如果可以断定给定公式是某个如果可以断定给定公式是某个永真式的置永真式的置换例式的话，则这个公式也是永真式。换例式的话，则这个公式也是永真式。二二.重言重言( (永真永真) )蕴涵式蕴涵式 有些重言有些重言( (永真永真) )式，如式，如(p(pq)q，公式中间是公式中间是“”联结词，是很重要的，联结词，是很重要的，称之为称之为重言蕴涵式。重言蕴涵式。1.定义

30、定义：如果公式：如果公式ab是是重言式，则称重言式，则称a a重重言言( (永真永真) )蕴涵蕴涵 b b，记作，记作ab。 上式可以写成上式可以写成 (p(pq)q 注意符号注意符号“”不是联结词，它是表示公不是联结词，它是表示公式间的式间的“永真蕴涵永真蕴涵”关系，也可以看成是关系，也可以看成是“推导推导”关系。即关系。即ab可以理解成由可以理解成由a a可推可推出出b b，即，即由由a为真，可以推出为真，可以推出b也为真也为真。 2.重言重言( (永真永真) )蕴涵式证明方法蕴涵式证明方法 方法方法1 1. .列真值表。列真值表。( (即列永真式的真值表即列永真式的真值表) )这里就不再

31、举例了。这里就不再举例了。 下面讨论另外两种方法。下面讨论另外两种方法。a b aa b a bf f tf t tt f ft t t先看一看先看一看a ab b的真的真值表，如果值表，如果a ab b为为永真式，则真值表永真式，则真值表的第三组指派不会的第三组指派不会出现。于是有下面出现。于是有下面两种证明方法。两种证明方法。方法方法2.假设前件为真，推出后件也为真假设前件为真，推出后件也为真。例如求证：例如求证： (ab)c) d( cd) a b证明证明:设前件设前件(ab)c) d( cd) 为为 真。则真。则(ab)c)、 d、( cd)均真，均真， d为为t，则，则d为为f 得得

32、c为为f得得a ab b为为f如果如果a为为f，则，则 a为为t，所以，所以 a b为为t。 如果如果b为为f，则，则 b为为t，所以，所以 a b 为为t。 (ab)c) d( cd) a b(ab)c为为t cd为为t方法方法3.假设后件为假，推出前件也为假假设后件为假，推出前件也为假。例如求证：例如求证： (ab)c) d( cd) a b证明证明:假设后件假设后件 a b为为f,则则a与与b均为均为t。1.如如c为为f，则，则(ab)c为为f，所以前件，所以前件 (ab)c) d( cd) 为为f2.如如c为为t，则，则若若d为为t，则，则 d为为f，所以，所以 前件前件(ab)c)

33、d( cd) 为假为假 若若d为为f，则，则 cd为为f，所以，所以 前件前件(ab)c) d( cd) 为假。为假。(ab)c) d( cd) a b3.重要的重言蕴涵式(如教材第43页所示) i1.pqp i2. pqq i3. ppq i4. qpq i5. ppq i6. qpq i7. (pq)p i8. (pq)q i9. p,q pq i10. p(pq)q i11. p(pq)q i12. q(pq)p i13. (pq)(qr)pr i14. (pq)(pr)(qr)r i15. ab (ac)(bc) i16. ab (ac)(bc) 上述公式的证明都比较简单，可以用假设前

34、件为上述公式的证明都比较简单，可以用假设前件为t，推出后件也为，推出后件也为t的方法证明。的方法证明。4. 性质性质 1) 有自反性：对任何命题公式有自反性：对任何命题公式a，有，有aa 2) 有传递性：若有传递性：若ab且且bc，则，则ac 3) 有反对称性：若有反对称性：若ab且且ba，则，则ab 符号符号“”表示表示“等价等价”。本节重点掌握本节重点掌握：永真式及永真蕴涵式的定义、证：永真式及永真蕴涵式的定义、证明方法、以及常用的公式。明方法、以及常用的公式。 作业：第作业：第23页页: (2) b) 、(6)、(8) e) 1-5 等价公式 equivalent formulas1.

35、例子例子 看下面三个公式的真值表看下面三个公式的真值表 p q pq pq qp f f t t t f t t t t t f f f f t t t t t 从真值表可以看出，不论对从真值表可以看出，不论对p、q作何指作何指派，都使得派，都使得pq、 pq和和 qp的真的真值相同，表明它们之间彼此等价。值相同，表明它们之间彼此等价。2. 定义定义：a、b是含有命题变元是含有命题变元p1,p2, pn的命题公式，如不论对的命题公式，如不论对p1, p2 , , pn作任何作任何指派，都使得指派，都使得a和和b的真值相同，则称之为的真值相同，则称之为a a与与b b等价等价，记作，记作ab。

36、显然显然 pqpqqp3. 重要的等价公式重要的等价公式 对合律对合律 pp 幂等律幂等律 ppp ppp 结合律结合律 p(qr)(pq)r p(qr)(pq)r 交换律交换律 pqqp pqqp分配律分配律 p(qr)(pq)(pr) p(qr)(pq)(pr) 吸收律吸收律 p(pq)p p(pq)p底底-摩根定律摩根定律 (pq)p q (pq)p q 同一律同一律 pfp ptp 零律零律 ptt pff 互补律互补律 p pt p pf pqpq pqqp pq (pq)(qp) pq ( pq)(p q) pq (pq)( p q ) 为便于记忆，将等价公式为便于记忆，将等价公式

37、(前前10个个)与集合论的公式比较，与集合论的公式比较，请看集合公式：请看集合公式： 对合律对合律 aa a表示表示a的绝对补集的绝对补集 幂等律幂等律 aaa aaa 结合律结合律 a(bc)(ab)c a(bc)(ab)c 交换律交换律 abba abba 分配律分配律 a(bc)(ab)(ac) a(bc)(ab)(ac) 吸收律吸收律 a(ab)a a(ab)a 底底-摩根定律摩根定律 (ab)ab (ab)ab 同一律同一律 aa aea e表示全集表示全集 零律零律 aee a 互补律互补律 aae aa4. 等价公式的证明方法等价公式的证明方法 方法方法1：用列真值表。（不再举例

38、）：用列真值表。（不再举例） 方法方法2：用公式的等价变换：用公式的等价变换.(用置换定律用置换定律)置换定律置换定律:a a是一个命题公式，是一个命题公式，x x是是a a中的一中的一部分且也是合式公式部分且也是合式公式(a(a的子公式的子公式) )，如果，如果x xy y，用，用y y代替代替a a中的中的x x得到公式得到公式b b，则，则a ab b。 应用置换定律以及前面列出的等价公式应用置换定律以及前面列出的等价公式可以对给定公式进行等价变换。可以对给定公式进行等价变换。例题例题1. 求证吸收律求证吸收律 p(pq)p证明证明 p(pq) (pf)(pq) (同一律同一律) p(f

39、q) (分配律分配律) pf (零律零律) p (同一律同一律)例题例题2. 求证求证 ( pq)(pq) p证明证明 ( pq)(pq) ( pq)(pq) (公式公式e16) 公式公式e16 ： pqpq ( p q)(pq) (摩根定律摩根定律) (p q)(pq) (对合律对合律)p( qq) (分配律分配律) pt (互补律互补律) p (同一律同一律)例题例题3.化简化简 (pq)( p( pq)解：解： 原公式原公式(pq)( p p)q) (e16,结合结合)(pq)( pq) (对合律，幂等律对合律，幂等律)(pq)(q p) (交换律交换律)(pq)q) p (结合律结合律

40、)q p (吸收律吸收律) 吸收律吸收律 p(pq)p p(pq)p5. 性质性质 1) 有自反性：任何命题公式有自反性：任何命题公式a，有，有aa。 2) 有对称性：若有对称性：若ab，则，则ba 3) 有传递性：若有传递性：若ab且且bc，则，则ac 4) 如果如果a(p1,p2,pn)b(p1,p2,pn)，则，则 a( p1, p2, pn)b( p1, p2, pn) 例例 a(p,q)pq b(p,q)pq于是有于是有 a(p,q)b(p,q) a( p, q)p q b( p, q)p q可见可见 a( p, q)b( p, q)6.等价公式的对偶性等价公式的对偶性 (duali

41、ty) 从前面列出的等价公式看出，有很多是从前面列出的等价公式看出，有很多是成对出现的。这就是等价公式的对偶性。成对出现的。这就是等价公式的对偶性。 对偶式对偶式：在一个只含有联结词：在一个只含有联结词 、的公式的公式a中，将中，将换成换成，换成换成，t换成换成f，f换成换成t，其余部分不变，得到另，其余部分不变，得到另一个公式一个公式a*，称，称a与与a*互为对偶式。互为对偶式。 例如例如: a a* p p qr qr (pt) q (pf) q 用对偶式求公式的否定用对偶式求公式的否定 定理定理1-5.1 令令a(p1,p2,pn)是一个只含有是一个只含有联结词联结词 、的命题公式，则的

42、命题公式，则 a(p1,p2,pn)a*( p1, p2, pn) 此定理可以反复地使用底此定理可以反复地使用底-摩根定律得以摩根定律得以证明。证明。 下面我们下面我们验证验证一下。一下。 令令 a(p,q)pq a*(p,q)pq a(p,q)(pq) a*( p, q)p q 可见可见 a(p,q)a*( p, q) 推论推论:a( p1, p2, pn)a*(p1,p2,pn)例如例如，利用上述求公式的否定公式求，利用上述求公式的否定公式求 (pq)(p q)r) ( p q)( pq) r对偶原理对偶原理(定理定理1-5.2)： 令令a(p1,p2,pn) 、b(p1,p2,pn)是只

43、含有是只含有联结词联结词 、的命题公式，则如果的命题公式，则如果 a(p1,p2,pn)b(p1,p2,pn) 则则 a*(p1,p2,pn)b*(p1,p2, pn) 证明证明：因为：因为 a(p1,p2,pn)b(p1,p2,pn) 故故 a( p1, p2, pn)b( p1, p2, pn) 而而 a( p1, p2, pn)a*(p1,p2,pn) b( p1, p2, pn)b*(p1,p2,pn)故故 a*(p1,p2,pn) b*(p1,p2,pn)所以所以 a*(p1,p2,pn)b*(p1, p2, pn)下面我们验证一下对偶原理：下面我们验证一下对偶原理： p(qr)(p

44、q)(pr) a b p(qr)(pq)(pr) a* b* pt t a b pf f a* b*本节要求本节要求掌握等价公式的证明方法及记忆公式掌握等价公式的证明方法及记忆公式。作业：作业：第第19页页 (7) f) g) , (8) c)1-6.范式 normal form 范式就是命题公式形式的规范形式。这里范式就是命题公式形式的规范形式。这里约定在范式中约定在范式中 只含有联结词只含有联结词 、和和。一一.析取范式与合取范式析取范式与合取范式1.合取式与析取式合取式与析取式 合取式合取式：是用：是用“”联结命题变元或变元的联结命题变元或变元的否定构成的式子。否定构成的式子。 如如 p

45、 、 p 、p q、p q r 析取式析取式：是用：是用“” 联结命题变元或变元联结命题变元或变元的否定构成的式子。的否定构成的式子。 如如 p 、 p 、p q、p q r注注: ppp ppp p是合是合(析析)取式取式.2.析取范式析取范式 公式公式a如果写成如下形式：如果写成如下形式： a1a2.an (n1) 其中每个其中每个ai (i=1,2,n)是合取式，称之为是合取式，称之为a的的析取范式析取范式。 3.合取范式合取范式 公式公式a如果写成如下形式：如果写成如下形式： a1a2.an (n1) 其中每个其中每个ai (i=1,2,n)是析取式，称之为是析取式，称之为a的的合取范

46、式合取范式。 例如例如，pq 的的析取范式与合取范式：析取范式与合取范式： pq (pq)( p q)-析取范式析取范式 pq ( pq)(p q)-合取范式合取范式4.析取范式与合取范式的写法析取范式与合取范式的写法 先用相应的公式去掉先用相应的公式去掉和和。 公式公式e16 pqpq 公式公式e21 pq (pq)( p q) 公式公式e20 pq (pq)(qp) 再用再用e16 pq ( pq)(p q) 用公式的否定公式或摩根定律将用公式的否定公式或摩根定律将 后移到命题后移到命题变元之前。变元之前。 a(p1,p2,pn)a*( p1, p2, pn) 底底-摩根定律摩根定律 (p

47、q)p q (pq)p q 用分配律、幂等律等公式进行整理，使之成用分配律、幂等律等公式进行整理，使之成为所要求的形式。为所要求的形式。 例如例如求求(p(pq)r的的析取范式与合取范式析取范式与合取范式 (p(pq)r ( pq)(p q)r 去去 (p q)( pq)r 后移后移 -析取范式析取范式 (p(pq)r(pq)( p q)r 去去 ( p q)(pq)r 后移后移( p qr)(pqr) 分配律分配律 -合取范式合取范式二二.主析取范式与主主析取范式与主合取范式合取范式 一个公式的一个公式的析取范式与合取范式的形式是不唯析取范式与合取范式的形式是不唯一的。下面定义形式唯一的一的

48、。下面定义形式唯一的主析取范式与主主析取范式与主合取合取范式。范式。主析取范式主析取范式 1.小项小项 minterms 定义定义：在一个有：在一个有n个命题变元的合取式中，个命题变元的合取式中，每个变元必出现且仅出现一次，称这个合取式是每个变元必出现且仅出现一次，称这个合取式是个个小项小项。 例如例如，有两个变元的小项：，有两个变元的小项： pq、p q、 pq、 p q 小项的性质小项的性质 m3 m2 m1 m0 p q pq p q pq p q 00 f f f f f t 01 f t f f t f 10 t f f t f f 11 t t t f f f a).有有n个变元，

49、则有个变元，则有2n个小项。个小项。 b).每一组指派有且只有一个小项为每一组指派有且只有一个小项为t。为了记忆方便，可将各组指派对应的为为了记忆方便，可将各组指派对应的为t的小项的小项分别记作分别记作m0,m1,m2,m2n-1 上例中上例中 m0 p q m1 pq m2p q m3pq2.2.主析取范式定义主析取范式定义 析取范式析取范式 a1a2.an, , 其中每个其中每个ai (i=1,2,n)都是小项，称之为都是小项，称之为主析取范式主析取范式。3.3.主析取范式的写法主析取范式的写法 方法方法：列真值表列真值表 列出给定公式的真值表。列出给定公式的真值表。 找出真值表中每个找出

50、真值表中每个“t”对应的小项。对应的小项。 根据一组指派写对应的为根据一组指派写对应的为“t”的小项：的小项： 如变元如变元p被指派为被指派为t，p在小项中以在小项中以p形式出现；形式出现； 如变元如变元p被指派为被指派为f，p在小项中以在小项中以 p形式出现。形式出现。 (要保证该小项为要保证该小项为t)。 用用“”联结上述小项，即可。联结上述小项，即可。例如求例如求 pq和和p pq的的主析取范式主析取范式 p q pq p pq f f t t f t t f t f f f t t t t pq m0m1m3 ( p q)( pq)(pq) p pqm0m3 ( p q)(pq)思考题

51、思考题:永真式的永真式的主析取范式是什么样主析取范式是什么样 ？方法方法：用公式的等价变换：用公式的等价变换 先写出给定公式的析取范式先写出给定公式的析取范式 a1a2.an 。 为使每个为使每个ai都变成小项，对缺少变元的都变成小项，对缺少变元的ai补全变元，比如缺变元补全变元，比如缺变元r，就用，就用联结永真联结永真式式(r r)形式补形式补r。 用分配律、幂等律等公式加以整理。用分配律、幂等律等公式加以整理。 pqpq( p(q q)(p p) q)( pq)( p q)(pq)( pq)( pq)( p q)(pq)主主合取范式合取范式1.大项大项 maxterms定义定义:在有在有n

52、个命题变元的析取式中，每个命题变元的析取式中，每个变元必出现且仅出现一次个变元必出现且仅出现一次,称之为称之为大项大项。 例如，有两个变元的大项及其真值表：例如，有两个变元的大项及其真值表： m0 m1 m2 m3 p q pq p q pq p q f f f t t t f t t f t t t f t t f t t t t t t f大项的性质大项的性质 a).有有n个变元，则有个变元，则有2n个大项。个大项。 b).每一组指派有且只有一个大项为每一组指派有且只有一个大项为f。 为了记忆方便，可将各组指派对应的为为了记忆方便，可将各组指派对应的为f 的大项分别记作的大项分别记作m0,

53、m1,m2,m2n-1 。 上例中上例中 m0 pq m1 p q m2 pq m3 p q 2.主合取范式定义主合取范式定义 合合取范式取范式 a1a2. an, , 其中每个其中每个ai (i=1,2,n)都是大项，称之为都是大项，称之为主合取范式主合取范式。3.主合取范式的写法主合取范式的写法 方法方法：列真值表：列真值表 列出给定公式的真值表。列出给定公式的真值表。 找出真值表中每个找出真值表中每个“f”对应的大项。对应的大项。 根据一组指派写对应的为根据一组指派写对应的为“f”的大项：的大项： 如变元如变元p被指派为被指派为f，p在大项中以在大项中以p形式出现；形式出现； 如变元如变

54、元p被指派为被指派为t，p在大项中以在大项中以 p形式出现。形式出现。 (确保该大项为确保该大项为f)。 用用“”联结上述大项，即可。联结上述大项，即可。例如求例如求 pq和和p pq的的主合取范式主合取范式 p q pq p pq f f t t f t t f t f f f t t t t pq m2 pq p pq m1m2 (p q )( pq)课堂练习课堂练习：1.已知已知a(p,q,r)的真值表如图：的真值表如图：求它的主析取求它的主析取和主合取范式。和主合取范式。2.已知已知a(p,q,r)的主析取范式中含有小项的主析取范式中含有小项m1, m3, m5, m7 求它的主合取范

55、式。求它的主合取范式。3.已知已知a(p1,p2,pn)的主合取范式中含有的主合取范式中含有k个大个大项，问它的主析取范式中有多少个小项？项，问它的主析取范式中有多少个小项？p q r a(p,q,r)f f f tf f t ff t f ff t t tt f f tt f t ft t f tt t t t练习答案：练习答案：1.a(p,q,r)的主析取范式的主析取范式:a(p,q,r) m0m3m4m6m7 ( p q r)( pqr)(p q r)(pq r)(pq r)a(p,q,r)的的主合取范式：主合取范式：a(p,q,r) m1m2m5 (pq r)(p qr)( pq r)

56、 2. a(p,q,r) m0m2m4 m6 (pqr)(p qr)( pqr) ( p qr)3. a(p1,p2,pn)的主析取范式中含有的主析取范式中含有2n-k个小项个小项.方法方法：用公式的等价变换：用公式的等价变换先写出给定公式的合取范式先写出给定公式的合取范式 a1a2.an 。为使每个为使每个ai变成大项，对缺少变元的析取变成大项，对缺少变元的析取式式ai补全变元，比如缺变元补全变元，比如缺变元r，就用，就用联结联结永假式永假式(r r)形式补形式补r。用分配律、幂等律等公式加以整理。用分配律、幂等律等公式加以整理。例如，求例如，求(pq)r的主合取范式的主合取范式(pq)r

57、( pq)r(p q)r(pr)( qr) (p(q q)r)(p p) qr) (pqr) (p qr) (p qr)( p qr) (pqr)(p qr) ( p qr)三三.范式的应用范式的应用 范式在逻辑设计方面有广泛的应用。范式在逻辑设计方面有广泛的应用。例例1. 加法器的设计，有两个加法器的设计，有两个n位二进制数位二进制数a,b相加和相加和为为s(s=a+b)，a,b分别写成：分别写成： a=an an-1ai . a2a1, + b=bn bn-1bi . b2b1 cn cn-1cn-2 ci-1c1 s= cn sn sn-1si s2 s1 其中其中si是第是第i位位ai

58、、bi及及ci-1 (ci-1是第是第i-1位向第位向第i位的位的进位进位) 的和，的和，si是是ai、bi及及ci-1的函数的函数, 进位进位ci也是也是ai 、bi及及ci-1的函数的函数, 分别写成分别写成si(ai,bi,ci-1)，ci(ai,bi,ci-1)。它们与它们与ai,bi,ci-1的关系如下表：的关系如下表： ai bi ci-1 si(ai,bi,ci-1) ci(ai,bi,ci-1) 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1在电路逻辑设计中用如下逻辑

59、部件：在电路逻辑设计中用如下逻辑部件： 非门非门 与门与门 或门或门 根据前边的表根据前边的表, ,列出列出si(ai,bi,ci-1)的主析取范式：的主析取范式：si(ai,bi,ci-1)=( ai bici-1)( aibi ci-1) (ai bi ci-1)(aibici-1) 类似可以求出进位位类似可以求出进位位ci(ai,bi,ci-1)的表达式。的表达式。 (在指派在指派001、010、100、111时时si为为1)下面设计出下面设计出si(ai,bi,ci-1)的线路图的线路图。 ababa ababasi(ai,bi,ci-1)=( ai bici-1)( aibi ci-

60、1) (ai bi ci-1)(aibici-1)si(ai,bi,ci-1)a ai i a ai ib bi i b bi ic ci-1i-1 ci-1 ai bici-1 aibi ci-1ai bi ci-1aibici-1ci(ai-1,bi-1,ci-2)的线路图与之类似。的线路图与之类似。 a与b的和s的图：由n个si的图与n个ci的图合并而成。s1c1s2c2sn-1cn-1sncna1a2anan-1a:s:b1b2bn-1bnb:s=cn sn sn -1 s2 s1例例2. 安排课表，教语言课的教师希望将课安排课表，教语言课的教师希望将课程安排在第一或第三节；教数学课的