离散数学 复习资料

注：重要的是弄清楚前束范式的定义，求前束范式主要是利用基本等值式、蕴含式和换名规则，把一个谓词公式化为量词在最前面，后面不含量词的公式，即前束范式. 虽然前束范式是谓词公式的一种标准形式，但是一般一个谓词公式的前束范式并不是唯一的.

例2.6 构造推理证明

前提：?xF(x), ?x(F(x)?G(x)?H(x)) 结论：?x(F(x)?H(x))

证明：① ?xF(x) [前提引入] ②F(c) [①ES] ③ ?x(F(x)?G(x)?H(x)) [前提引入] ④ F(c)?G(c)?H(c) [③US] ⑤ G(c)?H(c) [②,④假言推理] ⑥ H(c)?G(c) [⑤置换] ⑦ H(c) [⑥化简]

⑧ F(c)?H(c) [②,⑦合取] ⑨ ?x(F(x)?H(x)) [EG]

例2.7 单项选择题

1. 谓词公式?x(P(x)??yR(y))?Q(x)中量词?x的辖域是( ) (A) ?x(P(x)??yR(y)) (B) P(x) (C) P(x)??yR(y) (D) Q(x) 答案：(C)

解答：?x后面的公式是P(x)?(?yR(y)). 故应选择(C).

2. 谓词公式?xA(x)???xA(x)的类型是（ ） (A) 永真式 (B) 矛盾式

(C) 非永真式的可满足式 (D) 不属于(A),(B),(C)任何类型 答案：(B)

解答：对于任意解释I，?xA(x)???xA(x)?0 所以?xA(x)???xA(x)是永假式. 选择(B).

3 设个体域为整数集，下列公式中其真值为1的是( )

(A) ?x?y(x?y?0) (B) ?y?x(x?y?0)

(C)?x?y(x?y?0) (D) ??x?y(x?y?0)

答案：(A) 解答：任意一个整数x，都能找到y＝－x，使x+y=0, 故(A)式是永真式. 4 设L(x)：x是演员，J(x)：x是老师，A(x,y)：x佩服y. 那么命题“所有演员都佩服某些老师”符号化为( )

(A) ?xL(x)?A(x,y) (B) ?x(L(x)??y(J(y)?A(x,y)) (C) ?x?y(L(x)?J(y)?A(x,y)) (D) ?x?y(L(x)?J(y)?A(x,y)) 答案：(B)

解答：将命题符号化为?x(L(x)??y(J(y)?A(x,y))，故应选择(B). 5 在谓词演算中，P(a)是?xP(x)的有效结论，根据是 ( ) (A)US规则 (B) UG规则 答案：(A)

(C)ES规则 (D)EG规则

?xA(x)解答：全称量词消去规则的定义为?A(c),即A(c)是?xA(x)的有效结论. 应选择(A).

例2.8 填空题

1.公式?x(P(x)?Q(x,y))??zR(y,z)?S(x))的自由变元是 , 约束

变元是 . 答案：y,x ; x,z

解答：?x的辖域是P(x)?Q(x,y),故x是约束出现，y是自由出现，?z的辖域是

R(y,z)，故z是约束出现，y是自由出现，而S(x)中的x是自由出现. 总之y,x是自由变元，

x,z是约束变元.

2. 谓词逻辑公式?xP(x)??xQ(x)的前束范式是 . 答案：?x(?P(x)?Q(x)) 解答：求前束范式

?xP(x)??xQ(x)??(?xP(x))??xQ(x)??x?P(x)??xQ(x)??x(?P(x)?Q(x))

3. 设个体域D＝{a,b},消去公式中的量词，则?xP(x)??xQ(x)? 答案：P(a)?P(b)?(Q(a)?Q(b)) 解答：由?x和?x真值的定义，

?xP(x)??xQ(x)?P(a)?P(b)?(Q(a)?Q(b))

4. 换名规则施于 变元，代入规则施于 变元 答案：约束；自由.

解答：见换名规则和代入规则的定义.

三、练习题

1. 将下列命题符号化：

(1) 丘华和李兵都是学生； (2) 存在偶素数；

2. 指出谓词公式?x(P(x)?Q(x))??xP(x)?Q(x)中量词的辖域，并指出变元的每

次出现是约束出现，还是自由出现，以及公式的约束变元，自由变元.

3. 设个体域D＝{岳飞，文天祥，秦荟}，谓词F(x)：x是民族英雄。求?xF(x)的真值。 4. 设P是二元谓词，给定解释I如下：D＝{a,b},P(a,a)=P(b,a)=1，P(b,a)=P(b,b)=0 求下列公式的真值：(1) ?xP(x,x)； (2) ?x?yP(x,y); (3) ?x?yP(x,y)

5.讨论公式?xF(x)??xF(x)的类型.

6. 用归谬法，构造下面的推理证明.

?xA(x)??xB(x)??x(A(x)?B(x))

四、练习题答案

1. (1) 设 P(x)：:x是学生。. a：丘华，b：黎兵 该命题符号化为：P(a)?P(b)

(2) 设N(x):x是自然数，F(x)：x是偶数，Q(x)：x是素数 该命题符号化为?x(N(x)?F(x)?Q(x))

2. 在公式?x(P(x)?Q(x))??xP(x)?Q(x)中,?x有二次出现，第一次出现的辖域是P(x)?Q(x)?Q(x)中; 第二次出现的辖域是P(x). 变元x在该公式中有六次出现，其中第1，4次出现和第2，3，5次出现均是约束出现；第6次是自由出现. 变元x在该公式中5次约束出现，1次自由出现. 因此变元x既是该公式的约束变元，也是自由变元. 3. 设a,b,c分别为岳飞，文天祥和秦桧，?xF(x)?F(a)?F(b)?F(c)?0 4.(1)0；(2)?x?y(P(y,x)??yP(y,a)??yP(y,b)?(P(a,a)?P(b,a))?(P(a,b)? P(b,b))?1?0?0

(3) ?x?y(P(x,y)??yP(a,y)??xP(b,y)=P(a,a)?P(a,b)?P(b,a)?P(b.b)?1

5. 设I为任意一个解释，D为个体域. ?xF(x)为假，则?xF(x)??xF(x)为真. ?xF(x)为真，即?x, F(x)为真, 显然?x0?D, F(x0)为真，即?xF(x)为真 则?xF(x)??xF(x)为真.

故在任何解释I下?xF(x)??xF(x)为真. ?xF(x)??xF(x)是永真式.

6. 前提：?xA(x)??xB(x) 结论：?x(A(x)?B(x))

证明：(1) ?(?x(A(x)?B(x))) [否定结论引入] (2) ?x(?(A(x)?B(x))) [T(1)E]

(3) ?(A(c)?B(c)) [(2)ES ] (4) A(c)??B(c) [ T(3) E]

(5) A(c) [(4)化简] (6) ?B(c)?A(c) [T(4) .E]

(7) ?B(c) [(6)化简] (8) ?xA(x)??xB(x) [P]

(9) ?x(?A(x)?B(x)) [(8)化简] (10) ?A(c)?B(c) [T(9) US] (11) ?A(c) [T(10),(7)I10] (12) ?A(c)?A(c)[T(11),(5)合取] 可见，推理成立。

第3章 集合论

本章重点：集合概念，集合的运算，集合恒等式的证明，笛卡儿积.

一、重点内容

1. 集合的概念

?集合与元素，具有确定的，可以区分的若干事物的全体称为集合，其中的事物叫元素.集合A中元素的个数为集合的元数?A?.

?集合的表示方法：列举法和描述法.

列举集合的元素，元素不能重复出现，集合中的元素无顺序之分. 集合与其元素之间存在属于“?”或不属于“?”关系.

2. 集合的关系：包含，子集，集合相等.

?包含(子集)，若?a?A?a?B，则B包含A(或A包含于B)，称A是B的子集，记

A?B，又A?B，则A是B的真子集，记A?B.

?集合相等，若A?B，B?A，则A＝B.

注意：元素与集合,集合与子集，子集与幂集，?与?(?)，空集?与所有集合等的关

系. 3. 特殊集合：全集、空集和幂集.

?全集合E，在一个具体问题中，所涉及的集合都是某个集合的子集，该集合为全集. ?空集?，不含任何元素的集合为空集. 空集是惟一的，它是任何集合的子集. ?集合A的幂集P(A)，有集合A的所有子集构成的集合

P(A)={xx?A}.

若?A?＝n, 则?P(A)?=2n. 4. 集合的运算 ?集合A和B的并A?B，由集合A和B的所有元素组成的集合. ?集合A和B的交A?B，由集合A和B的公共元素组成的集合. ?集合A的补集?A，属于E但不属于集合A的元素组成的集合，?A. 补集总相对于一个全集. ?集合A与B的差集A－B，由属于A，而不属于B的所有元素组成的集合.. ?集合A与B的对称差A?B，A?B＝(A－B)?(B－A)或A?B＝）A?B〕－（A?B）

应该很好地掌握10条运算律(运算的性质)(教材P71～72)，即交换律、结合律、分配律、幂等律、同一律、零律、补余律、吸收律、摩根律和双补律等. 5. 恒等式证明

集合运算部分有三个方面的问题：其一是进行集合的运算；其二是集合运算式的化简；其三是集合恒等式的推理证明. 集合恒等式的证明方法通常有二：(1)要证明A＝B，只需要证明A?B，又A?B；(2)通过运算律进行等式推导. 6. 有序对与笛卡儿积 ?有序对，就是有顺序的数组，如，x,y 的位置是确定的，不能随意放置. 注意：有序对?，以a,b为元素的集合{a,b}={b,a}；有序对(a,a)有意义，而集合{a,a}是单元素集合，应记作{a}. ?笛卡儿积，把集合A，B合成集合A×B，规定