联结词与复合命题。
复合命题“p并且q”(或“p与q”) 记作p∧q
“p并且q” 的多种表述方式：
既p又q.不仅p而且q.
虽然p但qpq 的逻辑关系： q为p的必要条件， p为q的充分条件。
如果p,则q” 的多种表述方式：
若p,就q只要p,就q
p仅当q只有q 才p
除非q, 才p
除非q, 否则非p
假如没有q，就没有p
基本等值式。
双重否定律 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
零律 a11, a00
同一律 a0a, a1a
排中律 aa1
矛盾律 aa0
蕴涵等值式 abab
等价等值式 ab(ab)(ba)
假言易位 abba
等价否定等值式 abab
归谬论ab)(ab) a
求主析取范式的步骤。
设公式a含命题变项p1,p2,…,pn
1) 求a的析取范式a=b1 b2 … bs, 其中bj是简单合取。
式 j=1,2, …s
2) 若某个bj既不含pi, 又不含pi, 则将bj展开成
bj bj(pipi) (bjpi)(bjpi)
重复这个过程， 直到所有简单合取式都是长度为n的极小。
项为止。3) 消去重复出现的极小项， 即用mi代替mimi
4) 将极小项按下标从小到大排列。
快速求法。设公式含有n个命题变项， 则。
长度为k的简单合取式可展开成2n-k个极小项的析取。
例如公式含p,q,r
q (pqr)(pqr)(pqr)(pqr)
m2 m3 m6 m7
由主析取范式求主合取范式。
设。没有出现的极小项是。
则。重言式的主析取范式含全部2n个极小项。
矛盾式的主析取范式不含任何极大项， 记作0
矛盾式的主合取范式含全部2n个极大项。
重言式的主合取范式不含任何极大项， 记作1
推理定律——重言蕴涵式。
a(a∨b) 附加律
a∧b)a 化简律。
a→b)∧ab 假言推理。
a→b)∧ba 拒取式。
a∨b)∧ba析取三段论。
a→b)∧(b→c) (a→c) 假言三段论。
ab)∧(bc) (ac) 等价三段论。
a→b)∧(c→d)∧(a∨c) (b∨d) 构造性二难
a→b)∧(a→b) b 构造性二难(特殊形式)
a→b)∧(c→d)∧(b∨d) (a∨c) 破坏性二难。
归缪法。例构造下面推理的证明。
前提： (p∧q)∨r, r→s, s, p
结论： q证明用归缪法。
q 结论否定引入。
r→s 前提引入。
s 前提引入。
r拒取式。
(p∧q)∨r 前提引入
(p∧q) ④析取三段论。
p∨q ⑥置换。
p析取三段论。
p 前提引入。
p∧p ⑧⑨合取。
由于p∧p是矛盾式，所以推理正确，q是有效结论。
一阶逻辑。个体词： 所研究对象中可以独立存在的具体或抽象的客体。
个体常项：具体的事务，用a, b, c表示。
个体变项：抽象的事物，用x, y, z表示。
个体域（论域）: 个体变项的取值范围。
有限个体域，如，
无限个体域，如n, z, r, …
全总个体域： 宇宙间一切事物组成
如果事先没有给出个体域，都应以全总个体域为个体域。
谓词： 刻划个体词性质或相互之间关系的词。
谓词常项：表示具体性质和关系的谓词， 用f, g, h…表示；
谓词变项：表示抽象或泛指的谓词， 也用f, g, h…表示；
一元谓词： 表示事物的性质。
多元谓词(n元谓词， n2): 表示事物之间的关系。
如 l(x,y)：x与y有关系l，l(x,y)：xy，…
0元谓词： 不含个体变项的谓词， 即命题常项或命题变项
例2 在一阶逻辑中将下面命题符号化
(1)人都爱美； (2) 有人用左手写字。
分别取(a) d为人类集合， (b) d为全总个体域 .
解：(a) d为人类集合。
1) 设g(x)：x爱美， 符号化为 x g(x)
(2) 设g(x)：x用左手写字， 符号化为 x g(x)
b) d为全总个体域。
设f(x)：x为人，g(x)：同(a)中。
1) x (f(x)g(x))
2) x (f(x)g(x))
命题符号化设d 为个体域。
1）“d中所有x都有性质f”
2）“d中存在x具有性质f”
3）“对d中所有x而言，如果x有性质f，则x就有性质g”
4）“d 中存在x具有性质f，又有性质g”
5）“对于d中所有x和y而言，若x有性质f，y有性质g，则x与y有关系h” xy(f(x)g(y)h(x,y))
兔子比乌龟跑得快。
6）“对于d中所有x而言，若x有性质f，就存在y具有性质g，并且x与y有关系h” x (f(x) y (g(y) h(x,y)) 所有的兔子比某些乌龟跑得快。
7）“存在d中的x有性质f，并且对于d中所有y而言，如果y有性质g，则x与y有关系h” x(f(x)(y (g(y)h(x,y)))
有的兔子比所有的乌龟跑得快。
8）“d中的存在着x与y ，x有性质f，y有性质g，并且 x与y有关系h” xy(f(x)g(y)l(x,y))
存在跑得同样快的兔子和乌龟。
等值式与基本等值式
基本等值式：
命题逻辑中16组基本等值式的代换实例。
如，xf(x)yg(y) xf(x)yg(y)
(xf(x)yg(y)) xf(x)yg(y) 等
消去量词等值式设d=
xa(x)a(a1)a(a2)…a(an)
xa(x)a(a1)a(a2)…a(an)
例设个体域d=, 消去下面公式中的量词：
2) x(f(x)yg(y))
xf(x)yg(y) 量词辖域收缩。
f(a)f(b)f(c))(g(a)g(b)g(c))
3) xyf(x,y)
x(f(x,a)f(x,b)f(x,c))
(f(a,a)f(a,b)f(a,c))(f(b,a)f(b,b)f(b,c))
(f(c,a)f(c,b)f(c,c))
量词否定等值式
设a(x)是含x自由出现的公式。
xa(x) x a(x)
xa(x) x a(x)
量词辖域收缩与扩张等值式
设a(x)是含x自由出现的公式，b中不含x的出现。
关于全称量词的：
x(a(x)b)xa(x)b
x(a(x)b)xa(x)b
x(a(x)b)xa(x)b
x(ba(x))bxa(x)
关于存在量词的：
x(a(x)b)xa(x)b
x(a(x)b)xa(x)b
x(a(x)b)xa(x)b
x(ba(x))bxa(x)
量词分配等值式
x(a(x)b(x))xa(x)xb(x)
x(a(x)b(x))xa(x)xb(x)
注意：对无分配律，对无分配律
求公式的前束范式的方法： 利用重要等值式、
置换规则、换名规则、代替规则进行等值演算。
离散数学复习
离散数学 复习资料 2014年12月。一 单项选择题 每小题3分，本题共15分 1 若集合a b 则下列表述正确的是 a a ab，且a b b ba，且a b c ab，且ab d ab，且a b 2 设有向图 a b c 与 d 如图一所示，则下列结论成立的是 d 图一。a a 是强连通的b b...
离散数学作业
集合恒等式与等价关系的判定。单个文件上传形式 一 一 集合运算跟我练习 每题10分，共20分 1 设集合a b a,b 求ba，ab和a b，ba 解 b a a,b a b a,b ab a,b ba 2 设a，b，c为任意集合，试证 ab c a bc 证明设任意x ab c，那么xab或 xc...
离散数学作业
集合恒等式与等价关系的判定。一 集合运算跟我练习 每题10分，共20分 1 设集合a b a,b 求ba，ab和a b，ba 解 ba a,b a,b b a b a,b 2 设a，b，c为任意集合，试证 ab c a bc 证明设任意x ab c，那么xab或 xc 也就是xa或xb或xc，由此得...