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

离散数学(第3讲)

  • 格式：ppt
  • 大小：790.00 KB
  • 文档页数：28

下载文档原格式

  / 28

合集下载

离散数学第三章课件ppt

离散数学第三章课件ppt

以|P(A)|＝Cn0＋Cn1＋…＋Cnn＝2n。
定理3.6 设A和B是两个集合，则： (1)B∈P(A)BA。 (2)ABP(A)P(B)。 (3)P(A)＝P(B)A＝B。 (4)P(A)∈P(B)A∈B。 (5)P(A)∩P(B)＝P(A∩B)。 (6)P(A)∪P(B)P(A∪B)。
A∪B＝B。
反之，若A∪B＝B，因AA∪B，所以AB。 同理可证ABA∩B＝A。
定义3.7
设A和B为两个集合，所有属于A而不
属于B的元素组成的集合称为B对于A的补集
(Complement) ， 或 相 对 补 。 记 作 A － B ＝
{x|x∈A∧xB} 。 A － B 也 称 为 A 和 B 的 差 集
A的真子集，但A不是A的真子集。 注：∈与表示元素和集合的关系，而、与＝
表示集合和集合的关系。 例如，若A＝{0，1}，B＝{0，1，{0，1}}，则 AB且AB。
定理3.3 设A、B和C是三个集合，则
(1)(AA)。 (2)AB(BA)。 (3)AB∧BCAC。
证 仅证(2)和(3) 明 (2)AB x(x∈A→x∈B)∧x(x∈B∧xA)
例如，若A＝{0，{0}}，则P(A)A＝(P(A)－A)∪(A－ P(A))＝{，0，{{0}}，{0，{0}}}。
定理3.9 设A、B和C为三个集合，则： (1)AB＝BA。 (2)(AB)C＝A(BC)。 (3)A∩(BC)＝(A∩B)(A∩C)。
例1 设A和B为两个集合，且AB，则A∩CB∩C。
证 对任意的 x∈A∩C ，则有 x∈A 且 x∈C 。而 AB ， 明 由 x∈A 得 x∈B ，则 x∈B 且 x∈C ，从而 x∈B∩C 。所
以，A∩CB∩C。 例2 设A和B为两个集合，则ABA∪B＝BA∩B＝A。

离散数学 第3讲 同余关系和商代数

离散数学 第3讲 同余关系和商代数
定理1：等价关系～关于二元运算*是一个同余关系当且仅当对 任意a、b、c、d∈S, a～b和c～d 时有ac～bd。
证明： 必要性： 设～是关于运算*的同余关系,并对任意a、b、c、d∈S,假设 a～b和c～d。a～b蕴含着ac～bc,而c～d蕴含着bc～bd。根据～ 的传递性, 得出ac～bd。 充分性： ～是一等价关系, 假设对任意a、b、c、d∈S,当a～b和c～d 时,ac～bd。因为c～c,故如果a～b,那么ac～bc。类似地,ca～cb。
一、同余关系
同余关系定义: 设R为代数A=<S, *, △>的载体S上的等价关系, 如果在代 数运算*下仍能保持, 则称R是关于运算*的同余关系。
a b
a*c b*c
a b
c
△a △b
一、同余关系
例1：给定代数A=<I, ·>，I：整数集合，运算· 为普通乘法运算，R为I
上的模k相等(k∈I+)关系, 即xRy当且仅当x≡y(mod k)，现在证明R是 关于运算· 的同余关系。
由定理2可以看出，一 个同态可以诱导出一 个同余关系； 反过来， 可以证明一个同余关 系也可以导出一个同 态。
∵h为同态 ∴ h(△a)=△′h(a)，h(△b)=△′h(b)
∴ h(△a)= h(△b), ∴△aR△b，即R是关于运算△的同余关系；
ii）如果aRb，cRd，则h(a)=h(b),h(c)=h(d), ∴ h(a)*′h(c)= h(b)*′h(d)， ∵h为同态 ∴ h(a*c)=h(a)*′h(c)，h(b*d) = h(b)*′h(d) ∴ h(a*c)= h(b*d)， ∴ (a*c)R(b*d)，即R是关于运算*的同余关系。
(2) 证明h是双射函数。h: S/～→f(S)是单射：对任意x1、x2∈S, 若f(x1)

离散数学第三讲-范式与主范式

离散数学第三讲-范式与主范式

Mj mj
n 2 k
n 2 k
17
极小项与极大项之间的关系
3.
主析取范式与主合取范式的关系
例题： A (P Q ) R m1 m3 m5 m 6 m7 主合取范式 3 5 6 7 （ 1，，，，） 主析取范式
M0 M2 M4 （ 0 ，，） 2 4
(0,2,4) 其中表示合取.
16
极小项与极大项之间的关系
1.
极小项与极大项的关系

一个命题公式的主析取范式和主合取范式紧密相关, 在它们的简 记式中, 代表极小项和极大项的足标是互补的,
mi Mi,
2.

M i m i.
原命题A与其否命题A的关系
设命题公式A中含n个命题变元，且设A的主析取范式中含k个极 小项mil,mi2,…,mik则 A的主析取范式中必含2n-k个极小项,设为 mjl,mj2, …, ,
则称它为A 的合取范式。 合取式---称为积 析取式---称为和
3
1、范式---析取范式与合取范式
析取范式:
A A 1 A 2 A n ( n 1), n 1时，单个质合取式也是 A ：质合取式 i
析取范式
合取范式:
A B 1 B 2 B m ( m 1) m 1时，单个质析取式也是 B ：质析取式 i
(1)求出A的主析取范式中没包含的极小项mj1,mj2,··m j ·, (2)求出与(1)中极小项下标相同的极大项Mj1,Mj2,··M j ·, (3)由以上极大项构成的合取式为A的主合取范式.
n
n 2 k
.
.
2 k
18
2、主范式

离散数学(chapter3集合的基本概念和运算)PPT课件

离散数学(chapter3集合的基本概念和运算)PPT课件
离散数学
主讲教师
13.11.2020
1
第三章 集合的基本概念和运算
§3.1 集合的基本概念 §3.2 集合的基本运算 §3.3 集合中元素的计数
13.11.2020
离散数学
2
集合论 集合论是研究集合一般性质的数学分支,它的创 始人康托尔(G.Cantor ,1845－1918)。在现代数学中， 每个对象(如数，函数等)本质上都是集合，都可以用 某种集合来定义，数学的各个分支，本质上都是在研 究某一种对象集合的性质。集合论的特点是研究对象 的广泛性，它也是计算机科学与工程的基础理论和表 达工具，而且在程序设计，数据结构，形式语言，关 系数据库，操作系统等都有重要应用。本课程在第三， 四章中介绍集合论的内容。
如：
A∪B
E
A∩B
E
AB
E
~A
E
AB
E
13.11.2020
离散数学
15
二、文氏图 （Jahn Venn）
例4：用文氏图表示下面集合
13.11.2020
离散数学
16
二、文氏图 （Jahn Venn）
例5：用集合公式表示下面文氏图中的阴影部分
(1)A ∩ B ∩ C，
(2) (A∩B )∪(B∩C)∪(C∩A)
或A = B x(x A x B)
x(x A x B) x(x B x A)
13.11.2020
离散数学
8
四、集合之间的关系
3、真子集： B A。 BABABA BABA B=A
4、幂 集：集合A的全体子集构成的集合，记作P (A)。 符号化为 P (A) = { x | x A}
n 元集A的幂集P (A)含有2n个元素。

离散数学 第三-四章

离散数学 第三-四章
n i 1
Ai
(f) A (A∪B ), B (A∪B )
集合与关系 >集合的运算
交与 并的关系 定理3-2.1 设A、B、C为三个集合,则下列分配律 成立。 a) A∩(B∪C)=(A∩B)∪(A∩C) b) A∪(B∩C)=(A∪B)∩(A∪C) 定理3-2.2 设A、B为任意两个集合,则下列吸收律 成立 a) A∪(A∩B)=A b) A∩(A∪B)=A 定理3-2.3 A B 当且仅当 A∪B=B 或 A∩B=A。
集合与关系 > 集合的运算
本节重点掌握的概念: 集合, 集合相等,集合包含, 幂集。
本节重点掌握的方法: 集合的表示, 求幂集.
作业
3-1 （1）（a）,（c） ,（e）
（3） （4） （a）,（c） ,（e） (5) (6) （a）,（c） ,（e） (9)
集合与关系 >集合的概念和表示法
上节知识点: 1. 集合的概念 2. 集合的表示 3 集合之间的关系 4 空集和全集 5 幂集(power set)
A-B
E B
A
集合与关系 >集合的运算
• 绝对补 定义3-2.4 设E为全集,任一集合A关于E的补 E-A, 称为集合A的绝对补,记作~A。
即 ~ A={ x| xE ∧ xA}
集合与关系 >集合的运算
(3) 集合的补(complement) 定义3-2.3 设A、B为任意两个集合,所有属于A而 不属于B的一切元素组成的集合S称为B对于A的 补集,或相对补,记作A-B。 即 A-B={ x| xA ∧ xB} 或 xA-B xA但 xB
例如 A={2, 5, 6} B={1, 2, 4, 7, 9} A-B={5, 6} B-A={1,4,7,9} E - 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)

《离散数学》课件-第3章集合的基本概念

17
例题
计算以下幂集：
，{}；{，{}}
解：
P()={} P({})={，{}} P({，{}})= {, {}，{{}},{，{}}}
18
3.3 集合的运算
集合的运算 并，交，补（绝对补），差（相对补－），和对称差等。
19
集合的并运算
• 定义3.3.1 设A，B为集合，由A和B的所有元素组成的集 合称为A与B的并集， 可表示为： AB={x|xAxB} 其文氏图：
其文氏图如下：
~E = ， ~ = E， ~（~A）= A A ~A = ， A ~A = E
27
德.摩根定律
• 定理3.3.5 设A，B为任意二个集合，则有： • （1） （AB）= A B • （2） （A B）= A B • 证明 设E为全集，显然有AE=A，AE=E成立。 • （1） （AB）= {x | xEx（AB）}= {x |
据的增加、删除、修改、排序，以及数据间关系的描述。
集合论在计算机语言、数据结构、编译原理、数据库与
知识库、形式语言及人工智能等许多领域得到广泛的应
用。
2
3.1 集合及其表示
• 集合是由一些对象聚集在一起构成的。 例如，全体整数 全体中国人 26个英文字母
• 构成集合的对象可以是各种类型的事物。 • 定义3.1.1 集合中的对象叫集合的元素，或成员。
• 集合中的元素可以具有共同性质，也可以表面上看起来不相干。
• 如{2，Tom，计算机，广州}
• 在集合论中，规定元素之间是彼此相异的，并且是没有次序关 系的。
例如，{3,4,5},{3,4,4,5,5},{5,3,4}都是同一个集合。
• 例如，A={3,4,5},

《离散数学》第3章集合


(5) A B (6) ~ (A B)
{2, 4,5} {3}
(7) (A B) ~ C
{1, 3, 5}
(8) (A B) (A C) {1, 4}
二、文氏图 (John Venn)。
1、文氏图。
(1) 用大矩形表示全集 E，
(2) 矩形内的圆表示集合， (3) 除特殊情形外，一般表示两个集合的圆是相交的， (4) 圆中的阴影的区域表示新组成的集合。
其中 A, B 分别表示 A、B的元数．
把包含排斥定理推广到n个集合的情况可用如下定
理表述：
设A1, A2 , A为n 有限集合，其元数分别为 A1 , A2 ,, An ，则
n
A1 A2 An Ai Ai Aj
Ai Aj Ak
i 1
1i jn
解： P(A) ,{,2},{2}, A
第二节 集合的运算
内容： 集合的运算，文氏图，运算律。 重点：(1) 掌握集合的运算
A B, A B, A B, ~ A, A B
(2) 用文氏图表示集合间的相互 关系和运算，
(3) 掌握基本运算律的内容及运用。
一、集合的运算。
例1、 ，A 0,1, B a,b,c
求 A B，B A，A A，A， B。
解：A B 0, a , 0,b , 0, c , 1, a , 1,b , 1,c
(1) A 解： P(A) {}
(2) A {} 解： P(A) {, A}
(3) A ,{}
解：P(A) ,{},{}, A
(4) A 1,{2,3}
解：P(A) ,{1},{2,3}, A
(5) A {, 2},{2}

离散数学(第3讲)


2018/11/12
计算机学院
27
（6）若析取范式的某一个短语中缺少该命题公式中所 规定的命题变元P ，则可用公式： （～Ｐ∨Ｐ）∧Q=Q 将命题变元 P 补进去，并利用分配律展开，然后合并 相同的短语，此时得到的短语将是标准的极小项； （7）若合取范式的某一个子句中缺少该命题公式中所 规定的命题变元P ，则可用公式： （～Ｐ∧Ｐ）∨Q=Q 将命题变元 P 补进去，并利用分配律展开，然后合并 相同的子句，此时得到的子句将是标准的极大项。 （8）利用幂等律将相同的极小项和极大项合并，同时 利用交换律进行顺序调整，由此可转换成标准的主析 取范式和主合取范式。
2018/11/12 计算机学院 8
求一个命题公式的与之等价的析取范式和合取 范式，其步骤如下： （1）利用等价公式中的等价式和蕴涵式将公式 中的→、用联结词～ 、∧、∨来取代； （ 2 ）利用德 摩根定律将否定号┐移到各个命 题变元的前端； （3）利用结合律、分配律、吸收律、幂等律、 交换律等将公式化成其等价的析取范式和合取范 式。
demorgan定律可知对公式的否定可以直接作用到原子本身并且把公式中的变成把变成即得201521计算机学院结合律分配律该式正好是b左端的对偶式由a及对偶原理得证该式正好是右端的对偶式201521计算机学院一个命题公式可有无穷多个和它等价的命题公式用真值表或等价变换证明它们是否等价往往比较困难甚至连计算机也不能解决
2018/11/12
计算机学院
14
主（特异、正则）合取范式
定义1-4.4 在n个变元的基本和（子句）中，若每一个变 元与其否定并不同时存在，且二者之一必出现且仅出现一 次，则这种基本和称为极大项。 由有限个极大项组成的合取式称为 主合取范式。 以下是由两个原子构成的极大项的真值表 P 1 1 0 0 Q 1 0 1 0 P∨Q 1 1 1 0 P∨～Q 1 1 0 1

《离散数学》第三章集合的基数

第三章 集合的基数
本章讨论集合论中较为困难的问题—集 合的基数问题；但只限于对基数作一简 单介绍；如学时较少可不讲本章或对本 章作恰当的删减.
本章主要概念为:集合的等势、有限集与 无限集、可数集与不可数集及较为常见 的集合的基数.
返回首页
1 2020/2/14
第一节 无穷集的概念
本节主要内容: 1.两个集合等势的定义； 2.基数的概念:基数是集合的一种性质，一
3.设A是任意集合,P(A)为A的幂集,则P(A)的基 数大于A的基数.
返回本章首页
4 2020/2/14
本章小结
本章的主要内容有：集合的等势、有限 集与无限集、可数集与不可数集、较为 常见的集合的基数等.集合的基数反映了 集合的元素的多少，它是集合的一种性 质，一种与该集合等势的集合构成的集 合族的共同性质.
种与该集合等势的集合所构成的集合族 的共同性质，即任何两个集合，如果它 们等势，它们便有相同的基数 （Von.Neumann的观点）； 3.利用等势的概念来定义有限集与无限集.
返回本章首页
2 2020/2/14
第二节 可数集与不可数集
可数集是无限集中最简单的一种，本节把无 限集区分为可数集与不可数集，主要结论有:
1.任意可数集都有一个与其等势的真子集; 2.任意一个无限集都包含一个可数子集； 3.可数集的任意无限子集是可数集； 4.可数集与有限集的并集是可数集； 5.两个（因而有限个）可数集的并集仍是可数
集； 6.可数个可数集的并集是可数集； 7.两个（因而有限个）可数集合的笛卡尔积仍
然是可数集.
Hale Waihona Puke 返回本章首页返回本章首页
5 2020/2/14
3 2020/2/14
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2013-7-4 计算机学院 26
基本要求
1、深刻理解等价式的定义，知道公式之间 的等价关系具有自反性、对称性、传递性； 2、牢记基本等价式的名称及它们的内容； 3、熟练地应用基本等价式及置换规则进行 等价演算 4、理解对偶原理及在等价演算中的应用 5、理解逻辑联结词功能完备集和最小功能 完备集的概念
2013-7-4
计算机学院
25
根据定义,我们知道{↑}、{↓}是最小的功 能完备集，那么{～，∨，∧}是不是最小功能 完备集？由于P∨Q～(～P∧～Q)，可见∨可 由{～，∧}表达；同理, P∧Q～(～P∨～Q) , 因而∧可由{～，∨}表达，这说明{～，∨，∧} 不是最小功能完备集，但是 在实际应用中，普 遍采用的功能完备集却是{～,∨,∧},这也是逻 辑系统中最主要的3个常用联结词。
2013-7-4
计算机学院
5
替换定理
定理1.2设G1是G的子公式(即 G1是公式G的一
部分)，H1 是任意的命题公式，在G中凡出现G1
处都以H1 替换后得到新的命题公式H，若G1
H1，则G H。
替换定理是经常使用的重要定理。
定理1.3公式G、H等价的充分必要条件是公 式 GH是永真公式。 此定理是从另一角度来看待等价性
2013-7-4 计算机学院 9
例1-3.2（续）
所以该电路图可简化为：
P Q R
2013-7-4
计算机学院
10
例1-3.3
证明P∨┐((P∨┐Q)∧Q) 是永真公式。
证：P∨┐((P∨┐Q)∧Q) P∨┐(P∨┐Q)∨┐Q (De Morgan定律) (P∨┐Q)∨┐(P∨┐Q) (交换律) (结合律) T ■（矛盾律）
2013-7-4
计算机学院
11
对偶式
E3 ～E18 ，E23 ～E24 都是成对出现的，它是逻辑系 统对偶性的反映，即对偶式。利用对偶式可以 扩大等价式的个数，也可减少证明的次数。
定义1.13：设A和A*是两个包含、∨、∧的命题 公式。如果把A中的联结词∨换成∧，把∧换成 ∨，把Ｔ换成Ｆ，把Ｆ换成Ｔ后得到的正是A* ， 则称A*是A的对偶公式。 如公式（P∨Q）∧R的对偶式为（P∧Q）∨R ～P∨（Q∧R）的对偶式为～P∧（Q∨R）
2013-7-4
计算机学院
19
这些等价式告诉我们，↑可由∧和～表
示出来，↓可由∨和～表示出来，反过
来，↑和↓都可以单独表示出所有已知
联结词，它们的这一性质使得在逻辑电 路设计中只用一种门式电路元件就能实 现任何电路功能，当然，元件的数量通 常也显得更多。
2013-7-4 计算机学院 20
还有一个二元联结词“ ”,称为条件否定， 可以用下面的真值表定义： P 1 1 Q 1 0 P Q
冯伟森
Email：fws365@ 2013年7月4日星期四
1.3 命题公式的等价
定义1.12 设G、H是公式，如果在任意解释Ｉ 下，G与H的真值相同，则称公式G、H是等价的 ， 记作GH。
等价式的性质: 1）自反性：A A 2）对称性：若 A B，则 B A 3）可传递性:若 A B，B C，则A C
PQ ～Q ～P
P 1
1 0 0
Q 1
0 1 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 0 1 1 1 0 1 1 1 0
1 0 1 1 0 1 1 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 1 1 1 0 0 1 0
Ｐ∨Q P→Q PQ
式。
其次，如果要求用计算机来判断命题公式G、
H是否逻辑等价，即GH那是办不到的，然而计
算机却可“计算”公式GH是否是永真公式。
2013-7-4 计算机学院 7
等价式的判定
1.真值表法 2.公式推演（等价变换） 例1-3.1：试证 P→Q ～Q→～P 证：P→Q ～P∨Q 蕴涵 E2 ～P∨～～Q 双重否定 E19 ～～Q∨～P 交换律 E5 ～Q→～P 蕴涵 E2
2013-7-4 计算机学院 12
问题：如果两个公式等价，那么它们的对偶式是否也是 等价的？ 定理1.4 ：设P1,P2,…Pn 是公式A和A* 中的所有命题变元， 则 ～A（P1,P2,…Pn）A*（～P1,～P2,…,～Pn） 证：∵由 De Morgan定律可知 ～（P∨Q） ～P∧～Q， ～（P∧Q） ～P∨～ Q ～T F， ～F T ∴对公式的否定可以直接作用到原子本身，并且把公式 中的∧变成∨，把∨变成∧，即得 ～A（P1,P2,…Pn）A*（～P1,～P2,…,～Pn）
2013-7-4
计算机学院
2
基本等价式——命题定律
1. Ｅ1: GH (G→H)∧(H→G) 2. Ｅ2：(G→H) (～G∨H) 3. Ｅ3：G∨G G Ｅ4：G∧G G 4. Ｅ5：G∨H H∨G Ｅ6：G∧H H∧G 5. Ｅ7：G∨(H∨S) (G∨H)∨S Ｅ8: G∧(H∧S) (G∧H)∧S 6. Ｅ9：G∨(G∧H) G Ｅ10：G∧(G∨H) G
Q P
23
0
1 0 1
0
0 1 1
0
0 0 1
0
0 1 0
0
1 0 0
1
0 0 0
2013-7-4
计算机学院
显然公式1是永真式，2代表矛盾式，3代表 Ｐ∨Q，4代表Q→P,5代表P→Q，6代表P↑Q， 7 是P，8是Q，9代表PQ，10代表PQ，11代表～Q ，12代表～P，13代表P↓Q，14代表Q 表P P,15代
0
1
0
0
1
0
0
0 Q～(P→Q)
计算机学院 21
显然，P
2013-7-4
至此我们定义了9个联结词，其中1
个一元联结词，8个二元联结词。那么，
还能不能定义出新的联结词呢？下面是 含两个命题变元的所有公式的真值表所 能取得的情况：
2013-7-4
计算机学院
22
P↑Q
P↓Q P
Q
P∧Q
T F
Q→P
P Q
2013-7-4 计算机学院 6
“” 与“”的区别
首先，双条件词“”是一种逻辑联结词，
公式GH是命题公式，其中“”是一种逻辑运
算，GH的结果仍是一个命题公式。 而逻辑等价“”则是描述了两个公式G与H 之间的一种逻辑等价关系，GH表示“命题公式 G等价于命题公式H”，GH 的结果不是命题公
2013-7-4
计算机学院
27
习题一
5（1）（3）、6、 8(1)（3）、9、10、
2013-7-4
计算机学院28Fra bibliotek2013-7-4 计算机学院 14
1.4
联结词的完备集
前面我们已经介绍了最常见的6种逻辑联结 词。他们都和自然语言中使用的联结词紧密相关， 易于理解。不同联结词产生的真值表是互不相同
的，根据对含两个命题变元的公式的解释方式看，
共有2*2=4种不同的解释，因而公式的真值表相
应有2*2*2*2=16种可能结果。对其中每一种真值
2013-7-4 计算机学院
(等价律) (蕴涵律) (幂等律)
(交换律) (结合律)
(吸收律)
3
基本等价式（续）
7. Ｅ11：G∨(H∧S) (G∨H)∧(G∨S) (分配律） Ｅ12：G∧(H∨S) (G∧H)∨(G∧S) 8. Ｅ13：G∨F G (同一律) Ｅ14：G∧T G 9. Ｅ15：G∨T T (零律) Ｅ16：G∧F F 10.Ｅ17：G∨～G T (矛盾律) Ｅ18：G∧～G F
1 1 0 0
2013-7-4
Q
1 0 1 0
P↑Q
0 1 1 1
计算机学院 17
P 1
1 0 0
Q 1
0 1 0
P↓Q 0
0 0 1
由真值表可以看出
P↑Q～（P∧Q）,
P↓Q ～（P∨Q）
2013-7-4 计算机学院 18
根据联结词↑和↓的定义，不难证明下面的 等价式。 ① P↑P～（P∧P）～P ② ( P↑Q)↑( P↑Q) ～( P↑Q) P∧Q ③ ( P↑P)↑(Q↑Q) ～P↑～Q ～（～P∧～Q）P∨Q ④ P↓P～（P∨P）～P ⑤ ( P↓Q) ↓( P↓Q) ～( P↓Q) P∨Q ⑥ ( P↓P) ↓(Q↓Q) ～P↓～Q ～（～P∨～Q）P∧Q
Q，16代表P∧Q，可见，已定义的9个联
结词就是全部可以定义的联结词。
2013-7-4
计算机学院
24
定义 1.15
设S 是由某些联结词构成的集合，
如果每个逻辑联结词的功能都能够由S中的联结
词实现，则称S是逻辑联结词的一个功能完备集；
进一步，如果去掉S中的任何一个联结词后，至 少有一个联结词的功能不能由S中剩余的联结词 实现时，则称S是逻辑联结词的一个最小功能完 备集。
2013-7-4 计算机学院 13
对偶原理（定理1.5）
设A和B是两个命题公式，若A B， 则 A* B*
例1-3.4 证明（a）～(P∧Q)→(～P∨(～P∨Q) ～P∨Q （b）(P∨Q) ∧(～P∧(～P∧Q)) ～P∧Q 证明:（a） ～(P∧Q)→(～P ∨(～P∨Q)) (P∧Q)∨(～P∨(～P∨Q)) （蕴涵） (P∧Q)∨～P∨Q (幂等律) ((P∨～P)∧(Q∨～P))∨Q (结合律) （分配律） ～P∨Q∨Q （矛盾律）(同一律) 该式正好是右端的对偶式 ～P∨Q (幂等律) （b） 该式正好是（b）左端的对偶式, 由（a）及对偶原 理得证
表都应该存在相应的联结词。下面从真值表取值