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

离散数学 第二讲

  • 格式：pdf
  • 大小：134.49 KB
  • 文档页数：34

下载文档原格式

  / 34

合集下载

离散数学2PPT课件

离散数学2PPT课件
在讨论Ａ与Ｂ是否有相同的真值表时，应将哑元考虑在内， 即将Ａ、Ｂ都看成含所有p1 , p2 , … pn的命题公式，如果在所有 2n个赋值下，Ａ与Ｂ的真值相同，则ＡＢ为重言式。
3/25/2021
2021
4
定义
CHAPTER TWO
定义2.1 设A ,B 是两个命题公式，若A, B构成的等价式A ↔ B为 重言式，则称A与B是等值的, 记为A⇔B。
3/25/2021
2021
11
例24
证明：(p→q)→r
⇔
p→(q→r）.
CHAPTER TWO
证 方法一：真值表法。
方法二：观察法。 方法三: 记A=(p→q)→r, B= p→(q→r)。先将A,B等值演算
化成易于观察真值的公式，再进行判断。
A=(p→q)→r⇔(┐p∨q)→r
(蕴含等值式)
⇔ ┐(┐p∨q)∨r
(交换律，结合律)
(10) ⇔ p∧(1∨p)
（排中律）
(11) ⇔ p∧1
（零律）
(12) ⇔ p
（同一律）
(13) 可见，（3）中公式不是重言式，因为00，01 都是成假赋
值；它也不是矛盾式，因为10，11 都是其成真赋值，故它是可
3/25/20满21足式。
2021
15
例2.6
CHAPTER TWO
B2∧C3∧D10, B3∧C1∧D2p∧┐q∧r, B3∧C2∧D10 于是，由同一律可知 E(┐p∧q∧┐r) ∨(p∧┐q∧r)
但因为王教授不能既是苏州人，又是杭州人，因而p,r必有一个为假命 题，即p∧┐q∧r0 。
于是 E┐p∧q∧┐r 为真命题，因而必有p,r为假命题，q为真命题， 即王教授为上海人，甲说得全对，丙说对了一半，而乙全说错啦。

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

离散数学课件第2章

离散数学课件第2章
4
序,而集合中的元素是不讲顺序的。但是 为了将所有的 概念都统一于集合概念， 可采用克亚托斯基(Kazimierz Kurafowski)在1921年给出的定义 (a, b)={{a},{a, b}} 将二元组定义为比其元素高二层的集合； (4) 也可用二元组来递归的定义n元组如下： (a,b,c)=((a,b),c)
例9 .设 A={1,2,3} R1 ={(1,1),(2,2)} ， R2 ={(1,2),(2,1)} 。
16
元素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 。 定理.设R A×B是一个二元关系， A1 ,A2 A 。则 (1)保序性：A1 A2 R(A1) R(A2) ； (2)R(A1∪A2) = R(A1)∪R(A2) ； (3)R(A1∩A2) R(A1)∩R(A2) 。
例.设A={a,b,c,d}， A1 = {c,d} ， R={(a,a),(a,b),(b,c),(c,a),(d,c),(c,b)}。
17
§3 .关系的表示
关系的性质
一.关系表示法 1°关系的矩阵表示法 设关系RA×B ， 这里A,B是两个非空的有限集合， A={ a1,a2,a3,…,am } ， B={ b1,b2,b3,…,bn } 。 则 用一个m×n阶0—1矩阵MR来表示关系R， 称此矩 阵MR为关系R的关系矩阵(relation matrix)。 MR=(xij)m×n ，其中 1 当（ai,bj) R时 xij = ( i=1,…,m ； j=1,…,n) 0 当（ai,bj) R时

离散数学第二章课件

离散数学第二章课件

2013/9/12
离散数学
15
关系图举例
• 例：设A={1,2,3,4,5} , R={<1,1>,<1,2>,<3,2>,<1,4>,<5,4>,<5,1>}, 则，R的关系图GR如下：
1
5 4
2013/9/12
2 3
离散数学 16
下面关系图有什么性质
a b c a b d c b a c
(a)
2013/9/12
离散数学
5
二元关系的性质的举例1
• 数值之间的相等关系“=” 对任意的x,y,z∈R(实数集),由“=”的性 质得: 对每一个x∈R ，x=x，∴ “=”是 自反的；若x=y,必有y=x,因此“=”是对 称的； 若x=y,y=x,必有x=y,因此“=”是 反对称的； 若x=y,y=z,必有x=z,因此“=” 是传递的；
25
• 定理2.2.1: 设R是A到B的关系,S是B到C的关系,T是C到D的关 系,则 ( R S ) T R (S T )
证明： 同理可证 R (S T ) ( R S ) T
于是有：( R S ) T R (S T )
2013/9/12
2013/9/12
离散数学
2
关系及其表示
特别地： (1)若R= A×B,称R为全关系。 (2)若A=B,则称R为集合A上的二元关系。 设:|A|=n,则|A×A|=n2,于是,A上所有不同的二 n2 n2 元关系共有2 。（|(A×A)|= 2 ） 其中大多数关系没什么意义，我们关心的是 具有一定性质的关系。
7
反对称性的讨论：
在反对称性定义中，对任意x,y ∈A， 若xRy 且yRx ,则x=y， 就称R是反对称的。 xRy 且yRx是条件； x=y是结论，在这里， 只要条件不成立，关系R就是反对称的。 当条件成立时，R是否是反对称的，要视 结论的真假而定。[例如]

离散数学第二章讲解

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

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

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讲)


《定理》：设*是S上的二元运算,且x S,对任一m,n
I+有（1）xmxn=xm+n
（2）(xm)n=xmn
证明： （1） xmxn= (xm x) x… x = (xm+1 x) x… x
n

n-1
=….= xm+n
（2）(xm)n= xm … xm= xm+m xm … xm=…=xmn
n
例：设M= {0º,60º,120º,240º,300º,180º}表示平面上几何图形 顺时针旋转的六种位置，定义一个二元运算*，对M中任一 元素a,b有a*b=图形旋转(a+b)的角度，并规定当旋转到 360º时即为0º，试验证<M ,*>是一个群。
* 0º 60º 120º 180º 240º 300º 0º 0º 60º 120º 180º 240º 300º 60º 60º 120º 180º 240º 300º 0º 120º 120º 180º 240º 300º 0º 60º 180º 180º 240º 300º 0º 60º 120º 240º 240º 300º 0º 60º 120º 180º 300º 300º 0º 60º 120º 180º 240º
例： <I ,max>，其中max(x1,x2)取二者之大值；<I ,min>， 其中min(x1,x2)取二者之小值，均不为独异点（不存在幺 元）。<N ,max>则为独异点，其中 e =0
《定义》：设< S ,* >是一半群，TS，且*在T上是封闭的， 那么< T ,* >也是半群，称< T ,* >是< S ,* >的子半群。

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

离散数学图论2PPT教学课件

（1）欧拉回路要求边不能重复，结点可以重复. 笔不离开纸，不重复地走完所有的边，
且走过所有结点，就是所谓的一笔画.
2020/12/11
6
（2）欧拉图或通路的判定 1) 无向连通图G是欧拉图G不含奇数度结点(G的
所有结点度数为偶数):(定理1) 2) 非平凡连通图G含有欧拉通路G最多有两个奇
数度的结点；(定理1的推论) 3) 连通有向图D含有有向欧拉回路(即欧拉图)D
m
② mij degvi() j1
nm
nm
③ (m ij 1 ) (m ij 1 )m
2020/12i /11 1 j 1
i 1j 1
3
4．(有向图)邻接矩阵
设D=<V,E>, Vn,Em
A(D)= aij n
其中aij=邻接vi与vj的边的条数 (与A(G)类似) ( 以行和列均为结点)
aij
0
，表明vi是孤立点;
j1
i1
j1
2020/12/11
2
3．(有向图)关联矩阵
设D＝<V,E>, Vn,Em
M(D)= mij nm
1
其中 mij 0
vi为始,点 vj为终点
vi与vj不关联 (结点为行，边为列).
具有性质： 1 vi为终， 点vj为始点
n
① mij 0 (列元素之和为 0）； i1
二、图的矩阵表示、欧拉图
1．（无向图)
设G=<V,E>, Vn,Em M(G)= mij nm
其中mij=vi与ej的关联次数(行为结点，列为边). 具有性质：
m
① mij 2(列元素之和为2)；
i1
m
② mij degv,(i若)
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

1.1.3 命题符号化1.1.2介绍的5种常用的联结词也可称为真值联结词或逻辑联结词。

在命题逻辑中，利用这些联结词可将各种各样的复合命题符号化，基本的步骤如下：9找出各简单命题，将它们符号化；9使用合适的联结词，将简单命题逐个联结起来，组成复合命题的符号化形式。

例1.12将下列命题符号化：（1）小王是游泳冠军或百米赛跑冠军。

（2）小王现在在宿舍或在图书馆里。

（3）选小王或小李中的一人做班长。

解：根据以上步骤，上述命题可符号化为：（1）p ∨q，其中，p：小王是游泳冠军，q：小王是百米赛跑冠军。

（2）p ∨q，其中，p：小王在宿舍，q：小王在图书馆。

这里的“或”是排斥或，但因p与q不能同时发生，所以仍然符号化为p ∨q。

（3）(p ∧¬q) ∨(q ∧¬p)，其中，p：选小王做班长，q：选小李做班长。

这里的“或”是排斥或，因p与q可能同时发生，所以须符号化为(p ∧¬q) ∨(q ∧¬p)。

例1.13将下列命题符号化：（1）如果我上街，我就去书店看看，除非我很累。

（2）小王是电子工程学院的学生，他生于1983年或1984年，他是三好学生。

解：上述命题可符号化为：（1）¬r→(p→q)，其中，p：我上街，q：我去书店看看，r：我很累。

（该命题也可符号化为(p∧¬r)→q或p→(¬r→q)）（2）p∧(q∨r)∧s，其中，p：小王是电子工程学院的学生，q：他生于1983年，r：他生于1984年，s：他是三好生。

1.1 命题符号化及联结词5个联结词的优先级顺序为：¬、∧、∨、→、↔例我们写符号串：p ∨q ∧r→q∧¬s ∨r即为如下公式：(p ∨(q ∧r))→((q∧(¬s)) ∨r)1.2 命题公式及分类1.2.1 命题公式命题公式是由命题常项、命题变项、联结词、括号等组成的符号串，但并不是由这些符号任意组成的符号串都是命题公式，下面给出命题公式的严格定义：定义1.6（1）单个命题常项或变项p , q , r , …p i , q i , r i , …, 0, 1是合式公式；（2）若A 是合式公式，则¬A 也是合式公式；（3）若A 、B 是合式公式，则A ∧B 、A ∨B 、A →B 、A ↔B 也是合式公式；（4）只有有限次地应用（1）—（3）组成的符号串才是合式公式。

我们将合式公式称为命题公式，或简称为公式。

1.2 命题公式及分类注意：¾公式(¬p)、(p∧q)等的括号可以省略，写成¬p、p∧q ，整个公式的最外层括号可以省略；¾p∧q→r是公式，但pq→r不是公式。

定义1.7（1）设A为单个命题（常项或变项），p, q, r, …pi , qi,r i, …, 0,1，则称A为0层公式；（2）称A是n+1（n ≥0）层公式，若A符合下列情况之一：①A = ¬B，B是n层公式；②A=B ∧C，其中B、C分别为i层和j层公式，且n=max( i,j)；③A=B ∨C，其中B、C的层次同②；④A=B →C，其中B、C的层次同②；⑤A=B ↔C，其中B、C 的层次同②；（3）若A的最高层为k，则A是k层公式。

例1.2.2¬p ∨q、p ∧q ∧r、¬(¬p ∧q) →r ∨s分别为2、2、4层命题公式。

1.2 命题公式及分类1.2.2 解释（赋值）公式：(p ∧q )→r若p ：电子院学生，q ：2004级本科生，当r ：学习离散数学，(p ∧q )→r 为真；当r ：学习复变函数，(p ∧q )→r 为假。

定义1.8设A 为命题公式，p 1, …, p n 是出现在A 中的所有命题变项，给p 1, …, p n 指定一组真值，称为对A 的一个赋值或解释。

若指定的一组值使A 的值为真，则称这组值为A 的成真赋值；若指定的一组值使A 的值为假，则称这组值为A 的成假赋值。

1.2 命题公式及分类1.2 命题公式及分类定义含n（n≥1）个命题变项的命题公式，共有2n组赋值，将命题公式A在所有赋值之下取值的情况列成表，称为A的真值表。

构造真值表的步骤：¾列出每个命题变项的所有可能的取值（按字典顺序）；¾按命题公式的层次从低到高写出各个层次。

例1.7（1）求命题公式p ∧(q ∨¬r)的真值表解：例1.7（2）求命题公式(p∧(p→q)) →q 的真值表解：例1.7（3）求命题公式¬(p→q) ∧q 的真值表解：1.2 命题公式及分类定义1.9设A为一个命题公式：（1）若A在它的各种赋值下均为真，则称A为重言式或永真式；（2）若A在它的各种赋值下均为假，则称A为矛盾式或永假式；（3）若A至少存在一组赋值是成真赋值，则称A为可满足式。

显然：例1.7(2) （真值表最后一列全为1）为永真式，例1.7(3) （真值表最后一列全为0）为永假式，例1.7(1)（真值表最后一列即有0又有1）为可满足式。

1.3 等值演算定义1.10设A、B为两个命题公式，若等价式A↔B 是永真式，则称A与B等值，记为A⇔B。

注意：¾“⇔”不是联结词，它只是A与B等值时的记号。

¾等值关系具有自反性、对称性和传递性。

¾A与B是否等值应判断A↔B是否为永真式。

例1）基本等值式：（1）A⇔¬¬A（双重否定律）（2）A ⇔A∨A （等幂律）（3）A ⇔A∧A（等幂律）（4）A∨B ⇔B∨A （交换律）（5）A∧B ⇔A∧B（交换律）（6）A∨(B∨C) ⇔(A∨B)∨C （结合律）（7）A∧(B∧C) ⇔(A∧B)∧C（结合律）（8）A∨(B∧C) ⇔(A∨B)∧(A∨C) （分配律）（9）A∧(B∨C) ⇔(A∧B)∨(A∧C)（分配律）证明（基本等值式：（10）¬(A∨B) ⇔¬A∧¬B （德·摩根律）（11）¬(A∧B) ⇔¬A∨¬B（德·摩根律）（12）A∨(A∧B) ⇔A （吸收律）（13）A∧(A∨B) ⇔A（吸收律）（14）A∧0 ⇔0 （零律）（15）A∨1 ⇔1（零律）（16）A∨0 ⇔A （同一律）（17）A∧1 ⇔A（同一律）证明：（基本等值式：（18）A ∨¬A ⇔1（排中律）（19）A ∧¬A ⇔0（矛盾律）（20）A→B ⇔¬A∨B（蕴涵等值式）（21）A↔B⇔(A→B) ∧(B→A)（等价等值式）（22）A→B ⇔¬B→¬A（假言易位）（23）A↔B⇔¬A ↔¬B（等价否定等值式）（24）(A→B) ∧(A→¬B) ⇔¬A（归谬论）其中：A、B、C代表任意的命题公式，因此每个公式都是一个模式。

请大家牢记以上24种等值式。

证明：1.3 等值演算1.3.2 等值演算利用已知的等值式，推算出另外一些等值式的方法即为等值演算。

等值演算还将用到如下的置换规则：定理1.1设Φ(A)是含公式A的命题公式，Φ(B)是用公式B置换了Φ(A)中的A得到的命题公式，若A⇔B，则Φ(A)⇔Φ(B)例1.9 验证等值式: （1）p→(q→r) ⇔(p∧q)→r证明：p→(q→r)⇔¬p∨(q→r)（蕴涵等值式）⇔¬p ∨(¬q∨r)（蕴涵等值式）⇔(¬p∨¬q)∨r（结合律）⇔¬(p∧q) ∨r（德·摩根律）⇔(p∧q)→r（蕴涵等值式）例1.9（2）验证等值式：p⇔(p∧q) ∨(p∧¬q)证明：p⇔p ∧1（同一律）⇔p ∧(q ∨¬q )（排中律）⇔(p ∧q) ∨(p ∧¬q )（分配律）例1.10（1）验证：p→(q→r)⇔¬r→(q→¬p)证明：p→(q→r)⇔¬p∨(q→r) （蕴涵等值式）⇔⇔¬p∨(¬q ∨r) （蕴涵等值式）⇔⇔r∨(¬q∨¬p)（结合律）⇔⇔r∨(q→¬p) （蕴涵等值式）⇔¬r→(q→¬p) （蕴涵等值式）例1.10（2）判断下列公式的类型：((p∨q)∧¬(¬p∧(¬q∨¬r)))∨(¬p∧¬q)∨(¬p∧¬r)解：原式（7层公式）⇔((p∨q)∧¬(¬p∧¬(q∧r)))∨¬(p∨q)∨¬(p∨r)（德·摩根律）⇔((p∨q)∧(p∨(q∧r)))∨¬(p∨q)∨¬(p∨r)（双重否定律、德·摩根律）⇔((p∨q)∧(p∨r))∨¬((p∨q)∧(p∨r))（分配律、德·摩根律）⇔1（排中律）则：原式为永真式。

1.3 等值演算例1.11 用等值演算解决以下问题：A、B、C、D四人做百米竞赛，观众甲、乙、丙预报比赛的名次为：甲：C第一、B第二；乙：C第二、D第三；丙：A第二、D第四。

比赛结束后发现甲、乙、丙每人报告的情况都是各对一半，试问实际名次如何（假设无并列名次的情况）？解：设p i , q i , , r i , s i 分别表示A 、B 、C 、D 四人却取得第i 名（i =1,2,3,4），显然p i , q i , r i , s i 各有一个为真命题。

由题意，以下三个命题均为真命题：（1）(r 1 ∧¬q 2) ∨(q 2 ∧¬r 1) ⇔1（甲：C 第一、B 第二）（2）(r 2 ∧¬s 3) ∨(s 3 ∧¬r 2) ⇔1（乙：C 第二、D 第三）（3）(p 2 ∧¬s 4) ∨(s 4 ∧¬p 2) ⇔1（丙：A 第二、D 第四）由1⇔（1）∧（2）⇔((r 1 ∧¬q 2) ∨(q 2∧¬r 1) ) ∧((r 2 ∧¬s 3) ∨(s 3 ∧¬r 2))⇔(r 1 ∧¬q 2 ∧r 2 ∧¬s 3) ∨(¬q 2 ∧r 1∧s 3 ∧¬r 2) ∨(q 2 ∧¬r 1 ∧r 2 ∧¬s 3) ∨(q 2 ∧¬r 1 ∧s 3 ∧¬r 2)⇔0 ∨0 ∨(¬q2 ∧r1∧s3 ∧¬r2)∨(q2 ∧¬r1 ∧s3 ∧¬r2) 即：（4）(¬q2 ∧r1∧s3 ∧¬r2)∨(q2 ∧¬r1 ∧s3 ∧¬r2) ⇔1同理：1 ⇔（3）∧（4）⇔((p2 ∧¬s4) ∨(s4 ∧¬p2)) ∧((¬q2 ∧r1∧s3 ∧¬r2) ∨(q2 ∧¬r1 ∧s3 ∧¬r2))⇔(p2∧¬s4∧¬q2∧r1∧s3∧¬r2)∨(p2∧¬s4 ∧q2∧¬r1∧s3∧¬r2)∨(s4∧¬p2∧¬q2∧r1∧s3∧¬r2)∨(s4∧¬p2∧q2∧¬r1∧s3∧¬r2)⇔(p2∧¬s4∧¬q2∧r1∧s3 ∧¬r2)∨(s4∧¬p2∧¬q2∧r1∧s3∧¬r2) （5）1 ⇔(p2∧¬s4 ∧¬q2 ∧r1∧s3∧¬r2)∨(s4∧¬p2 ∧¬q2∧r1∧s3∧¬r2)由（5）可知：p2、r1、s3必须是真命题，即C第一、A第二、D第三，那么B只能是第四了。