量词的辖域
定义:量词的辖域是邻接量词之后的最小子公式，故除非辖域是个原子公式，否则应在该子公式的两端有括号。
例：?XP(X)→Q(X)
?X的辖域是P(X)
?X(P(X,Y)→Q(X，Y) ) ∨ P(Y,Z)
?X的辖域是P(X，Y)→Q(X，Y)
有限个体域上消去量词
例15: 个体域D={a,b,c}, 则消去下面公式中的量词?x?yF(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)) 例16：设个体域D={a,b}，消去下面各公式中的量词：
(1) ?x?y(F(x) →G(y)) ??x(F(x)→?y G(y))
??xF(x)→?y G(y) ? (F(a)∨F(b))→(G(a)∨G(b))
(2) ?x?y(F(x,y) →G(x,y))
??x((F(x,a) →G(x,a))∨(F(x,b)→G(x,b))
?((F(a,a) →G(a,a))∨(F(a,b)→G(a,b)))∧
((F(b,a) →G(b,a))∨(F(b,b)→G(b,b)))
注：(1)中量词辖域可以缩小，先缩小量词辖域，再消量词，演算简单；但在(2)中，因为全称量词和存在量词均约束F与G中个体变量，因而它们的辖域不能缩小，消去量词后的公式也不易化的更简单。
例17 将下面命题用两种形式符号化, 并证明两者等值:
(1) 没有不犯错误的人
解令F(x)：x是人，G(x)：x犯错误.
??x(F(x)∧?G(x)) 或?x(F(x)→G(x
??x(F(x)∧?G(x))
??x?(F(x)∧?G(x)) 量词否定等值式
??x(?F(x)∨G(x)) 置换
??x(F(x)→G(x)) 置换
(2) 不是所有的人都爱看电影
解令F(x)：x是人，G(x)：爱看电影.
??x(F(x)→G(x)) 或?x(F(x)∧?G(x))
??x(F(x)→G(x))
??x?(F(x)→G(x)) 量词否定等值式
??x?(?F(x)∨G(x)) 置换
??x(F(x)∧?G(x)) 置换
例18 求下列公式的前束范式
(1) ??x(M(x)∧F(x))
解??x(M(x)∧F(x))
??x(?M(x)∨?F(x)) （量词否定等值式）
??x(M(x)→?F(x))
后两步结果都是前束范式，说明公式的前束范式不惟一.
(2) ?xF(x)∧??xG(x)
解?xF(x)∧??xG(x)
??xF(x)∧?x?G(x) （量词否定等值式）
??x(F(x)∧?G(x)) （量词分配等值式）
或
?xF(x)∧??xG(x)
??xF(x)∧?x?G(x) 量词否定等值式
??xF(x)∧?y?G(y) 换名规则
??x?y(F(x)∧?G(y)) 辖域收缩扩张规则
(3) ?xF(x)→?y(G(x,y)∧?H(y))
解?xF(x)→?y(G(x,y)∧?H(y))
??zF(z)→?y(G(x,y)∧?H(y)) 换名规则
??z?y(F(z)→(G(x,y)∧?H(y))) 辖域收缩扩张规则
或
??xF(x)→?y(G(z,y)∧?H(y)) 代替规则
??x?y(F(x)→(G(z,y)∧?H(y)))
推理定理
第一组命题逻辑推理定理的代换实例
如, ?xF(x)∧?yG(y) ??xF(x)
第二组基本等值式生成的推理定理
如, ?xF(x) ????xF(x), ???xF(x) ??xF(x)
??xF(x)??x?F(x), ?x?F(x) ???xF(x)
第三组其他常用推理定律
(1) ?xA(x)∨?xB(x) ??x(A(x)∨B(x))
(2) ?x(A(x)∧B(x))??xA(x)∧?xB(x)
(3) ?x(A(x)→B(x)) ??xA(x)→?xB(x)
(4) ?x(A(x)→B(x)) ??xA(x)→?xB(x)
一个公式如果它的所有量词均非否定的出现在公式的最前面，且它们的辖域一直延伸到公式的末尾，此种形式的公式就叫前束范式。
定义设A为一个一阶逻辑公式，若A具有如下形式
Q
1x
1
Q
2
x
2
…Q k x k B
则称A为前束范式，其中Q i (1≤i≤k)为?或?，B为不含量词的公式.
例如，?x?(F(x)∧G(x))
?x?y(F(x)→(G(y)∧H(x,y))) 是前束范式
而??x(F(x)∧G(x))
?x(F(x)→?y(G(y)∧H(x,y))) 不是前束范式
注:任何公式的前束范式都是存在的，但一般说来并不是唯一的。四条重要的推理规则
A.全称量词消去规则，简记为UI
B.存在量词消去规则，简记为EI
C.存在量词引入规则，简记为EG
D.全称量词引入规则，简记为UG
1.全称量词消去规则UI
或
含义：如果个体域的所有元素都具有性质A，则个体域中的任一元素具有性质A。
(1) x是A(x)中自由出现的个体变项。
(2) y为任意的不在A(x)约束出现的个体变项。
(3) c为论域中任意的个体常项。
例如
(1) ?x(F(x)→G(x)) 前提引入
(2) F(a)→G(a) (1)UI
2. 全称量词引入规则UG
(1) y在A(y)中自由出现，且y取何值A(y)均为真。
(2) 取代y的x不能在A(y)中约束出现。
例：?y?xF(x,y) 个体域为实数集R,F(x,y):x＞y
设A(y)= ?xF(x,y), y在A(x)中是自由出现的,满足条件(1).
若取x代替y
得?xA(x) ??x?xF(x,x)
结论为“?x?x(x>x)”,是假命题。原因违背条件(2).
2. 存在量词消去规则EI
该式成立的条件是：
(1)c 是使A 为真的特定的个体常项。
(2)c 不在A(x)中出现。
(3)若A(x)中除自由出现的x 外，还有其它自由出现的个体变项，此规则不能使用。
4. 存在量词引入消去规则(?+)
① ②
③ ④
其中x ,y 是个体变项符号, c 是个体常项符号, 且在A 中y 和c 不在?x 和?x 的辖域内自由出现.
要特别注意使用?-、?+、?-、?+规则的条件.
反例1. 对A =?x ?yF (x ,y )使用?-规则, 推得B =?yF (y ,y ).
取解释I : 个体域为R,
在I 下A 被解释为?x ?y (x >y ), 真; 而B 被解释为?y (y >y ), 假 原因: 在A 中x 自由出现在?y 的辖域F (x ,y )内
反例2. 前提: P (x )→Q (x ), P (x )
结论: ?xQ (x )
A(c)
xA(x)∴?
取解释I : 个体域为Z, ,
在I 下前提为真, 结论为假, 从而推理不正确
“证明”:
① P (x )→Q (x ) 前提引入
② P (x ) 前提引入
③ Q (x ) ①②假言推理
④ ?xQ (x ) ③?+
错误原因: 在④使用?+规则, 而x 在前提的公式中自由出现.
例19在自然推理系统N L 中构造下面推理的证明, 取个体域R:
任何自然数都是整数. 存在自然数. 所以, 存在整数.
解 设F (x ):x 是自然数, G (x ):x 是整数.
前提: ?x (F (x )→G (x )), ?xF (x )
结论: ?xG (x )
证明:
① ?x (F (x )→G (x )) 前提引入 ② F (x )→G (x ) ①?-
③ F (x )→?xG (x ) ②?+
④ ?xF (x )→?xG (x ) ③?-
⑤ ?xF (x ) 前提引入 ⑥?xG (x ) ④⑤假言推理 例20在自然推理系统N L 中构造下面推理的证明, 取个体域R:
整除被是偶数2:)(,:)(x x Q x x P
不存在能表示成分数的无理数. 有理数都能表示成分数.
所以, 有理数都不是无理数.
解设F(x):x是无理数, G(x):x是有理数, H(x):x能表示成分数. 前提: ??x(F(x)∧H(x)), ?x(G(x)→H(x))
结论: ?x(G(x)→?F(x))
证明:
①??x(F(x)∧H(x)) 前提引入
②?x(?F(x)∨?H(x)) ①置换
③?x(F(x)→?H(x)) ②置换
④F(x)→?H(x) ③?-
⑤?x(G(x)→H(x)) 前提引入
⑥G(x)→H(x) ⑤?-
⑦H(x)→?F(x) ④置换
⑧G(x)→?F(x) ⑥⑦假言三段论
⑨?x(G(x)→?F(x)) ⑧?+
笛卡儿积
定义2 设A,B为集合，A与B的笛卡儿积记作A?B，且A?B = {
例 20 A={1,2,3}, B={a,b,c} 求笛卡儿积A?B,B?A
A?B
={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>} B?A
={
A?B ≠B?A (A≠B, A≠?, B≠?)
(2) 不适合结合律
(A?B)?C ≠A?(B?C) (A≠?, B≠?, C≠?)
(3) 对于并或交运算满足分配律
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)
(4) 若A 或B 中有一个为空集，则A?B 就是空集.
A?? = ??B = ?
(5) 若 |A| = m, |B| = n, 则 |A?B| = | B?A | =mn
例 21 (1) 证明A=B,C=D ?A?C=B?D
(2) A?C = B?D是否推出A=B,C=D? 为什么？
解 (1) 任取
?x∈A∧y∈C
?x∈B∧y∈D
?
(2) 不一定.反例如下：
A={1}，B={2}, C = D = ?, 则A?C = B?D但是A ≠B.
例22：设A， C， B， D为任意集合，判断以下命题是否为真，并
说明理由。
(1) A×B= A×C =>B= C
(2) A-(B×C)=( A-B)×(A-C)
(3) 存在集合A,使得A ? A × A.
解：
(1) 不一定为真。反例A= φ, B、C为任意不相等的非空集合。
(2) 不一定为真。反例A= {1}, B={2}, C={3}.
(3) 为真。当 A= φ时成立。
定义3 如果一个集合符合以下条件之一：
(1) 集合非空，且它的元素都是有序对
(2) 集合是空集
则称该集合为一个二元关系，记作R，简称为关系。
对于二元关系R，若
aR1b, 1R12, 5R16
定义5 设A 为集合,
(1) ?是A上的关系，称为空关系
(2)全域关系E A = {
恒等关系I A= {
小于等于关系 L A
整除关系D B
包含关系 R?
例如, A={1, 2}, 则
E A = {<1,1>,<1,2>,<2,1>,<2,2>}
I A = {<1,1>,<2,2>}
例如 A = {1, 2, 3}, 则
L A ={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}
D A ={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}
关系的定义域、值域与域分别定义为
dom R = { x | ?y (
ran R = { y | ?x (
fld R = dom R ? ran R
例 R ={<1,2>,<1,3>,<2,4>,<4,3>}, 则
dom R ={1, 2, 4}
ran R ={2, 3, 4}
fld R ={1, 2, 3, 4}
关系的表示:
关系图 例24： 例 A ={1,2,3,4}, R ={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}, R 的关系矩阵M R 和关系图G R 如下：
设R 是一个X 到Y 的关系， S 是一个Y 到Z 的关系 , 则R 与S 的合成关系 ( 或复合关系 ) : R ? S 为：
R ? S ={
?????
???????=0010000011000011R M
例 25 R = {<1,2>, <2,3>, <1,4>, <2,2>}
S = {<1,1>, <1,3>, <2,3>, <3,2>, <3,3>}
R?S = {<1,3>, <2,2>, <2,3>}
S?R = {<1,2>, <1,4>, <3,2>, <3,3>}
利用图示（不是关系图）方法求合成
R?S ={<1,3>, <2,2>, <2,3>}
S?R ={<1,2>, <1,4>, <3,2>, <3,3>}
设R 为A上的关系, R的性质主要有以下 5 种
(1) R 在A 上是自反的：?x(x∈A→
该定义表明在自反的关系R中，除其他有序对外，必须包括有全部由每个x∈A所组成的元素相同的有序对。在关系矩阵中，反映为主对角线元素均为1；在关系图中，反映为每结点都有自回路。例如：设A={1, 2, 3}, R 是 A 上的关系，
R={<1,1>,<2,2>, <3,3>, <1,2>}
则 R 是自反的
全域关系E A, 恒等关系I A, 小于等于关系L A, 整除关系D A都是自反关系
(2) R 在 A 上是反自反：?x(x ∈A →
该定义表明了，一个反自反的关系R中，不应包括有任何相同元素的有序对。在关系矩阵中，反映为主对角线元素均为0；在关系图中，反映为每结点都没有自回路。
例：设A={1,2,3}， R={<2,3>,<3,2>}， R是 A 上的关系，R是反自反的。
再如实数集上的小于关系、幂集上的真包含关系也是反自反关系。(3)若?x?y( x,y∈A∧
该定义表明在表示对称的关系R的有序对集合中，若有有序对
在关系矩阵中，反映为是对称矩阵；
在关系图中，反映为若有a到b的边则必有b到a的边。
例如：设A={1,2,3},R是A上的关系，
R={<1,2>,<2,1> ,<3,3>}
则R 是对称的
(4)若?x?y( x,y∈A∧
在关系矩阵中，反映为若a ij=1,则a ji=0 (注：若a ij=0,不一定有a ji=1)
在关系图上，反映为若存在a到b的边，则不存在b到a的边。
例如：设A={1,2,3}, R={<1,2>,<1,3>} 是A上的关系，则 R是
反对称的
(5)设R为A上的关系，若
?x?y?z(x,y,z∈A∧
则称R在A上是传递的关系。
例如：设A={1,2,3}，R1,R2,和R3是A上的关系，其中
R1={<1,1>,<2,2>} R2={<1,2>,<2,3>} R3={<1,3>}
说明R1，R2 和R3是否为A上的传递关系
解：R1和R3是A上的传递关系，R2不是A上的传递关系
集合
例 26 判断下列命题是否为真
(1) ???（1）
(2) ?∈?（0）
(3) ??{?} (1)
(4) ?∈{?} （1）
(5) { a, b } ? { a, b, c, {a, b, c}} （1）
(6) { a, b } ∈{ a, b, c, {a, b}} (1)
(7) { a, b} ? { a, b, {{a, b}}} (1)
(8) { a, b} ∈{ a, b, {{a,b}}} (0
)
解 (1)、(3)、(4)、(5)、(6)、(7)为真，其余为假.
例 27 判断以下命题的真假，并说明理由.
（1）A-B = A ?B=?
（2）A-(B?C) = (A-B)?(A-C)
（3）A⊕A = A
（4）如果A?B = B，则A = E.
（5）A = {x}?x，则x∈A且x ?A.
解
(1) B=?是A-B=A的充分条件，但不是必要条件. 当B不空但是与A不交时也有A-B=A.
(2) 这是DM律，命题为真.
(3) 不符合算律，反例如下：
A={1}，A⊕A=?，但是A≠?.
(4) 命题不为真. A?B=B的充分必要条件是B?A，不是A=E.
(5) 命题为真，因为x 既是A 的元素，也是A 的子集
例 28．设A,B为集合，试确定下列各式成立的充分必要条件：
(1) A-B=B
(2) A-B=B-A
(3) A?B=A?B
(4) A⊕B=A
解
(1) A-B=B ?A=B=?. 求解过程如下：
由A-B=B得
(A?~B)?B = B?B
化简得B=?. 再将这个结果代入原来的等式得A= ?. 从
而得到必要条件A=B=?.
再验证充分性. 如果A=B=?成立，则A-B=?=B也成立.
(2) A-B=B-A ?A=B. 求解过程如下：
充分性是显然的，下面验证必要性. 由A-B=B-A得
(A-B)?A=(B-A)?A
从而有A=A?B, 即A?B. 同理可证B?A.
商集
定义设R 为非空集合A上的等价关系, 以R 的所有等价类作为元素的集合称为A关于R的商集, 记做A/R,
A/R = {[x]
| x∈A}
R
实例设A={1,2,…,8}，A关于模3等价关系R的商集为
A/R = {{1,4,7}, {2,5,8}, {3,6}}
A关于恒等关系和全域关系的商集为：
A/I
= {{1}, {2}, …, {8}}，
A
A/E
= {{1,2,…,8}}
A
例28 .A＝{{a}, {b}, {a,b}, {a,b, c}, {a,b, c,d}, { a,b,c,e}}，画出< A, ? > 的哈斯图。
例 29 无向图G有16条边，3个4度顶点，4个3度顶点，其余顶点度数均小于3，问G的阶数n为几？
解 设除3度与4度顶点外，还有x 个顶点v 1, v 2, …, v x ， 则 d (v i ) ≤ 2，i =1, 2, …, x ，
于是
32 ≤ 24+2x
得 x ≥ 4, 阶数 n ≥ 4+4+3=11.
例 29设无向图G 有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G 至少有多少个顶点？在最少顶点的情况下，写出度数列、)()(G G δ、?。 解：由握手定理图G 的度数之和为：20102=?
3度与4度顶点各2个，这4个顶点的度数之和为14度。 其余顶点的度数共有6度。
其余顶点的度数均小于3，欲使G 的顶点最少，其余顶点的度数应都取2,所以，G 至少有7个顶点, 出度数列为3,3,4,4,2,2,2,2)(,4)(==?G G δ. 例 30设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点？
解：由握手定理图G 的度数之和为：1262=?
设2度点x 个，则1221513=+?+?x ，2=x ，该图有4个顶点. 例 31有向图D 如图
(1)求2v 到5v 长度为1，2，3，4的通路数；
(2)求5v 到5v 长度为1，2，3，4的回路数；
(3)求D 中长度为4的通路数；
(4)求D 中长度小于或等于4的回路数；
(5)写出D 的可达矩阵。
v3v4
解：有向图D 的邻接矩阵为：
???????? ??=01010001011000000101
10000A ，???????? ??=00202200000101020000010102A ???????
? ??=40000020200020202020002023A ????????
??=04040004044000000404400004A ???????
? ??
=+++4525
22252
4
5121
22252
55121
0432A A A A (1)2v 到5v 长度为1，2，3，4的通路数为0,2,0,0；
(2)5v 到5v 长度为1，2，3，4的回路数为0,0,4,0；
(3)D 中长度为4的通路数为32；
(4)D 中长度小于或等于4的回路数10；
(4)出D 的可达矩阵??
??
?
???
??=1111111111111111111111111P
离散数学复习要点第一章命题逻辑 一、典型考查点 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：他用功，命题“他虽聪明但不用功”的符号化正确的是（）
《离散数学》考试题库及答案 一、 填空 10% （每小题 2分） 1、 若P ，Q 为二命题，Q P ?真值为1，当且仅当 。 2、 对公式),()),(),((y x xR z x zQ y x yP ?∨?∧?中自由变元进行代入的 公 式 为 。 3、 )) (()(x xG x xF ??∧?的 前 束 范 式为 。 4、 设x 是谓词合式公式A 的一个客体变元，A 的论域为D ，A （x ）关于y 的自由的， 则 被称为全称量词消去规则，记为US 。 5、 与非门的逻辑网络为 。 二、 选择 30% （每小题 3分） 1、 下列各符号串，不是合式公式的有（ ）。 A 、R Q P ?∧∧)(； B 、)()((S R Q P ∧→→； C 、R Q P ∧∨∨； D 、S R Q P ∨∧∨?))((。 2、 下列语句是命题的有（ ）。 A 、2是素数； B 、x+5 > 6； C 、地球外的星球上也有人； D 、这朵花多好看呀！。 3、 下列公式是重言式的有（ ）。 A 、)(Q P ??； B 、Q Q P →∧)(； C 、P P Q ∧→?)(； D 、P Q P ?→)( 4、 下列问题成立的有（ ）。 A 、 若C B C A ∨?∨，则B A ?； B 、若C B C A ∧?∧，则B A ?； C 、若B A ???，则B A ?； D 、若B A ?，则B A ???。 5、 命题逻辑演绎的CP 规则为（ ）。 A 、 在推演过程中可随便使用前提； B 、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果； C 、如果要演绎出的公式为C B →形式，那么将B 作为前提，设法演绎出C ；
离散数学必备知识点总 结 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.1判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题。（1）2是无理数。 （2）5能被2整除。 （3）现在开会吗？ （4）x+5>0 （5）这朵花真是好看！ （6）2是素数当且仅当三角形有三条边。 （7）雪是黑色的当且仅当太阳是从东方升起。 （8）2000年10月1日天气晴好。 （9）太阳系以外的星球上有生物。 （10）小李在宿舍里。 （11）全体起立。 （12）4是2的倍数或是3的倍数。 （13）4是偶数且是奇数。 （14）李明和王华是同学。 （15）蓝色和黄色可以调配成绿色。 1..2 将上题中的命题符号化，并讨论他们的真值。 1.3判断下列各命题的真值。 （1）若2+2=4，则3+3=6； （2）若2+2=4，则3+3≠6； （3）若2+2≠=4，则3+3=6； （4）若2+2≠=4，则3+3≠=6； （5）2+2=4，当且仅当3+3=6； （6）2+2=4，当且仅当3+3≠6； （7）2+2≠4，当且仅当3+3=6； （8）2+2≠4，当且仅当3+3≠6； 1.4将下列命题符号化，并讨论其真值。 （1）如果今天是1号，则明天是2号； （2）如果今天是1号，则明天是3号； 1.5将下列命题符号化。 （1）2是偶数不是素数； （2）小王不但聪明而且用功； （3）虽然天气冷。老王还是来了； （4）他一边吃饭，一边看电视； （5）如果天下大雨，他就乘公交汽车来； （6）只有天下大雨，他才乘公交汽车来； （7）除非天下大雨，否则他不乘公交汽车来； （8）不经一事，不长一智； 1.5设p,q的真值为0 ，r,s的真值为1，求下列命题公式的真值。（1）p∨(q∧r);
一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝{3} ; ρ(A) - ρ(B)＝{3},{1,3},{2,3},{1,2,3}} . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = 2 2n. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是α1= {(a,1), (b,1)}, α2= {(a,2), (b,2)},α3= {(a,1), (b,2)}, α4= {(a,2), (b,1)}, 其中双射的是α3, α4 . 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是(P∧?Q∧R) 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为12，分枝点数为3. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝{4} ; A?B＝{1,2,3,4}; A－B＝{1,2} . 7.设R是集合A上的等价关系，则R所具有的关系的三个特性是自反性, 对称性传递性. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有(1, 0, 0), (1, 0, 1),(1, 1, 0) 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R2 = {(2,1),(3,2),(4,3)}, 则 R1?R2 ={(1,3),(2,2),(3,1)} , R2?R1 = {(2,4),(3,3),(4,2)} _ R12 ={(2,2),(3,3). 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = . 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = -1<=x<0 , B-A = {x | 1 < x < 2, x∈R} , A∩B ={x | 0≤x≤1, x∈R} , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除关系，则R以集合形式(列举法)记为 {(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)} . 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是?x(?P(x)∨Q(x)) . 15.设G是具有8个顶点的树，则G中增加21 条边才能把G变成完全图。(完全图的边 数 2)1 (- n n ，树的边数为n-1) 16.设谓词的定义域为{a, b},将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是_ (R(a)∧R(b))→(S(a)∨S(b)) _. 17. 设集合A＝{1, 2, 3, 4}，A上的二元关系R＝{(1,1),(1,2),(2,3)}, S＝{(1,3),(2,3),(3,2)}。则
集合论部分 第四章、二元关系和函数 集合的笛卡儿积与二元关系有序对 定义由两个客体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) A?B=B?A (交换律) 证?x x∈A?B ? x∈A 或x∈B, 自然有x∈B 或x∈A ? x∈B?A 得证A?B?B?A. 同理可证B?A?A?B. (2) A?(B?C)=(A?B)?(A?C) (分配律) 证?x x∈A?(B?C) ? x∈A或(x∈B且x∈C ) ?(x∈A或x∈B)且(x∈A或x∈C) ?x∈(A?B)?(A?C) 得证A?(B?C)?(A?B)?(A?C). 类似可证(A?B)?(A?C)?A?(B?C). (3) A?E=E (零律) 证根据并的定义, 有E?A?E. 根据全集的定义, 又有A? E?E. (4) A?E=A (同一律) 证根据交的定义, 有A?E?A. 又, ?x x∈A, 根据全集E的定义, x∈E, 从而x∈A且x∈E, ?x∈A?E 得证A?A?E. 例4 证明A?(A?B)=A（吸收律） 证利用例3证明的4条等式证明 A?(A?B) = (A?E)?(A?B) (同一律) = A?(E?B) (分配律) = A?(B?E) (交换律) = A?E (零律) = A (同一律) 例5 证明(A-B)-C=(A-C)-(B-C) 证(A-C)-(B-C) = (A ?~C) ? ~(B ? ~C) (补交转换律) = (A ?~C) ? (~B ? ~~C) (德摩根律) = (A ?~C) ? (~B ? C) (双重否定律) = (A ?~C? ~B)?(A ?~C? C) (分配律) = (A ?~C? ~B)?(A ??) (矛盾律) = A ?~C? ~B (零律,同一律) = (A ?~B) ? ~C (交换律,结合律)
【半群】G非空，·为G上的二元代数运算，满足结合律。 【群】（非空，封闭，结合律，单位元，逆元）恰有一个元素1适合1·a=a·1=a,恰有一个元素a-1适合a·a-1=a-1·a=1。 【Abel群/交换群】·适合交换律。可能不只有两个元素适合x2=1 【置换】n元置换的全体作成的集合Sn对置换的乘法作成n 次对称群。 【子群】按照G中的乘法运算·,子集H仍是一个群。单位子群{1}和G称为平凡子群。 【循环群】G可以由它的某元素a生成,即G=（a）。a所有幂的集合an，n=0，±1，±2，…做成G的一个子群，由a生成的子群。若G的元数是一个质数，则G必是循环群。 n元循环群（a）中,元素ak是（a）的生成元的充要条件是（n，k）=1。共有?（n）个。【三次对称群】{I（12）（13）（23）（123）（132）} 【陪集】a，b∈G，若有h∈H，使得a =bh，则称a合同于b（右模H），a≡b（右mod H）。H有限，则H的任意右陪集aH的元数皆等于H的元数。任意两个右陪集aH和bH或者相等或者不相交。 求右陪集：H本身是一个；任取a?H而求aH又得到一个；任取b?H∪aH而求bH又一个。G=H∪aH∪bH∪… 【正规子群】G中任意g，gH=Hg。（H=gHg-1对任意g∈G都成立） Lagrange定理G为有限群，则任意子群H的元数整除群G的元数。 1有限群G的元数除以H的元数所得的商，记为（G：H），叫做H在G中的指数，H的指数也就是H的右（左）陪集的个数。 2设G为有限群,元数为n,对任意a∈G，有an=1。 3若H在G中的指数是2，则H必然是G的正规子群。证明：此时对H的左陪集aH，右陪集Ha，都是G中元去掉H的所余部分。故Ha=aH。 4G的任意多个子群的交集是G的子群。并且，G的任意多个正规子群的交集仍是G的正规子群。 5 H是G的子群。N是G的正规子群。命HN为H的元素乘N的元素所得的所有元素的集合，则HN是G的子群。 【同态映射】K是乘法系统，G到K的一个映射σ（ab）=σ（a）σ（b）。 设（G，*），（K，+）是两个群，令σ：x→e，?x∈G，其中e是K的单位元。则σ是G到K 内的映射，且对a，b∈G，有σ（a*b）=e=σ（a）+ σ（b）。即，σ是G到K的同态映射，G～σ（G）。σ（G）={e}是K的一个子群。这个同态映射是任意两个群之间都有的。 【同构映射】K是乘法系统，σ是G到σ（G）上的1-1映射。称G与σ（G）同构，G?G′。同构的群或代数系统，抽象地来看可以说毫无差别。G和G′同态，则可以说G′是G的一个缩影。 【同态核】σ是G到G′上的同态映射，核N为G中所有变成G′中1′的元素g的集合，即N=σ-1（1′）={g∈G∣σ（g）=1′}。 N是G的一个正规子群。对于Gˊ的任意元素aˊ，σ-1(aˊ)={x|x∈G ,σ(x)= aˊ}是N在G 中的一个陪集。Gˊ的元素和N在G中的陪集一一对应。 设N是G的正规子群。若A，B是N的陪集，则AB也是N的陪集。 【环】R非空，有加、乘两种运算 a+b=b+a2）a+（b+c）=（a+b）+c， 3）R中有一个元素0，适合a+0=a， 4）对于R中任意a,有-a,适合a+(-a)=0， 5）a（bc）=（ab）c，
离散数学 一、逻辑和证明 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也是可数的。
离散数学试题一（A 卷答案） 一、（10分）证明(A ∨B )(P ∨Q )，P ，(B A )∨P A 。 二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4 种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。 三、（10分）指出下列推理中，在哪些步骤上有错误为什么给出正确的推理形式。 (1)x (P (x ) Q (x )) P (2)P (y )Q (y ) T (1)，US (3)xP (x ) P (4)P (y ) T (3)，ES (5)Q (y ) T (2)(4)，I (6)xQ (x ) T (5)，EG 四、（10分）设A ＝{a ，b ，c}，试给出A 上的一个二元关系R ，使其同时不满足自反性、反自反性、 五、（15分）设函数g ：A →B ，f ：B →C ， (1)若f o g 是满射，则f 是满射。 (2)若f o g 是单射，则g 是单射。 六、（15分）设R 是集合A 上的一个具有传递和自反性质的关系，T 是A 上的关系，使得T R 且R ，证明T 是一个等价关系。 七、（15分）若
离散数学习题答案 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ?→∧∧ 解：原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧ ()()p q r p q r ??∧∧∨∧∧37m m ?∨，此即公式的主析取范式， 所以成真赋值为011，111。 6、求下列公式的主合取范式，并求成假赋值： （2）()()p q p r ∧∨?∨ 解：原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?，此即公式的主合取范式， 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()p q r ∧∨ 解：原式()(()())p q r r p p q q r ?∧∧?∨∨?∨∧?∨∧ ()()()()()()p q r p q r p q r p q r p q r p q r ?∧∧?∨∧∧∨?∧?∧∨?∧∧∨∧?∧∨∧∧ ()()()()()p q r p q r p q r p q r p q r ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ? ∨∨∨∨，此即主析取范式。 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式： （1）()()p q p r ∨∨?∧ 解：公式的真值表如下：
由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式 1234567m m m m m m m ?∨∨∨∨∨∨ 习题三及答案：（P52-54） 11、填充下面推理证明中没有写出的推理规则。 前提：,,,p q q r r s p ?∨?∨→ 结论：s 证明： ① p 前提引入 ② p q ?∨ 前提引入 ③ q ①②析取三段论 ④ q r ?∨ 前提引入 ⑤ r ③④析取三段论 ⑥ r s → 前提引入 ⑦ s ⑤⑥假言推理
数理逻辑部分 第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)中
离散数学练习题 一、填空题 1. 命题Q →P 的真值为0，当且仅当 。 2. 构造公式S R S R →∨∧)(的真值表 。 3. 仅用∧和┐写出下列表达式的等价形式 a) R Q P ?→∨?? b) P Q ∨? 4. 仅用∨和┐写出下列表达式的等价形式 a) )()(D C B A ∨→∨? 。 b) )(E D A ?→→?? 5. 公式A 有三个命题变元P 、Q 、R 组成，其主析取范式为A 6531m m m m ∨∨∨?，则其主合取 范式为： 6. 公式A 有三个命题变元P 、Q 、R 组成，其主合取范式为A ?65310M M M M M ∧∧∧∧，则 其主析取范式为： 。 7. 设解释I 如下： D={n ，m} P(n ，n) P(n ，m) P(m ，n) P(m ，m) 1 1 0 0 8. 确定下列各式的真值： ),(m x xP ? ___ ___; ),(y n yP ? __ ___; ),(y x yP x ??) __ ___。 ),(n x xP ? ___ ___; ),(y m yP ? __ ___; ),(y x yP x ??) __ ___。 9. 谓词合式公式)()(x xQ x xP ?→?的前束范式为 。 10. 某集合有101个元素，则有 个子集的元素为奇数。 11. 某班有32个学生，其中14个人选择艺术，7个人选择生物，6个人选择音乐，三门课都选的有 2人，问这三门课都没选的至少有 人？ 12. 设全集U={1,2,3,4,5,6,7,8,9,10}, A={1,2,3,5,6}, B={2,4,6,8,9}, 则：A ∩B= , B ⊕A= , B A ?= ; (A ∪B)-B = , (A ∪B)-(B ∩C)= 13. =Φ=)(},,a {A A ρ 。 14. B A b a B A ×==2},,{},1{= =×B A )(ρ
数理逻辑部分 第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、 P ：你努力，Q ：你失败。 2、 “除非你努力，否则你将失败”符号化为 ； “虽然你努力了，但还是失败了”符号化为 。 2、论域D={1，2}，指定谓词P 则公式x ??真值为 。 3设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则 R= （列举法）。 R 的关系矩阵M R = 。 4、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系 R= ；A 上既是对称的又是反对称的关系R= 。 5、设代数系统，其中A={a ，b ，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 6、4阶群必是 群或 群。 7、下面偏序格是分配格的是 。
8、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。 二、选择 1、在下述公式中是重言式为（ ） A ．)()(Q P Q P ∨→∧； B ．))()(()(P Q Q P Q P →∧→??； C ．Q Q P ∧→?)(； D ．)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为（ ），成真赋值的个数为（ ）。 A ．0； B ．1； C ．2； D ．3 。 3、设}}2,1{},1{,{Φ=S ，则 S 2 有（ ）个元素。 A ．3； B ．6； C ．7； D ．8 。 4、设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生 的S S ?上一个划分共有（ ）个分块。 A ．4； B ．5； C ．6； D ．9 。 5、设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为 则R 具有（ ）性质。 A ．自反性、对称性、传递性； B ．反自反性、反对称性； C ．反自反性、反对称性、传递性； D ．自反性 。
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={