当前位置：文档之家 › 离散数学第2章第3节

离散数学第2章第3节

  • 格式：ppt
  • 大小：654.00 KB
  • 文档页数：50

下载文档原格式

  / 50

合集下载

离散数学2PPT课件

离散数学2PPT课件
在讨论Ａ与Ｂ是否有相同的真值表时，应将哑元考虑在内， 即将Ａ、Ｂ都看成含所有p1 , p2 , … pn的命题公式，如果在所有 2n个赋值下，Ａ与Ｂ的真值相同，则ＡＢ为重言式。
3/25/2021
2021
4
定义
CHAPTER TWO
定义2.1 设A ,B 是两个命题公式，若A, B构成的等价式A ↔ B为 重言式，则称A与B是等值的, 记为A⇔B。
3/25/2021
2021
11
例24
证明：(p→q)→r
⇔
p→(q→r）.
CHAPTER TWO
证 方法一：真值表法。
方法二：观察法。 方法三: 记A=(p→q)→r, B= p→(q→r)。先将A,B等值演算
化成易于观察真值的公式，再进行判断。
A=(p→q)→r⇔(┐p∨q)→r
(蕴含等值式)
⇔ ┐(┐p∨q)∨r
(交换律，结合律)
(10) ⇔ p∧(1∨p)
（排中律）
(11) ⇔ p∧1
（零律）
(12) ⇔ p
（同一律）
(13) 可见，（3）中公式不是重言式，因为00，01 都是成假赋
值；它也不是矛盾式，因为10，11 都是其成真赋值，故它是可
3/25/20满21足式。
2021
15
例2.6
CHAPTER TWO
B2∧C3∧D10, B3∧C1∧D2p∧┐q∧r, B3∧C2∧D10 于是，由同一律可知 E(┐p∧q∧┐r) ∨(p∧┐q∧r)
但因为王教授不能既是苏州人，又是杭州人，因而p,r必有一个为假命 题，即p∧┐q∧r0 。
于是 E┐p∧q∧┐r 为真命题，因而必有p,r为假命题，q为真命题， 即王教授为上海人，甲说得全对，丙说对了一半，而乙全说错啦。

离散数学第2章-高等教育出版社-屈婉玲-耿素云-张立昂--ppt课件

离散数学第2章-高等教育出版社-屈婉玲-耿素云-张立昂--ppt课件
p(qr) （蕴涵等值式，置换规则） (pq)r （结合律，置换规则） (pq)r （德摩根律，置换规则） (pq)r （蕴涵等值式，置换规则）
今后在注明中省去置换规则 注意：用等值演算不能直接证明两个公式不等值
8
等值演算的应用举例
证明两个公式不等值 例3 证明 p(qr) 与 (pq)r 不等值 证 方法一 真值表法, 见例1(2)
(pqr)(pqr)(pqr)
m0m1m3 m5m7
非重言式的可满足式
29
主范式的应用
3. 判断两个公式是否等值 例8 用主析取范式判以下每一组公式是否等值
⑴ p(qr) 与 (pq)r ⑵ p(qr) 与 (pq)r 解 p(qr) = m0m1m2m3 m4m5 m7 (pq)r = m0m1m2m3 m4m5 m7 (pq)r = m1m3 m4m5 m7 显见，⑴中的两公式等值，而⑵的不等值.
例如 (pq)r m1m3m5 m6m7 成真赋值为 001, 011, 101, 110, 111， 成假赋值为 000, 010, 100.
类似地，由主合取范式也立即求出成假赋值和成真赋值.
27
主范式的应用
2. 判断公式的类型 设A含n个命题变项. A为重言式 A的主析取范式含全部2n个极小项 A的主合取范式不含任何极大项, 记为1. A为矛盾式 A的主合析取范式含全部2n个极大项 A的主析取范式不含任何极小项, 记为0. A为非重言式的可满足式 A的主析取范式中至少含一个、但不是全 部极小项 A的主合取范式中至少含一个、但不是全 部极大项.
30
主范式的应用
4. 解实际问题 例9 某单位要从A,B,C三人中选派若干人出国考察, 需满足下
述条件: (1) 若A去, 则C必须去; (2) 若B去, 则C不能去; (3) A和B必须去一人且只能去一人. 问有几种可能的选派方案? 解 记 p:派A去, q:派B去, r:派C去 (1) pr, (2) qr, (3) (pq)(pq) 求下式的成真赋值 A=(pr)(qr)((pq)(pq))

离散数学课件第2章

离散数学课件第2章
4
序,而集合中的元素是不讲顺序的。但是 为了将所有的 概念都统一于集合概念， 可采用克亚托斯基(Kazimierz Kurafowski)在1921年给出的定义 (a, b)={{a},{a, b}} 将二元组定义为比其元素高二层的集合； (4) 也可用二元组来递归的定义n元组如下： (a,b,c)=((a,b),c)
例9 .设 A={1,2,3} R1 ={(1,1),(2,2)} ， R2 ={(1,2),(2,1)} 。
16
元素aA和集合A1A在关系R A×B下的关联集 (1)a的R-关联集(R-relative set of a)： R(a)={b : bBaRb }B ； (2) A1的R-关联集(R-relative set of A1)： R(A1)={b : bB (aA1)(aRb) }B 。 定理.设R A×B是一个二元关系， A1 ,A2 A 。则 (1)保序性：A1 A2 R(A1) R(A2) ； (2)R(A1∪A2) = R(A1)∪R(A2) ； (3)R(A1∩A2) R(A1)∩R(A2) 。
例.设A={a,b,c,d}， A1 = {c,d} ， R={(a,a),(a,b),(b,c),(c,a),(d,c),(c,b)}。
17
§3 .关系的表示
关系的性质
一.关系表示法 1°关系的矩阵表示法 设关系RA×B ， 这里A,B是两个非空的有限集合， A={ a1,a2,a3,…,am } ， B={ b1,b2,b3,…,bn } 。 则 用一个m×n阶0—1矩阵MR来表示关系R， 称此矩 阵MR为关系R的关系矩阵(relation matrix)。 MR=(xij)m×n ，其中 1 当（ai,bj) R时 xij = ( i=1,…,m ； j=1,…,n) 0 当（ai,bj) R时

离散数学第二章课件

离散数学第二章课件

2013/9/12
离散数学
15
关系图举例
• 例：设A={1,2,3,4,5} , R={<1,1>,<1,2>,<3,2>,<1,4>,<5,4>,<5,1>}, 则，R的关系图GR如下：
1
5 4
2013/9/12
2 3
离散数学 16
下面关系图有什么性质
a b c a b d c b a c
(a)
2013/9/12
离散数学
5
二元关系的性质的举例1
• 数值之间的相等关系“=” 对任意的x,y,z∈R(实数集),由“=”的性 质得: 对每一个x∈R ，x=x，∴ “=”是 自反的；若x=y,必有y=x,因此“=”是对 称的； 若x=y,y=x,必有x=y,因此“=”是 反对称的； 若x=y,y=z,必有x=z,因此“=” 是传递的；
25
• 定理2.2.1: 设R是A到B的关系,S是B到C的关系,T是C到D的关 系,则 ( R S ) T R (S T )
证明： 同理可证 R (S T ) ( R S ) T
于是有：( R S ) T R (S T )
2013/9/12
2013/9/12
离散数学
2
关系及其表示
特别地： (1)若R= A×B,称R为全关系。 (2)若A=B,则称R为集合A上的二元关系。 设:|A|=n,则|A×A|=n2,于是,A上所有不同的二 n2 n2 元关系共有2 。（|(A×A)|= 2 ） 其中大多数关系没什么意义，我们关心的是 具有一定性质的关系。
7
反对称性的讨论：
在反对称性定义中，对任意x,y ∈A， 若xRy 且yRx ,则x=y， 就称R是反对称的。 xRy 且yRx是条件； x=y是结论，在这里， 只要条件不成立，关系R就是反对称的。 当条件成立时，R是否是反对称的，要视 结论的真假而定。[例如]

离散数学PPT课件

离散数学PPT课件
定义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
第一部分数理逻辑
第一章 命题逻辑基本概念 第二章 命题逻辑等值演算 第三章 命题逻辑推理理论 第四章 一阶逻辑基本概念 第五章 一阶逻辑等值演算与推理

离散数学第2章 关系(祝清顺版)

离散数学第2章 关系(祝清顺版)
第二章 二元关系 2007年8月20日
离散数学
关系矩阵的实例
例9 设A={3, 5, 6, 9}, A上的二元关系
R={<x, y｜x＞y},
试求出关系矩阵。
[解] 关系的集合表示为:
R＝{9, 3, 9, 5, 9, 6, 6, 3, 6, 5, 5, 3}.
关系矩阵为: 0 1 MR= 1 1
关系的三种表示方法： 集合表达式 关系矩阵
关系图
关系矩阵和关系图可以表示有限集合上的关系。
离散数学
第二章 二元关系
2007年8月20日
关系矩阵
设给定集合A={a1,a2,…,an}，B={b1,b2,…,bm}，R为从A到B
的一个二元关系，构造一个n×m矩阵。用集合A的元素标注矩
阵的行，用集合B的元素标注矩阵的列，对于aiA和bjB，令
n2 n2
个. 不
每一个子集代表一个A上的二元关系，所以A上有 2 同的二元关系。 |Ai|=mi，则A1×A2×…×An上有 2 二元关系。
离散数学 第二章 二元关系 2007年8月20日
m1m2…mn
个不同的
常用的关系
定义 对任意集合A，定义 (1) 空关系 (2) 全域关系 EA={<x, y>|x∈A且y∈A}=A×A (3) 恒等关系 IA={<x, x>|x∈A} (4) 小于或等于关系：LA={<x, y>|x, y∈A且x≤y}, 其中 AR。 (5) 整除关系：DA={<x, y>|x, y∈A且x整除y}, 其中 AZ* , Z*是非零整数集 (6) 包含关系：R＝{<x, y>|x, y∈A且xy}, 其中A是集 合族。

离散数学第二章(第3讲)

离散数学第二章(第3讲)

2、规则使用说明
（1）用US,ES在推导中去掉量词，用UG,EG使结论量化 （加上量词）。 （2）在使用ES,US时,要求谓词公式必须是前束范式
（3）推导中既用ES，又用US， 则必须先用ES ，后 用US方可取相同变元，反之不行。
xP(x) P(c) xQ(x) Q(c)
（4）推导中连续使用US规则可用相同变元 xP(x) P(c) xQ(x) Q(c)
（x）(M(x)D(x))，M(s) D(s)
(1) x(M(x)D(x))
P
(2) M(s) D(s)
US(1)
(3) M(s)
P
(4) D(s)
T(2)(3)I
（2）CP 规则证明
例 证明: x (P(x)Q(x)) x P(x) xQ(x)
(1) x P(x)
附加前提
(2) x (P(x)Q(x))
x(P(x)(Q(x)S(x))),x(P(x)T(x))，Q(c)T(c)P(c)S(c)
推理形式如下：
(1) P(c)
附加前提
(2) x(P(x)(Q(x)S(x)))
P
(3) P(c)(Q(c)S(c))
US (2)
(4) Q(c)S(c)
T(1)(3) I
(5) Q(c)T(c)
P
(6) Q(c)
T (6)(10) I
T(1) E
(3) xP(x)
T (2) I
(4) P(a)
ES (3)
(5) xQ(x)
T(2) I
(6) Q(a)
US (5)
(7) x( P(x) Q(x) )
P
(8) P(a) Q(a)
US(7)

离散数学---谓词逻辑推理

离散数学---谓词逻辑推理

证明: (1). (x(P(x)S(x)))
(2). (3). 西 华 (4). 大 (5). 学 (6). (7). (8). (9). (10). (11). (12). (13). (14). (15). (16).
P规则
(1)E P(c)S(c) 全称量词消除规则 P(c) (3)I S(c) (3)I x(P(x)(Q(x)R(x))) P规则 P(c)(Q(c)R(c)) (6)全称量词消除规则，使用(3)中个体c Q(c)R(c) (4) (7)I x(P(x)(Q(x)S(x))) P规则 P(c)(Q(c)S(c)) 全称量词消除规则，使用(3)中个体c Q(c)S(c) (4) (11)I Q(c)S(c) (11)I Q(c) (12) (5)I R(c) (13) (8)I P(c) R(c) (4)和(14)的合取 x(P(x)R(x)) (15) 存在量词的引入
// 前提
(2). P(a)Q(a) // 全称量词消除规则
举例：全称量词消除规则
西 华 B 大 学
指出下列推导中的错误，并加以改正： (1). x P(x)Q(x) // 前提 (2). P(y)Q(y) // 全称量词消除规则
量词 x 的辖域为 P(x) ，而非 P(x)Q(x) ，所以不 能直接使用全称量词消除规则。
x(P(x)S(x))
前提：x(P(x)(Q(x)R(x)))、 x(P(x)(Q(x)S(x)))、 x(P(x)S(x))、 (x(P(x)S(x))) 结论：x(P(x)R(x))
一阶逻辑的永真蕴涵式
西 华 大 学
推理定律是一阶逻辑的一些永真蕴涵式，重要 的推理定律有： [1]. 附加律：A(AB) // 或称为析取的引入 [2]. 化简律： (AB)A, (AB)B // 或称为合取的消除 [3]. 假言推理： (AB)AB // 或称为分离规则 [4]. 拒取式： (AB)BA [5]. 析取三段论：(AB)BA [6]. 假言三段论：(AB)(BC)(AC) // 或称为传递规则

离散数学讲义第2章

离散数学讲义第2章
例2：H(x, y)：“x比y长得高”，l：“李四”，c：“张 三则” H(l, c)：“李四不比张三长得高”； H(l, c) H(c, l)：“李四不比张三长得高且张三不比 李四长得高”，即“李四与张三一样高”。
10
2-2 命题函数与量词（续）
例3：Q(x, y)：“x比y重” 当x，y指人或物时，它是一个命题，若x，y为实数时， Q(x, y)不是命题。
b) (x)(P(x)(y) R(x,y)) (x)的作用域是：(P(x)(y)(R(x,y))， (y)的作用域是：R(x,y)。 x,y为约束变元。
22
2-4 变元的约束（续）
c) (x)(y)(P(x,y)Q(y,z))(x)P(x,y) (x)(y)的作用域是：(P(x,y)Q(y,z)) x,y为约束变元，z是自由变元。 (x)的作用域是P(x,y) x为约束变元，y是自由变元。
例2：没有不犯错误的人。(F(x), M(x)) 解： (x)(M(x) F(x))
且该命题与“任何人都会犯错误”意义相同： (x)(M(x) F(x))
例3：尽管有些人聪明，但未必一切人都聪明。(P(x),M(x)) 解： (x)(M(x) P(x)) ((x)(M(x) P(x)))
18
某些为假。
例5：(P(x, y) P(y, z)) P(x, z)。考虑P(x, y)的解释： （1）“x小于y”，则P(x, y)永真。 （2）“x为y的儿子”，则P(x, y)永假。 （3）“x距离y10米”，则P(x, y)可能为真或假。
12
2-2 命题函数与量词（续）
个体变元：函数P(x)中的x。
(z)(P(z)R(z,y)) Q(x,y) 但不可换名为
(y)(P(y)R(y,y)) Q(x,y) 或

离散数学第2章ppt课件

离散数学第2章ppt课件
E AA∪B∪BC
C
n
A k A 1A 2 A n
k 1
二、集合的并 (Union)
3、性质
1)幂等律 A∪A =A
2)零律
A∪U =U
3)同一律 A∪ =A
4)交换律 A∪B =B∪A
5)结合律 A∪(B∪C) =(A∪B)∪C
二、集合的并 (Union)
3、性质
， 6)
若A⊆B，C⊆D，则A∪C
是集合，没有元素
有1个元素的集合
2) ∈{}， {}
五、特殊集合
1、空集
定理 空集是任一集合A的子集，即 ⊆A。
下列命题是否为真。
1)√⊆;
2) ∈ ; 3) ⊆{}; 4) ∈{} 。
√
√
五、特殊集合
1、空集
推理 空集是唯一的。(绝对唯一)
证明： 设1，2是两个空集, 则1 2，且2 1，
证明唯一性 一般采用反
1、符号表示法
通常用大写字母A, B, C, …代表集合; 用小写字母a, b, c, …代表元素。
1)如果a是集合A的一个元素, 则记为 a∈A, 读做“a属于A”,或 “a在集合A中”。
2)如果a不是集合A的一个元素, 则记为 a∈A, 读做“a不属于A”,或 “a不在集合A中”。
注：任一元素, 对某一集合而言, 或属于该集合, 或不属于该集合, 二者必居其一, 且只居其一。
1) 若b∈A，则b是不给自己刮脸的人， 而由题意，b只给集合A中的人刮脸。 ∴b 要给b 刮脸， 即b ∈ A。
理发师问题
在一个很僻静的孤岛上，住着一些人家，岛上只 有一位理发师，该理发师专给那些并且只给那些自己 不刮脸的人刮脸。那么，谁给这位理发师刮脸？

《离散数学第2章》课件

《离散数学第2章》课件

关系的运算
总结词
关系的运算包括并、交、差、对称差两个关系的元素合并，并 保留重复的关联；交运算是保留两个关系中 共有的关联；差运算是从一个关系中去除另 一个关系中的关联；对称差运算是将两个关 系中的不同元素合并；复合运算是根据一个 关系来定义另一个关系中的关联。
01
分布函数是单调非减的，且在无 穷大处的极限为1，在负无穷处 的极限为0。
03
离散随机变量的分 布函数
对于离散随机变量，其分布函数 可以表示为一系列离散的阶梯函 数。
随机变量的数字特征
数学期望
数学期望是随机变量所有可能取值的 概率加权和，表示随机变量取值的平 均值。
协方差和相关系数
协方差是两个随机变量的数学期望的 差的期望值，相关系数是协方差与两 个随机变量标准差的乘积的比值。
随机变量的取值范围
随机变量的取值范围称为随机变量的值域，可以是有 限集、可数无穷集或不可数集。
随机变量的分类
根据取值范围的不同，离散随机变量可以分为离散型 和连续型。
随机变量的分布函数
01
分布函数的定义
对于离散随机变量，其分布函数 是所有可能取值的概率之和，表 示随机变量取某个值的概率。
02
分布函数的性质
必然事件
概率值为1的事件，表示一定会 发生。
不可能事件
概率值为0的事件，表示一定不 会发生。
互斥事件
两个或多个事件不能同时发生 。
条件概率
条件概率的公式
P(A|B) = P(A∩B) / P(B)。
条件概率的应用
在决策树、贝叶斯定理等领域有广泛应用。
独立性
01
事件的独立性是指一个事件的 发生不受另一个事件是否发生 的影响。

离散数学 ch2.二元关系(3,4节)

离散数学 ch2.二元关系(3,4节)

下边R3、R4、 R6 、 R8均是对称关系。
1
。

1
。
2
。 。 3
R1
1
。 。 3
R2
1
。 。 2。 。 3 3
R3
1
R4
1
。
2
。
2
。
。
2
。 。 3
R5
。 。 3
R6
。 。 2。 。 3 3
R7 R8
四.反对称性
定义:设R为集合X中关系,若对任何x, y∈X,如果有 （x,y)∈ R,和(y ,x)∈ R,就有x=y,则称R为A中反对称关系 。 如实数的小于关系<，≤ ，均是反对称的。父子关系是反 对称的。
R 3 {(1,2), (3,0), (3,2)}
性质 判定 自反性
从关系的有向图 每个结点都有环
从关系的矩阵 主对角线全是1
反自反性
对称性 反对称性
每个结点都无环
主对角线全是0
不同结点间如果有边, 是以对角线为对称 则有方向相反的两条 的矩阵 边. 不同结点间,最多有一 以主对角线为对称 条边. 的位置不会同时为1
实际上r(R)、(s(R) 、t(R)) 就是包含R的“最小” 的自反(对称、传递)关系。 三.计算方法 定理1.给定 A中关系R,则 r(R)=R∪IA。 证明：令R’=R∪IA,显然R’是自反的和RR’，下 面证明R’是“最小的”：如果有A上自反关系 R”且RR”,又IAR”,所以 R∪IAR”,即R’R”。 所以R’就是R的自反闭包。即r(R)=R∪IA 。 ~ R 定理2.给定 A中关系R,则 s(R)=R∪ 。 证明方法与1.类似。（集合法） 定理3.给定 A中关系R,则 t(R)=R∪R2∪R3∪... 。 证明：令R’= R∪R2∪R3∪..., ⑴显然有 RR’ ；

离散数学第二章课件

离散数学第二章课件
2013-7-27 213页-第19
河南工业大学离散数学课程组
结论
F(x, y)：x是y的父亲
1.谓词中客体词的顺序是十分重要的，不能随意变 更。如命题F(b, c)为‚真‛，但命题F(c, b)为‚假‛； 2.具体命题的谓词表示形式和n元谓词是不同的，前 者是有真值的，而后者不是命题，它的真值是不确 定的。如上例中S(x)：x是一个三好学生， a为王童， S(a)是有真值的，但S(x)却没有真值。 3.一个n元谓词不是一个命题，但将n元谓词中的客 体变元都用具体的客体取代后，就成为一个命题。 而且，客体变元取不同的值对是否成为命题及命题 的真值有很大的影响。
2013-7-27 213页-第6
河南工业大学离散数学课程组 所有的人都是要死的。 苏格拉底是人。 所以苏格拉底是要死的。 逻辑学中著名的三段论方法，是由一个大前 提，一个小前提推出结论的方法。这方面的例 子如： 著名的苏格拉底三段论： 显然这是正确的推理，但在命题逻辑中却 苏格拉底（前469-前399） 无法得到证明，因为三段论的每句话都 古希腊唯心主义哲学家。 是一个原子命题，我们可分别用P，Q， 出现问题的原因 R来表示。这样，三段论方法用形式符号 在于，三段论中， 表示应为 P∧Q R 结论R与前提P， 但在命题逻辑里， P∧Q→R显然不是重言 Q的内在联系不 式。 可能在命题逻辑 命题演算的局限性: 不能反映命题之间的内在 中表示出来。 联系,即不能将命题分解开。
2013-7-27 213页-第20
河南工业大学离散数学课程组
2-2 命题函数与量词
一、命题函数 1、命题函数 单独一个谓词不是命题,例如设A:…是大学生,不是 命题, 只有当这个谓词后面紧跟一个具体客体后才是 命题,如A(张三)是一个命题。 设L(x, y): x小于y, 则L(2, 3)表示‚2小于3” 是真命题, 而L(5, 1)表示‚5小于1”是假命题。 上例中当x,y是客体变元时,谓词L(x,y)不是命题。 设P(x)表示‚x是大学生‛, 当x取特定的客体即客体常量时,则P(x)是命题, 而当x可在一定的范围任意取值, 则P(x)不是命 题，称为命题函数。

离散数学 第二章 谓词逻辑-2-3节

离散数学 第二章 谓词逻辑-2-3节

河南工业大学离散数学课程组
个体域 (论域)
个体域的给定形式有两种： （1）具体给定。
如：{a,b,c}
（2）全总个体域/任意域。 所有个体域的总和，即世间一切万物的主体。
河南工业大学离散数学课程组 3、量词：在命题中表示客体数量的词，称之为量词。
：全称量词 ：存在量词
Anyone
Exit
河南工业大学离散数学课程组
例
（2）每一个大学生都会说英语； 无特性谓词： Q(x):x会说英语。(x)Q(x) x∈{大学生}
Q(x):x会说英语。U(x):x是大学生。 (x) (U(x) → Q(x))
（3）有一些自然数是素数。 无特性谓词：T(x)：x是素数。(x) T(x) x∈{自然数}
一、谓词演算的原子公式
定义2-3.1 ：称n元谓词P(x1,x2,...,xn)为原子谓词公式， 简称原子公式。即不出现命题联结词和量词。 例如 P、Q(x)、A(x,f(x),a)都是谓词演算的原子公式。
二、谓词演算的合式公式(WFF)(Well Formed formulas) 定义2-3.2：谓词合式公式递归定义如下： (1)原子谓词公式是合式公式。
河南工业大学离散数学课程组
将命题函数→命题的两种方法
1）将变元取定具体的值，如P(a),P(b)。 2）将谓词量化。如(x)P(x), (x)P(x)。
河南工业大学离散数学课程组
命题函数举例
例.设S(x)表示“x学习很好”, W(x)表示“x工作很 好”, A(x)表示“ x身体好” S(x) 表示“x学习不是很好”, S(x) ∧W(x) 表示“x学习和工作都很好”。 A(x)→(S(x)∧W(x)) 表示“如果x身体不好，则x的学习与工作都不 会好”。 S(x), W(x)是简单命题函数, 而S(x), S(x)W(x), A(x)→(S(x)∧W(x))是 复合命题函数。

自考离散数学第2章

自考离散数学第2章

域E，若对 A和B的任一组变元进行赋值，所得命题的真值相同，则称 谓词公式A和B在E上是等价的，并记作 A B
定义2.3.2 给定任意谓词公式WffA，其个体域为E，对于A的所有赋值
WffA都为真，则称WffA在E上有效的（或永真的）
定义2.3.3 一个谓词公式WffA，如果在所有赋值下都为假，则称WffA
P
（2）H(s)→M(s)
（3）H(s) （4）M(s)
US(1)
P T(2)(3)I
2.5 谓词演算的推理理论
例：专业委员会成员都是教授，并且是计算机设计师，有些成员是资
深专家，所以有的成员是计算机设计师，且是资深专家。请用谓词推 理理论证明上述推理。
证：设个体域为全总个体域。 M(x):x 是专业委员会成员； H(x):x 是教授； G(x):x 是计算机设计师；
2.3 谓词演算的等价式与蕴含式
表2.3.1
2.3 谓词演算的等价式与蕴含式
2.3 谓词演算的等价式与蕴含式
2.3 谓词演算的等价式与蕴含式
2.4 前束范式
定义2.4.1 一个公式，如果量词均在全式的开头，它们的作用域，延伸
到整个公式的末尾，则该公式叫做前束范式。
定理2.4.1 任意一个谓词公式均和一个前束范式等价。
2.3 谓词演算的等价式与蕴含式
例：寻求下式的真值。
(x)(P Q( x)) R(a) ，其中P:2>1,Q(x):x≦3，R(x):x>5,a=5，
且论域{-2,3,6}
2.3 谓词演算的等价式与蕴含式
2.3 谓词演算的等价式与蕴含式
定义2.3.1 给定任何两个谓词公式 WffA和WffB，设它们有共同的个体

离散数学标准讲义sy第2章精品PPT课件

离散数学标准讲义sy第2章精品PPT课件

2021/2/4
离散数学
10
一阶逻辑命题符号化
例：在个体域分别限制为(a)和(b)条件时，将 下面两个命题符号化: (1) 凡是人都要呼吸. (2) 有的人用左手写字.
其中: (a)个体域 D1为人类集合； (b)个体域 D2为全总个体域.
解答
2021/2/4
离散数学
11
F (x) : x呼吸。
再取i癌痛治疗工作的开展使阿片类止痛药用量出现明显增加的趋势然而阿片类的滥用人数却呈现下降的趋势阿片类止痛药物医疗用药并未增加阿片类药物滥用的危险2020622离散数学57一阶逻辑知识结构21一阶逻辑基本概念22一阶逻辑等值演算23一阶逻辑的推理理论第四次课第一二次课第三次课癌痛治疗工作的开展使阿片类止痛药用量出现明显增加的趋势然而阿片类的滥用人数却呈现下降的趋势阿片类止痛药物医疗用药并未增加阿片类药物滥用的危险2020622离散数学58一阶逻辑等值演算知识点量词消去等值式量词否定等值式量词辖域收缩与扩张等值式量词分配等值式代替规则癌痛治疗工作的开展使阿片类止痛药用量出现明显增加的趋势然而阿片类的滥用人数却呈现下降的趋势阿片类止痛药物医疗用药并未增加阿片类药物滥用的危险2020622离散数学59一阶逻辑等值式b为逻辑有效式则称a与b是等值的记作
(a)个体域 D1为人类集合；
(b)个体域 D2为全总个体域.
2021/2/4
离散数学
13
一阶逻辑命题符号化
例：在个体域限制为(a)和(b)条件时，将下列命题符 号化:
(1) 对于任意的x，均有 x2-3x+2=(x-1)(x-2) .
(2) 存在x，使得 x+5=3.
其中: (a) 个体域 D1=N (N为自然数集合) (b) 个体域 D2=R (R为实数集合)
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

(x)(y) A( x, y) (y)(x) A( x, y)
具有两个量词的谓词公式有如下一些蕴含关系：
(x)(y) A( x, y) (y)(x) A( x, y) (y)(x) A( x, y) (x)(y) A( x, y)
(y)(x) A( x, y) (x)(y) A( x, y)
用分析法证明 (x)A(x)∨(x)B(x)(x)(A(x)∨B(x)) 。 证明 若(x)(A(x)∨B(x))为假, 则必有个体a, 使 A(a)∨B(a)为假; 因此A(a), B(a)皆为假, 所以(x)A(x)和(x)B(x)为假， 即 (x)A(x)∨(x)B(x)为假。 故(x)A(x)∨(x)B(x)(x)(A(x)∨B(x))
xi(i=1,2,
…,n)是客体变元，
Aij是原子公式或其否定。
举例
(x)(u)(z)(( P( x) P(u)) ( P( x) Q( y, z)) (Q( x, y) P(u)) (Q( x, y) Q( y, z)))
(x)(z)(y){[P ( x a) ( z b)] [Q( y) (a b)]}
命题演算的等价式
P Q P Q
P Q (P Q)
P P F
(x) H ( x, y) (x) H ( x, y) F
2、量词与联结词¬之间的关系 ¬ (x)P(x) (x)¬ P(x) ¬ (x)P(x) (x)¬ P(x)

其中Qi(1≤i≤k)为或, A为不含有量词的谓词公式。

特别地，若谓词公式中无量词，则该公式也看作 是前束范式。 前束范式的特点:所有量词均非否定地出现在公 式最前面，且它的辖域一直延伸到公式之末。

例如， (x)(y)(z)(P(x,y)Q(y,z))
R(x,y)
都是前束范式， 而(x)P(x)(y)Q(y)， (x)(P(x)(y)Q(x,y)) 不是前束范式。
一、有关量词消去和添加规则
量词消去规则：
(1)全称量词消去规则：称为全称指定规则，简称US规则
(2)存在量词消去规则：称为存在指定规则，简称ES规则
量词产生规则：
(3)存在量词产生规则：称为存在推广规则，简称EG规则
(4)全称量词产生规则：称为全称推广规则，简称UG规则

谓词逻辑是命题逻辑的进一步深化和发展，谓词演 算的推理方法，可以看作是命题演算推理方法的扩 张。因此命题逻辑的推理理论在谓词逻辑中几乎可 以完全照搬，只不过这时涉及的公式是谓词逻辑的 公式罢了。

在谓词逻辑中，某些前提和结论可能受到量词的约 束，为确立前提和结论之间的内部联系，有必要消 去量词和添加量词，因此正确理解和运用有关量词 规则是谓词逻辑推理理论中十分重要的关键所在。
例题4 将wffD： (x)( P( x) Q( x, y)) ((y) P( y) (z)Q( y, z)) 转化为与其等价的前束析取范式。 解
D (x)(P( x) Q( x, y)) ((y) P( y) (z)Q( y, z))
(x)( P( x) Q( x, y)) ((u) P(u) (z)Q( y, z))
1、命题公式的推广

结论：命题演算中的等价公式表和蕴含公式表都 可推广到谓词演算中使用。
谓词演算的等价式
(x)( P( x) Q( x)) (x)(P( x) Q( x))
(x) P( x) (y) R( x, y) ((x)( P( x) (y) R( x, y))
(x)(u)(z)( P( x) Q( x, y)) ( P(u) Q( y, z))
求前束析取范式的方法
第一步：消去多余量词
第二步：换名
第三步：消去条件联结词
第四步：将否定深入
第五步：将量词推到左边 第六步：化为析取范式
作业
P75: （1）b), （2） b、c)
§2—7 谓词演算的推理理论
证明 B(x)A(x)(x)(BA(x)) (B不含x)
证 B(x)A(x) ¬ B∨(x)A(x) (x)(¬ B∨A(x)) (x)(BA(x))
条件表达式 量词辖域扩张 条件表达式
4、量词与命题联结词之间的一些等价式
量词分配律 (x)(A(x)∧B(x))(x)A(x)∧(x)B(x)
(x)(y) A( x, y) (y)(x) A( x, y)
(x)(y) A( x, y) (y)(x) A( x, y)
(y)(x) A( x, y) (x)(y) A( x, y)
作业
P66: 3,4,5
P72:
2a),4,7
一、前束范式
定义2-6.1 一个合式公式称为前束范式，如果它有如 下形式：(Q1x1)(Q2x2)…(Qkxk)A
第二步改名，以便把量词提到前面。
(x){(y) A( x, y) (u)(v)[B(u, v) (z)( A( z, u) B(u, z))]}
(x)(y)(u)(v)(z){A( x, y) [B(u, v) ( A( z, u) B(u, z))]}
化为前束范式
解 第一步否定深入
原式
(x){(y) A( x, y) (x)(y)[ B( x, y) (y)( A( y, x) B( x, y))]} (x){(y) A( x, y) (x)(y)[B( x, y) (y)( A( y, x) B( x, y))]}
定理2.6.1 (前束范式存在定理) 任意谓词公式A都有 与之等价的前束范式。
证明：
前束范式的求取方法
举例
73页 例题1、例题2、例题3
例题2 化公式 (x)(y)((z)(P(x,z)∧P(y,z))(u)Q(x,y,u))为前束范式 解 原公式 (x)(y)(┐(z)(P(x,z)∧P(y,z))∨(u)Q(x,y,u))
B (x) A( x) (x)(B A( x))
这里A(x)是任意包括个体变元x的谓词公式， B是不包括个体变元x的任意谓词公式。
证明 (x)A(x)B (x)(A(x)B) (B不含x) 证 (x)A(x)B ¬ (x)A(x)∨B (x)¬ A(x)∨B (x)(¬ A(x)∨B) (x)(A(x)B) 条件表达式 量词否定 量词辖域扩张 条件表达式
第二步换名
D (x)[ P( x) (z)Q( z, y) (w) R( x, w)]
第三步消去条件联结词
D (x)[( P( x) (z)Q( z, y)) (w) R( x, w)]
第四步将否定深入
D (x)[P( x) (z)Q( z, y)) (w)R( x, w)]
Qi(1≤i≤k)为量词或，
xi(i=1,2, …,n)是客体变元，
Aij是原子公式或其否定。
举例
(x)(u)(z)(( P( x) Q( x, y)) ( P(u) Q( y, z)))
是前束析取范式。
定理2-6.3 每一个wffA都可转化为与其等价的前束 析取范式。 证明：略。
当B为真时,左右两边都为真;否则, B为假,此时左右两 边都等价于(x)A(x), 证迄.
3、量词扩张/收缩律(2)
(x) A( x) B (x)( A( x) B)
(x) A( x) B (x)( A( x) B)
B (x) A( x) (x)( B A( x))
第四步：将否定深入
第五步：将量词推到左边 第六步：化为合取范式
二、前束析取范式
定义2-6.3 一个wffA称为前束析取范式，如果它有 如下形式：
(Q1x1)(Q2x2)…(Qkxk)[(A11∧A12∧…∧A1l1) ∨(A21∧∧…∧A2l2) ∨ …∨(Am1∧Am2∧…∧Amlm)]
其中:
将约束变元x改名为u， 将约束变元y改名为z，
二、前束合取范式
定义2-6.2 一个wffA称为前束合取范式，如果它有如下 形式： (Q1x1)(Q2x2)…(Qkxk)[(A11∨A12∨…∨A1l1)∧(A21∨A22 ∨…∨A2l2) ∧ …∧(Am1∨Am2∨…∨Amlm)] 其中：
Qi(1≤i≤k)为量词或，
第五步将量词推到左边
D (x)(z)(w)[(P( x) Q( z, y)) R( x, w)]
第六步化为合取范式
D(x)(z)(w)[(┐P(x)∨┐R(x,w))∧(┐Q(z,y)∨┐R(x,w))]
求前束合取范式的方法
第一步：消去多余量词
第二步：换名
第三步：消去条件联结词
离 散 数 学
Discrete Mathematics
山东科技大学 信息科学与工程学院
上次课回顾

指导变元、作用域、约束变元、自由变元、闭式
约束变元换名和自由变元代入 有限论域客体变元的枚举



谓词公式赋值、谓词公式等价、永真式、不可满足 式、可满足式 谓词公式的等价式和蕴含式

四、谓词演算的等价式和蕴含式
(x)(A(x)∨B(x))(x)A(x)∨(x)B(x) (x)(A(x)B(x)) (x)A(x)(x)B(x)
5、量词与命题联结词之间的一些蕴含式 (x)A(x)∨(x)B(x)(x)(A(x)∨B(x))
(x)(A(x)∧B(x))(x)A(x)∧(x)B(x) (x)(A(x)B(x))(x)A(x)(x)B(x) (x)(A(x)B(x))(x)A(x)(x)B(x) (x)A(x)(x)B(x)(x)(A(x)B(x))
表 2 ― 1 谓词演算中常用的等价式和蕴含式
6、多个量词的使用