离散数学2

格式：doc
大小：186.50 KB
文档页数：4

下载文档原格式

离散数学2联结词(否定、合取)

联结词----否定、合取复合命题是用“联结词”将原子命题联结起来构成的.归纳自然语言中的联结词，定义了六个逻辑联结词：(1)否定“⌝”(2)合取“∧”(3) 析取“∨”和异或“”∨(4) 条件（蕴涵）“→”(5)双条件（等价）“∆”或记做“↔”一. 否定“⌝”表示：“…不成立”，“不…”.用于：对一个命题P的否定，写成⌝P，并读成“非P”.⌝P的真值：与P真值相反.例 P：2是素数.⌝P：2不是素数. P ¬P F T T F例1. P: 天津是一个城市.Q: 3是偶数.于是: ⌝ P: 天津不是一个城市.⌝ Q: 3不是偶数.例2. P:济宁学院处处清洁.Q:这些都是男同学.(注意,不是处处不清洁)⌝ P:济宁学院不处处清洁.⌝ Q:这些不都是男同学.二. 合取“∧”表示：“并且”、“不但…而且...”、“既…又...” “尽管…还…”.例 P：小王能唱歌.Q：小王能跳舞.P∧Q：小王能歌善舞. P∧Q读成P合取Q.P∧Q的真值为真，当且仅当P和Q的真值均为真.P Q P∧Q F F F F T F T F F T T T例3. 将下列命题符号化:(1)李平既聪明又用功.(2)李平虽然聪明, 但不用功.(3)李平不但聪明,而且用功.(4)李平不是不聪明,而是不用功.解: 设P:李平聪明. Q:李平用功.则 (1) P∧Q (2) P∧⌝ Q(3) P∧Q (4) ⌝(⌝ P)∧⌝ Q例4. 翻译下列命题的合取.(1) P: 我们在C403教室. Q: 今天是星期二.(2) S：李平在吃饭. R：张明在吃饭.解: (1) P∧Q :我们在C403教室且今天是星期二.(2) S∧R:李平与张明在吃饭.“∧”与日常语言中“与”“和”的不同之处：（1）逻辑学中允许两个相互独立无关，甚至相反的原子命题生成一个新命题.（2）自然语言中有时在不同意义时可以同时使用“与”“和”，但是不能都用“∧”翻译.（如：我和你是好朋友.李敏和李华是姐妹.）说明：“∧”属于二元运算符.合取运算特点：只有参与运算的二命题全为真时，运算结果才为真，否则为假.自然语言中的表示“并且”意思的联结词，如“既…又…”、“不但…而且…”、“虽然…但是…”、“一面…一面…”、“…和…”、“…与…”等都可以符号化为∧.。

离散数学第二章关系

例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 于是，

离散数学第二章

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 为项，则

离散数学II

b)：相同的运算符，从左到右次序计算时，括号可省去。
c)：最外层括号可省。如，(¬((P ∧ ¬Q) ∨R) →((R ∨P)∨Q))
¬(P ∧ ¬Q∨R) →R ∨P∨Q
21/73
1.1 命题与命题联结词
• 例1.3：符号化下列命题。
a)：他既有理论知识又有实践经验 b)：i. 如果明天不是雨夹雪则我去学校
26/73
1.2 公式的解释与真值表
• 原子命题在不指派真值时称为命题变元，而
复合命题由原子命题和联结词构成，可以看作是命题变元的函数，且该函数的值仍为 “真”或“假”，可以称为真值函数（True Value Function）或命题公式。但不是说原子命题和联结词的一个随便的组合都可以为命题公式，我们用递归的方法来定义命题公式。
• 例，(¬ P∧Q)，(P→(¬P ∧Q)) ，(((P∧Q) ∧(R
∨Q)) ↔(P →R))是命题公式 (P →Q )∧¬ Q)， (P →Q， (¬ P∨Q ∨(R， P∨Q ∨不是命题公式
28/73
1.2 公式的解释与真值表
• 注意：
– 如果G是含有n个命题变元 P1, P2, …,Pn的公式，通常记为G（P1, …,Pn）或简记为G。
汇集起来的一门综合学科。离散数学的应用遍
及现代科学技术的诸多领域。
–离散数学是随着计算机科学的发展而逐步建立
起来的一门新兴的工具性学科，形成于上上个
世纪七十年代。
2/73
引言
• 课程意义
–离散数学是计算机科学的数学基础，其基本概念、理论、方法大量地应用在数字电路、编译原理、数据结构、操作系统、数据库系统、算法设计、人工智能、计算机网络等专业课程中，是这些课程的基础课程。

离散数学2

离散数学（2）复习题一、判断题1、两个集合相等的充分必要条件是这两个集合互为补集。

（ × ）2、两个集合相等的充分必要条件是这两个集合互为子集。

（ √ ）3、两个集合相等的充分必要条件是这两个集合互为幂集。

（ × ）4、对于任意一个集合A ，A f Í。

（ √ ）5、对于任意一个集合A ，A f Î。

（ × ）6、如果有限集合有n 个元素，则其幂集有2n 个元素。

（ √ ）7、设R 、S 是集合A 上的关系，且R S Ê，则()()s R s S Ê。

（ √ ）8、设R 、S 是集合A 上的关系，且R S Ê，则()()t R t S Ê。

（ √ ）9、设R 、S 是集合A 上的关系，且R S Ê，则()()r R r S Ê。

（ √ ）10、一个关系可以：既不满足自反性，也不满足非自反性。

（ √ ）11、一个关系可以：既不满足对称性，也不满足反对称性。

（ √ ）12、一个关系可以：既满足对称性，同时也满足反对称性。

（ √ ）13、若图G 是不连通的，则图G 的补图G -是连通的。

（ √ ）二、单项选择题1、由集合运算定义，下列各式正确的有（ A ）。

A.X ⊆X ⋃YB.X ⊇X ⋃YC.X ⊆X ⋂YD.Y ⊆X ⋂Y2、设A B -=∅，则有（ C ）。

A.B =∅B.B ≠∅C.A B ⊆D.A B ⊇3、对任意的集合A 、全集U ，下列命题为假的是（ D ）。

A.A ⋃∅ ＝A ，B.A ⋃U = UC.A ⋂∅ = ∅，D.A ⋂U = U4、集合A={1，2，…，10}上的关系R={<x,y>|x+y=10,x ∈A,y ∈A},则R 的性质为（ B ）。

A.自反的B.对称的C.传递的，对称的D.反自反的，传递的5、设R 和S 是集合A 上的任意关系，则下列命题为真的是（ A ）。

离散数学2联结词(否定、合取)

离散数学(第2版)

离散数学（第2版）——关于数学中重要的研究方向
离散数学是一门涉及数学中各种离散对象的研究方向，包括数论、图论、代数等。

离散数学是计算机科学、通信工程和其他许多工科领域的基础，对于理解计算机算法的原理和应用具有重要意义。

本文将对离散数学（第2版）这本数学教材进行介绍。

离散数学（第2版）是由美国杜克大学的Kenneth H. Rosen所著的数学教材。

这本书共分为五章，分别是基础概念、逻辑和计算、数论、图论、代数和应用。

第一章主要介绍了离散数学的基础概念，包括逻辑基础、集合、关系和函数。

第二章介绍了逻辑和计算的相关内容，包括命题逻辑、谓词逻辑、计算机科学中的逻辑和布尔代数。

第三章是关于数论的章节，包括质数、最大公约数、最小公倍数、模运算、同余方程等内容。

第四章是关于图论的章节，包括无向图、有向图、连通图、生成树、最短路径、最小生成树等内容。

第五章是关于代数和应用的章节，包括代数系统、群、域、同余环、线性代数和代数应用等内容。

本书还附有大量的练习题，帮助读者检验自己的学习效果。

离散数学（第2版）是一本系统而全面的数学教材，涵盖了离散数学的各个方面。

它适合作为计算机科学和工科领域的数学基础教材，也可作为普及离散数学的参考书。

离散数学第2章谓词逻辑

命题“凡人要死。”符号化为：(x)F (x) ⑵ 令G(x)：x是研究生。命题“有的人是研究生。”符号化为：(x)G(x)
在命题函数前加上量词(x)和(x)分别叫做个体变元x 被全称量化和存在量化。一般地说，命题函数不是命题，如果对命题函数中所有命题变元进行全称量化或存在量化，该函数就变成了命题。这一结论在例2.3中得到验证。
为假。 ⑵ 如果5大于3，则2大于6。解：设G(x,y)： x大于y a：5，b：3，c：2，d：6 该命题符号化为：G(a,b)→G(c,d) G(a,b)表示5大于3，它是真命题。G(c,d)表示2大于6，
ห้องสมุดไป่ตู้这是个假命题。所以G(a,b)→G(c,d)为假。
(3) 2 是无理数, 而 3 是有理数解：设F(x): x是无理数, G(x): x是有理数符号化为 F( 2) G( 3) 真值为 0 (4) 如果2>3，则3<4 解：设 F(x,y): x>y, G(x,y): x<y, 符号化为 F(2,3)G(3,4) 真值为1
谓词：刻划个体性质或个体之间相互关系的模式叫做谓词。谓词常用大写英文字母表示，叫做谓词标识符。
例如可以用F，G，H表示上面三个命题中谓词： F：„是优秀共产党员。 G：„比„高。 H：„坐在„和„的中间。
第2章谓词逻辑
一元谓词：与一个个体相关联的谓词。如上例中的F。二元谓词：与两个个体相关联的谓词。如上例中的G。三元谓词：与三个个体相关联的谓词。如上例中的H。
返回章目录
第2章谓词逻辑
课外作业
• 教材P59-60页: 练习题（需要做在练习本上）（1）（2） a)、c) 、d)、e)、 f)、i)、k)、l)
返回章目录

离散数学第二章

怎么符号化？怎么符号化？
5
3 量词的有关概念
1. 全称量词： “所有的”，“任何一个”，“每全称量词：所有的” 任何一个” 一个” 凡是” 一切” 一个”，“凡是”，“一切”表示个体域中每一表示，称为全称量词。用符号“ 个，用符号“∀”表示，称为全称量词。
如，所有的人都要呼吸。所有的人都要呼吸。
16
常用一阶逻辑中的基本等值式
1. 有限个体域有限个体域D={a1, a2, … ,an }中消去量词中消去量词等值式: 等值式
1) ∀xA( x) ⇔ A(a1 ) ∧ A(a2 ) ∧⋯∧ A(an );
2) ∃xA( x ) ⇔ A(a1 ) ∨ A(a2 ) ∨ ⋯ ∨ A(an ).
10
指导变项（指导变项（元）等概念
在合式公式∀ 和在合式公式∀xA和∃xA中，称x是指导变元，称A为相应量词中是指导变元，为相应量词作用域或辖域。的作用域或辖域。在辖域中x的出现称为在公式中的约束出现在辖域中的出现称为x在公式中的约束出现；的出现称为在公式A中的约束出现；公式A中不是约束出现的其它变元称为该变元的自由出现. 中不是约束出现的其它变元称为该变元的自由出现公式中不是约束出现的其它变元称为该变元的自由出现例1 指出下列公式中的指导变项、量词的辖域、个体变项的指出下列公式中的指导变项、量词的辖域、自由出现和约束出现. 自由出现和约束出现 1) 2) ∀xF(x,y)→∃x(G(x) ∧¬ ∀zP(x,z)) → ∀x ∃ y(A(x,y)→∃z(B(x) ∧P(x,z))) →
永假式如果在任何解释下均为假称A为矛盾如果A在任何解释下均为假解释下均为假,称为或称永假式式(或称永假式；或称永假式)；如果存在一个解释使A为真则称A为为真,则称可满足式如果存在一个解释使为真则称为可满足式；可满足式；

离散数学2

23
在上例中3个结果矩阵是在上例中个结果矩阵是: 个结果矩阵是
24
求传递闭包--Warshall算法求传递闭包--Warshall算法 --Warshall
设集合基数为n 构造n+1个矩阵W 设集合基数为n，构造n+1个矩阵W0,W1,W2, n+1个矩阵 …Wn,W0为t( R )的关系矩阵,Wn即为t( R )的关系矩阵 Wn,W )的关系矩阵,Wn即为的关系矩阵,Wn即为t( )的关系矩阵 (1)令 (1)令W0=MR (2)设Wi- 已求出，现求Wi (2)设Wi-1已求出，现求Wi 考虑Wi- 的第i 考虑Wi-1的第i列，列中为1的元素分别位于P1,P2…行， Wi 列中为1的元素分别位于P 行同时考虑第i 该行中为1的元素位于q 同时考虑第i行，该行中为1的元素位于q1,q2…列，则：列 i中第中第P 列的元素改为1 把W i中第PS行qt列的元素改为1； (3)重复(2)过程，直到求出Wn (3)重复(2)过程，直到求出Wn 重复(2)过程 (4)根据Wn写出t( (4)根据Wn写出t( R ) 根据Wn写出 2.5.3）（见书上例2.5.3）见书上例2.5.3
7
传递性：若ｘ到ｙ有边，ｙ到ｚ有边，则ｘ到ｚ必有边。
8
二元关系的性质对应于关系图，二元关系的性质对应于关系图，有：（1）自反性：每个顶点都有自回路，）自反性：每个顶点都有自回路，（2）反自反性：每个顶点都没有自回路；）自反性：每个顶点都没有自回路；（ 3）对称性：任二个顶点间或没有边，或有二）对称性：任二个顶点间或没有边，条方向相反的有向边；条方向相反的有向边；（ 4）反对称性：任二个顶点至多只有一条有向）反对称性：也即：或没有边，或只有一条有向边）边；（也即：或没有边，或只有一条有向边）有边，有边，（5）传递性：若ｘ到ｙ有边，ｙ到ｚ有边，）传递性：则ｘ到ｚ必有边。必有边。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

离散数学测试题2
一、选择题
1、若集合A ={1，2}，B ={1，2，{1，2}}，则下列表述正确的是( )．
A ．A ⊂
B ，且A ∈B B ．B ⊂A ，且A ∈B
C ．A ⊂B ，且A ∉B
D ．A ⊄B ，且A ∈B
2．设集合A= {1, 2, 3, 4, 5}上的偏序关系的哈斯图如下图所示，若A 的子集B= {3, 4, 5}，则元素3为B 的（）．
A. 下界
B. 最小上界
C. 最大下界
D. 最小元 3.设A （x ）：x 是人，B （x ）：x 是工人，则命题“有人是工人”可符号化为（）．
A ．(∃x )(A (x )∧
B (x )) B ．(∀x )(A (x )∧B (x ))
C ．┐(∀x )(A (x ) →B (x ))
D ．┐(∃x )(A (x )∧┐B (x )) 4．图G 如图一所示，以下说法正确的是 ( ) ．
A ．{(a, d )}是割边
B ．{(a, d )}是边割集
C ．{(a, d ) ,(b, d )}是边割集
D ．{(b , d )}是边割集
5、已知一棵无向树T 中有8个顶点，4度、3度、2度的分支点各一个，T 的树叶数为( )． A ．6 B ．4 C ．3 D ．5 二、填空题
1.设集合A ={0, 1, 2}，B ={1,2, 3, 4,}，R 是A 到B 的二元关系，
},,{B A y x B y A x y x R ⋂∈∈∈><=且且
则R 的有序对集合为．
2.设G 是连通平面图，v , e , r 分别表示G 的结点数，边数和面数，则v ，e 和r 满足的关系式．
3.已知一棵无向树T 中有8个结点，4度，3度，2度的分支点各一个，T 的树叶数为．
4.设集合A ={1，2}上的关系R ＝{<1, 1>,<1, 2>}，则在R 中仅需加一个元素，就可使新得到的关系为对称的．
5.()(()()(,))x P x Q x R x y ∀→∨中的自由变元为．三、逻辑翻译
1.将语句“他今天不去锻炼，仅当他没有时间．”翻译成命题公式．
2.将语句“所有的人都学习努力．”翻译成命题公式．
四、计算题
1.给出命题公式∧
∧
B
↔
⌝的主析取范式。

(C
⌝
A⌝
→))
∧
(
(C
A))
B
(
2.已知带权图G如右图所示．
(1) 求图G的最小生成树；(2)计算该生成树的权值．
五、证明题
1.对任意三个集合A, B和C，试证明：若A⨯B = A⨯C，且A≠∅，则B = C．
2. 试证明如下逻辑公式成立()()()(())
∃→⇒∀→。

x A x B x A x B
答案
一、选择题
1.A
2.B
3. A
4.C
5.D
二、填空题
1.{<1, 1>，<1, 2>，<2, 1>，<2, 2>}；
2.2.v -e +r =2；
3. 5；
4. <2, 1>；
5.(,)R x y 中的y
三、逻辑翻译
1.设 P ：他去锻炼；Q ：他有时间。

则命题公式为：⌝P →⌝Q ． 3.设():P x x 是人，():Q x x 学习努力；则命题公式为：()(()())x P x Q x ∀→．四、计算题
1. 解：方法1：列表法
设))(())((C B A C B A S ⌝∧⌝↔⌝∧∧→=
根据真值表中S 真值为1的赋值所对应的极小项的析取，即为S 的主析取范式。

由表可知
)()(C B A C B A S ∧∧∨⌝∧⌝∧⌝=
方法2：等值演算
))(())((C B A C B A ⌝∧⌝↔⌝∧∧→
)))(())((())((A C B C B A C B A ⌝→⌝∧⌝∧⌝∧⌝→⌝∧∧∨⌝= ))())((())((A C B C B A C B A ⌝∨∨∧⌝∧⌝∨∧∧∨⌝=
)))()(())(((())(((C B A C B C B A A C B A ∨∨⌝∧⌝∧⌝∨∨∨⌝∧∧∧∨⌝= ))()()(())(((C B A C A B A C B A ⌝∧⌝∧⌝∨∨∨∨∧∧∨⌝= )()()(C B A C B A C B A ∧∧∨∧∧∨⌝∧⌝∧⌝=
7
0)
()(m m C B A C B A ∨=∧∧∨⌝∧⌝∧⌝=
2. 解（1）图G 有6个结点，其生成树有5条边，用Kruskal 算法求其权最小的生成树T ：
第1步，取具最小权1的边；第2步，取剩余边中具最小权2的边；第3步，取剩余边中不与前2条边构成回路的具最小权3的边；
第4步，取剩余边中不与前3条边构成回路的具最小权5的边；第5步，取剩余边中不与前4条边构成回路的具最小权7的边．所求最小生成树T 如右图．
（2）该最小生成树的权为()1235718W T =++++=．五、证明题
1.证明
若B ＝∅，则A ×C ＝A ×B ＝∅，由于A ≠∅，所以C ＝∅，从而B ＝C ．若B ≠∅，则A B ⨯≠∅，
任意b B ∈，存在a A ∈，使,a b A B <>∈⨯，由于A ⨯B = A ⨯C ，所以,a b A C <>∈⨯，从而b C ∈，故B C ⊆．
A C A
B ⨯⨯≠∅＝，
C ≠∅
任意c C ∈，存在a A ∈，使,a c A C <>∈⨯，由于A ⨯B = A ⨯C ，所以,a c A B <>∈⨯，从而c B ∈，故C B ⊆．所以B C =．
2.证明：
（1）()() P x A x B ∃→ （2）()() T(1) E x A x B ⌝∃∨ （3）()() T(2) E x A x B ∀⌝∨ （4）()(()) T(3) E x A x B ∀⌝∨ （5）()(()) T(4) E x A x B ∀→。

离散数学2

合集下载

离散数学2联结词(否定、合取)

离散数学第二章关系

离散数学第二章

离散数学II

离散数学2

离散数学2联结词(否定、合取)

离散数学(第2版)

离散数学第2章谓词逻辑

离散数学第二章

离散数学2

文档推荐

最新文档

离散数学2

合集下载

离散数学2联结词(否定、合取)

离散数学第二章关系

离散数学第二章

离散数学II

离散数学2

离散数学2联结词(否定、合取)

离散数学(第2版)

离散数学第2章 谓词逻辑

离散数学第二章

离散数学2

文档推荐

最新文档

离散数学第2章谓词逻辑