第2章谓词逻辑
一、教学要求
1. 理解谓词、量词、个体词、个体域、原子公式、谓词公式和变元等概念。会将不太复杂的命题符号化。
2. 掌握在有限个体域下求公式的真值和某些公式在给定解释下真值的方法，判别公式类型(永真式、永假式和可满足式)的方法。
3. 掌握谓词演算的等值式和重言蕴含式(六种情况：(1)命题公式的推广；(2)量词否定式的等值式；(3)量词辖域扩张和收缩的等值式；(4)量词与联结词∨，∧，→的等值式；(5)量词与联结词的重言蕴含式；(6)两个量词公式间的等值式与重言蕴含式)。会进行谓词公式的等值演算。
4. 了解前束范式的概念，会求公式的前束范式。
5. 了解谓词逻辑推理的规则：全量词消去规则(US规则)；全量词附加规则(UG规则)；存在量词消去规则(ES规则)；存在量词附加规则(EG规则)
本章重点：谓词与量词，公式与解释，前束范式，谓词逻辑推理证明。
二、学习辅导
在命题逻辑中，我们把原子命题作为基本研究单位，对原子命题不再进行分解，只有复合命题才可以分解，揭示了一些有效的推理过程. 但是进一步研究发现，仅有命题逻辑是无法把一些常见的推理形式包括进去. 例如
“凡人要死，张三是人，张三要死”
显然是正确推理. 用命题逻辑解释三段式. 设
P：人要死；Q张三是人；R：张三要死。
表示成复合命题有
P∧Q→R
这不是重言式，即R不是前提P，Q的有效结论. 这反映了命题逻辑的局限性，其原因是把本来有内在联系的命题P，Q，R，视为独立的命题。要反映这种内在联系，就要对命题逻辑进行分析，分析出其中的个体词、谓词和量词，再研究它们之间的逻辑关系，总结出正确的推理形式和规则，这就是谓词逻辑的研究内容。
1. 谓词与量词
学习这一部分要反复理解谓词和量词引入的意义，概念的含义。
在谓词逻辑中，原子命题分解成个体词和谓词。个体词是可以独立存在的客体，它可以是具体事物或抽象的概念，如小张，房子，南京，大米，思想，实数2等等。谓词是用来刻划个体词的性质或事物之间的关系的词。例如
(1)(1)ln5是无理数；
(2)(2)高可比李木相高4cm；
(3) 郑州位于北京和广州之间。
这时三个简单命题，其中ln5，高可，李木相，郑州，北京，广州等都是个体词，而“是无理数”，“……比……高4cm”，“……位于……和……之间”等都是谓词。
个体词分个体常项(用a,b,c,d,…表示)和个体变项(用x,y,z,…表示)；谓词分谓词常项(表
示具体性质和关系的词)和谓词变项(表示抽象的或泛指的谓词)，用F,G,P,…表示。
个体常项a和个体变项都具有性质F，记作F(a)或F(x);个体常项a,与b或个体变项x 与y具有关系L,记作L(a,b)或L(x,y)。一般地，用F(a)表示a是无理数，其中a表示ln5，F 表示的是“…是无理数”。当F的含义不变时，则F(x)表示x是无理数，x是个体变项，F 谓词常项，F(x)不是命题，而是命题变项，F(a)是命题。用M(x,y,z)表示“z=x×y”，M(x,y,z)不是命题。a表示3，b表示5，c表示15，M(a,b,c)表示“15＝3×5”。M(a,b,c)是命题，真值为1，若c=12，那么M(a,b,c)是命题，真值为0。
注意，单独的个体词和谓词不能构成命题，将个体词和谓词分开不是命题。
例2.1将下列命题符号化：
(1) 丘华和李兵都是学生；
(2) 2既是偶数又是素数；
(3) 如果张华比黎明高，黎明比王宏高，则张华比王宏高。
解(1) 设个体域是人的集合。
P(x)：:x是学生。
a：丘华
b：黎兵
该命题符号化为P(a)∧P(b)
(2) 设个体域为正整数集合N＋。
F(x)：x是偶数，
Q(x)：x是素数
a：2
该命题符号化为F(a)∧Q(a)
(3)(3)设个体域是人的集合。
G(x,y)：x比y高。
a：张华
b：黎明
c：王宏
该命题符号化为G(a,b)∧G(b,c)→G(a,c)
量词是在命题中表示数量的词，量词有两类：全称量词?，表示“所有的”或“每一个”；存在量词?，表示“存在某个”或“至少有一个”。
例2.2将下列命题符号化
(1)(1)每个母亲都爱自己的孩子；
(2) 所有的人都呼吸；
(3) 有某些实数是有理数。
解(1) 设个体域是所有母亲的集合。
M(x)：x表示爱自己的孩子；
该命题符号化为?xM(x)。
(2) 设个体域为人的集合。
H(x)：x表示要呼吸。
该命题符号化为?xH(x)
或设个体域为生物集合，
M(x)：x是人。
H(x)：x 表示要呼吸。
该命题符号化为?x(M(x)→H(x))
(3) 设个体域为数的集合。
R(x)：x 表示实数
Q(x)：x 表示有理数。
该命题符号化?x(R(x)∧Q(x))。 在谓词逻辑，使用量词应注意以下几点：
(1) (1) 在不同个体域中，命题符号化的形式可能不同，命题的真值也可能会改变。
(2) (2) 在考虑命题符号化时，如果对个体域未作说明，一律使用全个体域。
(3) (3) 多个量词出现时，不能随意颠倒它们的顺序，否则可能会改变命题的涵义。
2. 公式与解释
学习这一部分内容要侧重于能将谓词逻辑公式表达式中，量词消除写成与之等值的公式，然后将解释中的数值代入，求出真值，并着重理解在谓词和量词的作用下变元的自由性、约束性和更名规则、代入规则等。
我们将命题常数0，1，一个命题和命题变元以及一个命题函数P (x 1,x 2,…,x n )，统称原子公式，由原子公式、联结词和量词可构成谓词公式(严格定义见教材)。命题的符号化结果都是谓词公式，例如?x(F(x)→G(x))，?x(F(x)∧G(x))，?x ?y(F(x)∧F(y)∧L(x,y)→H(x,y))等都是谓词公式，当然?x(F(x)∧G(x,y)),?x(F(x)→G(x,y))等也是谓词公式。
在谓词公式?xA 和?xA 中，x 是指导变元，A 是相应量词的辖域。在?x 和?x 的辖域A 中，x 的所有出现都是约束出现，即x 是约束变元，不是约束出现的变元，就是自由变元。也就是说，量词后面的式子是辖域。量词只对辖域内的同一变元有效。
例2.3 指出下列公式中量词的每次出现的辖域，并指出变元的每次出现是约束出现，还是自由出现，以及公式的约束变元，自由变元。
(1) ),()),(),((y x xH z y L y x R y x ?∧∨??
(2) )()())()((x Q x xP x Q x P x ∧?→∧?
解 (1) 在公式),()),(),((y x xH z y L y x R y x ?∧∨??中，?x 只有一次出现，辖域是)),(),((z y L y x R y ∨?；?y 只有一次出现，辖域是),(),(z y L y x R ∨；?x 只有一次出现，辖域是H (x ,y )。变元x 在公式),()),(),((y x xH z y L y x R y x ?∧∨??中有四次出现，其中第一次出现是在?x 中的出现，是约束出现；第二次出现是在?x 的辖域中的出现，也是约束出现；第三次出现是在?x 中的出现，也是约束出现；第四次出现是在?x 的辖域中的出现，也是约束出现。这四次出现都是约束出现，所以x 是该公式的约束变元。不是它的自由变元。变元y 在公式),()),(),((y x xH z y L y x R y x ?∧∨??中有四次出现。其中第一次是在?y 中的出现，是约束出现；第二次出现和第三次出现是在?y 的辖域中的出现，也是约束出现；第四次出现是自由出现。Y 在该公式中有三次约束出现，一次自由出现，因此变元y 既是该公式的约束变元，也是自由变元。变元z 在该公式),()),(),((y x xH z y L y x R y x ?∧∨??中
只有一次自由出现，所以z 是该公式的自由变元，约束也是变元。
(2) 在公式)()())()((x Q x xP x Q x P x ∧?→∧?中，?x 有二次出现，其第一次出现的辖域是)()(x Q x P ∧；其第二次出现的辖域是)(x P 。变元x 在公式)()())()((x Q x xP x Q x P x ∧?→∧?中有六次出现，其中第一次出现和第四次出现是在?x 中的出现，是约束出现；第二次出现和第三次出现是在?x 的第一次出现的辖域中的出现，是约束出现，第五次出现是在?x 的第二次出现的辖域中的出现，也是约束出现；x 的第六次出现是自由出现。变元x 在该公式中五次约束出现，一次自由出现。因此变元x 既是该公式的约束变元，也是自由变元。
从例3看到，同一个个体变项，在同一个公式中，既可以是约束出现，也可以是自由出现，这种情况有时会造成一些混淆，带来不变。要改变这种情况，使一个个体变项在同一个公式中不同时既是约束出现，又是自由出现，采取换名规则或代入规则。
换名规则，就是把公式中量词的指导变元及其该量词的辖域中的该变元换成该公式中没有出现的个体变元，公式的其余部分不变。
代入规则，就是把公式中的某一自由变元，用该公式中没有出现的个体变元符号替代，且要把该公式中所有的该自由变元都换成新引入的该符号。
如例3(1)中，变元y 既是约束出现，又是自由出现，把约束变元y 换名为u.。于是原公式换为
),()),(),((y x xH z u L u x R u x ?∧∨??
也可以将自由变元y 代换为t ，原公式变为
),()),(),((t x xH z y L y x R y x ?∧∨??
都是与原公式等值的。
例3(2)中，原公式换为 )()())()((t Q u uP x Q x P x ∧?→∧?
是与原公式等值的，且个体变元符号不再相同。
谓词公式只是一个符号串，没有什么意义，但我们给这个符号串一个解释，使它具有真值，就变成一个命题。所谓解释就是使公式中的每一个变项都有个体域中的元素相对应。 解释有四部分组成：
(1) 非空个体域D ；
(2) D 中有一部分特定元素，用来解释个体常项；
(3) D 上一些特定函数，用来解释出现的函数变项；
(4) D 上一些特定谓词，用来解释谓词变项。
例2.4 给定解释I ： ① D ＝{2,3};
② D 中特定元素a=2；
③ 函数为2)3(,3)2(==f f
④ 谓词F(x)为F(2)=0,F(3)=1
G(x,y)为G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=1
L(x,y)为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0
求在解释I 下各公式的真值。
(1) ),()(a x G x xF ∧?;
(2) )))(,())(((x f x G x f F x ∧?；
(3) ),(y x yL x ??；
(4) ),(y x xL y ??。 解 设所求四个公式分别记作A ，B ，C ，D 。有
000)01()00())2,3()3(())2,2()2(()),()(()1(?∧?∧∧∧?∧∧∧?∧?G F G F a x G x F x
1)10()11())2,3()2(())3,2()3(())
3(,3())3((()))2(,2())2((()))(,())((()2(?∧∨∧?∧∨∧?∧∨∧?∧??G F G F f G f F f G f F x f x G x f F x B
111)10()01()}
3,3()3,3({)}2,3()2,3({)3,2()3,2()]2,2()2,2({[)]
,3(),3(([)],2(),2(([),()3(?∧?∨∧∨?∧∨∧∧∧∨∧?∧?∧∧?????L L L L L L L L y L y L y y L y L y y x yL x C
000)10()01()]
3,3()3,2([)]2,3()2,2([)]
3,(([)]2,(([),()4(?∨?∧∨∧?∧∨∧??∨?????L L L L x L x x L x y x xL y D
由例4的(3)，(4)可知，量词的次序不能随便颠倒。
和命题逻辑一样，在谓词逻辑中，有的公式在任何解释下都真，也有的公式在任何解释下都假。以此，把公式分为三类：在任何解释下公式A 为真，或者公式A 的真值表全为1，这就是永真式；在任何解释下公式A 为假，或者公式A 的真值表全为0，这就是永假式；公式A 不总是假，或者公式A 的真值表至少有一个1，这就是可满足式。由此可见，永真式也是可满足式。
一般地，判定一个公式是不是可满足式，还没有一定的算法。但是，可以证明，重言式的代换实例一定是永真式。而矛盾式的代换实例均为矛盾式。
例2.5 讨论下列公式的类型： (1) )()(x xF x xF ?→?;
(2) ),(),(y x yF x y x yF x ??→??
证明 设(1)，(2)的公式分别记作A ，B 。 (1) 设I 为任意一个解释，其个体域为D ，若存在D x ∈0,使得F(x 0)为假，则)(x xF ?为假，从而A 为真。若对于任意的D x ∈,F(x)均为真。则)(x xF ?与)(x xF ?都为真。从而A
也为真。故在解释I 下A 为真。由于I 的任意性，所以A 是永真式。
(2) (2) 取解释I 如下：个体域仍为自然数集，F(x,y)：x ≤ y 。 在I 下，B 的前、后件
均为真。所以B 为真，这说明B 不是是矛盾式；
再取解释I '：个体域认为N 。F(x,y)：x=y 。在解释I '下，B 的前件为真，后件为假。故B 为假，这又说明B 不是永真式。
综上所述，B 是非永真式的可满足式。
3. 前束范式
一个谓词公式的前束范式，仍然是谓词公式，只是把谓词公式的所有量词均提到公式的开头，而且它的辖域一直延伸到公式的末尾。如若一个谓词公式F 等值地转化成 B x Q x Q x Q k k (2211)
那么B x Q x Q x Q k k ...2211就是谓词公式F 的前束范式，其中Q 1，Q 2，…，Q k 只能是?或?，而x 1,x 2,…,x k 是个体变元，B 是不含量词的谓词公式。如
),,,()()(())),,()(()((z y x G y F x F z y x y x H y G x F y x →∧???∧→??
等是前束范式，而
))),,()(()(())),,()(()((z y x H y G y x F x y x H y G y x F x →?→?∧?→? 等不是前束范式，因为没有把所有量词放到公式的开头。
每个谓词公式F 都可以变换成与它等值的前束范式。其步骤如下：
① 消去联结词→，?，?∨；
② 将联结词?向内深入，使之只作用于原子谓词公式；
③ 利用换名或代入规则使所有约束变元的符号均不同，并且自由变元与约束变元的符号也不同；
④ 利用量词辖域的扩张和收缩律，扩大量词的辖域至整个公式；
⑤ 利用分配律将公式化为前束范式。
例2.6 将公式F )),()(()),()((z y zD y yC y x B x A x ?→?→→?
化为前束范式。
解 ①消去联结词→，?，?∨；
)),()(()),()(((z y zD y yC y x B x A x F ?∨??∨∨????
② 将联结词?深入至原子公式
)),()(()),()(())
,()(()),()((z y zD y C y y x B x A x z y zD y C y y x B x A x F ?∨??∨?∧???∨??∨∨????
③ 换名
)),()(()),()((z y zD t C t y x B x A x F ?∨??∨?∧??
④ 把量词提到整个公式的前面
)),()()),()((z y D t C y x B x A z t x F ∨?∨?∧????
为所求前束范式。
重要的是弄清楚前束范式的定义，求前束范式主要是利用基本等值式、蕴含式和换名规则，把一个谓词公式化为前束范式，虽然前束范式是谓词公式的一种标准形式，但是一般一个谓词公式的前束范式并不是唯一的。
4.谓词逻辑的推理理论
谓词演算的推理是命题演算推理的推广和扩充，命题演算中的一些规则，如基本等值公式，重言蕴含式以及P ，T ，CP 规则在谓词演算中仍然使用。但是在谓词演算推理中，某些前提和结论可能受到量词的限制，为了使用这些推理，必须在推理过程中，有消去和附加量词的规则，即US 规则(全称量词消去规则)，UG 规则(全称量词附加规则)，ES 规则(存在量词消去规则)，EG 规则(存在量词附加规则)等，以便使谓词演算公式的推理过程可类似于命题演算的推理进行。
例2.7 试证)()()(P S P R R Q P →→→?→→
证明 [方法1] 等值演算法。
要证明)()()(P S P R R Q P →→→?→→，只需证明
))()(())((P S P R R Q P →→→→→→
的真值是1。
证))()(())((P S P R R Q P →→→→→→
),,()()]()()))(([(),()())](())()[((),,()
()())(()())
()(())((6427798116E E E P S P R R R P R P Q E E P S P R R P R Q P E E E P S P R R Q P E P S P R R Q P ∨?∨?∨?∧?∨∧?∧∨?∨?∨?∨?∧∨?∧?∧∨∨??∨?∨?∧∨?∧∨??∨?∨∨??∨∨∨????
),(1)
,()()()()
()()
,,()
()]()[(1514426141210E E E E S
P P R Q E P S P R Q E E E P S P R P Q ??∨∨?∨?∧?∨?∨?∨?∧?∨?∨?∨?∧?∨? [方法2]形式证明。
① (P →Q)→R P
② R →P CP
③ (P →Q)→P ①,②,I 13假言三段式
④ ?(?P ∨Q)∨P ③,E 16
⑤ (P ∧?Q)∨P ④,E 8,E 9,E 1
⑥ P ⑤,E 14
⑦S →P ⑥,I 6
⑧)()(P S P R →→→ ②,⑦,CP
例2.8 证明：)()(x xB x xA ?→??))()((x B x A x →?
证明 前提：)()(x xB x xA ?→?
结论：))()((x B x A x →?
(1) )))()(((x B x A x →?? 附加前提
(2) )))()(((x B x A x →?? (1) ,T,E
(3) ))()((c B c A →? (2),ES
(4) A (c ) (3),T,E
(5) ?B (c ) (3),T,E
(6) )(x xA ? (4),EG
(7) )()(x xB x xA ?→? P
(8) )(x xB ? (6),(7),T,E
(9) B(c) (8),US
(10) )()(c B c B ∧?
(5),(9)矛盾式
三、举例
例1谓词公式)())()((x Q y yR x P x →?∨?中量词?x 的辖域是( )
(A) ))()((y yR x P x ?∨? (B) P (x ) (C) ))(()(y yR x P ?∨ (D) )(),(x Q x P 答案：(C)
解答：?x 后面的公式是))(()(y yR x P ?∨。故应选择(C)。
例2 设个体域为整数集，下列公式中其值为1的是( )
(A) )0(=+??y x y x (B) )0(=+??y x x y
(C))0(=+??y x y x (D) )0(=+???y x y x
答案：(A) 解答：任意一个整数x ，都能找到y ＝－x ，有x+y=0,故(A)式是永真式。
例3 设L(x)：x 是演员，J(x)：x 是老师，A(x,y)：x 佩服y 。那么命题“所有演员都佩服某些老师”符号化为( )
(A) ),()(y x A x xL →? (B) )),()(()((y x A y J y x L x ∧?→?
(C) )),()()((y x A y J x L y x ∧∧?? (D) )),()()((y x A y J x L y x →∧??
答案：(D) 解答：将命题符号化为“)),()()((y x A y J x L y x →∧??”，故应选择(D)。注意：符号化为“),()()(y x A y yJ x xL →?∧?”是不对的，它的意义是所有演员和某些老师，x 佩服y 。
例4 在谓词演算中，P(a)是)(x xP ?的有效结论，根据是 ( )
(A)US 规则 (B) UG 规则 (C)ES 规则 (D)EG 规则
答案：(A)
解答：全称量词消去规则的定义为)()(c A x xA ∴?，即A(c)是)(x xA ?的有效结论。故应选择(A)。
例5 公式))(),()),()((x S z y zR y x Q x P x →?∨→?的自由变元是 , 约束变元是 。
答案：y,x ; x,z
解答：?x 的辖域是),,()(y x Q x P →故x 是约束出现，y 是自由出现，z ?的辖域是),(z y R ，故z 是约束出现，y 是自由出现，而S(x)中的x 是自由出现。总之y,x 是自由变元，x,z 是约束变元。
例6 谓词逻辑公式)()(x xQ x xP ?→?的前束范式是 。 答案：))()((x Q x P x ∨??
解答：求前束范式
))()(()
()()
())(()()(x Q x P x x xQ x P x x xQ x xP x xQ x xP ∨????∨????∨????→?
例7 设个体域D ＝{a,b},消去公式中的量词，则??∧?)()(x xQ x xP 答案：))()(()()(b Q a Q b P a P ∨∧∧
解答：由?x和?x真值的定义，
x
xQ
P
a
b
P
x
xP∨
∧
?
?
?
∧
∧
Q
(
)
(
)
))
(
a
(
(b
Q
)
)
(
(
)
例8换名规则施于变元，代入规则施于变元答案：约束；自由
解答：见换名规则和代入规则的定义。
第二章谓词逻辑 2—1基本概念 例题1. 所有的自然数都是整数。 设N(x):x是自然数。I(x):x是整数。此命题可以写成?x(N(x)→I(x)) 例题2. 有些自然数是偶数。 设E(x):x是偶数。此命题可以写成?x(N(x)∧E(x)) 例题3. 每个人都有一个生母。 设P(x):x是个人。M(x,y):y是x的生母。此命题可以写 成:?x(P(x)→?y(P(y)∧M(x,y))) 2-2 谓词公式及命题符号化 例题1. 如果x是奇数,则2x是偶数。 其中客体x与客体2x之间就有函数关系,可以设客体函数g(x)=2x, 谓词O(x):x是奇数,E(x):x是偶数, 则此命题可以表示为:?x(O(x)→E(g(x))) 例题2 小王的父亲是个医生。 设函数f(x)=x的父亲,谓词D(x):x是个医生,a:小王,此命题可以表示为D(f(a))。 例题3 如果x和y都是奇数,则x+y是偶数。 设h(x,y)=x+y ,此命题可以表示为:?x?y((O(x)∧O(y))→E(h(x,y)) 命题的符号表达式与论域有关系 两个公式:一般地,设论域为{a1,a2,....,an},则有 (1). ?xA(x)?A(a1)∧A(a2)∧......∧A(an) (2). ?xB(x)?B(a1)∨B(a2)∨......∨B(an) 1.每个自然数都是整数。该命题的真值是真的。 表达式?x(N(x)→I(x))在全总个体域的真值是真的, 因?x(N(x)→I(x))?(N(a1)→I(a1))∧(N(a2)→I(a2))∧…∧(N(an)→I(an)) 式中的x不论用自然数客体代入,还是用非自然数客体代入均为真。例如(N(0.1)→I(0.1))也为真。 而?x(N(x)∧I(x))在全总个体域却不是永真式。
谓词逻辑习题 1. 将下列命题用谓词符号化。 （1）小王学过英语和法语。 （2）2大于3仅当2大于4。 （3）3不是偶数。 （4）2或3是质数。 （5）除非李键是东北人，否则他一定怕冷。 解： (1) 令)(x P ：x 学过英语，Q(x)：x 学过法语，c ：小王，命题符号化为)()(c Q c P ∧ (2) 令),(y x P ：x 大于y, 命题符号化为)3,2()4,2(P P → (3) 令)(x P ：x 是偶数，命题符号化为)3(P ? (4) 令)(x P ：x 是质数，命题符号化为)3()2(P P ∨ (5) 令)(x P ：x 是北方人；)(x Q ：x 怕冷；c ：李键；命题符号化为)()(x P c Q ?→ 2. 设个体域}{c b a D ，， =，消去下列各式的量词。 （1）))()((y Q x P y x ∧?? （2）))()((y Q x P y x ∨?? （3）)()(y yQ x xP ?→? （4）))()((y yQ y x P x ?→?， 解： (1) 中))()(()(y Q x P y x A ∧?=，显然)(x A 对y 是自由的，故可使用UE 规则，得到 ))()(()(y Q y P y y A ∧?=，因此))()(())()((y Q y P y y Q x P y x ∧?∧?? ，再用ES 规则， )()())()((z Q z P y Q y P y ∧∧? ，D z ∈，所以)()())()((z Q z P y Q x P y x ∧∧?? （2）中))()(()(y Q x P y x A ∨?=，它对y 不是自由的，故不能用UI 规则，然而，对 )(x A 中约束变元y 改名z ，得到))()((z Q x P z ∨?，这时用UI 规则，可得： ))()((y Q x P y x ∨?? ))()((z Q x P z x ∨??? ))()((z Q x P z ∨? （3）略 （4）略 3. 设谓词)(y x P ，表示“x 等于y ”，个体变元x 和y 的个体域都是}321 {，，=D 。求下列各式的真值。 （1）)3(，x xP ? （2）)1(y yP ，? （3）)(y x yP x ，?? （4）)(y x yP x ，?? （5）)(y x yP x ， ?? （6）)(y x xP y ， ?? 解：
北京邮电大学 离散数学 第一次阶段作业 判断题 1. 如果A∪B=B，则A?B。【答案：A】 A. 正确 B. 错误 2. 如果a∈A∪B，则a?A或a?B。【答案：B】 A. 正确 B. 错误 3. a∈{a,a}。【答案：A】 A. 正确 B. 错误 4.{?}是空集。【答案：B】 A. 正确 B. 错误 5.设ρ是集合A上的等价关系，则当a,b∈ρ时，aρ=bρ。【答案：A】 A. 正确 B. 错误 单项选择题 1. 设A={a,a}，则下列各式中错误的是【答案：B】 A. a∈2A B. {a}?2A C. {a}∈2A D. {a}?2A 解：2A={?,a,a, a,a} 2. 下列各式中不正确的是【答案：C】 A. ??? B. ?∈{?} C. ??? D. ?∈{?,?} 3. 设ρ是集合A上的关系，则（）不是ρ为反对称关系的充分必要条件【答案：D】 A. ρ是反对称关系 B. ρ∩ρ?i A C. 对任意x,y∈A，当x,y∈ρ且x≠y时y,x?ρ D. 对A的某两个元素x, y，当x,y,y,x∈ρ时有x=y 4. 设A，B，C是集合，ρ,μ分别是A到B，B到C的关系，x∈A，z∈C，则存在y∈B使得x,y∈ρ且y,z∈μ是x,z∈ρ°μ的（）条件【答案：C】 A. 充分而非必要 B. 必要而非充分 C. 充分必要
D. 既非充分又非必要 5. 设A={0,b}，B={1,b,3}，则A∪B的恒等关系为【答案：A】 A.{0,0,1,1,b,b,3,3} B. {0,0,1,1,3,3} C. {0,0,b,b,3,3} D. {0,1,1,b,b,3,3,0}
第2章谓词逻辑 一、教学要求 1. 理解谓词、量词、个体词、个体域、原子公式、谓词公式和变元等概念。会将不太复杂的命题符号化。 2. 掌握在有限个体域下求公式的真值和某些公式在给定解释下真值的方法，判别公式类型(永真式、永假式和可满足式)的方法。 3. 掌握谓词演算的等值式和重言蕴含式(六种情况：(1)命题公式的推广；(2)量词否定式的等值式；(3)量词辖域扩张和收缩的等值式；(4)量词与联结词∨，∧，→的等值式；(5)量词与联结词的重言蕴含式；(6)两个量词公式间的等值式与重言蕴含式)。会进行谓词公式的等值演算。 4. 了解前束范式的概念，会求公式的前束范式。 5. 了解谓词逻辑推理的规则：全量词消去规则(US规则)；全量词附加规则(UG规则)；存在量词消去规则(ES规则)；存在量词附加规则(EG规则) 本章重点：谓词与量词，公式与解释，前束范式，谓词逻辑推理证明。 二、学习辅导 在命题逻辑中，我们把原子命题作为基本研究单位，对原子命题不再进行分解，只有复合命题才可以分解，揭示了一些有效的推理过程. 但是进一步研究发现，仅有命题逻辑是无法把一些常见的推理形式包括进去. 例如 “凡人要死，张三是人，张三要死” 显然是正确推理. 用命题逻辑解释三段式. 设 P：人要死；Q张三是人；R：张三要死。 表示成复合命题有 P∧Q→R 这不是重言式，即R不是前提P，Q的有效结论. 这反映了命题逻辑的局限性，其原因是把本来有内在联系的命题P，Q，R，视为独立的命题。要反映这种内在联系，就要对命题逻辑进行分析，分析出其中的个体词、谓词和量词，再研究它们之间的逻辑关系，总结出正确的推理形式和规则，这就是谓词逻辑的研究内容。 1. 谓词与量词 学习这一部分要反复理解谓词和量词引入的意义，概念的含义。 在谓词逻辑中，原子命题分解成个体词和谓词。个体词是可以独立存在的客体，它可以是具体事物或抽象的概念，如小张，房子，南京，大米，思想，实数2等等。谓词是用来刻划个体词的性质或事物之间的关系的词。例如 (1)(1)ln5是无理数； (2)(2)高可比李木相高4cm； (3) 郑州位于北京和广州之间。 这时三个简单命题，其中ln5，高可，李木相，郑州，北京，广州等都是个体词，而“是无理数”，“……比……高4cm”，“……位于……和……之间”等都是谓词。 个体词分个体常项(用a,b,c,d,…表示)和个体变项(用x,y,z,…表示)；谓词分谓词常项(表
第一次 第1题 空集不是任何集合的真子集 您的答案：错误 题目分数：0.5 此题得分：0.5 批注：本题考查空集的基本概念 第2题 一个集合可以是另一个集合的元素 您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题考查集合的基本概念 第3题 设A、B为集合，如果集合A的元素都是集合B的元 素，则称A是B的子集 您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题考查子集的基本概念 第4题 如果一个集合包含了所要讨论的每一个集合，则称该 集合为全集，记为U 您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题考查全集的基本概念 第5题 在笛卡儿坐标系中，平面上点的坐标< 1,2> 与< 2,1> 代表不同的点 您的答案：正确 题目分数：0.5
此题得分：0.5 批注：本题考查笛卡儿坐标系的基本概念 第6题 复合运算不满足交换律，但复合运算满足结合律您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题考查复合运算的是否满足交换律和结合律 第7题 映射也可以称为函数，是一种特殊的二元关系 您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题考查映射的基本概念 第8题 映射的复合运算不满足交换律 您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题为映射的基础知识 第9题 空集是唯一的 您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题考查空集的唯一性 第10题 对任意的集合A，A包含A 您的答案：正确 题目分数：0.5 此题得分：0.5
批注：本题考查集合的包含概念 第11题 集合上的三种特殊元是单位元、零元及可逆元 您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题考查集合上的三种特殊元 第12题 集合A上的偏序关系的三个性质是自反性、反对称性和传递性 您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题考查集合偏序关系的三个性质 第13题 设f:A→B, g:B→C。若f, g都是满射，则gf也是满射 您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题考查复合关系的满射概念 第14题 设f:A→B, g:B→C。若f, g都是双射，则gf也是双射 您的答案：正确 题目分数：0.5 此题得分：0.5 批注：本题考查复合关系的双射概念 第15题 设f:A→B, g:B→C。若f, g都是单射，则gf也是单射 您的答案：正确 题目分数：0.5 此题得分：0.5
离散数学作业 作业11——第3章谓词逻辑 1. 符号化下列命题并推证其结论。 每个大学生不是文科学生就是理工科学生，小张不是理工科学生，因此如果小张是大学生，则他就是文科生。 解：a：小张；M(x):x是大学生；F(x): x是文科生；G(x): x是理工科学生，则符号化为 (x)(M(x)F(x)∨G(x))，┐G(a)M(a) F(a) (1) M(a) P（附加前提） (2) (x)(M(x)F(x)∨G(x)) P (3) M(a)F(a)∨G(a) (2),US (4) ┐M(a)∨F(a)∨G(a) (3),等值演算 (5) F(a)∨G(a) (1),(4),析取三段论 (6) ┐G(a) P (7) F(a) (5),(6),析取三段论 (8) M(a) F(a) (1),(7),CP规则 注：也可采用直接证法。 2. 符号化下列命题并推证其结论。 所有的主持人都是有风度的，黎明既是学生又是主持人，所以有一些学生是有风度的。 解：S(x): x是学生；Z(x): x是主持人；F（x）：x是有风度的；a：黎明。
(x)(Z(x)F(x))，S(a)Z(a)(x) (S(x)F(x)) (1) (x)(Z(x)F(x)) P (2) Z(a)F(a) (1),US (3) S(a)Z(a) P (4) S(a) (3),化简 (5) Z(a) (3),化简 (6) F(a) (2),(5),假言推理 (7) S(a)F(a) (4),(6),合取引入 (8) (x) (S(x)F(x)) （7），EG 3．在一阶谓词逻辑中构造下面推理的证明。 前提：(x)(F(x)∨G(x))，(x)(F(x)→H(x))， 结论：(x)(H(x)→G(x))。 证明：反证法 (1)(x)(H(x)→G(x)) 附加前提 (2)(x)(H(x)→G(x)) (1),量词否定等值式 (3)(H(c)→G(c)) (2), ES (4)(H(c) ∨G(c)) (3), 等值演算 (5)H(c)G(c) (4), 等值演算 (6)H(c) （5），化简 (7)G(c) （5），化简 (8)(x)(F(x)∨G(x)) P (9)F(c)∨G(c) （8），US
2013年9月份考试离散数学第一次作业 一、单项选择题（本大题共40分，共20 小题，每小题2 分） 1. 下列语句中不是命题的只有（）。A. 鸡毛也能飞上天？B. 人的死或重于泰山，或轻于鸿毛。C. 不经一事，不长一智。 D. 牙好，胃口就好。 2. 设A={1，2，3，4，5}，A上二元关系R={〈1，2〉，〈3，4〉，〈2，2〉}，S={〈2，4〉，〈3，1〉，〈4，2〉}，则S-1oR-1的运算结果是（）。 A. {〈4，1〉，〈2，3〉，〈4，2〉} B. {〈2，4〉，〈2，3〉，〈4，2〉} C. {〈4，1〉，〈2，3〉，〈2，4〉} D. {〈2，2〉，〈3，1〉，〈4，4〉} 3. 下列集合关于所给定的运算成为群的是（）。 A. 已给实数a的正整数次幂的全体，且a∈{0，1，-1}，关于数的乘法 B. 所有非负整数的集合，关于数的加法 C. 所有正有理数的集合，关于数的乘法 D. 实数集，关于数的除法 4. 在有n个结点的连通图中，其边数（） A. 最多有n-1条 B. 至少有n-1条 C. 最多有n条 D. 至少有n条 5. 一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条（） A. 汉密尔顿回路 B. 欧拉回路 C. 汉密尔顿通路 D. 初级回路 6. .以下命题公式中，为永假式的是（） A. .p→(p∨q∨r) B. (p→┐p)→┐p C. ┐(q→q)∧p D. ┐(q∨┐p)→(p∧┐p) 7. 在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是（）。 A. b∧(a∨c) B. (a∧b)∨(a∧b) C. (a∨b)∧(a∨b∨c)∧(b∨c) D. (b∨c)∧(a∨c) 8. 所有使命题公式为真的赋值为（）。 A. 010，100，101，110，111 B. 010，100，101，111 C. 全体赋值 D. 不存在 9. 设i是虚数，·是复数乘法运算，则G=<{i,-i,1,-1},?>是群，下列是G的子群是（）。 A.
命题逻辑和谓词逻辑习题课的题目及参考 答案 说明：红色标注题目可以暂且不做 命题逻辑和谓词逻辑习题课的题目 一、填空 1、若P，Q，为二命题，Q P→真值为0 当且仅当。2、命题“对于任意给定的正实数，都存 在比它大的实数”令F(x)：x为实数，:) , (则命题的逻辑谓词公式y L> x x y 为 。
3、谓词合式公式)( xP? ?的前束式 x → ) (x xQ 为。 4、将量词辖域中出现的 和指导变元交换为另一变元符号，公式 其余的部分不变，这种方法称为换名规 则。 5、设x是谓词合式公式A的一个客体变 元，A的论域为D，A(x)关于y是自由的，则 被称为存在量词消去规则，记为ES。 6．设P，Q 的真值为0，R，S的真值为1，则 → ∨ Q P? ∨ ?的真值 → ∧ ? (S ))) ( R ( ) P R ( = 。 7．公式P ∧) ( ) (的主合取式为 ∨ R S R P? ∨ ∧
。 8．若解释I的论域D仅包含一个元素，则)( xP? → ?在I下真值为 xP ) (x x 。 9. P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。 10. 论域D={1，2}，指定谓词P 则公式),(x y ?真值 x? yP 为。 11.P，Q真值为0 ；R，S真值为1。则
∧ wff∧ R ∨ → )) ∧的真值∨ S P )) P ) ( ( (( Q R (S 为 。 12. R ?) ) ((的主合取式 ∧ R Q ∨ P wff→ 为 。 13.设 P（x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y)：x可以整数y。则谓词))) x y O P y ?的自然语言是 → ? wff∧ x ( ) ( N ( , y ( (x ) 。 14.谓词)),,( x y z P x z ?的前束 ? P ? ∧ → wff? y ) , ( , )) y ( z ( uQ x (u 式为 。
2017秋课件作业 第一部分集合论 第一章集合的基本概念和运算 1-1设集合A={{2，3,4}，5，1}，下面命题为真是（选择题）[A] A．1∈A；B．2∈A；C．3∈A；D．{3，2,1}?A。 1-2A,B,C为任意集合，则他们的共同子集是（选择题）[D] A．C；B．A；C．B；D．?。 1-3设S={N，Z，Q，R}，判断下列命题是否正确（是非题） （1）N?Q，Q∈S，则N?S，［错］（2）-1∈Z，Z∈S，则-1∈S。［错］ 1-4设集合B={4，3}∩?，C={4，3}∩{?}，D={3，4，?}，E={x│x∈R并且x2-7x+12=0}，F={4，?，3，3}，试问：集合B与那个集合之间可用等号表示（选择题）[A] A.C; B.D; C.E; D. F. 1-5用列元法表示下列集合：A={x│x∈N且3－x〈3}（选择题）[D] A.N; B.Z; C.Q; D.Z+ 1-6为何说集合的确定具有任意性?(简答题) 答：按研究的问题来确定集合的元素。我们所要研究的问题当然是随意的呗。之所以，集合的定义（就是集合成分的确定）当然带有任意性哪。 第二章二元关系 2-1设A={1，2，3}，A上的关系R={〈1，2〉，〈2，1〉}∪IA， 试求：（综合题） (1)domR=?;(2)ranR=?;(3)R的性质。 （4）商集A/R=？（5）A的划分∏=？（6）合成运算（R。R）=？ 答：R={<1,2>,<1,3>,<2,3>，<1，1>，<2，2>，<3，3>}； (1)DomR={R中所有有序对的x}={3,2,1}; (2)RanR={R中所有有序对的y}={2,1,3}； (3)R的性质:自反,反对称,传递性质.这时，R不是等价关系。 （4）商集A/R={{1，2，3}，{2，3}，{3}}。由于R不是等价关系，所以，等价类之间出现交集。这是不允许的。请看下面的划分问题。 （5）A的划分∏={{1，2，3}，{2，3}，{3}}；也由于R不是等价关系，造成划分的荒谬结果：出现交集。试问：让“3”即参加第一组，又参加第二组，她该如何分配呢！！！ 所以，关系R必须是等价关系。至于作业中，此两题应说：因为R不是等价关系，此题无解。 2-2设R是正整数集合上的关系，由方程x+3y=12决定，即 R={〈x，y〉│x，y∈Z+且x+3y=12}， 试给出dom（R。R）。（选择题）[B] A.3； B.{3}； C.〈3，3〉； D.{〈3，3〉}。
离散数学第一次作业（命题逻辑） 1、证明下列各式是重言式 （1）（（P∧Q）→P）?T ù((?(P∧Q) ∨ P) ?T ù(?P∨?Q∨P) ?T ù（T∨?Q）?T ùT?T 所以此式为重言式 （2）?（?（P∨Q）→? P）?F ù?（（P∨Q）∨? P）?F ù?（T∨Q）?F ù?T?F ùF?F 所以此式为重言式 （3）（Q→P）∧（? P→Q）∧（Q?Q）? P ù（? Q∨P）∧（P∨Q）∧T? P ù（(? Q∨P）∧P) ∨(（? Q∨P）∧Q) ? P ù(P∨((? Q∨P）∧Q) ? P ù(P∨P) ? P
ùP? P 所以此式为重言式 （4）（P→? P）∧（? P→P）?F ù（? P∨? P）∧（P∨P）?F ù（? P∧P）?F ùF?F 所以此式为重言式 2、求出下列公式的最简等价式：（1）（（P→Q）?（? Q→? P））∧R ù（（P→Q）?（P→Q））∧R ùT∧RùR （2）P∨? P∨（Q∧?Q） ùT∨FùT （3）（P∧（Q∧S））∨（? P∧（Q∧S））ù（（P∨? P ）∧（Q∧S））） ùT∧（Q∧S） ù（Q∧S）
3、（1）与非运算符↑（又叫悉菲（Sheffer）记号）用下述真值表定义，可以看出P↑Q??（P∧Q），试证明： （a）P↑P?? P；（b）（P↑P）↑（Q↑Q）? P∨Q； （c）（P↑Q）↑（P↑Q）? P∧Q 证明： （a）P↑P??（P∧P）??P (b) （P↑P）↑（Q↑Q）??P↑?Q??(?P∧?Q) ? P∨Q (c) （P↑Q）↑（P↑Q）??（P∧Q）↑?（P∧Q） ??(?（P∧Q）∧?（P∧Q）) ???（P∧Q） ? P∧Q （2）或非运算符↓（又叫皮尔斯（Peirce）箭头）用下述真值表定义，它与?（P∨Q）逻辑等价。对下述每一式，找出仅用↓表示的等价式。（a）? P；（b）P∨Q；（c）P∧Q。 P Q P↑Q P↓Q 0 0 1 1 0 1 1 0 1 0 1 0 1 1 0 0 证明： （a）? Pù? P∧Tù? P∧?Fù?（P∨F）ùP↓ F （b）P∨Qù??（P∨Q）ù?（P↓Q）ù（P↓Q）↓ F （c）P∧Qù?(?P∨?Q) ù??（? P↓? Q）ù? P↓? Qù（P↓ F）↓（Q↓ F）
离散数学作业 作业10 ——第3章谓词逻辑 1. 利用谓词公式翻译下列命题。 (1)所有人都是要呼吸的。 解：M(x):x是人；F(x):x是要呼吸的。 (?x)(M(x)→F(x)) (2)任何整数或是正的或是负的。 解：Z(x):x是整数；P(x):x是正的； N(x):x是负的。 (?x)(Z(x)→P(x)∨N(x)) (3)存在一些数是质数。 解：Z(x):x是数；P(x):x是质数。 (?x)(Z(x)∧P(x)) (4)一些人是聪明的。 解：M(x):x是人；F(x):x是聪明的。 (?x)(M(x) ∧F(x)) (5)并非每个实数都是有理数。 解：R(x):x是实数；Q(x):x是有理数。 (?x)(R(x) ∧┐Q(x))或者┐(?x)(R(x)→Q(x)) (6) 如果有限个数的乘积是零，那么至少有一个因子等于零； 解：E(x):x是有限个数的乘积；F(y,x): y是x的一个因子； Z(x):x 是零。
(?x)（E(x) ∧Z(x) →(?y)(F(y,x) ∧Z(y))） (7) 对于每一个实数x，存在一个更大的实数y； 解：R(x):x是实数；Q(x,y):x比y大。 (?x)(R(x)→(?y)( R(y) ∧Q(y,x))) (8) 存在实数x,y和z，使得x与y之和大于x与z之积； 解：R(x):x是实数；Q(x,y):x比y大; f(x,y)=x+y;g(x,y)=xy。 (?x)(?y)(?z)(R(x) ∧ R(y) ∧ R(z) ∧Q(f(x,y),g(x,y))) 2. 取个体域为实数集R ，函数f 在a 点连续的定义是：f 在点连续，当且仅当对每个a 0>ε，存在一个0>δ，使得对所有x ，若δ0)→(?δ)((δ>0)∧(?x) ((|x-a|<δ)→(|f(x)-f(a)|<ε))))。
离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外） 安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出 掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有 解答过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。并在 03任务界面下方点击“保存”和“交卷”按钮，完成并上交任课教师。 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)-P(B )= {{3}，{1,3}，{2,3}， A B {1,2,3}} ，A?B= {<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3.2>} ．2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ．3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为 {<2, 2>，<2, 3>，<3, 2>}，<3,3> ．4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} ∈ y x∈ y < > = {B , , x , 2 y A x 那么R－1＝ {<6,3>,<8,4>} 5．设集合A=｛a, b, c, d｝，A上的二元关系R={
注意看参考答案 1. A．明年国庆节是晴天。 B．在实数范围内，x+y〈3。 C．请回答这个问题！ D．明天下午有课吗？ 在上面句子中，是命题的只有（） 答题： A. B. C. D. 参考答案：A 2. 在上面句子中，是命题的是( ) A．雪是黑色的。 B．这朵花多好看呀！。 C．请回答这个问题！ D．明天下午有会吗？ 答题： A. B. C. D. 参考答案：A 3. A．现在开会吗？ B．在实数范围内，x+y >5。 C．这朵花多好看呀！ D．离散数学是计算机科学专业的一门必修课。 在上面语句中，是命题的只有( ) 答题： A. B. C. D. 参考答案：D 4. A．1＋101＝110 B．中国人民是伟大的。 C．全体起立！ D．计算机机房有空位吗？ 在上面句子中，是命题的是( ) 答题： A. B. C. D. 参考答案：B 5.下面的命题不是简单命题的是( ) A．3是素数或4是素数 B．2018年元旦下大雪 C．刘宏与魏新是同学 D．圆的面积等于半径的平方与之积 答题： A. B. C. D. 参考答案：A
6.设：p：派小王去开会。q：派小李去开会。则命题： “派小王或小李中的一人去开会” 可符号化为：（） A． B． C． D． 答题： A. B. C. D. 参考答案：B 7.下面“”的等价说法中，不正确的为 A．p是q的充分条件 B． q是p的必要条件 C．q仅当p D．只有q才p 答题： A. B. C. D. 参考答案：C 8. p,q都是命题，则p→q的真值为假当且仅当( ) A．p为假，q为真 B．p为假，q也为假 C．p为真，q也为真 D．p为真，q也为假 答题： A. B. C. D. 参考答案：D 9.个命题变元组成的命题公式，有( )种真值情况 A． B． C． D．2 答题： A. B. C. D. 参考答案：C 10. 答题： A. B. C. D. 参考答案：C 11.设F（x）：x是火车，G（x）：x是汽车，H（x，y）：x比y快。命题“说
谓词逻辑习题 1. 将下列命题用谓词符号化。 （1）小王学过英语和法语。 （2）2大于3仅当2大于4。 （3）3不是偶数。 （4）2或3是质数。 （5）除非李键是东北人，否则他一定怕冷。 解： (1) 令)(x P ：x 学过英语，Q(x)：x 学过法语，c ：小王，命题符号化为)()(c Q c P ∧ (2) 令),(y x P ：x 大于y, 命题符号化为)3,2()4,2(P P → (3) 令)(x P ：x 是偶数，命题符号化为)3(P ? (4) 令)(x P ：x 是质数，命题符号化为)3()2(P P ∨ (5) 令)(x P ：x 是北方人；)(x Q ：x 怕冷；c ：李键；命题符号化为)()(x P c Q ?→ 2. 设个体域}{c b a D ，，=，消去下列各式的量词。 （1）))()((y Q x P y x ∧?? （2）))()((y Q x P y x ∨?? （3）)()(y yQ x xP ?→? （4）))()((y yQ y x P x ?→?， 解： (1) 中))()(()(y Q x P y x A ∧?=，显然)(x A 对y 是自由的，故可使用UE 规则，得到 ))()(()(y Q y P y y A ∧?=，因此))()(())()((y Q y P y y Q x P y x ∧?∧?? ，再用ES 规则， )()())()((z Q z P y Q y P y ∧∧? ，D z ∈，所以)()())()((z Q z P y Q x P y x ∧∧?? （2）中))()(()(y Q x P y x A ∨?=，它对y 不是自由的，故不能用UI 规则，然而，对 )(x A 中约束变元y 改名z ，得到))()((z Q x P z ∨?，这时用UI 规则，可得： ))()((y Q x P y x ∨?? ))()((z Q x P z x ∨??? ))()((z Q x P z ∨? （3）略 （4）略 3. 设谓词)(y x P ，表示“x 等于y ”，个体变元x 和y 的个体域都是}321 {，，=D 。求下列各式的真值。 （1）)3(，x xP ? （2）)1(y yP ，? （3）)(y x yP x ， ?? （4）)(y x yP x ，??
份考试离散数学第一次 作业精选文档 TTMS system office room 【TTMS16H-TTMS2A-TTMS8Q8-
2014年9月份考试离散数学第一次作业 一、单项选择题（本大题共42分，共 21 小题，每小题 2 分） 1. 下列语句中是命题的只有（） A. 在实数范围内，x2+y2>=0 B. 在实数范围内，x+y C. 请回答这个问题 D. 真正有学问的人怎么回不关心政治呢？ 2. 设R为实数集，R+={x|x∈R∧x>0}，*是数的乘法运算，
4. 下述是命题且真值为真的是（） A. 下个月8日是晴天 B. 他真年轻啊！ C. 长方形面积等于长乘以宽 D. 每个月至少有29天 5. 2.设G是n个顶点的无向简单图，则下列说法不正确的是（） A. 若G是树，则其边数等于n-1 B. 若G是欧拉图，则G中必有割边 C. 若G中有欧拉路，则G是连通图，且有零个或两个奇度数顶点 D. 若G中任意一对顶点的度数之和大于等于n-1，则G中有汉密尔顿路 6. .以下命题公式中，为永假式的是（） A. .p→(p∨q∨r) B. (p→┐p)→┐p C. ┐(q→q)∧p D. ┐(q∨┐p)→(p∧┐p)
7. 设A={Φ}，B=P（P（A）），以下不正确的式子是（）。 A. {{Φ}，{{Φ}}，{Φ，{Φ}}}包含于B B. {{{Φ}}}包含于B C. {{Φ，{Φ}}}包含于B D. {{Φ}，{{Φ，{Φ}}}}包含于B 8. 无向图结点之间的连通性，是结点集之间的一个（） A. 连通关系 B. 偏序关系 C. 等价关系 D. 函数关系 9. 设R为实数集，函数f：R→R，f(x)=2x，则f是（） A. 满射函数 B. 入射函数 C. 双射函数 D. 非入射非满射
一、判断题（共5道小题，共50.0分） 1. 如果，则或． A. 正确 B. 错误 知识点: 集合 学生答案: [B;] 得分: [10] 试题分值: 10.0 提示: 2. 是空集． A. 正确 B. 错误 知识点: 集合 学生答案: [B;] 得分: [10] 试题分值: 10.0 提示: 3. 设为集合上的等价关系, 则 A. 正确 B. 错误 知识点: 关系 学生答案: [B;] 得分: [10] 试题分值: 10.0 提示: 4. 设集合，则是到的关系
A. 正确 B. 错误 知识点: 关系 学生答案: [A;] 得分: [10] 试题分值: 10.0 提示: 5. 设集合，，则 A. 正确 B. 错误 知识点: 关系 学生答案: [B;] 得分: [10] 试题分值: 10.0 提示: 6. 二、单项选择题（共5道小题，共50.0分） 1. 设为实数集合，下列集合中哪一个不是空集 A. B. C. D. 知识点: 集合 学生答案: [A;] 得分: [10] 试题分值: 10.0 提示:
2. 设是集合A上的关系，则（）不是为反对称关系的充分必要条件. A. 是反对称关系 B. ∩ C. 对任意 D. 对A的某两个元素 知识点: 关系 学生答案: [D;] 得分: [10] 试题分值: 10.0 提示: 3. 设为集合上的等价关系，对任意，其等价类为 A. 空集 B. 非空集 C. 是否为空集不能确定 D. 知识点: 关系 学生答案: [B;] 得分: [10] 试题分值: 10.0 提示: 4. 设，，则的恒等关系为 A. B.
1、设)()()(),,(323221321x x x x x x x x x E ∧∨∧∨∧=是布尔代数],,},1,0[{-∧∨上的一个布尔表达式，试写出),,(321x x x E 的析取范式和合取范式。 答： 析取范式：)()() ()()(),,(321321321321321321x x x x x x x x x x x x x x x x x x E ∧∧∨∧∧∨∧∧∨∧∧∨∧∧= 合取范式：)()()(),,(321321321321x x x x x x x x x x x x E ∨∨∧∨∨∧∨∨∨= 2．设P(x)：x 是大象，Q(x)：x 是老鼠，R(x,y)：x 比y 重，则命题“大象比老鼠重”的符号化为 答： ?x ?y ( (P(x) ∧ Q(x)) → R(x,y)) 3．设L(x)：x 是演员，J(x)：x 是老师，A(x , y)：x 钦佩y ，命题“所有演员都钦佩某些老 师”符号化为（ B ）。 A 、)),()((y x A x L x →?； B 、))),()(()((y x A y J y x L x ∧?→? ； C 、)),()()((y x A y J x L y x ∧∧??； D 、)),()()((y x A y J x L y x →∧?? 。 4．下列各式中哪个不成立（ A ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。 5．用推理规则证明)()(a G a P ∧?是 ))()((,)(,))()((, )))()(()((x G x S x a S a R a Q x R x Q x P x ??∧?∧→?的有效 结论。 证明：（1） ))()(()(x P x Q x xP ∧→? P （2） ))()(()(a P a Q a P ∧→ US(1) (3) ))()((a R a Q ∧? P
2013年4月考试离散数学第一次作业 一、单项选择题（本大题共50分，共 25 小题，每小题 2 分） 1. 下列关系中为等价关系的是（） A. 朋友关系 B. 父子关系 C. 住在同一街区的邻居关系 D. 买卖关系 2. 集合A上的相容关系所得关系矩阵M(R)的对角线元素（）。 A. 全为1 B. 全为0 C. 有的是1，有的是0 D. 有的是2 3. 完全图的结点数目为（）时，有欧拉回路。 A. 3 B. 为奇数 C. 为偶数 D. 10 4. 下面哪一个图是树（）？ A. B. C. D.
5. 任何无向图中结点间的连通关系是（） A. 偏序关系 B. 等价关系 C. 相容关系 D. 拟序关系 6. 若集合A的基数为７，则其幂集的基数|P(A)|是多少？（） A. 107 B. 70 C. 27 D. 17 7. 若R和S是集合A上的两个关系，则下述结论正确的是（） A. 若R和S是自反的，则RoS是自反的。 B. 若R和S是对称的，则RoS是对称的。 C. 若R和S是反自反对称的，则RoS是反自反的。 D. 若R和S是传递的，则RoS是传递的。 8. 设A是整数集，下列说法正确的是（）。 A. B. C. D. 9. 设P：我去踢球，Q：明天下雨，命题“如果我踢球，当且仅当明天不下雨”的符号化表示为（）。 A. P→Q B. Q→P C. D. P Q 10. 以下哪个不是最小联结词组？（） A. { ∧，?} B. { ∨，?} C. { ∧，∨，→} D. {?，→ } 11. 集合A={1，2，… ，10}上的关系R={|x+y=10,x∈A,y∈A}，则R的性质为（）。 A. 自反的 B. 对称的 C. 传递的、对称的 D. 反自反的、传递的 12. 下面哪一个命题是命题“2是偶数或-3是负数”的否定？（） A. 2是偶数或-3不是负数 B. 2是奇数或-3不是负数 C. 2不是偶数且-3不是负数 D. 2是奇数且-3不是负数
1. 将下列命题用谓词符号化。 4) 2 或 3 是质数。 5)除非李键是东北人，否则他一定怕冷。 解： (1) 令 P( x) ：x 学过英语， Q(x) ：x 学过法语， c ：小王，命题符号化为 P(c) Q(c) (2) 令P(x,y)：x 大于 y, 命题符号化为 P(2,4) P(2,3) (3) 令 P(x)：x 是偶数，命题符号化为 P(3) (4) 令 P(x)：x 是质数，命题符号化为 P(2) P(3) (5) 令 P(x)：x 是北方人； Q(x)：x 怕冷； c ：李键；命题符号化为 Q(c) P(x) 2. 设个体域 D {a ，b ，c} ，消去下列各式的量词。 (1) x y(P(x) Q(y)) (2) x y(P(x) Q(y)) (3) xP(x) yQ(y) (4) x(P(x ，y) yQ(y)) 解： (1) 中 A(x) y(P(x) Q( y)) ，显然 A(x)对y 是自由的，故可使用 UE 规则，得到 A(y) y(P(y) Q(y)) ， 因此 x y(P(x) Q(y)) y(P(y) Q( y)) ，再用 ES 规则， y( P( y) Q(y)) P(z) Q(z)，z D ，所以 x y(P(x) Q(y)) P(z) Q(z) (2)中 A(x) y(P(x) Q( y)) ，它对 y 不是自由的，故不能用 UI 规则，然而，对 A( x)中约束变元 y 改名z ，得到 z(P(x) Q( z)) ，这时用 UI 规则，可得： x y(P(x) Q(y)) x z(P(x) Q(z)) z(P(x) Q(z)) 3) 略 4) 略 3. 设谓词 P(x ，y)表示“x 等于 y ”，个体变元 x 和y 的个体域都是 D {1，2，3} 。求下列各式 的真值。 (1) xP( x ，3) (2) yP(1，y) (3) x yP(x ，y) (4) x yP( x ，y) (5) x yP(x ，y) (6) y xP(x ，y) 解： (2) 当 x 3时可使式子成立，所以为 Ture 。 (3) 当 y 1 时就不成立，所以为 False 。 谓词逻辑习题 1) 小王学过英语和法语。 2) 2大于3仅当 2大于 4。 3) 3 不是偶数。
4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ? (?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q)) ?(p∨?p)∧(p∨q)∧(?q∨?p) ∧(?q∨q) ?1∧(p∨q)∧?(p∧q)∧1 ?(p∨q)∧?(p∧q) 14.在自然推理系统P中构造下面推理的证明： (4)前提：q→p,q?s,s?t,t∧r 结论：p∧q 证明： ②t∧r 前提引入 ②t ①化简律 ③q?s 前提引入 ④s?t 前提引入 ⑤q?t ③④等价三段论 ⑥（q→t）∧(t→q) ⑤置换 ⑦（t→q）⑥化简 ⑧q ②⑥假言推理 ⑨q→p 前提引入 ⑩p ⑧⑨假言推理 ○11p∧q ⑧⑩合取 P59. 18. 在自然推理系统P中构造下面推理证明
（1）如果今天是星期六，我们就要到颐和园或圆明园去玩，如果颐和园游人太多，我们就不去颐和园玩，今天是周末颐和园游人太多，所以我们去圆明园玩。 证明：设p：今天是星期六，q：我们到颐和园玩，r:我们到圆明园玩，s:颐 和园游人太多 前提：p → (q∨r), s →?q ,p ,s 结论：r 推理：① s →?q 前提引入 ② s 前提引入 ③?q ①②假言推理 ④ p 前提引入 ⑤ p → (q∨r) 前提引入 ⑥ q∨r ④⑤假言推理 ⑦ r ③⑥析取三段论 P86. 22. 在自然推理系统N￡中，构造下列推理的证明。 （1）偶数都能被2整除。6是偶数。所以6能被2整除。 设：F（x）:x为偶数，G（x）:x能被2整除，a：6 前提：?x(F(x) →G(x)), F(a) 结论：G（a） 证明： ①任意x（F（x）—>G（x））前提引入 ②F（a）—>G（a）①全称量词消去规则 ③F（a）前提引入 ④G（a）假言推理