定义2.1设A,B是两个命题公式，若A，B构成的等价 式AB为重言式，则称A与B等值，记为AB。
20
例2.1判断下面两个公式是否等值： (pq), pq 例2.2判断下面各组公式是否等值： （1）p(qr) 与 (pq)r （2） ( pq)r与 (pq)r
21
置换规则 ： 设（A）是含公式A的命题公式， （B） 是用公式B置换了（A）中所有的A以后得到的命题公式， 若BA，则（B） （A）。
定义1.2 设p，q为两命题，复合命题“p并且q”称为p与 q的合取式，记作“pq”。 pq为真当且仅当 p， q同 时为真。
定义1.3 设p，q为两命题，复合命题“p或q”称为p与q的 析取式，记作“pq”。 p q为假当且仅当 p， q同时为 假。
7
例1.3将下列命题符号化 （1）吴影既用功又聪明。 （2）吴影不仅用功而且聪明。 （3）吴影虽然聪明，但不用功。 （4）张辉与王丽都是三好学生。 （5）张辉与王丽是同学
16
例1.8求下列公式的真值表，并求成真赋值。 (1) (pq)r (2) (pp)(qq) (3) (p q) q r
定义1.10设A为一命题公式 （1）若A在它的各种赋值下取值均为真，则称A是重 言式或永真式。 （2）若A在它的各种赋值下取值均为假，则称A是矛 盾式或永假式。 （3）若A不是矛盾式，则称A是可满足式。
离散数学
1
离散数学课件
离散数学是计算机科学的核心理论课程， 是计算机专业的专业基础课。
第一部分 数理逻辑 第二部分 集合与关系代数 第三部分 图论
2
第一部分数理逻辑
第一章 命题逻辑基本概念 第二章 命题逻辑等值演算 第三章 命题逻辑推理理论 第四章 一阶逻辑基本概念 第五章 一阶逻辑等值演算与推理
15
定义1.8 设p1,p2…pn是出现在公式A中的全部命题变 项 ，给p1,p2…pn各指定一个真值，称为对A的一个赋 值。若指定的一组值使A的真值为1，则称这组值为A 的成真赋值。若使A的真值为0，则称这组值为A的成 假赋值。
定义1.9将命题公式A在所有赋值下取值情况列成表， 称为A的真值表。
13
1.2命题公式及赋值
定义1.6（1）单个命题变项是合式公式，称为原子命题 公式。 （2）若A是合式公式，则（A）也是合式公式。 （3）若A，B是合式公式有 则（AB），（AB）， （AB）， （A B）也是合式公式。 （4）只有有限次应用（1）~（3）形成的符号串才是 合式公式。
14
定义1.7 (1)若A是单个命题变项，则A是0层公式。 （2）称A是n+1 (n0)层公式: (a)A= B, B是n层公式; （b)A=B C, 其中B，C分别是i 层和j层公式且 n=max(i,j); (c) A=B C,其中B，C的层次及n同（b) ； (d) A=B C，其中B，C的层次及n同（b) ； (e) A=B C ，其中B，C的层次及n同（b) 。 (3)若公式A的层次为k，则称A是k层公式。
例1.4将下列命题符号化 （1）张晓静爱唱歌或爱听音乐。 （2）张晓静是江西人或安徽人。 （3）张晓静只能挑选202或203房间。
8
定义1.4 设p，q为两命题，复合命题“如果p则q”称为p与q的 蕴涵式，记作“pq”。 p q为假当且仅当 p为真， q为假。
例1.5将下列命题符号化，并指出下列命题的真值
3
第一章 命题逻辑基本概念
1。1命题与联结词
命题：能判断真假的陈述句。 命题真值：作为命题的陈述句所表达的判断结果。
4
例1。判断下列句子是否为命题。
（1）4是素数 （2） 5 是无理数 （3）x大于y。 （4）月球上有冰。 （5）2000年元旦是晴天。 （6）大于 2 吗？ （7）请不要吸烟！ （8）这朵花真美丽啊！ （9）我正在说假话。
（1）如果3+3=6，则雪是白色的。
（2）如果3+36，则雪是白色的。
（3）如果3+3=6，则雪不是白色的。
（4）如果3+36，则雪不是白色的。
（5）只要a能被4整除，则a能被2整除。
（6） a能被4整除，仅当a能被2整除。
（7）除非a能被2整除， a才能被4整除。
（8）除非a能被2整除，否则a不能被4整除。
5
例1.2将下面这段话中所出现的原子命题符号化，并指出 其真值， 然后写出这段陈述。
3 是有理数是不对的；2是偶素数；2或4是素数；如果 2是素数，则3也是素数； 2是素数当且仅当3也是素数
解 p: 2 是无理数。 q: 2是素数。 r: 2是偶数。 s: 3是素数。 t: 4是素数。
6
定义1.1 设p为命题，复合命题“非p”称为p的否定式， 记作 p。 p为真当且仅当 p为假。
9
（9）只有a能被2整除， a才能被4整除。 （10）只有a能被4整除， a才能被2整除。
定义1.5 设p，q为两命题，复合命题“p当且仅当 q”称为p与q的等价式，记作“pq”。 p q为 真当且仅当 p， q同为真，或p， q 为假。
10
例1.6将下列命题符号化，并指出下列命题的真值 （1） 3 是无理数当且仅当加拿大位于亚洲。 （2）2+3=5的充要条件是 3 是无理数。 （3）若两圆01，02的面积相等，则它们半径相等，反 之亦然。 （4）当小王心情愉快时就唱歌，反之当她唱歌时就心 情愉快。
17
例1.9 下列公式都有两个命题变项p,q，它们中哪些具有相 同的真值表？ (1)pq (2)pq (3)(pq) (4)(pq)(qp) (5)qp
18
例1.10 下列公式中哪些具有相同的真值表？ (1)pq (2)qr (3)(pq)((pr)p)） (4)(qr)(pp)
19
ቤተ መጻሕፍቲ ባይዱ
第二章 命题逻辑等值演算 2.1等值式
11
基本复合命题的真值
P q p pq pq pq pq 00 1 0 0 1 1 01 1 0 1 1 0 10 0 0 1 0 0 11 0 1 1 1 1
12
例1.7 令 P：北京比天津的人口多。
q：2+2=4 r：乌鸦是白色的。 求下列复合命题的真值 (1) ((Pq)(p q ))r (2) (q r) (p r) (3) (P r) ((p r)