当前位置：文档之家 › DM-专题1：集合和二元关系

DM-专题1：集合和二元关系

  • 格式：ppt
  • 大小：962.50 KB
  • 文档页数：65

下载文档原格式

  / 65

合集下载

第三章 二元关系

第三章 二元关系

（4）整数集合I ＝ {…，-2，-l，0，l， 2，…} =｛xx是正整数,或零,或负整数｝ （5）偶整数集合 E ＝ {…，-4，-2，0，2，4，…} ＝{xx是偶数} ＝ {xxI且2x} (2x表示2整除x) （6）前n个自然数的集合 Nn＝{0，1，2，…，n-1} ＝ { x xN且0≤x＜n}
4、指出下列集合序列的排列规律，并依 此规律再写出两个后续集合： ，｛｝，｛,｛｝｝,｛， ｛｝，｛，｛｝｝｝，┅ 5、“如果AB, BC，那么AC‖对任 意对象A,B,C都成立吗？都不成立吗？举 例说明你的结论。 6、确定下列各命题的真、假； (1) (2) (3) ｛｝ (4) ｛｝
在集合论中，集合是一个不作定义的 原始概念（就像几何学中的点、线、面等 概念）。不过，上述关于集合概念的描述， 有益于对它的内涵和外延作直观的理解和 认识。 集合论的特点是研究对象的广泛性。 它总结出由各种对象构成的集合的共同性 质，并用统一的方法来处理。因此，集合 论被广泛地应用于各种科学和技术领域。
定义3 集合A称为集合B的子集合（或子 集，subsets），如果A的每一个元素都是B 的元素，即,若元素x属于A ,那么x属于B。 A是B的子集，表示为AB（或BA）， 读作“A包含于B‖（或“B包含A‖）。 A不是B的子集用AB来表示。 集合之间的子集关系或包含关系是集合 之间最重要的关系之一。读者必须彻底弄清 集合之间的子集关系和元素与集合之间的隶 属关系这两个完全不同的概念。
定理2 对任意集合A，A U。 此定理显然成立。 定理3 设A，B，C为任意集合，若A B , B C，则A C。 证.设x为A中任一元素．由于A B，因 此xB;又因为B C，故xC。这就是说， A的所有元素都是C的成员，故A C。 定理4 对任何集合A， A。 证 假设 A，即不是集合A的子集，于 是有元素x，但xA，而x与是空集 矛盾，因此 A。

二元 关系

二元 关系

1.4.3.传递性
例1.13 设A={a，b，c}，R，S，T是A上的二元关系，其中 R={<a，a>，<b，b>，<a，c>}， S={<a，b>，<b，c>，<c，c>}，T={<a，b>} 说明R，S，T是否为A上的传递关系。 解 根据传递性的定义知，R和T是A上的传递关系，S不是A上 的传递关系，因为<a，b>∈R，<b，c>∈R，但<a，c>R。
（2）设R，S都是A上的关系，A={1，2，3，4}。
R={<1，2>，<1，3>，<3，4>}，
S={<1，1>，<2，2>，<3，3>，<4，4>}， 即S为A上的恒等关系，则R◦S=S◦R=R。 如图所示：
1
。 。
。 4 。 3
2
（3）设R是A上的关系，S为A上的空关系，即S=，则 R◦S=S◦R=。
R在A上是反自反的 x（x∈A < x，x > R）
1.4.2
对称性和反对称性
定义1.12 设R是集合A上的二元关系，如果对于每个x，y∈A， 当<x，y>∈R，就有<y，x>∈R，则称二元关系R是对称的。 R在A上是对称的 x y（x∈A∧y∈A∧<x，y>∈R<y，x>∈R）
1.4.1 关系的自反性和反自反性
定义1.10 设R是集合A上的二元关系，如果对于每个xA，都 有<x，x>R，则称二元关系R是自反的。 R在A上是自反的 x（x∈A<x，x>∈R）
定义1.11 设R是集合A上的二元关系，如果对于每个xA，都有 < x，x > R，则称二元关系R是反自反的。

二元关系的性质及二元关系的应用（可编辑）

二元关系的性质及二元关系的应用（可编辑）

二元关系的性质及二元关系的应用引言在日常生活中,关系一词是大家在生活学习和工作中经常遇到和处理的概念,我们都熟知关系一词的含义,例如兄弟关系、上下级关系、位置关系等.在数学中关系可抽象为表达集合中元素之间的关系,如“4大于2”,“在点,之间”.在离散数学中关系是刻画元素之间相互联系的一个重要的概念,广泛应用于计算机科学技术如计算机程序的输入、输出关系,数据库的数据特性关系,其中关系数据库就是以关系及其运算作为理论基础的.近世代数利用等价关系将代数系统进行分类,进而加以研究.关系也是点集拓扑中一个重要概念,通过关系分类来研究集合元素之间的某种联系.熟练掌握关系的定义和性质,也是学好近世代数和点集拓扑的基础.最基本的关系就是二元关系,就是集合中两个元素之间的某种相关性.例如有三个人和四项工作.已知可以从事,可以从事,可以从事,那么人和工作之间的对应关系可以记作: 这是人的集合到工作的集合之间的二元关系.一基础知识定义1 设,为集合,用中元素为第一元素,中元素为第二元素,构成有序对,所有这样的有序对组成的集合叫做和的笛卡尔积,记作,符号化表示为.定义2 如果一个集合满足以下条件之一:⑴集合非空,且它的元素都是有序对;⑵集合是空集,则称这个集合是一个二元关系,通常记作大写的英文字母,二元关系也可简称为关系.对于二元关系,如果有序对,可记为,否则记为.例如, ,则为二元关系,不是二元关系,只是一集合,除非将和定义为有序对.二元关系中特别重要的是从到的关系与上的关系.定义3为集合,的任何子集所定义的二元关系叫做从到的二元关系,特别当时则叫做上的二元关系.集合上的二元关系的数目依赖于中的元素数,当含有个元素时即,则,的子集有个,每一个子集代表一个上的关系,所以上有个不同的关系.定义4 对任意的集合都有三种特殊的关系:①空集是任何集合的子集当然也是的子集,也是上的关系,称为空关系.②称为上的全域关系.③为上的恒等关系.给定集合,定义几种常用的关系:定义5 是实数集的任意非空子集,则称上的二元关系为上的小于等于关系.定义6 为非0整数集,则称上的二元关系为上的整除关系.定义7 设是整数集的任意非空子集,是任意正整数,则称上的二元关系为上的模同余关系.定义8 设是由一些集合构成的集合族,则称上的二元关系为上的包含关系.例:设,求上的包含关系.解:由于, 在日常生活、生产活动和科学研究中,人们常用点表示事物,用点与点之间是否有连线表示事物之间是否有某种关系,这样构成的图形就是图论中的图.定义9 一个无向图是一个有序的二元组,其中⑴是一个非空有穷集,称为顶点集,其元素称为顶点或结点.⑵是无序集的有穷多重子集,称为边集,其元素称为无向边,简称为边.定义10 一个有向图是一个有序的二元组,其中⑴是一个非空有穷集,称为顶点集,其元素称为顶点或结点.⑵是笛卡尔积的有穷多重子集,称为边集, 其元素称为有向边,简称边.通常用图形来表示有向图和无向图:用小圆圈或实心点表示顶点,用顶点之间的连线表示无向图,用带箭头的连线表示有向边.定义11设为一个有向图,,若从到存在通路,则称可达,记作.规定总是可达自身的,即.若且,则称与是相互可达的,记作.规定.与定义9和定义10有关的还有下面一些概念和规定.⑴无向图和有向图统称为图,但有时也常把无向图简称为图.通常用表示无向图,表示有向图,有时也用泛指图有向的或无向的.用,分别表示的顶点集和边集, ,分别是的顶点数和边数.有向图也有类似的符号.⑵设为无向图, ,称为的端点,与关联.若,则称与的关联次数为1;若,则称与的关联次数为2,并称为环.如果顶点不与边关联,则称与的关联次数为0.若两个顶点与之间有一条边连接,则称这两个顶点相邻.若两条边至少有一个公共端点,则称这两条边相邻.⑶设为有向图, ,称为的端点, 为的始点, 为的终点,并称与关联.若,则称为中的环.若两个顶点之间有一条有向边,则称这两个顶点相邻.若两个边中一条边的终点是另一条边的始点,则称这两条边相邻二关系的三种表示方法表示关系的方法有三种:集合表达式,关系矩阵和关系图.2.1 集合表达式由于关系是一种特殊的集合,当然可以用集合表达式表示.例如:设,则用集合表达式表示上的关系.⑴.⑵.解: ⑴⑵2.2 关系矩阵和关系图关系矩阵可以用来表示有穷集到的关系与上的关系,关系图只能表示有穷集上的关系.当关系中的元素较多时,利用关系矩阵和关系图可以形象直观的表示关系.设给定两个有限集合,,对应于从到的二元关系有一个关系矩阵,其中如果是有限集合上的二元关系或和含有相同数量的有限个元素,则其关系矩阵是方阵.而同时对应的关系图就是在平面上用个点分别表示中的元素,另外再在平面上画出个点分别表示中的元素,如果集合和中有相同的元素则用同一点表示.当时,则从点至画一条有向边,其箭头指向,否则就没有边联结.例从到的关系, 通常将和中的元素设定为升序顺序,则对应的关系矩阵为:对应的关系图为:特别地,当为上的二元关系时,如果,则对应于的关系矩阵是阶方阵,方阵中的元素应有: ……………… (★)其关系图表示可以在平面上仅画个点,有向边的规定不变.例如,则的关系矩阵是对应的关系图为实际上,除了二元关系可用图表示之外,图中还蕴含许多丰富的二元关系.从图论中图的定义简单分析,图有点、线和点边关系构成.根据图中“边”就可以获得图中点间的“邻接关系”、“可达关系”及点边之间的“关联关系”.在图中,这些关系都是在(★)式所规定的方法基础上来表示成矩阵. 下面就来看一下这几种关系在离散数学中的定义.邻接矩阵的定义:设有向图,,令为顶点邻接到顶点边的条数,称为的邻接矩阵,记作,或简记为.例如下图2.2.1, 写出其邻接矩阵有向图的邻接矩阵为: ;性质1 简单有向图的邻接矩阵是一个0,1的矩阵:对角线元素为0,但不一定对称.性质2 矩阵的各行和是相应顶点的出度,各个列和是相应顶点的入度。

集合和二元关系复习讲解

集合和二元关系复习讲解

XDC
温故而知新!
67--12
C
S
2.5 序偶与笛卡尔乘积
|
定义 由两个元素x,y按照一定的次序组成的二元组
S
称为有序偶对，简称序偶,记作<x,y>,其中，称x为<x,y>
W
的第一元素，y为<x,y>的第二元素。
U
例1 平面上点的坐标<x,y>，x,y∈R；中国地处亚洲<中
S
国，亚洲>，<上,下>,<左，右>等都是序偶。<操作码,地
U
S
例2 a年b月c日d时e分f秒可用下述六重有序组来
T
描述：<a,b,c,d,e,f>。
性质 <a1,a2,a3,…,an>＝<b1,b2,b3,…，bn>
当且仅当 ai＝bi（i＝1,2,3,…,n）。
XDC
温故而知新!
67--14
C
S
笛卡儿积
|
定义 A,B是两个集合，称集合
A×B＝{<x,y>|(x∈A)∧(y∈B)}
S
R是从A到B的一个二元关系， 称矩阵MR＝(rij)n×m为关系
R的关系矩阵或邻接矩阵，其中：
W
U
1, rij 0,
ai ,bj R (i 1,2,3,...,n; j 1,2,3,...,m) ai ,bj R
S
显然，关系矩阵是布尔矩阵。
T
注意 在写关系矩阵时，首先应对集合A和B中的元
定义，知A×B共有2|A|╳|B|个不同的子集。因此，从A到B不
同的关系共有2|A|╳|B|个。
XDC

第四章 二元关系1

第四章 二元关系1

| A1 A2 L An || A1 || A2 |L | An |
10/34
4.1关系的基本概念
一、关系的定义
定义：设n I且 A1,A2,,An为n个任意集合，
n
R
X
i1
Ai
(a) 称R为A1,A2,,An间的n元关系；
(b) 若n=2，则称R为A1到A2的二元关系n；
(c) 若 R ，则称R为空关系；若 称R为全关系；
3.5多重序元与笛卡尔乘积
一、序偶
定义：由两个具有固定次序的客体组成的序列， 称序偶，记作<x,y>。
{2,3}={3,2}
2,3 3, 2
3/34
一、序偶
序偶的相等：
x, y a,b ((x a) ( y b))
序偶<a,b>中，a称为第一元素，b称为第二 元素。两个元素不一定来自同一个集合，他 们可以代表不同类型的事务。
例：A={1,2,4}; B={3,5,6};
1
3
关系R={<1,3>,<2,6>,<2,5>}
2
5
4
6
A
B
一、关系图
例：设A={2,3,4,5,6},B={6,7,8,12}，从A到B的二元 关系R为R {x, y | x A y B x整除y}，画出其 关系图。
解：先求出R
R {2，6，2，8，2，12，3，6，3，12，4，8，4，12，6，6，6，12}
1
a
MR
[rij ]66
3 0 a 0
0 0
0 0
0 0
0 0
1 0
2
b
b 0 0 0 0 0 0

离散数学第4章 集合与关系-二元关系 -4.5-4.7

离散数学第4章 集合与关系-二元关系 -4.5-4.7
即：A/R = { [a]R | a∈A } 实例：令A={1, 2, …, 8}，A关于模 3 同余等价关系为
R=x,yx,yI∧x≡y mod 3
则R的所有等价类分别为：
[1]R= 1，4，7 [2]R= 2，5，8 [3]R= 3，6 于是，A关于R 的商集为： A/R = { {1, 4,7}, {2, 5, 8}, {3, 6} } A关于恒等关系和全域关系的商集为：
第4章 二元关系
模k同余关系
设x和y是两个整数，k是一个正整数，若x，y用k除的 余数相等，就称x和y模k同余，也称x和y模k等价。 记为 x ≡ y mod k
设x(y)用k除的商为t1 ( t2 )，余数为a1 ( a2 )，数学上将 x(y)表示成为：
x= k×t1＋a1， t1I，a1I且0≤a1＜k。 y= k×t2＋a2， t2I，a2I且0≤a2＜k。 若x，y用k除的余数相等，x-y= k×(t1-t2)，t1-t2I。 即x-y可以被k整除。 所以，x和y模k同余还可以描述为：x-y可以被k整除。 可以证明： x和y模k同余关系是等价关系。
第4章 二元关系
(3) 假设[a]R∩[b]R≠, 则存在z∈[a]R∩[b]R, 从而有 z∈[a]R∧z∈[b]R, 即<a,z>∈R∧<b,z>∈R 成立. 根据R 的对称性和传递性必有<a,b>∈R, 与a b矛盾.
(4) 先证
[x] A. 任取y∈
xA R
[x]
xA R
,则
y∈
[x]
xA R
第4章 二元关系
等价类
定义4.5.2 设R是非空集合A上的等价关系，aA，集合 x xA∧aRx 即x xA∧< a,x > R

第二章 二元关系(集合论讲义)

特别地，当 A = B 时， A 上的二元关系可以用方阵来表示。关系矩阵实际上是二元关系的 特征函数。 例 2.1 设 A = {2,3, 4} ， B = {3, 4,5, 6, 7} ，定义从 A 到 B 的整除关系如下：对于 ∀a ∈ A ，
∀b ∈ B ， aDb 当且仅当 a | b 。 ⎛0 1 0 1 0 ⎞ ⎜ ⎟ M ( D ) = ⎜1 0 0 1 0 ⎟ ⎜0 1 0 0 0⎟ ⎝ ⎠
下面定义另一些运算，通过这些运算可以由已知关系产生新的关系。 逆运算 首先通过关系的逆运算，由给定关系产生其逆关系。
定义 3.2 设 R 是从 A 到 B 的二元关系，如下定义从 B 到 A 的二元关系 R
−1
R −1 = {(b, a ) : (a, b) ∈ R} ，或 bR −1a 当且仅当 aRb ，
R1 ∪ R2 ： a( R1 ∪ R2 )b 当且仅当 aR1b 或 aR2b ； R1 ∩ R2 ： a( R1 ∩ R2 )b 当且仅当 aR1b 且 aR2b ； R1 − R2 ： a ( R1 − R2 )b 当且仅当 aR1b 且 a R2 b ；
R1 ： aR1b 当且仅当 a R1 b 。
5
注： M ( R1 R2 ) = M ( R1 ) ⋅ M ( R2 ) 。
例 3.2 设 A = { p, q, r , s} ， B = {a, b} ， C = {1, 2,3, 4} ，
R1 = {( p, a), ( p, b), (q, b), (r , a), ( s, a)} ， R2 = {(a,1), (a, 2), (b, 4)}
3
1
2
3
5
4
图 2.1 结点集及结点之间的弧集构成的有向图很自然直观地表示了一个关系。 这两种关系的表示形式给研究关系的运算和性质提供了极大方便。

四章节二元关系

4.1 二元关系及其表示法
• 定义4.2：设A，B是两个集合，称集合
A B { x, y | x A y B}
尔积(Descartes Product)。
为集合A与B的笛卡
例：设A={1,2}；B={a, b}则A ×B={<1,a>，<1,b>， <2,a>，<2,b>}；B ×A={<a, 1>，<a, 2>，<b, 1>， <b, 2>}。
元关系。
➢一般来说，若|A|=m，|B|=n，A到B上的二元关系共 2mn
有 个，A上的2共m2有 个二元关系；
➢特殊的二元关系：
(1). 空关系； (2). 全域关系：EA { x, y | x A y A} A A； (3). 恒等关系：I A { x, x | x A} 。
5/56
• 性质4.2：(1). | A ×B |=|A|×|B|(A, B为有限集
合)； (2).
A
， A
；
(3). 不适合交换律，即A×B ≠B×A(除非A，B=
或A=B)；
(4). 不适合结合律，(A×B)×C ≠A×(B×C)(除 非 A B C )； (5). 对∪和∩运算满足分配律，
(1).F (G H ) F G F H , (2).(G H ) F G F H F, (3).F (G H ) F G F H , (4).(G H ) F G F H F.
14/56
4.2 关系的运算
• 4.关系的幂运算 • 定义4.13：设R是集合A上的二元关系，则R的n次
17/56
• 1.关系的交，并，补，差运算 • 定义4.10：设R和S为A到B的二元关系，其并，交

离散数学第4章 集合与关系-二元关系 -4.1-4.2


证明：x,w(R∘S)∘T(z)(x,zR∘S∧z,wT)
(z)((y)(x,yR∧y,zS)∧z,wT)
(z)(y)((x,yR∧y,zS)∧z,wT)
(y)(z)(x,yR∧(y,zS∧z,wT))
(y)(x,yR∧(z)(y,zS∧z,wT))
(y)(x,yR∧y,wS∘T)x,wR∘(S∘T)
【例4.7】X=1,2,3,4,5，X上的二元关系R和S定义如下：
R=1,2,3,4,2,2
S=4,2,2,5,3,1,1,3
试求R∘S，S∘R，R∘(S∘R)，(R∘S)∘R，R∘R，S∘S，R∘R∘R
解：R∘S=1,5,3,2,2,5， S∘R=4,2,3,2,1,4
(R∘S)∘R=3,2，
R∘(S∘R)=3,2
都是用列举法表示的。 2.用描述法表示二元关系 设R是实数集，LR= x,y | xR∧yR∧x≤y， LR是
实数集R上的小于等于关系，是一个二元关系。
3.用矩阵表示二元关系 如果A，B是有限集，
A=a1, a2,„, am， B=b1, b2,„, bn，
R是A到B的二元关系，R的关系矩阵定义为： MR= rij mn
第4章 二元关系
4.2.2二元关系的复合运算（也叫合成运算）
定义4.2.2 （R与S的复合） 设X，Y，Z是集合，RX×Y，
SY×Z，则R与S的复合为：
R∘S = |<x, z> | y (<x,y>R<y,z>S) }
= x, zxX∧zZ∧(y)(yY∧x, yR∧y, zS)
[注]: R∘S 是从X到Z的二元关系，即R∘S X ×Z 。
<{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>} 类似的还可以定义A上的大于等于关系, 小于关系, 大于关 系, 真包含关系等等.

集合与二元关系

集合与关系部分习题参考答案习题三3.1 （1）假（2）真（3）真（4）真（5）假（6）假（7）假（8）真（9）假（10）真3.2 (1)A∪B={1,2,3,5,7,9,11}(2)A∩C={3}(3)(A∪B)∩C={1,5,7,9,11}(4)A－B={1,9}(5)C－D={3,6,12}(6)BÅD ={3,4,5,7,8,11}3.3 (1)A∪B={1,2,3,5,7,9,11} (2)A∩C={3} (3)(A∪B)∩C={1,5,7,9,11}(4)A－B ={1,9} (5)C－D ={3,6,12} (6)BÅD ={3,4,5,7,8,11} 3.4(1)如下图（2）（3）AB C（4）3.5（1）)P={Æ,{Æ}}(A（2）)P={Æ,{{1}},{1},{{1},1}}(A（3）)P={Æ,{Æ},{{1}},{{2}},{{1,2}},{Æ,{1}},{Æ,{2}},{Æ,{1,2}},(A{{1},{2}},{{1},{1,2}},{{2},{1,2}},{Æ,{1},{2}},{Æ,{1},{1,2}},{Æ,{2},{1,2} },{{1},{2},{1,2}},A}（4）P={Æ,{{1,1}},{{2,1}},{1,2,1},{{1,1},{2,1}},{{1,1},{1,2,1}},{{2,1},{1,2 )(A,1}},A}3.6 原式=((A∪(B－C))∩A)∪(B－(B－A))=A∪（A∩B）=A3.7（1）假。

例如，A={1,2},B={1,3},C={2,3}不成立（2）假。

例如，A=Æ, B={1},C={2}不成立3．8证明(A∪C)-(B∪C)=A-B-C。

（原题有误，右式少了C）证明：(A ∪C )-(B ∪C )= (A ∪C ) ∩C B=(A ∪C ) ∩C B =B C C A ))(( =B C A=C B A --3.9（1）(A ∩B )-C =A ∩(B -C )，右式左式=-===)()(C B A C B A C B A（2）A ∪(B -A )=A ∪B ， 右式左式=====B A E B A A A B A A B A ))()()()(（3）A -(A -B )=A ∩B ， 右式左式=====B A B A A A B A A B A A )()()(()(（4）A -(B -C )=(A -B )∪(A ∩C )， 右式左式====)()()(()(C A B A C B A C B A（5）(A ∪B )-C =(A -C )∪(B -C )， 右式左式=--===)()()()())(C B C A C B C A C B A（6）A ∪B =A ∪(B ∪(A ∩B ))。

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

21
一阶谓词逻辑基本概念

在命题逻辑中，我们把命题分析到简单命题为止，而简单命 题是不再进行分析的基本元素，因此，当推理涉及到简单命 题的结构时，命题逻辑对此是无能为力的。例如下面的推理 ： 所有的自然数都是实数，3是自然数。所以，3是实数。 根据数学方面的知识，我们知道这个推理是正确的。然而， 在命题逻辑中，这个推理的正确性是无法证明的，这是因为 上述推理中的三句话均是简单命题，且各不相同，如果把它 们形式化为命题逻辑中的公式，以p表“所有的自然数都是 实数”，以q表“3是自然数”，以r表“3是实数”，则推理 可以写为： (p∧q) → r

基本的等值式



双重否定律 AA 幂等律 AAA, AAA 交换律 ABBA, ABBA 结合律 (AB)CA(BC), (AB)CA(BC) 分配律 A(BC) (AB)(AC), A(BC) (AB)(AC) 德摩根律 (AB)AB (AB)AB 吸收律 A(AB)A, A(AB)A
一阶谓词逻辑基本概念

解： (1) 令F(x)：x是大学生；G(x)：x是二年级的； a：小王 。则原句形式化为： F(a)∧G(a) (2) 令F(x，y)：x是y的学生；a：小王；b：李老师。则 原句形式化为： F(a，b) (3) 令F(x，y)：x≤y；G(x，y)：x=y。则原句形式化为 (F(x，y)∧F(y，x))→G(x，y)
成真赋值
成假赋值
重言式（永真式） 矛盾式（永假式） 可满足式
等值式与基本的等值式
等值式 定义2.1 若等价式AB是重言式，则称A与B等值， 记作AB，并称AB是等值式 几点说明： 定义中，A, B, 均为元语言符号 A或B中可能有哑元出现. 例如，在 (pq) ((pq) (rr)) 中，r为左边公式的哑元.
一阶谓词逻辑基本概念

上面这些简单命题中，小王、2、3、5、6均是个体， “……是学生”，“……是素数”，“……整除……”， “……位于……与……之间”均是谓词。前两个谓词描述的 是一个个体的性质，称为一元谓词； 第三个表示两个个体 之间的关系，称为二元谓词； 第四个表示三个个体之间的 关系，称为三元谓词。以此类推，我们将描述n(n≥2)个个体 之间关系的谓词称为n元谓词。通常用大写字母F、G、H(可 加下标)来表示谓词。如： F表示“……是学生”； G表示“……整除……”； H表示“……位于……与……之间”。
7
合取联结词的实例
例2


将下列命题符号化. (1) 吴颖既用功又聪明. (2) 吴颖不仅用功而且聪明. (3) 吴颖虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学.
8
合取联结词的实例
解
令p:吴颖用功, q:吴颖聪明 (1) pq (2) pq (3) pq (4) 设p:张辉是三好生, q:王丽是三好生 pq (5) p:张辉与王丽是同学


(1)—(3) 为相容或 (4)—(5) 为排斥或, 符号化时(5)可有两种形式，而(4)则不能
11
蕴涵联结词
设p, q为两个命题，复合命题“如果p, 则q”称作p与 q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式 的后件，称作蕴涵联结词. 规定：pq为假当且仅当p为真 q为假. (1) pq 的逻辑关系：q为 p 的必要条件 (2) “如果 p, 则 q” 有很多不同的表述方法： 若p，就q 只要p，就q p仅当q 只有q 才p 除非q, 才p 或 除非q，否则非p，…． (3) 当 p 为假时，pq恒为真，称为空证明 (4) 常出现的错误：不分充分与必要条件
联结词集为{, , , , }，p, pq, pq, pq, pq为 基本复合命题. 其中要特别注意理解pq的涵义. 反复使用 {, , , , }中的联结词组成更为复杂的复合命题. 设 p: 2 是无理数，q: 3是奇数， r: 苹果是方的， s: 太阳绕地球转 则复合命题 (pq) ((rs) p) 是假命题. 联结词的运算顺序：, , , , , 同级按先出现者先运算.
p q
的逻辑关系：p与q互为充分必要条件
1 0 1 0 0
例5 求下列复合命题的真值 (1) 2 + 2 ＝ 4 当且仅当 3 + 3 ＝ 6. (2) 2 + 2 ＝ 4 当且仅当 3 是偶数. (3) 2 + 2 ＝ 4 当且仅当 太阳从东方升起. (4) 2 + 2 ＝ 4 当且仅当 美国位于非洲. (5) 函数 f (x) 在 x0 可导的充要条件是 它在 x0 连续.
命题公式
（1）单个命题命题常元或者变元是命题公式
（2）若A是命题公式，A也是命题公式 （3）若A,B是命题公式，则AB，AB
，
AB ，AB也是命题公式 （4）有限次应用（1）-（3）规则形成的符 号串才是命题公式，或称命题形式，简称公 式
命题公式
针对含变元的公式，可进行赋值
基本的等值式

零律 A11, A00 同一律 A0A. A1A 排中律 AA1 矛盾律 AA0 蕴涵等值式 ABAB 等价等值式 AB(AB)(BA) 假言易位 ABBA 等价否定等值式 ABAB 归谬论 (AB)(AB) A 注意：要牢记各个等值式，这是继续学习的基础
命题概念
例1 下列句子中那些是命题？ (1) 2是有理数. (2) 2 + 5 = 7. (3) x + 5 > 3. (4) 你去教室吗？ (5) 这个苹果真大呀！ (6) 请不要讲话！ (7) 2050年元旦下大雪. 假命题 真命题 不是命题 不是命题 不是命题 不是命题 命题，但真值现在不知道
定义1.4
12
蕴涵联结词的实例
例4
设 p：天冷，q：小王穿羽绒服，将下 列命题符号化 pq (1) 只要天冷，小王就穿羽绒服. pq (2) 因为天冷，所以小王穿羽绒服. pq (3) 若小王不穿羽绒服，则天不冷.
等价联结词
定义1.5
设 p, q为两个命题，复合命题“p当且仅当 q”称作p与q的等价式，记作pq，称作等价联结词 . 规定pq为真当且仅当p与q同时为真或同时为假.

命题分类：简单命题（也称原子命题）与复合 命题 简单命题符号化 用小写英文字母 p, q, r, …, pi, qi, ri (i1)表示简 单命题 用“1”表示真，用“0”表示假 例如，令 p： 是有理数，则 p 的真值为0， 2 q：2 + 5 = 7，则 q 的真值为1 p, q, r…可表示命题常元或者变元
等值演算
置换规则：设Φ(A)是含公式A的公式，用公
式B替换A，得到Φ(B)。如果A B,则 Φ(A) Φ(B) 由已知等值式，应用置换规则，推演出新的 等值式的过程，称为等值演算 例：证明p (q r ) 和(p q) r 等值 （教材P2）
命题相关小结

p, q, r, … 均表示命题.
10
析取联结词的实例





解 (1) 令p:2是素数, q:4是素数, pq (2) 令p:2是素数, q:3是素数, pq (3) 令p:4是素数, q:6是素数, pq (4) 令p:小元元拿一个苹果, q:小元元拿一个梨 (pq)(pq) (5) p:王小红生于 1975 年, q:王小红生于1976 年, (pq)(pq) 或 pq
一阶谓词逻辑基本概念

注意 (1) 多元谓词中变元的顺序不同，表示的意义也不同。如 G(x，y)表“x整除y”，而G(y，x)表“y整除x”。 (2) 在谓词逻辑中， 、∧、∨、→、 仍是联结词， 其含义和用法与命题逻辑中的相同。
【例】将下列语句形式化为谓词逻辑中的命题或命题函数。 (1) 小王是二年级大学生。 (2) 小王是李老师的学生。 (3) 如果x≤y且y≤x，则x=y。
一阶谓词逻辑基本概念


这里，a、b、c1、c2均是具体的个体，称为个体常元。一 般我们用F(x)表示“x是学生”，其中的x称为个体变元(简 称变元，亦称个体词)。类似地，我们也可用G(x，y)表示 “x整除y”。 由谓词符和变元符组成的符号串称为命题函数。只有谓词为 常元并将其中的变元代以具体的个体后，才能构成命题。例 如： “G(x，y)：x整除y。” 并不是命题，但若取a：2，b：6 ，则G(a，a)，G(a，b)以及G(b，a)均是命题，前两个是真 命题，第三个是假命题。G(a，a)、G(a，b)等称为0元谓词 ，它们不含个体变元，0元谓词即命题。
一阶谓词逻辑基本概念


这时F、G、H表示的是具体的谓词，称为谓词常元，否则， 称为谓词变元。 显然，单独的一个谓词(即使是谓词常元)并不能构成一个完 整的句子，必须以个体词取代“……”方能构成一个句子。 通常用小写的英文字母a、b、c(可加下标)等表示个体： “小王是学生”可符号化为F(a)，其中a表示小王。若用b 表示小李，则F(b)就表示“小李是学生”。若用c1表示2， 用c2表示6，则G(c1，c2)就表示“2整除6”
一阶谓词逻辑基本概念

而(p∧q)→r是一个可满足式，可知这个推理无法在 命题逻辑推理理论中得到证明。另外，命题“所有 的自然数都是实数”事实上隐含着“0是实数”， “1是实数”，“2是实数”，…，等无穷多个命题 ，单用一个p表示，很难体现这些。 因此，为了能够进一步深入地研究推理，需要 对简单命题做进一步的分析，将简单命题的结构分 解为个体词、谓词、量词等，并讨论它们与推理之 间的关系，这一部分的内容称为一阶逻辑(谓词逻辑 )。
一阶谓词逻辑基本概念

首先我们将简单命题的结构分解成个体和谓词。 个体(客体)——我们讨论的对象。可以是具体的，也可以是 抽象的。 个体域(论域)——个体所构成的非空集合。 全总个体域(无限域)——包含宇宙中一切事物的个体域 谓词——简单命题中，表示一个个体的性质或多个个体间的 关系的词。 之所以称之为谓词，是因为谓词和个体词一起构成了简单命 题中的主谓结构。如： 小王是学生。 3是素数。 2整除6。 3位于2与5之间。