离散数学第一章命题逻辑知识点总结
数理逻辑部分
第1章命题逻辑
命题符号化及联结词
命题: 判断结果惟一的陈述句
命题的真值: 判断的结果
真值的取值: 真与假
真命题: 真值为真的命题
假命题: 真值为假的命题
注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。
简单命题(原子命题)：简单陈述句构成的命题
复合命题：由简单命题与联结词按一定规则复合而成的命题
简单命题符号化
用小写英文字母p, q, r, … ,p i,q i,r i (i≥1）表示
简单命题
用“1”表示真，用“0”表示假
例如，令p：是有理数，则p 的真值为 0
q：2 + 5 = 7，则q 的真值为 1
联结词与复合命题
1.否定式与否定联结词“”
定义设p为命题，复合命题“非p”（或“p的否定”）称
为p的否定式，记作p. 符号称作否定联结词，并规定p为真当且仅当p为假.
2.合取式与合取联结词“∧”
定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q 的合取式，记作p∧q. ∧称作合取联结词，并规定 p∧q为真当且仅当p 与q同时为真
注意：描述合取式的灵活性与多样性
分清简单命题与复合命题
例将下列命题符号化.
(1) 王晓既用功又聪明.
(2) 王晓不仅聪明，而且用功.
(3) 王晓虽然聪明，但不用功.
(4) 张辉与王丽都是三好生.
(5) 张辉与王丽是同学.
解令p：王晓用功，q：王晓聪明，则
(1) p∧q
(2) p∧q
(3) p∧q.
令r : 张辉是三好学生，s :王丽是三好学生
(4) r∧s.
(5) 令t : 张辉与王丽是同学，t 是简单命题 .
说明:
(1)~(4)说明描述合取式的灵活性与多样性.
(5) 中“与”联结的是两个名词，整个句子是一个简单命题.
3.析取式与析取联结词“∨”
定义设p,q为二命题，复合命题“p或q”称作p与q的析取式，记作p∨q. ∨称作析取联结词，并规定p∨q为假当且仅当p与q同时为假.
例将下列命题符号化
(1) 2或4是素数.
(2) 2或3是素数.
(3) 4或6是素数.
(4) 小元元只能拿一个苹果或一个梨.
(5) 王晓红生于1975年或1976年.
解令p:2是素数, q:3是素数, r:4是素数, s:6是素数,
则 (1), (2), (3) 均为相容或.
分别符号化为: p∨r , p∨q, r∨s,
它们的真值分别为 1, 1, 0.
而 (4), (5) 为排斥或.
令t :小元元拿一个苹果，u:小元元拿一个梨，
则 (4) 符号化为 (t∧u) ∨(t∧u).
令v :王晓红生于1975年,w:王晓红生于1976年,则 (5) 既可符号化为 (v∧w)∨(v∧w), 又可符号化为v∨w , 为什么?
4.蕴涵式与蕴涵联结词“”
定义设p,q为二命题，复合命题“如果p,则q” 称作p与q的蕴涵式，记作p q，并称p是蕴涵式的前件，q为蕴涵式的后件. 称作蕴涵联结词，并规定，p q为假当且仅当p 为真q 为假.
p q 的逻辑关系：q 为p 的必要条件
“如果p，则q ” 的不同表述法很多：
若p，就q
只要p，就q
p 仅当q
只有q 才p
除非q, 才p 或除非q, 否则非p.
当p 为假时，p q 为真
常出现的错误：不分充分与必要条件
5.等价式与等价联结词“”
定义设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作p q. 称作等价联结词.并规定p q为真当且仅当p与q同时为真或同时为假.
说明:
(1) p q 的逻辑关系:p与q互为充分必要条件
(2) p q为真当且仅当p与q同真或同假
联结词优先级:( ),, , , ,
同级按从左到右的顺序进行
以上给出了5个联结词：, , , , ，组成
一个联结词集合{, , , , }，
联结词的优先顺序为：, , , , ; 如果出
现的联结词同级，又无括号时，则按从左到右
的顺序运算; 若遇有括号时，应该先进行括号
中的运算.
注意: 本书中使用的括号全为园括号.
命题常项
命题变项
命题公式及分类
命题变项与合式公式
命题常项：简单命题
命题变项：真值不确定的陈述句
定义合式公式 (命题公式, 公式) 递归定义如下：
(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) 若公式A是单个的命题变项, 则称A为0层公式.
(2) 称A是n+1(n≥0)层公式是指下面情况之一：
(a) A=B, B是n层公式；
(b) A=B C, 其中B,C分别为i层和j层公式，且
n=max(i, j)；
(c) A=B C, 其中B,C的层次及n同(b)；
(d) A=B C, 其中B,C的层次及n同(b)；
(e) A=B C, 其中B,C的层次及n同(b).
例如公式
p 0层p 1层
p q 2层
(p q)r 3层
((p q) r)(r s) 4层
公式的赋值
定义给公式A中的命题变项p1, p2, … , p n指定
一组真值称为对A的一个赋值或解释
成真赋值: 使公式为真的赋值
成假赋值: 使公式为假的赋值
说明：
赋值=12…n之间不加标点符号，i=0或1.
A中仅出现p1, p2, …, p n，给A赋值12…n是指p1=1, p2=2, …, p n=n
A中仅出现p,q, r, …, 给A赋值123…是指p=1,q=2 , r= 3 …
含n个变项的公式有2n个赋值.
真值表
真值表: 公式A在所有赋值下的取值情况列成的表
例给出公式的真值表
A= (q p) q p的真值表
例 B = (p q) q的真值表
例C= (p q) r的真值表
命题的分类
重言式
矛盾式
可满足式
定义设A为一个命题公式
(1) 若A无成假赋值，则称A为重言式(也称永真式)
(2) 若A无成真赋值，则称A为矛盾式(也称永假式)
(3) 若A不是矛盾式，则称A为可满足式
注意：重言式是可满足式，但反之不真.
上例中A为重言式，B为矛盾式，C为可满足式
A= (q p)q p，B =(p q)q，C= (p q)r
等值演算
等值式
定义若等价式A B是重言式，则称A与B等值，
记作A B，并称A B是等值式
说明：定义中，A,B,均为元语言符号, A或B中
可能有哑元出现.
例如，在 (p q) ((p q) (r r))中，r为左边公式的哑元.
用真值表可验证两个公式是否等值
请验证：p(q r) (p q) r
p(q r) (p q) r
基本等值式
双重否定律 : 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
零律: A11, A00
同一律: A0A, A1A
排中律: A A1
矛盾律: A A0
等值演算:
由已知的等值式推演出新的等值式的过程
置换规则：若A B, 则(B)(A)
等值演算的基础：
(1) 等值关系的性质：自反、对称、传递
(2) 基本的等值式
(3) 置换规则
应用举例——证明两个公式等值
例1 证明p(q r) (p q)r
证p(q r)
p(q r) （蕴涵等值式，置换规则）
(p q)r（结合律，置换规则）
(p q)r（德摩根律，置换规则）
(p q) r（蕴涵等值式，置换规则）说明:也可以从右边开始演算（请做一遍）
因为每一步都用置换规则，故可不写出
熟练后，基本等值式也可以不写出
应用举例——证明两个公式不等值
例2 证明: p(q r) (p q) r
用等值演算不能直接证明两个公式不等值,证明两个公式不等值的基本思想是找到一个赋值使一个成
真,另一个成假.
方法一真值表法（自己证）
方法二观察赋值法. 容易看出000, 010等是左边的
的成真赋值，是右边的成假赋值.
方法三用等值演算先化简两个公式，再观察.
应用举例——判断公式类型
例3 用等值演算法判断下列公式的类型
(1) q(p q)
解q(p q)
q(p q) （蕴涵等值式）
q(p q) （德摩根律）
p(q q) （交换律，结合律）
p0 （矛盾律）
0 （零律）
由最后一步可知，该式为矛盾式.
(2) (p q)(q p)
解 (p q)(q p)
(p q)(q p) （蕴涵等值式）
(p q)(p q) （交换律）
1
由最后一步可知，该式为重言式.
问：最后一步为什么等值于1？
(3) ((p q)(p q))r)
解 ((p q)(p q))r)
(p(q q))r（分配律）
p1r（排中律）
p r（同一律）
这不是矛盾式，也不是重言式，而是非重言式的可
满足式.如101是它的成真赋值,000是它的成假赋值.
总结：A为矛盾式当且仅当A0
A为重言式当且仅当A1
说明：演算步骤不惟一,应尽量使演算短些
对偶与范式
对偶式与对偶原理
定义在仅含有联结词, ∧,∨的命题公式A中，将
∨换成∧, ∧换成∨，若A中含有0或1，就将0换成
1，1换成0，所得命题公式称为A的对偶式，记为A*.
从定义不难看出，(A*)* 还原成A
定理设A和A*互为对偶式，p1,p2,…,p n是出现在A和
A*中的全部命题变项，将A和A*写成n元函数形式，
则 (1) A(p1,p2,…,p n) A* (p1, p2,…, p n) (2) A(p1, p2,…, p n) A* (p1,p2,…,p n) 定理（对偶原理）设A，B为两个命题公式，
若A B，则A* B*.
析取范式与合取范式
文字:命题变项及其否定的总称
简单析取式:有限个文字构成的析取式
如p, q, p q, p q r, …
简单合取式:有限个文字构成的合取式
如p, q, p q, p q r, …
析取范式:由有限个简单合取式组成的析取式
A 1A
2
A
r
, 其中A1,A2,,A r是简单合取式
合取范式:由有限个简单析取式组成的合取式
A 1A
2
A
r
, 其中A1,A2,,A r是简单析取式
范式:析取范式与合取范式的总称
公式A的析取范式: 与A等值的析取范式
公式A的合取范式: 与A等值的合取范式
说明：
单个文字既是简单析取式，又是简单合取式
p q r, p q r既是析取范式，又是合取范式
(为什么?)
命题公式的范式
定理任何命题公式都存在着与之等值的析取范式
与合取范式.
求公式A的范式的步骤：
(1) 消去A中的, （若存在）
(2) 否定联结词的内移或消去
(3) 使用分配律
对分配（析取范式）
对分配（合取范式）
公式的范式存在，但不惟一
求公式的范式举例
例求下列公式的析取范式与合取范式
(1) A=(p q)r
解 (p q)r
(p q)r（消去）
p q r（结合律）
这既是A的析取范式（由3个简单合取式组成的析
取式），又是A的合取范式（由一个简单析取式
组成的合取式）
(2) B=(p q)r
解 (p q)r
(p q)r（消去第一个）
(p q)r（消去第二个）
(p q)r（否定号内移——德摩根律）这一步已为析取范式（两个简单合取式构成）
继续： (p q)r
(p r)(q r) （对分配律）
这一步得到合取范式（由两个简单析取式构成）
极小项与极大项
定义在含有n个命题变项的简单合取式(简单析取式)中，
若每个命题变项均以文字的形式在其中出现且仅出现一
次，而且第i（1i n）个文字出现在左起第i位上，称这样
的简单合取式（简单析取式）为极小项（极大项）.
说明：n个命题变项产生2n个极小项和2n个极大项
2n个极小项（极大项）均互不等值
用m i表示第i个极小项，其中i是该极小项成真赋值的十进制表示. 用M i 表示第i个极大项，其中i是该极大项成假赋值的十进制表示, m i(M i)称为极小项(极大项)的名称.
m
与M i的关系: m i M i , M i m i
i
主析取范式与主合取范式
主析取范式: 由极小项构成的析取范式
主合取范式: 由极大项构成的合取范式
例如，n=3, 命题变项为p, q, r时，
(p q r)(p q r) m1m3是主析取范式
(p q r)(p q r) M1M5 是主合取范式
A的主析取范式: 与A等值的主析取范式
A的主合取范式: 与A等值的主合取范式.
定理任何命题公式都存在着与之等值的主析取范
式和主合取范式, 并且是惟一的.
用等值演算法求公式的主范式的步骤：
(1) 先求析取范式（合取范式）
(2) 将不是极小项（极大项）的简单合取式（简
单析取式）化成与之等值的若干个极小项的析
取（极大项的合取），需要利用同一律（零
律）、排中律（矛盾律）、分配律、幂等律等.
(3) 极小项（极大项）用名称m i（M i）表示，并
按角标从小到大顺序排序.
求公式的主范式
例求公式A=(p q)r的主析取范式与主合
取范式.
(1) 求主析取范式
(p q)r
(p q)r , （析取范式）①
(p q)
(p q)(r r)
(p q r)(p q r)
m 6m
7
,
r
(p p)(q q)r
(p q r)(p q r)(p q r)(p q r)
m 1m
3
m
5
m
7
③
②, ③代入①并排序，得
(p q)r m1m3m5m6m7（主析取范式）(2) 求A的主合取范式
(p q)r
(p r)(q r) , （合取范式）①
p r
p(q q)r
(p q r)(p q r)
M 0M
2,
②
q r
(p p)q r
(p q r)(p q r)
M 0M
4
③
②, ③代入①并排序，得
(p q)r M0M2M4 （主合取范式）主范式的用途——与真值表相同
(1) 求公式的成真赋值和成假赋值
例如 (p q)r m1m3m5m6m7，其成真赋值为001, 011, 101, 110, 111，
其余的赋值 000, 010, 100为成假赋值.
类似地，由主合取范式也可立即求出成假赋值和成真赋值.
(2) 判断公式的类型
设A含n个命题变项，则
A为重言式A的主析取范式含2n个极小项
A的主合取范式为1.
A为矛盾式A的主析取范式为0
A的主合取范式含2n个极大项A为非重言式的可满足式
A的主析取范式中至少含一个且不含全部极小项
A的主合取范式中至少含一个且不含全部极大项
例某公司要从赵、钱、孙、李、周五名新毕
业的大学生中选派一些人出国学习. 选派必须
满足以下条件：
(1)若赵去，钱也去；
(2)李、周两人中至少有一人去；
(3)钱、孙两人中有一人去且仅去一人；
(4)孙、李两人同去或同不去；
(5)若周去，则赵、钱也去.
试用主析取范式法分析该公司如何选派他们出
国？
解此类问题的步骤为：
①将简单命题符号化
②写出各复合命题
③写出由②中复合命题组成的合取式
④求③中所得公式的主析取范式
解①设p：派赵去，q：派钱去，r：派孙去，
s：派李去，u：派周去.
② (1) (p q)
(2) (s u)
(3) ((q r)(q r))
(4) ((r s)(r s))
(5) (u(p q))
③ (1) ~ (5)构成的合取式为
A=(p q)(s u)((q r)(q r))
((r s)(r s))(u(p q))
④ A (p q r s u)(p q r s u)
结论：由④可知，A的成真赋值为00110与11001，
因而派孙、李去（赵、钱、周不去）或派赵、钱、
周去（孙、李不去）.
A的演算过程如下:
A (p q)((q r)(q r))(s u)(u(p q)) ((r s)(r s)) （交换律) B
1
= (p q)((q r)(q r))
((p q r)(p q r)(q r)) （分配律）
B
2
= (s u)(u(p q))
((s u)(p q s)(p q u)) （分配律）
B 1
B
2
(p q r s u)(p q r s u) (q r s u)(p q r s)(p q r u)
再令B3 = ((r s)(r s))
得A B1B2B3
(p q r s u)(p q r s u)注意：在以上演算中多次用矛盾律
要求：自己演算一遍
推理理论
推理的形式结构
推理的形式结构—问题的引入
推理举例:
(1) 正项级数收敛当且仅当部分和有上界.
(2) 若
推理: 从前提出发推出结论的思维过程
上面(1)是正确的推理，而(2)是错误的推理.
证明: 描述推理正确的过程.
判断推理是否正确的方法
?真值表法
?等值演算法判断推理是否正确
?主析取范式法
?构造证明法证明推理正确
说明：当命题变项比较少时，用前3个方法比较方
便, 此时采用形式结构“” . 而在构
造证明时，采用“前提: , 结论: B”.
推理定律与推理规则
推理定律——重言蕴涵式
构造证明——直接证明法
例构造下面推理的证明：
若明天是星期一或星期三，我就有课. 若有课，今天必备课. 我今天下午没备课. 所以，
明天不是星期一和星期三.
解设p：明天是星期一，q：明天是星期三，
r：我有课，s：我备课
推理的形式结构为
例构造下面推理的证明:
2是素数或合数. 若2是素数，则是无理数.
若是无理数，则4不是素数. 所以，如果4是
素数，则2是合数.
用附加前提证明法构造证明
解设p：2是素数，q：2是合数，
r：是无理数，s：4是素数
推理的形式结构
前提：p∨q, p r, r s
结论：s q
证明
① s附加前提引入
②p r前提引入
③r s前提引入
④p s②③假言三段论
⑤p①④拒取式
⑥p∨q前提引入
⑦q⑤⑥析取三段论请用直接证明法证明之
离散数学答案命题逻辑
第二章 命题逻辑 习题．解 ⑴不是陈述句，所以不是命题。 ⑵x 取值不确定，所以不是命题。 ⑶问句，不是陈述句，所以不是命题。 ⑷惊叹句，不是陈述句，所以不是命题。 ⑸是命题，真值由具体情况确定。 ⑹是命题，真值由具体情况确定。 ⑺是真命题。 ⑻是悖论，所以不是命题。 ⑼是假命题。 2．解 ⑴是复合命题。设p ：他们明天去百货公司；q ：他们后天去百货公司。命题符号化为q p ∨。 ⑵是疑问句，所以不是命题。 ⑶是悖论，所以不是命题。 ⑷是原子命题。 ⑸是复合命题。设p ：王海在学习；q ：李春在学习。命题符号化为p q 。 ⑹是复合命题。设p ：你努力学习；q ：你一定能取得优异成绩。p q 。 ⑺不是命题。 ⑻不是命题 ⑼。是复合命题。设p ：王海是女孩子。命题符号化为：p 。 3．解 ⑴如果李春迟到了，那么他错过考试。 ⑵要么李春迟到了，要么李春错过了考试，要么李春通过了考试。 ⑶李春错过考试当且仅当他迟到了。 ⑷如果李春迟到了并且错过了考试，那么他没有通过考试。 4．解 ⑴p (q r )。⑵p q 。⑶q p 。⑷q p 。 习题 1．解 ⑴是1层公式。 ⑵不是公式。 ⑶一层： p q ，p 二层： p q 所以，)()(q p q p ??→∨是3层公式。 ⑷不是公式。 ⑸(p q )(q ( q r ))是5层公式，这是因为 一层：p q ，q ，r 二层：q r 三层：q ( q r ) 四层： (q ( q r )) 2．解 ⑴A =(p q )q 是2层公式。真值表如表2-1所示： 表2-1 p q q p ∨ A 0 0 0 0 0 1 1 1 1 0 1 0 1 1 1 1 ⑵p q p q A →→∧=)(是3层公式。真值表如表2-2所示：
离散数学必备知识点总结
离散数学必备知识点总 结 Document number：NOCG-YUNOO-BUYTT-UU986-1986UT
总结离散数学知识点 第二章命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n个变元共有n2个极小项或极大项，这n2为(0~n2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P规则，T规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第三章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系；
2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 第四章集合 1.N，表示自然数集，1,2,3……，不包括0； 2.基：集合A中不同元素的个数，|A|； 3.幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)； 4.若集合A有n个元素，幂集P(A)有n2个元素，|P(A)|=||2A=n2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 第五章关系 1.若集合A有m个元素，集合B有n个元素，则笛卡尔A×B的基 2种不同的关系； 数为mn，A到B上可以定义mn 2.若集合A有n个元素，则|A×A|=2n，A上有22n个不同的关系；
离散数学必备知识点总结
总结离散数学知识点 第二章命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项 时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n个变元共有n2个极小项或极大项，这n2为(0~n2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P规则，T规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第三章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^;
3.既有存在又有全称量词时，先消存在量词，再消全称量词； 第四章集合 1.N，表示自然数集，1,2,3……，不包括0； 2.基：集合A中不同元素的个数，|A|； 3.幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)； 4.若集合A有n个元素，幂集P(A)有n2个元素，|P(A)|=||2A=n2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 第五章关系 1.若集合A有m个元素，集合B有n个元素，则笛卡尔A×B的基数为mn，A到B上可以定义m n 2种不同的关系； 2.若集合A有n个元素，则|A×A|=2n，A上有22n个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性；
离散数学复习要点
离散数学复习要点第一章命题逻辑 一、典型考查点 1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。其它疑问句、祈使句、感叹句、悖论等皆不是。详见教材P1 2、联结词运算定律┐∧∨→记住特殊的：1∧1?1，0∨0?0，1→0?0，11?1，00?1详见P5 3、命题符号化步骤：A划分原子命题，找准联结词。特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q→P；除非P否则Q，应为┐P→Q。B设出原子命题写出符号化公式。详见P5 4、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。详见P9 5、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。②对每个指派，以二进制数从小到大或从大到小顺序列出。③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。详见P8。 6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P15 7、等价式详见P22表1.6.2 证明方法：①真值表完全相同②用等价演算③利用A?B的充要条件是A?B且B?A。主要等价式：(1)双否定：??A?A。(2)交换律：A∧B?B∧A，A∨B?B∨A，A?B?B?A。3)结合律：(A∧B)∧C?A ∧(B∧C)，(A∨B)∨C?A∨(B∨C)，(A?B)?C?A?(B?C)。(4) 分配律：A∧(B∨C)?(A∧B)∨(A∧C)，A∨(B∧C)?(A∨B)∧(A∨C)。(5) 德·摩根律：?(A∧B)??A∨?B，?(A∨B)??A∧?B。(6) 等幂律：A∧A?A，A∨A?A。(7) 同一律：A∧T?A，A∨F?A。(8) 零律：A∧F?F，A∨T?T。(9) 吸收律：A∧(A∨B)?A，A∨(A∧B)?A。(10) 互补律：A∧?A?F，(矛盾律)，A∨?A?T。(排中律)(11) 条件式转化律：A→B??A∨B，A→B??B→?A。(12) 双条件式转化律：A?B?(A→B)∧(B→A)?(A∧B)∨(?A∧?B) 8、蕴含式详见P23表1.6.3 证明方法：①前件真导后件真方法②后件假导前件假方法③真值表中，前件为真的行，后件也为真或者后件为假的行，前件也为假。④用定义，证A?B，即证A→B是永真式。 9、范式求法步骤：①使用命题定律，消去公式中除∧、∨和?以外公式中出现的所有联结词；②使用?(?P)?P和德·摩根律，将公式中出现的联结词?都移到命题变元之前；③利用结合律、分配律等将公式化成析取范式或合取范式。10、主范式的求法重点步骤：(a)把给定公式化成析取（合取）范式；(b)删除析取范式中所有为永假的简单合取（析取）式；(c)用等幂律化简简单合取（析取）式中同一命题变元的重复出现为一次出现，如P∧P?P。(d)用同一律补进简单合取（析取）式中未出现的所有命题变元，如Q，则P?P∧（?Q∨Q)或P?P∨（?Q∧Q)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现，这样得到了给定公式的主析取（合取）范式。 注意：主析取范式与主合取范式之间的联系。例如：(P→Q)∧Q?m1∨m3?M0∧M2，即剩下的编码就是另一个主范式的编码，因此，求主范式，哪一个简单易求，就先求哪个，然后对应出所求结果。详见P16 11、推理证明：重点方法：演算、演绎法（常用的格式）、反证法、CP规则即附加前提等。 重点规则（主要蕴含式）：(1) P∧Q?P化简(2) P∧Q?Q化简(3) P?P∨Q附加(4) ?P?P→Q变形附加(5)Q?P→Q变形附加(6) ?(P→Q)?P变形化简(7) ?(P→Q)??Q变形化简(8) P，(P→Q)?Q假言推理(9) ?Q，(P→Q)??P拒取式(10) ?P，(P∨Q)?Q析取三段论(11) (P→Q)，(Q→R)?P→R条件三段论(12) (P?Q)，(Q?R)?P?R 双条件三段论 文字证明推理三步：一命题符号化，二写出前提和结论，三进行证明。详见P21 二、强化练习 1.命题的是( )A.走，看电影去B.x+y>0C.空集是任意集合的真子集D.你明天能来吗? 2.下列式子为重言式的是( ) A.P→P∨Q B.(┐P∧Q)∧(P∨┐Q) C.┐ (P Q) D.(P∨Q) (P→Q) 3．下列为两个命题变元P，Q的小项是（） A．P∧Q∧? P B．? P∨Q C．? P∧Q D．? P∨P∨Q 4．下列语句中是真命题的是（） A．我正在说谎B．严禁吸烟C．如果1+2=3，那么雪是黑的D．如果1+2=5，那雪是黑的 5．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（） A．? P∧? Q B．? P∨? Q C．?（P?Q） D．?（? P∨? Q） 6．命题公式（P∧（P→Q））→Q是（）A．矛盾式B．蕴含式C．重言式D．等价式 7．命题公式?（P∧Q）→R的成真指派是（） A．000，001，110，B．001，011，101，110，111 C．全体指派D．无 8．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（）
离散数学知识点整理
离散数学 一、逻辑和证明 1.1命题逻辑 命题：是一个可以判断真假的陈述句。 联接词：∧、∨、→、?、?。记住“p仅当q”意思是“如果p，则q”，即p→。记住“q除非p”意思是“?p→q”。会考察条件语句翻译成汉语。 系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若pq无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。 1.3命题等价式 逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。
谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如?x>0P(x)。 当论域中的元素可以一一列举，那么?xP(x)就等价于P(x1)∧P(x2)...∧P(xn)。同理，?xP(x)就等价于P(x1)∨P(x2)...∨P(xn)。 两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如?x（P(x)∧Q(x))和(?xP(x))∧(?xQ(x))。 量词表达式的否定：??xP(x) ??x?P(x)，??xP(x) ??x?P(x)。 1.5量词嵌套 我们采用循环的思考方法。量词顺序的不同会影响结果。语句到嵌套量词语句的翻译，注意论域。嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。 1.6推理规则 一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。但有效论证
二、集合、函数、序列、与矩阵 2.1集合 ∈说的是元素与集合的关系，?说的是集合与集合的关系。常见数集有N={0,1,2,3...}，Z整数集，Z+正整数集，Q有理数集，R实数集，R+正实数集，C复数集。 A和B相等当仅当?x(x∈A?x∈B)；A是B的子集当仅当?x(x∈A→x∈B)；A是B的真子集当仅当?x(x∈A→x∈B)∧?x(x?A∧x∈B)。 幂集：集合元素的所有可能组合，肯定有?何它自身。如?的幂集就是{?}，而{?}的幂集是{?，{?}}。 考虑A→B的函数关系，定义域、陪域（实值函数、整数值函数）、值域、像集（定义域的一个子集在值域的元素集合）。 一对一或者单射：B可能有多余的元素，但不重复指向。 映上或者满射：B中没有多余的元素，但可能重复指向。 一一对应或者双射：符合上述两种情况的函数关系。 反函数：如果是一一对应的就有反函数，否则没有。 合成函数：fοg(a)=f(g(a))，一般来说交换律不成立。 2.4序列 无限集分为：一组是和自然数集合有相同基数，另一组是没有相同基数。前者是可数的，后者不可数。想要证明一个无限集是可数的只要证明它与自然数之间有一一对应的关系。 如果A和B是可数的，则A∪B也是可数的。
离散数学(命题逻辑)课后总结
离散数学（课件上习题） 第一章 例1-1.1 判定下面这些句子哪些是命题。 ⑴2是个素数。 ⑵雪是黑色的。 ⑶2013年人类将到达火星。 ⑷如果a>b且b>c，则a>c 。（其中a,b,c都是 确定的实数） ⑸x+y<5 ⑹请打开书！ ⑺您去吗？ ⑴⑵⑶⑷是命题 例1-2.1 P：2是素数。 ?P：2不是素数。 例1-2.2 P：小王能唱歌。 Q：小王能跳舞。 P∧Q：小王能歌善舞。 例1-2.3. 灯泡或者线路有故障。（析取“∨”） 例1-2.4. 第一节课上数学或者上英语。（异或、排斥或。即“?”） 注意：P ?Q 与(P∧?Q)∨(Q∧?P ) 是一样的。 归纳自然语言中的联结词，定义了六个逻辑联结词，分别是：（1）否定“?”(2) 合取“∧”(3) 析取“∨”(4) 异或“?”(5) 蕴涵“→”(6) 等价“?” 例1-2.5：P表示：缺少水分。 Q表示：植物会死亡。 P→Q：如果缺少水分，植物就会死亡。 P→Q：也称之为蕴涵式，读成“P蕴涵Q”，“如果P则Q”。 也说成P是P→Q 的前件，Q是P→Q的后件。 还可以说P是Q的充分条件，Q是P的必要条件。 以下是关于蕴含式的一个例子 P：天气好。Q：我去公园。 1.如果天气好，我就去公园。 2.只要天气好，我就去公园。 3.天气好，我就去公园。 4.仅当天气好，我才去公园。 5.只有天气好，我才去公园。 6.我去公园，仅当天气好。 命题1.、2.、3.写成：P→Q 命题4.、5.、6.写成：Q→P 例1-2.6：P：△ABC 是等边三角形。Q ：△ABC是等角三角形。 P?Q ：△ABC 是等边三角形当且仅当它是等角三角形。
离散数学第二章一阶逻辑知识点总结
数理逻辑部分 第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元谓词, n≥2): 表示事物之间的关系 如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)中
离散数学第四章二元关系和函数知识点总结
集合论部分 第四章、二元关系和函数 集合的笛卡儿积与二元关系有序对 定义由两个客体x 和y，按照一定的顺序组成的 二元组称为有序对，记作
不适合交换律A B B A (A B, A, B) 不适合结合律 (A B)C A(B C) (A, B)对于并或交运算满足分配律 A(B C)=(A B)(A C) (B C)A=(B A)(C A) A(B C)=(A B)(A C) (B C)A=(B A)(C A) 若A或B中有一个为空集，则A B就是空集. A=B= 若|A|=m, |B|=n, 则 |A B|=mn 证明A(B C)=(A B)(A C) 证任取
离散数学第一章命题逻辑知识点总结
数理逻辑部分 第1章命题逻辑 命题符号化及联结词 命题: 判断结果惟一的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题 注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。 简单命题(原子命题)：简单陈述句构成的命题 复合命题：由简单命题与联结词按一定规则复合而成的命题 简单命题符号化 用小写英文字母p, q, r, … ,p i,q i,r i (i≥1）表示 简单命题 用“1”表示真，用“0”表示假 例如，令p：是有理数，则p 的真值为 0 q：2 + 5 = 7，则q 的真值为 1 联结词与复合命题 1.否定式与否定联结词“” 定义设p为命题，复合命题“非p”（或“p的否定”）称 为p的否定式，记作p. 符号称作否定联结词，并规定p为真当且仅当p为假. 2.合取式与合取联结词“∧” 定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q 的合取式，记作p∧q. ∧称作合取联结词，并规定 p∧q为真当且仅当p 与q同时为真 注意：描述合取式的灵活性与多样性 分清简单命题与复合命题 例将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解令p：王晓用功，q：王晓聪明，则 (1) p∧q (2) p∧q (3) p∧q. 令r : 张辉是三好学生，s :王丽是三好学生 (4) r∧s. (5) 令t : 张辉与王丽是同学，t 是简单命题 . 说明:
(完整word版)离散数学知识汇总,推荐文档
离散数学笔记 第一章命题逻辑 合取 析取 定义 1. 1.3否定：当某个命题为真时，其否定为假，当某个命题为假时，其否定为真定义 1. 1.4条件联结词，表示“如果……那么……”形式的语句 定义 1. 1.5双条件联结词，表示“当且仅当”形式的语句 定义 1.2.1合式公式 (1)单个命题变元、命题常元为合式公式，称为原子公式。 (2)若某个字符串A 是合式公式，则?A、(A)也是合式公式。 (3)若A、B 是合式公式，则A ∧B、A∨B、A→B、A?B 是合式公式。 (4)有限次使用(2)~(3)形成的字符串均为合式公式。 1.3等值式 1.4析取范式与合取范式
将一个普通公式转换为范式的基本步骤
1.6推理 定义 1.6.1 设 A 与 C 是两个命题公式， 若 A → C 为永真式、 重言式，则称 C 是 A 的有 效结论，或称 A 可以逻辑推出 C ，记为 A => C 。（用等值演算或真值表） 第二章 谓词逻辑 2.1、基本概念 ?：全称量词 ?：存在量词 一般情况下， 如果个体变元的取值范围不做任何限制即为全总个体域时， 带 “全称量词”的谓词公式形如"?x(H(x)→B(x))，即量词的后面为条件式，带“存在量词”的谓词公式形如?x(H(x)∨WL(x))，即量词的后面为合取式 例题 R(x)表示对象 x 是兔子，T(x)表示对象 x 是乌龟， H(x,y)表示 x 比 y 跑得快，L(x,y)表示x 与 y 一样快，则兔子比乌龟跑得快表示为： ?x ?y(R(x)∧T(y)→H(x,y)) 有的兔子比所有的乌龟跑得快表示为：?x ?y(R(x)∧T(y)→H(x,y)) 2.2、谓词公式及其解释 定义 2.2.1、 非逻辑符号： 个体常元(如 a,b,c)、 函数常元(如表示22 y x 的 f(x,y))、 谓词常元(如表示人 类的 H(x))。 定义 2.2.2、逻辑符号：个体变元、量词(??)、联结词(﹁∨∧→?)、逗号、括号。 定义 2.2.3、项的定义：个体常元、变元及其函数式的表达式称为项(item)。 定义 2.2.4、原子公式：设 R(n x x ... 1)是 n 元谓词，n t t ...1是项，则 R(t)是原子公式。原子公式中的个体变元，可以换成个体变元的表达式(项)，但不能出现任何联结词与量词，只能为单个的谓词公式。 定义 2.2.5 合式公式：(1)原子公式是合式公式；(2)若 A 是合式公式，则(﹁A)也是合式公式；(3)若 A,B 合式，则 A ∨B, A ∧B, A →B , A ?B 合式(4)若 A 合式，则?xA 、?xA 合式(5)有限次使用(2)~(4)得到的式子是合式。 定义 2.2.6 量词辖域：?xA 和?xA 中的量词?x/?x 的作用范围，A 就是作用范围。 定义 2.2.7 约束变元：在?x 和?x 的辖域 A 中出现的个体变元 x ，称为约束变元，这是与量词相关的变元，约束变元的所有出现都称为约束出现。 定义 2.2.8 自由变元：谓词公式中与任何量词都无关的量词，称为自由变元，它的每次出现称为自由出现。一个公式的个体变元不是约束变元，就是自由变元。 注意：为了避免约束变元和自由变元同名出现，一般要对“约束变元”改名，而不对自由变元改名。 定义 2.2.9 闭公式是指不含自由变元的谓词公式
大学离散数学期末重点知识点总结(考试专用)
1.常用公式 p ∧(P →Q)=>Q 假言推论 ┐Q ∧(P →Q)=>┐P 拒取式 ┐p ∧(P ∨Q)=>Q 析取三段式 (P →Q) ∧(Q →R)=>P →R 条件三段式 (PQ) ∧(QR)=>PR 双条件三段式 (P →Q)∧(R →S)∧(P ∧R)=>Q →S 合取构造二难 (P →Q)∧(R →S)∧(P ∨R)=>Q ∨S 析取构造二难 (?x)((Ax)∨(Bx)) <=>( ?x)(Ax)∨(?x)(Bx) (?x)((Ax)∧(Bx)) <=>(?x)(Ax)∧(?x)(Bx) —┐(?x)(Ax) <=>(?x)┐(Ax) —┐(?x)(Ax) <=>(?x)┐(Ax) (?x)(A ∨(Bx)) <=>A ∨(?x)(Bx) (?x)(A ∧(Bx)) <=>A ∧(?x)(Bx) (?x)((Ax)→(Bx)) <=>(?x)(Ax)→(?x)(Bx) (?x)(Ax) →B <=>(?x) ((Ax)→B) (?x)(Ax) →B <=>(?x) ((Ax)→B) A →(?x)(Bx) <=>(?x) (A →(Bx)) A →(?x)(Bx) <=>(?x) (A →(Bx)) (?x)(Ax)∨(?x)(Bx) =>(?x)((Ax)∨(Bx)) (?x)((Ax)∧(Bx)) =>(?x)(Ax)∧(?x)(Bx) (?x)(Ax)→(?x)(Bx) =>(?x)((Ax)→(Bx)) 2.命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P ,Q,R 的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n 个变元共有n 2个极小项或极大项，这n 2为(0~n 2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 3.谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 4.集合 1.N ，表示自然数集，1,2,3……，不包括0； 2.基：集合A 中不同元素的个数，|A|； 3.幂集：给定集合A ，以集合A 的所有子集为元素组成的集合，P(A)； 4.若集合A 有n 个元素，幂集P(A)有n 2个元素，|P(A)|=||2A =n 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A 的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 5.关系 1.若集合A 有m 个元素，集合B 有n 个元素，则笛卡尔A ×B 的基数为mn ，A 到B 上可以定义mn 2种不同的关系； 2.若集合A 有n 个元素，则|A ×A|=2n ，A 上有22n 个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域(domR)：所有元素x 组成的集合； 后域(ranR)：所有元素y 组成的集合； 5.自反闭包：r(R)=RU Ix ; 对称闭包：s(R)=RU 1-R ; 传递闭包：t(R)=RU 2R U 3R U …… 6.等价关系：集合A 上的二元关系R 满足自反性，对称性和传递性，则R 称为等价关系； 7.偏序关系：集合A 上的关系R 满足自反性，反对称性和传递性，则称R 是A 上的一个偏序关系； 8.covA={