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

离散数学第2讲

  • 格式：ppt
  • 大小：496.50 KB
  • 文档页数：106

下载文档原格式

  / 106

合集下载

离散数学第二章一阶逻辑知识点总结

离散数学第二章一阶逻辑知识点总结

离散数学第二章一阶逻辑知识点总结数理逻辑部分第2章一阶逻辑2.1 一阶逻辑基本概念个体词（个体）: 所研究对象中能够独立存在的具体或抽象的客体个体常项：具体的事物，用a, b, c表示个体变项：抽象的事物，用x, y, z表示个体域: 个体变项的取值范围有限个体域，如{a, b, c}, {1, 2}无限个体域，如N, Z, R, …全总个体域: 宇宙间一切事物组成谓词: 表示个体词性质或相互之间关系的词谓词常项：F(a)：a是人谓词变项：F(x)：x具有性质F一元谓词: 表示事物的性质多元谓词(n元谓词, n2): 表示事物之间的关系如L(x,y)：x与y有关系L，L(x,y)：x y，…0元谓词: 别含个体变项的谓词, 即命题常项或命题变项量词: 表示数量的词全称量词: 表示任意的, 所有的, 一切的等如x 表示对个体域中所有的x存在量词: 表示存在, 有的, 至少有一具等如x表示在个体域中存在x一阶逻辑中命题符号化例1 用0元谓词将命题符号化要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化(1) 墨西哥位于南美洲在命题逻辑中, 设p:墨西哥位于南美洲符号化为p, 这是真命题在一阶逻辑中, 设a：墨西哥，F(x)：x位于南美洲符号化为F(a)例2 在一阶逻辑中将下面命题符号化(1) 人都爱美; (2) 有人用左手写字分不取(a) D为人类集合, (b) D为全总个体域.解：(a) (1) 设G(x)：x爱美, 符号化为x G(x)(2) 设G(x)：x用左手写字, 符号化为x G(x)(b) 设F(x)：x为人，G(x)：同(a)中(1) x (F(x)G(x))(2) x (F(x)G(x))这是两个基本公式, 注意这两个基本公式的使用.例3 在一阶逻辑中将下面命题符号化(1) 正数都大于负数(2) 有的无理数大于有的有理数解注意: 题目中没给个体域, 一律用全总个体域(1) 令F(x): x为正数, G(y): y为负数, L(x,y): x>y x(F(x)y(G(y)L(x,y))) 或x y(F(x)G(y)L(x,y)) 两者等值(2) 令F(x): x是无理数, G(y): y是有理数,L(x,y)：x>yx(F(x)y(G(y)L(x,y)))或x y(F(x)G(y)L(x,y)) 两者等值几点注意：1元谓词与多元谓词的区分无特殊要求，用全总个体域量词顺序普通别能随便颠倒否定式的使用考虑：①没有别呼吸的人②别是所有的人都喜爱吃糖③别是所有的火车都比所有的汽车快以上命题应怎么符号化？2.2 一阶逻辑合式公式及解释字母表定义字母表包含下述符号：(1) 个体常项：a, b, c, …, a i, b i, c i, …, i1(2) 个体变项：x, y, z, …, x i, y i, z i, …, i 1(3) 函数符号：f, g, h, …, f i, g i, h i, …, i1(4) 谓词符号：F, G, H, …, F i, G i, H i, …, i1(5) 量词符号：,(6) 联结词符号：, , , ,(7) 括号与逗号：(, ), ，定义项的定义如下：(1) 个体常项和个体变项是项.(2) 若(x1, x2, …, x n)是任意的n元函数，t1,t2,…,t n是任意的n个项，则(t1, t2, …, t n) 是项.(3) 所有的项基本上有限次使用(1), (2) 得到的.个体常项、变项是项，由它们构成的n元函数和复合函数依然项定义设R(x1, x2, …, x n)是任意的n元谓词，t1,t2,…, t n 是任意的n个项，则称R(t1, t2, …, t n)是原子公式.原子公式是由项组成的n元谓词.例如，F(x,y), F(f(x1,x2),g(x3,x4))等均为原子公式定义合式公式（简称公式）定义如下：(1) 原子公式是合式公式.(2) 若A是合式公式，则(A)也是合式公式(3) 若A, B是合式公式，则(A B), (A B), (A B),(A B)也是合式公式(4) 若A是合式公式，则xA, xA也是合式公式(5) 惟独有限次地应用(1)~(4)形成的符号串是合式公式.请举出几个合式公式的例子.定义在公式xA和xA中，称x为指导变元，A为相应量词的辖域. 在x和x的辖域中，x的所有浮现都称为约束浮现，A中别是约束浮现的其他变项均称为是自由浮现的.例如, 在公式x(F(x,y)G(x,z)) 中,A=(F(x,y)G(x,z))为x的辖域，x为指导变元, A中x的两次浮现均为约束浮现，y与z均为自由浮现.闭式: 别含自由浮现的个体变项的公式.给定公式A=x(F(x)G(x))成真解释: 个体域N, F(x): x>2, G(x): x>1代入得A=x(x>2x>1) 真命题成假解释: 个体域N, F(x): x>1, G(x): x>2 代入得A=x(x>1x>2) 假命题咨询: xF(x)x F(x) 有成真解释吗？xF(x)x F(x) 有成假解释吗？被解释的公式别一定全部包含解释中的4部分.闭式在任何解释下基本上命题，注意别是闭式的公式在某些解释下也也许是命题.永真式（逻辑有效式）：无成假赋值矛盾式（永假式）：无成真赋值可满脚式：至少有一具成真赋值几点讲明：永真式为可满脚式，但反之别真谓词公式的可满脚性（永真性,永假性)是别可判定的利用代换实例可判某些公式的类型定义设A0是含命题变项p1, p2, …,p n的命题公式，A1,A2,…,A n是n个谓词公式，用A i处处代替A0中的p i (1i n)，所得公式A称为A0的代换实例.例如:F(x)G(x), xF(x)yG(y) 等基本上p q的换实例，x(F(x)G(x)) 等别是p q 的代换实例.定理重言式的代换实例基本上永真式，矛盾式的代换实例基本上矛盾式.2.3 一阶逻辑等值式等值式定义若A B为逻辑有效式，则称A与B是等值的，记作A B，并称A B 为等值式.基本等值式:命题逻辑中16组基本等值式的代换实例如，xF(x)yG(y) xF(x)yG(y)(xF(x)yG(y)) xF(x)yG(y) 等消去量词等值式设D={a1,a2,…,a n} xA(x)A(a1)A(a2)…A(a n)xA(x)A(a1)A(a2)…A(a n)量词否定等值式设A(x)是含x自由浮现的公式xA(x)x A(x)xA(x)x A(x)量词分配等值式x(A(x)B(x))xA(x)xB(x)x(A(x)B(x))xA(x)xB(x)注意：对无分配律，对无分配律例将下面命题用两种形式符号化(1) 没有别犯错误的人(2) 别是所有的人都爱看电影解(1) 令F(x)：x是人，G(x)：x犯错误.x(F(x)G(x))x(F(x)G(x))请给出演算过程，并讲明理由.(2) 令F(x)：x是人，G(x)：爱看电影.x(F(x)G(x))x(F(x)G(x))给出演算过程，并讲明理由.前束范式定义设A为一具一阶逻辑公式, 若A具有如下形式Q1x1Q2x2…Q k x k B, 则称A为前束范式, 其中Q i(1i k)为或，B为别含量词的公式.例如，x y(F(x)(G(y)H(x,y)))x(F(x)G(x))是前束范式, 而x(F(x)y(G(y)H(x,y)))x(F(x)G(x))别是前束范式.定理（前束范式存在定理）一阶逻辑中的任何公式都存在与之等值的前束范式注意:公式的前束范式别惟一求公式的前束范式的办法: 利用重要等值式、置换规则、换名规则、代替规则举行等值演算.换名规则: 将量词辖域中浮现的某个约束浮现的个体变项及对应的指导变项，改成其他辖域中未曾浮现过的个体变项符号，公式中其余部分别变，则所得公式与原来的公式等值.代替规则: 对某自由浮现的个体变项用与原公式中所有个体变项符号别同的符号去代替，则所得公式与原来的公式等值.例求下列公式的前束范式(1) x(M(x)F(x))解x(M(x)F(x))x(M(x)F(x)) （量词否定等值式）x(M(x)F(x))两步结果基本上前束范式，讲明前束范式别惟一.(2) xF(x)xG(x)解xF(x)xG(x)xF(x)x G(x) （量词否定等值式）x(F(x)G(x)) （量词分配等值式）另有一种形式xF(x)xG(x)xF(x)x G(x)xF(x)y G(y) ( 换名规则) x y(F(x)G(y)) ( 量词辖域扩张) 两种形式是等值的(3) xF(x)xG(x)解xF(x)xG(x)xF(x)x G(x)x(F(x)G(x)) （为啥？）或x y(F(x)G(y)) （为啥？）(4) xF(x)y(G(x,y)H(y))解xF(x)y(G(x,y)H(y))zF(z)y(G(x,y)H(y)) （换名规则）z y(F(z)(G(x,y)H(y))) （为啥？）或xF(x)y(G(z,y)H(y)) （代替规则）x y(F(x)(G(z,y)H(y)))(5) x(F(x,y)y(G(x,y)H(x,z)))解用换名规则, 也可用代替规则, 这个地方用代替规则 x(F(x,y)y(G(x,y)H(x,z)))x(F(x,u)y(G(x,y)H(x,z)))x y(F(x,u)G(x,y)H(x,z)))注意：x与y别能颠倒。

离散数学第一章(第2讲)

离散数学第一章(第2讲)

P Q P ∨Q
FF F FT T TF T TT T
（Ｐ∨Ｑ）ΛＰ
F F T T
¬（（Ｐ∨Ｑ）ΛＰ）
T T F F
P Q R ＱΛＲ Ｐ∨（ＱΛＲ)
FFF F
F
FFT F
F
FTF F
F
FTT T
TTTF F
T
TTT T
T
例２．写出命题公式 Ｐ∨（ＱΛＲ）的真值表
由上二例可见，２个命题 变元有４组真值指派；３ 个命题变元有23＝ ８组 真值指派，ｎ个命题变元 则有 2n个真值指派。
翻译：P ：今天是周六 R: 我们到圆明园玩 T:我们到动物园玩
Q:我们到颐和园玩 S:颐和园游人太多
前提： P (Q∨R), S Q, P ， S
结论： R∨T
(11) 设P:明天下雨，Q:明天刮风，R:我去学校，则下列命 题公式各表示什么意思。
1） (PQ) R 如果明天不是风雨交加，则我去学校。
2） (PQ) R 如果明天不下雨也不刮风，我才去学校。
3） P ∨ Q R 若明天下雨或刮风，则我不去学校。
§３命题公式的翻译
步骤如下： (1)找出各简单命题，分别符号化。 (2)选择适当的联结词，把简单命题逐个联结起来。
例. 将下列命题符号化. (1)李明是计算机系的学生，他住在312室或313室。 解：首先用字母表示简单命题。 P：李明是计算机系的学生。 Q：李明住在312室。 R：李明住在313室。 该命题符号化为：P（Q▽R）
《定义》：命题公式A在其所有可能的赋值下取得的值 列成的表称为A的真值表。
构造真值表的步骤如下： 1)找出给定命题公式中所有的命题变元，列出所有可能的 赋值。 2)按照命题公式的运算次序列出命题公式的各层次。 3)对应每个赋值，计算命题公式各层次的值，直到最后计 算出整个命题公式的值。

离散数学II

离散数学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
引言
• 课程意义
–离散数学是计算机科学的数学基础，其基本概念、 理论、方法大量地应用在数字电路、编译原理、数 据结构、操作系统、数据库系统、算法设计、人工 智能、计算机网络等专业课程中，是这些课程的基 础课程。

《离散数学(二)》讨论课内容

《离散数学(二)》讨论课内容
1. 集合 A = { n | n 是与 5 互质的自然数}，则加法和乘法哪个是 A 上的二元运算，为什么？ 2. 在实数集 R 上定义二元运算 为： a,bR, a b = a | b |, 问该二元运算是否满足交换率、 结合律和幂等律。 3. 求出上述二元运算 的左单位元、右单位元、左零元和右零元，若单位元存在则求出 逆元。
第九周 第 14 章 代数系统 14.3.2 群（剩余部分）
1. 设<G, ◦>是群，f 和 g 是两个 G 上的自同态，令 H = { x | f (x) = g (x), x G }, 证明：H 是 G 的子群。 2. 设<G, ◦>是交换群，n 是任意给定的整数，令 Gn = { x | x = an, a G }, 证明：Gn 是 G 的子群。 3. 写出群<Z42, ⊕>的所有生成元和子群，并画出子群格。
第四周 6.4 几种特殊图 6.4.3 哈密顿图 6.4.4 平面图
1. 证明所示图不是汉密尔顿图。
2. 证明: 足球是由几个五边形和六边形组成的。 （提示：先用多面体的缺角和为 720˚求出 顶点数。 ） 3. 证明: 6 个结点 12 条边的连通简单平面图中，每个面均有 3 条边组成。
第五周 第 7 章 7.1 无向树
第七周 第 14 章 代数系统 14.2 代数系统
1. 设 f 和 g 是两个<S, ◦>到<V, *>的同态，其中二元运算 *满足交换律和结合率，证明： h ( x ) = f ( x ) * g ( x ), 也是<S, ◦>到<V, *>的同态。 2. 请写出代数系统<N, × >的所有子代数系统。那么代数系统<N, +, × >的子代数系统有 哪些。(注：考虑代数常数) 3. 设 V1 和 V2 都是一个代数系统 V 的子代数系统， 那么 V1 V2 和 V1 V2 也是 V 的子 代数系统吗？若是证明之，若不是请举一例。

离散数学第讲2

离散数学第讲2

(3)设R2是任何一个关系，且有RR2A×A，R2是传递的。 对任意<a,b>∈R1，存在Rj(1≤j＜)，使得<a,b>∈Rj，
所以存在c1,c2,c3,…,cj-1∈A，使得：
2022/10/25
计算机学院
7
<a,c1>∈R,<c1,c2>∈R,<c2,c3>∈R,....,<cj-1,b>∈R。 因RR2，所以 <a,c1>∈R2,<c1,c2>∈R2,<c2,c3>∈R2,…,<cj-1,b>∈R2。 由R2是传递的，有： <a,c2>∈R2,<c2,c3>∈R2,<c3,c4>∈R2,…,<cj-1,b>∈R2。 一直下去，最终有：<a,b>∈R2。 所以，R1R2。
由归纳法知，对任意有的i∈N+,有Ri t(R)。
R1,所以
1) r(R)＝{<a,b>,<b,b>,<b,c>,<a,a>,<c,c>}； (2) 对任意a,b,c∈A，若<a,b>∈R1，<b,c>∈R1,
j:=j+1; j=2,A的第二列有两个1,即A(1,2)=A(3,2)=1
1)r(R1) r(R2)
3）集合A上的关系的对称传递闭包定义为st(R) ＝s(t(R)) 同上，我们还可定义sr(R),tr(R),ts(R),…
定理4.9 设R是集合A上的关系，则：
1)rs(R)＝sr(R)
2)rt(R)＝tr(R)
3)st(R)ts(R)
2022/10/25

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

离散数学讲义 第二章命题逻辑PPT课件


解 令P：我得到这本小说；Q：我今夜就读完它。
于是上述命题可表示为P→Q。
7
5．等值“”
定义2.2.5 设P和Q是两个命题，则它们的等值命
题是一个复合命题，称为等值式复合命题，记作“P Q” （读作“P当且仅当Q”）。
当P和Q的真值相同时,PQ取真,否则取假。
例10
P
Q
P Q
0
0
1
0
1
0
1
0
0
德.摩根定律
E11
PQP∨Q
E12
P Q (P∧Q)∨(P∧Q)
E13
P (QR) (P∧Q) R
E14
P Q (PQ)∧(QP)
E15
PQQP
23
三、等价式的判别
有两种方法：真值表方法，命题演算方法
1、真值表方法
例1 用真值表方法证明 E10： (PQ) PQ
解 令：A= (PQ)，B= PQ，构造A，B
一个复合命题，记作“P→Q”（读作“如果P，则Q”）。
当P为真，Q为假时，P→Q为假，否则 P→Q为真。
P
Q
P→Q
0
0
1
0
1
1
1
0
0
1
1
1
例8 若P：雪是黑色的；Q：太阳从西边升起；
R：太阳从东边升起。则P→Q和P→R所表示的命题都是真的.
例9 将命题“如果我得到这本小说，那么我今夜
就读完它。”符号化。
对于上述五种联结词，应注意到： 复合命题的真值只取决于构成它的各原子命题的真 值，而与这些原子命题的内容含义无关。
9
命题符号化
利用联结词可以把许多日常语句符号化。基本步骤如下：

离散数学第二章知识点

命题逻辑等值演算等值式定理：设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等（这里可以发现的是里面都只含有合取联结词，简单合取式结构就是由合取联结词和命题变项组成的一个公式）课本中的定理：命题变项及其否定统称为文字。

离散第2讲 广义并交、笛卡尔、归纳定义


如何在集合的基础上定义出次序的概念？ 可以是单个客体，
集合，甚至序偶
定义1.9：设a, b为任意对象，称集合{{a}, {a, b}} 为二元有序组，或序偶，简记作<a,b>。其中a称 为序偶<a,b>的第一分量，b称为序偶的<a,b>第二 分量。 定理1.17：对任意序偶<a,b>, <c, d>， <a,b>=<c, d>当且仅当a=c且b=d。
例如
= {0，1} +={0，1，00，01，10，11，000，001，010，01 1，……}
第2讲 集合的运算与归纳定义
归纳定义*
*= +∪{}
*可归纳定义如下：
1、基础条款：* 2、归纳条款：如果x*且 ，则 x* 3、终极条款：只有有限次应用条款1、2所得之元素才 是*之元素
∪{A, B} = AB
∩{A, B} = AB
∪{A, B, C} = ABC ∩{A, B, C} = ABC ∪{} = ∩{} =
∪{, {}} = {}
∩{, {}} = ∪{, A} =A
∩{, A} =
第2讲 集合的运算与归纳定义
序偶(ordered pairs)
1.1
1.2 1.3
集合的概念与表示
集合运算
集合的归纳定义
第2讲 集合的运算与归纳定义
集合的表示方法
列举法 描述法 试定义算术表达式的集合S
S = {123, 55, 1+2, －100， (99×3)／10, …} ? S = {x | x是一算术表达式} ? (1) 如果x是整数，则xS（是算术表达式） (2) 如果x, y S ，则(+ x) 、(– x) 、(x + y) 、(x – y) 、(x y) 、(x／y) 均S （均是算术表达式） (3)只有有限次应用条款1、2所得的符号序列S

离散数学第二章


种
相当于 “任意”,“凡是”,“所有”...
存在量词(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. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

特性谓词，例如在①、③中令个体域为
全体大学生，②和④中的个体域为全部 自然数，则可符号化为：
• ①(x)L(x)
• ③(x)I(x)
②(x)R(x)
④(x)P(x)
• 谓词前加上了量词，称为谓词的量化。
若一个谓词中所有个体变元都量化了， 则该谓词就变成了命题。这是因为在谓
词被量化后，可以在整个个体域中考虑
•
若x的论域是某中学的全体学生，则S(x)是假的；
• 若x的论域是某剧场中的观众，且观众中有大学生 也有非大学生的其它观众，则S(x)是真值是不确定的。
• 通常，把一个n元谓词中的每个个体的论 域综合在一起作为它的论域，称为n元谓 词的全总论域。定义了全总论域，为深 入研究命题提供了方便。当一个命题没 有指明论域时，一般都从全总论域作为 其论域。而这时又常常要采用一个谓词 如P(x)来限制个体变元x的取值范围，并 把P(x)称为特性谓词。
个体变项(varible) 表示不确定的泛指对象 用小写英文字母x,y,z,…来表示 例如： F(x): x是人。G(x): x是数。 •“存在着人”: ∃xF(x) •“仅有一人”: ∃!xF(x) •“万物皆数”: ∀xG(x)
个体常项(constant) 表示具体的特定对象 用小写英文字母a,b,c,…来表示 例如： a:王大明，b:王小明， G(x,y): x与y是兄弟, “王大明与王小明是兄弟”: G(a,b)
• 在 Lp中，命题是具有真假意义的陈述句。 从语法上分析，一个陈述句由主语和谓 语两部分组成。在 Lp中，为揭示命题内 部结构及其不同命题的内部结构关系，
就按照这两部分对命题进行分析，并且
把主语称为个体或客体，把谓语称为谓
词。
– １.个体、谓词和命题的谓词形式
• 定义2.1.1 在原子命题中，所描述的对 象称为个体；用以描述个体的性质或个 体间关系的部分，称为谓词。 • 个体，是指可以独立存在的事物，它可 以是具体的，也可以是抽象的，如张明， 计算机，精神等。表示特定的个体，称 为个体常元，以a，b，c…或带下标的ai， bi，ci…表示；表示不确定的个体，称为 个体变元，以x，y，z…或xi，yi，zi…表 示。
一命题。
•
函数的使用给谓词表示带来很大方便。
•
例如，用谓词表示命题：“对任意整数x，
x2-1=(x+1)(x-1)是恒等式”。 • 解：令I(x):x是整数，f(x)=x2-1，
g(x)=(x+1)(x-1)，E(x,y):x=y，则该命题可表示
成：(x)(I(x)E(f(x),g(x)))。
– ２.原子谓词公式
• 原子命题的谓词形式还可以进一步加以抽 象，比如在谓词右侧的圆括号内的n个个体 常元被替换成个体变元，如x1,x2,· · · ,xn，这 样便得了一种关于命题结构的新表达形式， 称之为n元原子谓词。 • 定义2.1.3 由一个谓词(如P)和n个体变元 (如x1，x2，…，xn)组成的P(x1，x2，…， xn)，称它为n元原子谓词或n元命题函数， 简称n元谓词。而个体变元的论述范围，称 为个体域或论域。
“恰有一个”、“存在唯一”等词语；!x称为
存在唯一量词，称x为指导变元。 • 全称量词、存在量词、存在唯一量词统称
量词。量词记号是由逻辑学家Fray引入的，有 了量词之后，用逻辑符号表示命题的能力大大 加强了。
•
例
试用量词、谓词表示下列命题：
•
• •
① 所有大学生都热爱祖国；
② 每个自然数都是实数； ③ 一些大学生有远大理想；
•
④ 有的自然数是素数。
• 解 令S(x)：x是大学生，L(x)：x热爱祖国，
N(x)：x是自然数，R(x)：x是实数，I(x)：
x有远大理想，P(x)：x是素数。 • 则例中各命题分别表示为： • ①(x)(S(x)L(x)) • ③(x)(S(x)I(x)) ②(x)(N(x)R(x)) ④(x)(N(x)P(x))
例1 用0元谓词将命题符号化 要求：先将它们在命题逻辑中符号化，再在谓词 逻辑中符号化 (1) 墨西哥位于南美洲 在命题逻辑中, 设 p: 墨西哥位于南美洲 符号化为 p, 这是真命题 在一阶逻辑中, 设a：墨西哥，F(x)：x位于南美洲 符号化为F(a)
例1(续)
(2) 2 2 是无理数仅当 3 是有理数 在命题逻辑中, 设 p： 2 是有理数. 2是无理数，q： 33 符号化为 p q, 这是假命题 在一阶逻辑中, 设F(x): x是无理数, G(x): x是有理 数符号化为 F F (( 22 )) GG ( (3 )3 ) (3) 如果2>3，则3<4 在命题逻辑中, 设 p：2>3，q：3<4. 符号化为 pq, 这是真命题 在一阶逻辑中, 设 F(x,y)：x>y，G(x,y)：x<y, 符号化为 F(2,3)G(3,4)
命题的真值了。
量词(举例) 设：F(x)：x是自然数。G(x)：x是偶数。 H(x) ： x是奇数。I(x,y)：x=y。 “有些自然数是偶数”。∃x(F(x)∧G(x)) “既有奇数又有偶数” 。∃xH(x)∧∃yG(y) “存在既奇又偶的数” 。∃x(H(x)∧G(x)) “存在唯一的自然数0”。∃!x(F(，有时还是 不能用符号来很准确地表达某些命题， 例如S(x)表示x是大学生，而x的个体域 为某单位的职工，那么S(x)可表示某单 位职工都是大学生，也可表示某单位有 一些职工是大学生，为了避免理解上的 歧义，在Lp中，需要引入用以刻划“所 有的”、“存在一些”等表示不同数量 的词，即量词，其定义如下：
• 当n=1时，称一元谓词；当n=2时，称为 二元谓词，…。特别地，当n=0，称为零 元谓词。零元谓词是命题，这样命题与
谓词就得到了统一。
• n元谓词不是命题，只有其中的个体变元用特定个 体或个体常元替代时，才能成为一个命题。但个体变元 在哪些论域取特定的值，对命题的真值极有影响。 • 例如，令S(x)：x是大学生。 • 若x的论域为某大学的计算机系中的全体同学，则 S(x)是真的；
•
有了项的定义，函数的概念就可用来表示
个体常元和个体变元。
•
例如，令f(x,y)表示x+y，谓词N(x)表示x是
自然数，那么f(2,3)表示个体自然数5，而
N(f(2,3))表示5是自然数。
• 这里函数是就广义而言的。
•
例如P(x):x是教授，f(x):x的父亲，c:张强，
那么P(f(c))便是表示“张强的父亲是教授”这
•
谓词，当与一个个体相联系时，它刻
划了个体性质；当与两个或两个以上个体
相联系时，它刻划了个体之间的关系。表
示特定谓词，称为谓词常元，表示不确定
的谓词，称为谓词变元，都用大写英文字 母，如P，Q，R，…，或其带上、下标 来表示。
例：命题“张明是位大学生” “张明”是个体，“是位大学生”是谓词 设S：是位大学生，c：张明， 则S(c)：张明是位大学生。 • 如，命题“武汉位于北京和广州之间” • 武汉、北京和广州是三个个体，而“…位于… 和…之间”是谓词，它刻划了武汉、北京和广州之间 的关系。 • 设P：…位于…和…之间，a：武汉，b：北京，c： 广州， • 则P(a，b，c)：武汉位于北京和广州之间。
几点注意： 1元谓词与多元谓词的区分无特别要求 用全总个体域量词顺序一般不要随便颠 倒 否定式的使用 思考： ① 没有不呼吸的人 ② 不是所有的人都喜欢吃糖 ③ 不是所有的火车都比所有的汽车快 以上命题应如何符号化？
2.2 谓词公式与翻译
– １.谓词公式
• 为了方便处理数学和计算机科学的逻辑 问题及谓词表示的直觉清晰性，将引进 项的概念。 • 定义2.2.1 项由下列规则形成： • ① 个体常元和个体变元是项； • ② 若f是n元函数，且t1，t2，…，tn是项， 则f(t1，t2，…，tn)是项； • ③ 所有项都由①和②生成。
• 定义2.1.4 ①符号称为全称量词符，用
来表达“对所有的”、“每一个”、
“对任何一个”、“一切”等词语；x
称为全称量词，称x为指导变元。
• ②符号称为存在量词符，用来表达“存
在一些”、“至少有一个”、“对于一
些”、“某个”等词语；x称为存在量 词，x称为指导变元。
•
*③符号!称为存在唯一量词符，用来表达
•
在该例的解答中，由于命题中没有指明个
体域，这便意味着各命题是在全总论域中讨论，
因而都使用了特性谓词，如S(x)、N(x)。而且 还可以看出，量词与特性谓词的搭配还有一定 规律，即全称量词后跟一个条件式，而特性谓 词作为其前件出现；存在量词后跟一个合取式， 特性谓词作为一个合取项出现。
• 如果在解答时，指明了个体域，便不用
• 定义2.2.2 若P(x1，x2，…，xn)是n元谓 词，t1，t2，…，tn是项，则称P(t1， t2，…，tn)为Ls中原子谓词公式，简称 原子公式。 • 下面，由原子公式出发，给出Lp中的合
式谓词公式的归纳定义。
• 定义2.2.3 合式谓词公式当且仅当由下 列规则形成的符号串 • ① 原子公式是合式谓词公式； • ② 若A是合式谓词公式，则(A)是合式谓 词公式； • ③ 若A，B是合式谓词公式，则(A∧B)， (A∨B)，(A→B)和(AB)都是合式谓词 公式； • ④ 若A是合式谓词公式，x是个体变元， 则(x)A、(x)A都是合式谓词公式； • ⑤ 仅有有限项次使用①、②、③和④形 成的才是合式谓词公式。
例3 在一阶逻辑中将下面命题符号化 (1) 正数都大于负数 (2) 有的无理数大于有的有理数 解 注意: 题目中没给个体域, 一律用全总个体域 (1) 令F(x): x为正数, G(y): y为负数, L(x,y): x>y x(F(x)y(G(y)L(x,y))) 或 xy(F(x)G(y)L(x,y)) 两者等值 (2) 令F(x): x是无理数, G(y): y是有理数, L(x,y)：x>y x(F(x)y(G(y)L(x,y))) 或 xy(F(x)G(y)L(x,y)) 两者等值