例3 给出下列公式的真值表
(P Q R) P
PQ R PQ PQR A
000 0
0 01 0
010
0
0 11 0
10 0
0
101 0
11 0 1
111 1
1 1 1 1
0
0
0 0
11
110
1 1
1
成真指派：100，101，110，111
2020/8/12
总复习
1 of 65
例4
试求下面公式的主析取（主合取）范式，并写 出成真指派和成假指派。
x A (A B)
x {x x A x ( A B)} x {x x A (x A B)} x {x x A (x A x B)}
x {x x A (x A x B)}
x {x x A x B}
x A B 因为 x 是任意的,所以有
x ((x A (A B)) (x A B)) 的真值为T,
例: 求幺元、零元、逆元
• N, I, Q, R上的普通加法 + 和乘法 * +：幺元 0，a-1 = -a； *：幺元 1，零元 0， a-1 = 1/a； • 命题公式集合上的 和 ：幺元F，零元T ：幺元T，零元F • 幂集P(S)上的∪和∩
a)不是所有的男人都比女人高。 M(x):x是男人，W(x):x是女人，H(x,y):x比y高。
x (M (x) y (W ( y) H (x, y)))
2020/8/12
总复习
4 of 65
例2 证明ຫໍສະໝຸດ a)x(A(x) B(x)),xB(x) xA(x)
证明 1)x(A(x) B(x)) P
h
i 最大元：无
最小元：无
f
g B={a,b,c,d,e,f,g}
bc
d
a
e 上界： h,i,j,k
下界：无 无上（下）确界
2020/8/12
总复习
14 of 65
x1 例10 判断y1 函数x1的类型 y1
x2
y2
x2
y2
x3
y3
映射函数 y4
x3
y3
入 射 y4
x1 x2
x3 x 4 2020/8/12
X {a,b, c}, R { a,b , b,c }
解：
r(R) R I X
R { a, a , b,b , c,c }
{ a,b , b,c , a, a , b,b , c,c }
s(R) R RC
{ a,b , b,c , b, a , c,b }
2020/8/12
总复习
1 2
3
5
2020/8/12
总复习
12 of 65
例8 画出哈斯图 P{a, b, c}, R
{a,b, c}
{a, b}
{a, c} {b, c}
{a}
{c} {b}
2020/8/12
总复习
13 of 65
例9 求极大（小）元，最大（小）元、上（下）
界，上（下）确界
j
k 极大元：j,k
极小元:a,b,e
2)A(u) B(u)
US1)
3)xB( x)
P
4)B(u)
US3)
5) A(u)
T 2)4)
6)xA( x)
EG5)
2020/8/12
总复习
5 of 65
例1 求集合的幂集
P( ) {x x } {} P({}) {,{}} P({,{}}) {,{},{{}}, {,{}}}
2020/8/12
满射
y1 y2
y3
总复习
x1
y1
x2
y2
x3
y3
双(入、满)射 15 of 65
例11 求复合函数
X {1,2,3}, Y {p, q}, Z {a,b} f { 1, p , 2, p , 3, q } g { p,b , q,b }
求g f
g f { 1,b , 2,b , 3,b }
总复习
6 of 65
例2
• n 个元素的集合上，可以定义多少个关系？
(2n2 )
• 设集合X,Y, |X|=m, |Y|=n，可以定义多少个
从X到Y的函数？
nm (|Y||X| )
2020/8/12
总复习
7 of 65
例3 对任意两个集合A, B,试证 A (A B) A B
证明 对于任意的x
A ( A B) A B 因此 2020/8/12
总复习
8 of 65
例4 判断关系的性质
R1 { a, a , a,b , b,b , c,c }
a
1 1 0
M R 1 0 1 0
0 0 1
cb R1
R1 是自反的、反对称、传递的。
2020/8/12
总复习
9 of 65
例5 求关系的闭包
(P Q) (Q P)
(P Q) (Q P)
(P Q) Q P
(P Q) (Q (P P)) (P (Q Q))
(P Q) (P Q) (P Q)
0,2,3 1
(P Q)
2020/8/12
成真指派：00，10，11 成假指派：01
总复习
2 of 65
10 of 65
例5（续） X {a,b,c}, R { a,b , b,c }
R(2) { a, c }
R(3)
t(R) R R(2) R(3)
{ a,b , b,c }{ a,c }
{ a,b , b,c , a,c }
2020/8/12
总复习
11 of 65
例7 设 A={1,2,3}, 求出A上所有的等价关系
例5 试证 Q (P (P Q)) Q P
证明 Q (P (P Q)) Q (P (P Q)) Q ((P P) (P Q)) Q (P (P Q)) ( Q P) (P Q Q) Q P QP
2020/8/12
总复习
3 of 65
例1 符号化下列命题
2020/8/12
总复习
16 of 65
例12 求复合函数
X {1,2,3}, Y {p, q}, Z {a,b} f { 1, p , 2, p , 3, q } g { p,b , q,b }
求g f
g f { 1,b , 2,b , 3,b }
2020/8/12
总复习
17 of 65
解： 先求A的各种划分：
1 2
3
1 2
3
1 2
3
1 2
3
1 2
3
4
设对应于 i 的等价关系为Ri ,则：
R1={<1,1>,<2,2>,<3,3>} = IA
R2={<1,2>,<2,1>} ∪ IA
R3={<1,3>,<3,1>} ∪ IA
R4={<2,3>,<3,2>} ∪ IA R5={<1,2>,<1,3>,<2,1>,<2,3>, <3,1>,<3,2>} ∪ IA