当前位置：文档之家 › 四川大学离散数学第二章

四川大学离散数学第二章

  • 格式：pdf
  • 大小：232.39 KB
  • 文档页数：29

下载文档原格式

  / 29

合集下载

离散数学第二章关系

离散数学第二章关系


例9 .设A={1,2,3,4} ，B={2,4,6,8,10} 。 R={(1,2),(2,4),(3,6)}。
则 (R) = {1,2,3}A ， (R) = {2,4,6}B 。
二.关系的一些关联性质 17
离散数学
定理1. 设R1,R2 A×B是两个关系。若 R1 R2 ，则
(1)保序性： (R1) (R2) ； (2)保序性： (R1) (R2) ；
注：笛卡尔(1596-1650 )，法国数学家， 1637年发表《方法论》之 一《几何学》，首次提出坐标及变量概念。这里是其概念的推广。
定义2. • 二个集合A，B的(二维或二重)叉积定义为 A×B ={(a, b): a A bB} ； •其元素——二元组(a, b)通常称为序偶或偶对(ordered
故 (R1)∩ (R2) = {1,2 }
21
离散数学
所以 (R1)∩ (R2) (R1 ∩ R2) 。
元素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 。
•当A=B时，即RA×A，则称R是A上的一个二元关 系。
例1 . 设A是西安交通大学全体同学组成的集合。 11
离散数学
R={(a,b) : aAbAa与b是同乡}A×A 于是，R是西安交通大学同学之间的同乡关系。
例2 . 设A是某一大家庭。
R1 = {(a,b) : aAbAa是b的父亲或母亲}A×A R2 = {(a,b) : aAbAa是b的哥哥或姐姐}A×A R3 = {(a,b) : aAbAa是b的丈夫或妻子}A×A 于是，
离散数学第2章谓词逻辑新

离散数学第2章谓词逻辑新

第二章 谓词逻辑
问题的提出：
所有的金属都导电，铜是金属，所以铜导电。 设： A：所有的金属都导电。 B：铜是金属。 C：铜导电。 该推理符号化为： A，B C
这是著名的三段论推理，A是大前提，B是小前 提，C是结论。显然，这个推理是有效的，但是这个 推理用命题逻辑是无法推证的。
为什么？
因为命题 A、B、C 在句子内部是有联系的，而 仅把命题表示成一个大写字母，就掩盖了这种联系。 也就是说一个命题仅用一个大写字母表示的方式太粗 了，我们必须加以细化，用另外的表示方式来表达命 题。 命题是表达判断的陈述句，将其细分，表达出主 语、谓语及宾语(若有的话)，而一个句子中“谓语”
I
I 包含 N x(N(x)→I(x))
对于存在量词：例如， 有些大学生吸烟。 令 S：大学生集合，A：烟民的集合。
S
A
吸烟的大学生
吸烟大学生是 S 与 A 的交集 x(S(x)∧A(x))
例题3.
每个人都有一个生母。 M(x,y)：y 是 x 的生母。 此命题可以表达为： xyM(x,y)
约定：
将不带个体变元的谓词称为
0 元谓词。
例如，S(a)，G(3,7) 等。
当谓词是常项时，0
元谓词是命题；
当谓词是变项时， 0 元谓词是命题变元。
四、命题函数 含有 n 个变元的命题函数是以个体域为定 义域，以{ F,T } 为值域的 n 元函数。 例： A(x)：x身体好。 G(x, y)：x > y。 B(x, y, z)：点 x 在点 y 与点 z 之间。 这些都是命题函数。
例：若 A(x)：x 身体好。 B(x)：x 学习好。 C(x)：x 工作好。 A(x)→(B(x)∧C(x)) 表示：如果 x 身 体不好，则 x 的学习与工作都不会好。 这也是命题函数 。 约定：对于一个命题函数，如果没有指明其 个体域，则假定其个体域是全总个体域。
离散数学第二章

离散数学第二章


P (t1 , t2 , , tn ) 是原子公式。
32
§2.1.3 谓词逻辑公式（公式 ）
定义 谓词公式由下述各条规定组成： （1）原子公式是谓词公式。 （2）若A是谓词公式，则﹁ A也是谓词公式。 （3）若A和B是谓词公式，则A ∨ B，A ∧ B，A → B， 也是谓词公式。
22
2．存在量词
注意：１．在存在量词 的作用下，x不再起变量的作用， 存在量词也“约束”了x的变量作用。 注意：２．在存在量词作用下，命题中的特性谓词与命题 变元之间必须采用联结词合取，而不能用条件。 注意：3．命题的表示形式与个体域密切相关。 例：有些狗是聪明的。 若个体域为所有狗的集合，则该命题表示为：
这种“描述主语性质的谓语结构的抽象形式或描述主语所 涉及对象之间的关系的抽象形式”就是谓词。语句中的主 语称为个体。 在原子命题中引进谓词和个体的概念，这种以命题中的谓 词为基础的分析研究，称为谓词逻辑(或称谓词演算)。
7


§2.1.1 谓词与个体

在谓词逻辑中，将原子命题分解为谓词与个体两部分。
F (a1 , a2 , , an )
例如， T（a）：a是教师。 D（３，２）：３大于２。 C（武汉，北京，广州）：武汉位于北 京和 广州之间。 注意顺序
9
§2.1.1 谓词与个体
在一个谓词中，个体是可以变化的，如 “是大学生” 中个体是可以变化的，可以是“张华是大学生” 也可
以是“何勇是大学生” ，等等。
31
§2.1.3 谓词逻辑公式（公式 ）
定义( 项 ) (1)个体常量符是项；
(2)个体变量符是项；
(3)设f是n元函数符，
t1 , t2 , , tn 为项，则
离散数学第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))
离散数学第二章讲解

离散数学第二章讲解

2018/12/20 18
练习
1. 设A={0,1}, B={1,2}, 则AB ={(0,1),(0,2), (1,1),(1,2)} BB ={(1,1),(1,2), (2,1),(2,2)}
2. #A=2, #B=3 则#(AB)= 6
#(2AB)= 26 由A到B的不同的关系的个数是 26
2018/12/20 16
普遍关系 因为AB AB，AA AA 所以AB是一个由A到B的关系 AA是A上的一个关系
常将AA记作UA={(ai,aj)|ai,ajA}
恒等关系 定义集合A上的恒等关系IA={(a,a)|aA}
例:设A={a,b,c},则 UA=AA={(a,a),(a,b),(a,c), (b,a),(b,b),(b,c), (c,a),(c,b),(c,c)}是A上的普遍 关系 IA={(a,a),(b,b),(c,c)}是A上的恒等关系
2018/12/20 14
对于B={2,5,8}
则B×B ={(2,2),(2,5),(2,8),(5,2),(5,5),(5,8) ,(8,2),(8,5),(8,8)} 令6={(2,2),(5,2),(8,2)}
7={(8,5), (5,2),(2,8),(2,5)}
因为6 BB, 7 BB, 所以，6, 7均是集合B上的关系
其中第i个元素ai称为该有序n元组的第i个坐标。
例 {a,b,c,d}={b,a,d,c},但(a,b,c,d)(b,a,d,c) {4,4,3,2}={4,3,2} ,但(4,4,3,2)(4,3,2) 当n=2时，有序二元组(a,b)又称为序偶。
2018/12/20 2
定义：设(a1,a2,…,an) 和(b1,b2,…,bn)是两个有序n元组， 若a1= b1, a2=b2,…,an=bn,则称这两个有序n元组相等，并 记作(a1,a2,…,an)=(b1,b2,…,bn)。
离散数学第二章(第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)
离散数学 第2章习题答案

离散数学 第2章习题答案

第2章习题答案1. 解 (1)设F(x)表示“x犯错误”，N(x)表示“x为人”，则此语句符号化为：⌝∃x(N(x)∧⌝F(x))。

(2)设F(x)表示“x是推理”，M(x)表示“x是计算机”，H(x，y)表示“x能由y完成”，则此语句符号化为：⌝∀x(F(x)→∃ y M(y)∧H(x，y))。

(3)设C(x)表示“x是计算机系的学生”，D(x)表示“x学习离散数学”，则此语句符号化为：∀x(C(x)→D(x))。

(4)因原语句与“一切自然数x，都有一个自然数y，使得y是x的后继数；并且对任意自然数x，当y 和z都是x的后继时，则有y＝z”的意思相同，所以原语句可符号化为：∀x(N(x)→∃ y(N(y)∧M(x，y)))∧∀x∀y∀z(N(x)∧N(y)∧N(z)→(M(x，y)∧M(x，z)→( y＝z))) 其中N(x)表示x是自然数，M(x，y)表示y是x的后继数。

(5)设S(x，y，z)表示“x＋y＝z”，则此语句符号化为：∀x∀y∃z S(x，y，z)。

(6)设Z(x)表示“x是整数”，S(x，y)表示“xy＝0”，T(x，y)表示“x＝y”，则此语句符号化为：∀x∀y(Z(x)∧Z(y)→(S(x，y)→ T(x，0)∨T(y，0)))。

(7)设E(x)表示“x是偶数”，P(x)表示“x是素数”，S(x，y)表示“x＝y”，则此语句符号化为：∀x(E(x)∧P(x)→∀y(E(y)∧P(y)→ S(x，y)))。

(8)设E(x)表示“x是偶数”，O(x)表示“x是奇数”，N(x)表示“x是自然数”，则此语句符号化为：⌝∃x(E(x)∧O(x)∧N(x))。

(9)设R(x)表示“x是实数”，Q(x)表示“x是有理数”，Z(x)表示“x是整数”，则此语句符号化为：∃x(R(x)∧Q(x)∧⌝Z(x))。

(10)设R(x)表示“x是实数”，Q(x，y)表示“y大于x”，则此语句符号化为：∀x(R(x)→∃⌝y(R(y)∧Q(x，y)))。

离散数学讲义第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章)

离散数学第四版课后答案(第2章)

离散数学课后答案第2章习题解答2.1 本题没有给出个体域,因而使用全总个体域. (1) 令x(是鸟F:)x(会飞翔.G:)xx命题符号化为xFx→∀.))G((x)((2)令x(为人.xF:)(爱吃糖G:)xx命题符号化为GxFx→⌝∀(x))()(或者xFx⌝∧∃(xG))(()(3)令xF:)(为人.xG:)(爱看小说.xx命题符号化为xF∃.Gx∧(x()))((4) x(为人.xF:)G:)(爱看电视.xx命题符号化为Fx⌝⌝∃.x∧(x))()G(分析 1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个体域时，往往要使用特性谓词。

（1）-（4）中的)(x F 都是特性谓词。

2° 初学者经常犯的错误是，将类似于（1）中的命题符号化为))()((x G x F x ∧∀即用合取联结词取代蕴含联结词，这是万万不可的。

将（1）中命题叙述得更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。

”因而符号化应该使用联结词→而不能使用∧。

若使用∧，使（1）中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。

”这显然改变了原命题的意义。

3° （2）与（4）中两种符号化公式是等值的，请读者正确的使用量词否定等值式，证明（2），（4）中两公式各为等值的。

2.2 (1)d (a),(b),(c)中均符号化为)(x xF ∀其中,12)1(:)(22++=+x x x x F 此命题在)(),(),(c b a 中均为真命题。

（2） 在)(),(),(c b a 中均符号化为)(x xG ∃其中02:)(=+x x G ，此命题在（a ）中为假命题，在(b)(c)中均为真命题。

（3）在)(),a中均符号化为b(c(),∃xH)(x其中.1(bH此命题在)(),a中均为假命题，在(c)中为(=5:)xx真命题。

分析 1°命题的真值与个体域有关。

2°有的命题在不同个体域中，符号化的形式不同，考虑命题“人都呼吸”。

离散数学第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。
理发师问题
在一个很僻静的孤岛上，住着一些人家，岛上只 有一位理发师，该理发师专给那些并且只给那些自己 不刮脸的人刮脸。那么，谁给这位理发师刮脸？
离散数学第二章知识点

离散数学第二章知识点

命题逻辑等值演算等值式定理：设A，B两个命题公式（即前面的合式公式），若A，B构成的等价式A↔B为重言式，则A与B是等值的，记作A⇔B(可以说该式子为等值式模式)常用的16组等值式模式：双重否定律：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⇔1排中律:A∨﹁A⇔1矛盾律:A∧﹁A⇔0蕴涵等值式: A→B⇔﹁A∨B等价等值式: A↔B⇔(A→B)∧(B→A)假言易位:A→B⇔﹁B→﹁A(这里可以用逆否命题的概念证明)等价否定等值式:A↔B⇔﹁A↔﹁B(或写成﹁B↔﹁A，这里可以用逆否命题的概念证明)归谬(miu)论：(A→B)∧(A→﹁B)⇔﹁A(此处可以通过蕴涵等值式，交换律以及结合律进行结合证明)上述等值式模式可以通过真值表证明等值式的验证1.等值演算法（即通过等值式模式对原式进行变形）举例:(p∨q)→r⇔(p→r)∧(q→r)证明时可以从左边开始演算也可以从右边开始演算，无硬性要求，这里我们从右边开始演算。

(p→r)∧(q→r)⇔(﹁p∨r)∧(﹁q∨r) //蕴涵等值式⇔(﹁p∧﹁q)∨r //分配律⇔﹁(p∨q)∨r //德摩根律⇔(p∨q)→r //蕴涵等值式2.真值表法（我在第一章的最后有叙述，这里不再重述）3.观察法（也可称为带入法，此处适合用以证明两式不等值的情况）关于等值演算法的补充：等值演算法可以用以证明公式的类型。

1.当最后结果为1时为重言式（永真式）2.当最后结果为0时为矛盾式（永假式）3.当最后结果只能化成某个命题变项或公式时为可满足式析取范式与合取范式简单析取式：p,﹁p,p∨q,﹁p∨q,p∨﹁q,,﹁p∨﹁q,﹁p∨﹁q∨r等（这里可以发现的是里面都只含有析取联结词，简单析取式结构就是由析取联结词和命题变项组成的一个公式）简单合取式：p,﹁p,p∧q,﹁p∧q,p∧﹁q,,﹁p∧﹁q,﹁p∧﹁q∧r等（这里可以发现的是里面都只含有合取联结词，简单合取式结构就是由合取联结词和命题变项组成的一个公式）课本中的定理：命题变项及其否定统称为文字。

离散数学第二章


种
相当于 “任意”,“凡是”,“所有”...
存在量词(Existential Quantifier):
表示个体域中部分个体的词， 记作
相当于 “存在”,“至少有一个”,“有些”...
若个体域中所有个体x,均使A(x)为真,记作(x)A(x) 若个体域中存在某些个体x,使A(x)为真,记作(x)A(x)
4.特性谓词: 若在全总个体域讨论问题,还需在命题表达中
增加特性谓词,以说明命题中个体的取值范围.
5.命题符号化
“每个计算机系的学生都学离散数学“
“存在着偶素数”
现在你正浏览到当前第二十二页，共一百一十七页。
谓词逻辑 >谓词公式
课堂练习
在谓词逻辑中符号化： 1. 北京是中国的首都 2. 甲是乙的父亲 3. 3介于2与4之间 4. 3大于2仅当3大于4。 5. 张三和李四是同班同学 6. 天下乌鸦一般黑 7. 火车都比汽车跑得快 8. 有的火车比所有汽车快。
例题 用谓词逻辑处理苏格拉底三段论：
人总是要死的, (x) (M(x) P(x)),
苏格拉底是人, M(a),
所以,苏格拉底是要死的。 P(a).
令 P(x): x是要死的,
M(x): x是人, a: 苏格拉底
推理形式为: (x) (M(x) P(x)), M(a) P(a).
现在你正浏览到当前第十九页，共一百一十七页。
现在你正浏览到当前第二十三页，共一百一十七页。
谓词逻辑
２-1 谓词的概念与表示 ２-2 量词 ２-3 谓词公式
２-4 谓词公式的解释 ２-5 等价式与蕴含式 2－6 前束范式 ２-7 谓词演算的推理理论
现在你正浏览到当前第二十四页，共一百一十七页。

离散数学答案第二章习题解答

离散数学答案第二章习题解答第二章谓词逻辑习题与解答1、将下列命题符号化:(1) 所有的火车都比某些汽车快。

(2) 任何金属都可以溶解在某种液体中。

(3) 至少有一种金属可以溶解在所有液体中。

(4) 每个人都有自己喜欢的职业。

(5) 有些职业就是所有的人都喜欢的。

解 (1) 取论域为所有交通工具的集合。

令x x T :)(就是火车, x x C :)(就是汽车, x y x F :),(比y 跑得快。

“所有的火车都比某些汽车快”可以符号化为))),()(()((y x F y C y x T x ∧?→?。

(2) 取论域为所有物质的集合。

令x x M :)(就是金属, x x L :)(就是液体, x y x D :),(可以溶解在y 中。

“任何金属都可以溶解在某种液体中” 可以符号化为))),()(()((y xD y L y x M x ∧?→?。

(3) 论域与谓词与(2)同。

“至少有一种金属可以溶解在所有液体中” 可以符号化为))),()(()((y x D y L y x M x →?∧?。

(4) 取论域为所有事物的集合。

令x x M :)(就是人, x x J :)(就是职业, x y x L :),(喜欢y 。

“每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧?→?(5)论域与谓词与(4)同。

“有些职业就是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →?∧?。

2、取论域为正整数集,用函数+(加法),?(乘法)与谓词<,=将下列命题符号化:(1) 没有既就是奇数,又就是偶数的正整数。

(2) 任何两个正整数都有最小公倍数。

(3) 没有最大的素数。

(4) 并非所有的素数都不就是偶数。

解先引进一些谓词如下:x y x D :),(能被y 整除,),(y x D 可表示为)(x y v v =??。

《离散数学第2章》课件


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

离散数学 第二章 关系 (Relation)


例1 设R是实数集合，S={(x,y) | xR ∧ yR ∧ x≤y} 由实数的性质知，当x≤y且 y≤x时，有x=y，由反对称关系 的定义知S是R上的反对称关系。
定义5 设R是非空集合X上的二元关系。若对于任意的x,y,zX， 当 (x,y)R 且 (y,z)R 时，有 (x,z)R ，则称R是X上的传递 关系。
例3 设N是自然数集合， R= { (a,b)∣ aN ∧ bN ∧ a｜b } N×N 称R是自然数集合上的整除关系。
例4 设 X = {风，马，牛}， R = { (风,马)，(马,牛) } X×X 称R是X上的二元关系。
定义2 设A, B是两个非空集合，R A×B 1）若R = ，则称R为空关系 ； 2）若R = A×B，则称R为全关系 ； 3）若A=B 且 R = { (a,a)∣aA}，则称R是幺关系。
例1 A={ a,b,c }, B={0,1} AB={(a,0), (a,1), (b,0), (b,1), (c,0), (c,1)} BA={(0,a), (0,b), (0,c), (1,a), (1,b), (1,c)} 例2 A={张三,李四}，B={白狗,黄狗} AB={(张三,白狗), (张三,黄狗), (李四,白狗), (李四,黄狗)} BA={(白狗,张三), (白狗,李四), (黄狗,张三), (黄狗,李四)}
第四节
二元关系的基本性质
定义1 设R是非空集合X上的二元关系。若对X中的每个元素x， 都有(x,x) R，则称R是X上的自反关系。 例1 设X={a,b,c,d}，R={(a,b),(a,a),(b,b),(c,d),(c,c),(d,d)} 由自反关系的定义知R是X上的自反关系。 若R={(a,a),(b,b),(c,c),(d,d)}，则R是X上的幺关系。 由此可知幺关系一定是自反关系，但自反关系不一定是幺 关系。

离散数学第二章课后题目讲解


[解]：推证不正确，因为 ┐x （A（x）┐ B∧（x）＜≠＞┐（x A（x）∧x┐B（x））
Ｒ（x）∧Ｈ（x，y，z）中，y 约束出现，x，z 自由出现。
2­4（2）下列谓词公式中的约束变元进行换名： [解]（a）xy（Ｐ（x，z）→Ｑ（y））＜＝＞Ｓ（x，y）； （b）（x（Ｐ（x）→（Ｒ（x）∨Ｑ（x）））∧xＲ（x））→zＳ（x，z）
（a）uv（Ｐ（u，z）→Ｑ（v））＜＝＞Ｓ（x，y）。 （b）（u（Ｐ（u）→（Ｒ（u）∨Ｑ（u）））∧vＲ（v））→wＳ（x，w）
[解]：（a）设 W（x）：x 是工人。 c：小张 原命题可符号化为：┐W（c） （b）设 S（x）：x 是田径运动员。 B（x）：x 是球类运动员。h：他。 原命题可符号化为：S（h）B∨（h） （c）设 C（x）：x 是聪明的。 B（x）：x 是美丽的。l：小莉。 原命题可符号化为：C（l）B∧（l） （d）设 O（x）：x 是奇数。 原命题可符号化为：O（m）→┐O（2m） （e）设 P（x，y）：直线 x 平行于直线 y G（x，y）：直线 x 相交于直线 y 原命题可符号化为：P（x，y）→┐G（x，y） （f）设 O（x）：x 是老的。V（x）：x 是健壮的。j：全教练。 原命题可符号化为：┐O（j）┐V∧（j）
2­5（5）证明如下等价式：
（a） x（A（x）→B（x））＜＝＞x A（x）→x B（x）； （b） xy（Ｐ（x）→Ｑ（y））＜＝＞xＰ（x）→yＱ（y）。
[证]（a）x（A（x）→B（x））＜＝＞x（┐A（x）B∨（x）） ＜＝＞x┐A（x）∨x B（x） ＜＝＞┐x A（x）∨x B（x） ＜＝＞x A（x）→x B（x） （b）xy（Ｐ（x）→Ｑ（y））＜＝＞xy（┐Ｐ（x）∨Ｑ（y）） ＜＝＞x（┐Ｐ（x）∨yＱ（y）） ＜＝＞x┐Ｐ（x）∨yＱ（y） ＜＝＞┐xＰ（x）∨yＱ（y） ＜＝＞xＰ（x）→yＱ（y）

离散数学第二章第二节


7
第2-2讲 作业
P62 1eg，2，3a，7 P65 2bc，3b，4，5
8
第2-2讲 谓词公式与翻译
1. 谓词演算的合式公式 2. 用谓词公式表达命题 3. 约束变元和自由变元 4. 约束变元的换名规则
5.自由变元的代入规则
6. 第2-2讲 作业
1
1、谓词演算的合式公式
定义１ 不出现命题连接词和量词的ｎ元谓词 Ｐ（x1，x2，...，xn）（ｎ≥０） 称为谓词演算的原子公式，简称原子谓词公式。
根据这个定义，命题、命题变元、简单命题函数统称为谓词演算 的原子公式。如：R, Q(x), P(x,y), P(f(x),y), A(x,y,z), A(x,a,y当按下列规则生成： ⑴ 原子谓词公式是合式公式； ⑵ 若Ａ是谓词公式，则Ａ是合式公式； ⑶ 若Ａ、Ｂ是谓词公式，则Ａ∧Ｂ，Ａ∨Ｂ，Ａ→Ｂ ，ＡＢ是合式公式； ⑷ 若Ａ是谓词公式，ｘ是Ａ中出现的任意客体变元， 则(ｘ)Ａ和(ｘ)Ａ都是合式公式 ⑸ 有限次应用规则⑴－⑷所得到的式子是合式公式。
6
5、自由变元的代入规则
对谓词公式的自由变元可以用与原公式中所有变元名 称不同的符号去代替，但必须处处代替。
例如： (1) (x)P(x,y)∨Q(z,y) (x)P(x,w)∨Q(z,w) (2) (x)(y)（P(x,y)∨Q(y,z)）∧(x)P(x,y) (x)y)（P(x,y)∨Q(y,z)）∧(u)P(u,v)
3、约束变元和自由变元(续)
Ｐ（x1 ， x2 ， … ， xn ）是ｎ元谓词，它有ｎ个相互独立 的自由变元。若对其中ｋ个变元进行约束,则成为ｎ－ｋ 元谓词。因此，谓词公式中如果没有自由变元出现，则 该式就成为一个命题。例如，P(x,y,z)是三元谓词，而 (x)P(x,y,z)是二元谓词，(y)(x)P(x,y,z)是一元谓 词。 量词对变元的约束与量词的次序有关。 多个量词连续出现时,约定按从左到右的次序读出。量 词的次序不能颠倒，否则会改变命题的意义。 例如,(y)(x)(x<(y-2))表示“对任何ｙ均存在ｘ， 使得x<(y-2)” ； 而(x)(y)(x<(y-2))表示“存在ｘ对任 何ｙ均有x<(y-2)” 。 又如，(y)(x)(x<(y-2))表示“存在ｙ， 有ｘ，使得x<(y-2) ”。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

证明: ① q ② ～s∨q ③ s→q ④ s→p ⑤ (s→p)∧(s→q) ⑥ s→(p∧q) ⑦ (p∧q)→r ⑧ s→r P T ① 扩充法则 （关键） T ② 蕴涵式 P T ③ ④ 合取 T ⑤ 二难推论，幂等律 P T ⑥ ⑦ 假言三段论

范式
句节、子句、短语、析取范式、合取范式 极小项---主析取范式 极大项---主合取范式

命题公式的蕴涵 推理规则
基本蕴含（关系）式

① P规则（称为前提引用规则） ② Ｔ规则（逻辑结果引用规则） ③ ＣＰ规则（附加前提规则）
二、基本方法
1、应用基本等价式及置换规则进行等价演算 2、求主析取（主合取）范式的方法
三、典型例题
1.命题逻辑表达式的翻译：

除非你已满16周岁，否则只要你的身高不足1.2米就不 能乘公园滑行铁道游乐车。
解：令P：你能乘坐公园滑行铁道游乐车。 Q：你身高不足1.2米。 R：你已满16周岁。

翻译成： (¬RΛ Q)→¬ P
2、试证明 (P∧(Q∨R))∨(P∧ ～Q∧ ～R) P 证明： (P∧(Q∨R))∨(P∧ ～Q∧ ～R) P∧((Q∨R)∨(～Q∧ ～R))（分配律） P∧((Q∨R)∨～(Q∨R)) (De Morgan定律) P∧T（矛盾律） P (同一律)
共有四个极小项，但根据题意，需派两人出差，所以，只有 其中三项满足要求： （A∧～B∧C∧～D），（A∧～B∧～C∧D）， （～A∧B∧～C∧D） 即有三种方案：A和C去，或者A和D去，或者B和D去。
8、如果今天是星期一，则要进行离散数学或数据结构两门课 程中的一门课的考试；如果数据结构课的老师生病，则不 考数据结构；今天是星期一，并且数据结构的老师生病。 所以今天进行离散数学的考试。 解：设 P：今天是星期一； Q：要进行离散数学考试； R：要进行数据结构考试； S：数据结构课的老师生病； 则P→QR，S→～R，P∧S Q。
证: ⑴ ⑵ ⑶ ⑷ ⑸ ⑹ ⑺ ⑻
P∧S S S→～R ～R P P→QR QR Q
Ｐ Ｔ,⑴,I1 Ｐ Ｔ,⑵,⑶,I5 Ｔ,⑴,I1 Ｐ Ｔ,⑸,⑹,I5 Ｔ,⑷,⑺,I5

9、一位计算机工作者协助公安员审查一件谋杀案，他认为下列 情况是真的； （1）会计张某或邻居王某谋害了厂长。 （2）如果会计张某谋害了厂长，则谋害不能发生在半夜。 （3）如果邻居王某的证词是正确的，则谋害发生在半夜。 （4）如果邻居王某的证词不正确，则半夜时屋里灯光未灭。 （5）半夜时屋里灯光灭了，且会计张某曾贪污过。 计算机工作者用他的数理逻辑知识，很快推断出谋害者 是谁？请问:谁是谋害者？怎样推理发现他？
5、用公式转换法求上题中的主析取和主合取范式 ～(Ｐ→Ｑ)∨Ｒ ～（～P∨Q）∨R （P∧～Q）∨R (P∧～Q∧(R∨～R))∨( (P∨～P)∧(Q∨～Q)∧R) (P∧ ～ Q∧R) ∨ (P∧ ～ Q∧ ～ R ))∨ （ (P∨ ～ P) ∧((Q∧R)∨(～Q∧R))） (P∧～Q∧R)∨(P∧～Q∧～R)) ∨ (P∨～P) ∧(Q∧R)∨ (P∨～P) ∧(～Q∧R) （P∧～Q∧R）∨（P∧～Q∧～R）∨（P∧Q∧R） ∨（～P∧Q∧R）∨（P∧～Q∧R）∨（～P∧～Q∧R ）
P P T①②E23,I5 P T③④I5 P T⑤⑥I7 P T⑦⑧I5
13、若n是偶数，并且n大于5，则m是奇数。只有n是偶数，m才 大于6。n是大于5。所以，若m大于6，则m是奇数。 解：设p：n是偶数，q: n大于5, r: m是奇数, s: m大于6. 前提: (p∧q)→r, s→p, q 结论：s→r
4、 G=～(Ｐ→Ｑ)∨Ｒ，求公式G的主析取范式和主合取范式。
解：首先列出其真值表如下：
P Q R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 P→Q 1 1 1 1 0 0 1 1
～（P→Q）
0 0 0 0 1 1 0 0
～(P→Q)∨R
0 1 0 1 1 1 0 1
∴ {P∨Q，P→～N，O→N，～O→～R，R∧A} Q 结论是：邻居王某谋害了厂长。
10、证明下面论述的有效性。 在意甲比赛中，假如有四只球队，其比赛情况如下： 如果国际米兰队获得冠军，则AC米兰队或尤文图斯队获得亚 军；若尤文图斯队获得亚军，国际米兰队不能获得冠军； 若拉齐奥队获得亚军，则AC米兰队不能获得亚军；最后， 国际米兰队获得冠军。所以，拉齐奥队不能获得亚军。 解：设P：国际米兰队获得冠军； Q：AC米兰队获得亚军； R：尤文图斯队获得亚军； S：拉齐奥队获得亚军； 则原命题可符号化为： P→QR，R→～P，S→～Q，P～S
1）公式转换法 2）真值表技术法 主合取范式----在命题公式的真值表中，使公式取值 0时的解释所对应的全部极大项的合取式。 主析取范式----在命题公式的真值表中，使公式取值 1时的解释所对应的全部极小项的析取式。
3、推理的各种方法

（1）直接法 （2）利用CP规则 （3）反证法
4、消解法
3、证明 ((P∨Q) ∧～(P∧Q)) ～(PQ) 证： ((P∨Q)∧～(P∧Q)) ((P∨Q)∧(～P∨～Q)) (De Morgan定律) ((P∨Q)∧～P)∨ ((P∨Q)∧～Q)) （分配律） ((P∧～P)∨(Q∧～P))∨((P∧～Q)∨(Q∧～Q)) (Q∧～P)∨(P∧～Q) （矛盾律） ～(～Q∨P)∨～(～P∨Q) (De Morgan定律) ～((Q→P)∧(P→Q)) （蕴涵式） ～(PQ) （等价式）
11、P25
习题一 18
解：根据给定的条件有下述命题： P：珍宝藏在东厢房 Q：藏宝的房子靠近池塘 R：房子的前院栽有大柏树 S：珍宝藏在花园正中地下 T：后院栽有香樟树 M：珍宝藏在附近 根据题意，得出： （Q→～P）∧（R→P）∧Q∧（R∨S）∧（T→M）
？
（Q→～P）∧（R→P）∧Q∧（R∨S）∧（T→M） ～P∧（R→P）∧（R∨S）∧（T→M） 假言推理 ～R∧（R∨S）∧（T→M） 拒取式 S∧（T→M） 析取三段论 S 即珍宝藏在花园正中地下
习题课1
- 命题逻辑
2014 秋季
第一章 命题逻辑 总 结
一、基本概念

命题
命题的真值 原子命题、复合命题 逻辑联结词（～、∨、∧、、→、）

命题公式
公式的解释 永真式(重言式) 永假式(矛盾式，不可满足公式) 可满足式

命题公式的等价
基本等价式——命题定律 替换规则（定理） 对偶式 对偶原理
极大项 极小项
P∨Q∨R ～P∧～Q∧R P∨～Q∨R ～P∧Q∧R P∧～Q∧～R P∧～Q∧R ～P∨～Q∨R P∧Q∧R
主析取范式 =（～P∧～Q∧R）∨（～P∧Q∧R）∨ （P∧～Q∧～R）∨（P∧～Q∧R）∨（P∧Q∧R） =m1∨ m3∨ m4∨ m5∨ m7 主合取范式 =（ P∨Q∨R ）∧（ P∨～Q∨R ）∧（～P∨～Q∨R） =M0 ∨ M2 ∨ M6
⑴ ⑵ ⑶ ⑷ ⑸ ⑹ ⑺ ⑻ ⑼ ⑽ ⑾
～（～S） P（附加前提） S T,⑴,E1 S→～Q P ～Q T,⑵,⑶,I5 P→QR P P P Q R T,⑸,⑹,I5 R T,⑷,⑺,I7 R→～P P ～P T,⑻,⑼,I5 P∧～P( F) T,⑹,⑽,E19 所以，拉齐奥队不能获得亚军
6、将下面一段程序简化
A∧B then If B∨C then X Else Y End Else If A∧C then Y Else X End End If
执行程序段X 的条件为 ((A∧B)∧(B∨C))∨(～ (A∧B)∧～ (A∧C)) ～ (A∧～ B∧C) 执行程序段Y的条件为 ((A∧B)∧～ (B∨C))∨(～ (A∧B)∧ (A∧C)) A∧～ B∧C A∧～ B∧C Y Else X End If then
解：设P：会计张某谋害了厂长 Q：邻居王某谋害了厂长 N：谋害发生在半夜。 O：邻居王某的证词是正确的。 R：半夜时屋里灯光灭了。 A：会计张某曾贪污过。 上述案情有如下命题公式： （1）P∨Q （2）P→～N （3）O→N （4）～O→～R （5）R∧A
问题是需求证： {P∨Q，P→～N，O→N，～O→～R，R∧A} ？ 证：① R∧A P ② R T，①，I1 ③ ～O→～R P ④ O T，②，③，E23，I5 ⑤ O→N P ⑥ N T，④，⑤，I5 ⑦ P→～N P ⑧ ～P T，⑥，⑦， E23，I5 ⑨ P∨Q P ⑩ Q T，⑧，⑨，I7
12、P26
21（2）
解：根据给定的条件有下述命题： P：现场无任何痕迹 Q：失窃时，小花在OK厅 R：失窃时，小英在OK厅 S：失窃时，小胖在附近 T：金刚是偷窃者 M：瘦子是偷窃者 则根据案情有如下命题公式： {P，Q∨R，S→ ～ P，Q→ T，～ S→ ～ R，R→ M}
① P ② S→～P ③ ～S ④ ～S→～R ⑤ ～R ⑥ Q∨R ⑦ Q ⑧ Q→T ⑨ T 即 金刚是偷窃者
（主析取范式）
～(Ｐ→Ｑ)∨Ｒ ～（～P∨Q）∨R （P∧～Q）∨R （P∨R）∧（～Q∨R） （P∨（～Q∧Q）∨R ）∧（（～P∧P）∨～Q∨R） （P∨～Q∨R）∧（P∨Q∨R ）∧（ ～P∨～Q∨R）∧ （P∨～Q∨R） （P∨～Q∨R）∧（P∨Q∨R ）∧（ ～P∨～Q∨R） （主合取范式）
7、习题一 14题 解：由题设 A：A去，B：B去，C：C去，D：D去 则满足条件的选派应满足如下范式： （A→（CD））∧～（B∧C）∧～（C∧D） 构造和以上范式等价的主析取范式（为什么？） （A→（CD））∧～（B∧C）∧～（C∧D） （～A∧～B∧ ～C ∧D ）∨（～A∧～B∧～C∧～D）∨（～ A∧～B∧C∧～D）∨（～A∧B∧～C∧～D） ∨（A∧～B∧C∧～D）∨（A∧～B∧～C∧D） ∨（～A∧B∧～C∧D）∨（A∧B∧～C∧D）