计算机数学基础—离散数学谓词逻辑
第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
1
11)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 真值的定义，
))()(()()()()(b Q a Q b P a P x xQ x xP ∨∧∧??∧?
例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))在全总个体域却不是永真式。
离散数学作业答案
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月19日前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1 ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 (PQ)R ． 3．含有三个命题变项P ，Q ，R 的命题公式PQ 的主析取范式是 (PQR) (PQR) ． 4．设P(x)：x 是人，Q(x)：x 去上课，则命题“有人去上课．” 可符号化为 (x)(P(x) →Q(x)) ． 5．设个体域D ＝{a, b},那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) A(b)) (B(a) B(b)) ． 6．设个体域D ＝{1, 2, 3}，A(x)为“x 大于3”，则谓词公式(x)A(x) 的真值为 ． 7．谓词命题公式(x)((A(x)B(x)) C(y))中的自由变元为 ． 8．谓词命题公式(x)(P(x) Q(x) R(x ，y))中的约束变元为 X ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 1．解：设P ：今天是天晴； 则 P ． 2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 解：设P ：小王去旅游，Q ：小李去旅游， 则 PQ ． 3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式． 解：设P:明天天下雪 。 Q:我去滑雪 则 P Q ． 4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 7．解：设 P ：他去旅游，Q ：他有时间， 则 P Q ． 5．请将语句 “有人不去工作”翻译成谓词公式． 11．解：设P(x)：x 是人，Q(x)：x 去工作，
清华大学2006数学分析真题参考答案
清华大学2006数学分析真题参考答案 1．若数列{}n x 满足条件11221n n n n x x x x x x M ----+-++-≤g g g 则称{}n x 为有界变差数列，证：令10y =，11221n n n n n y x x x x x x ---=-+-++-g g g （n=2,3,….） 那么{}n y 单调递增，由条件知{}n y 有界， {}n y ∴收敛 ，从而0,0N ε?>?>，使当n m N >>时，有 n m y y ε-<，此即：11211n n n n m m x x x x x x ε---+--+-++-
(完整版)离散数学作业答案一
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、 数理逻辑部分的综合练习，基本上是按照考试的题型(除单项选择题外) 安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1 .命题公式P (Q P)的真值是T或1 ______ . 2?设P:他生病了，Q:他出差了. R:我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为(P V Q)-R 3. ____________________________________________________________ 含有三个命题变项P，Q，R的命题公式P Q的主析取范式是__________________ _(P Q R) (P Q R)_ 4. 设P(x): x是人，Q(x): x去上课，则命题“有人去上课.” 可符号化为— x(P(x) Q(x))_ 5. 设个体域D = {a, b},那么谓词公式xA(x) yB(y)消去量词后的等值式为 (A(a) A(b)) (B(a) B(b))_ 6 .设个体域D = {1,2, 3}，A(x)为“x大于3”，则谓词公式(x)A(x)的真值为F 或0 ________________ . 7.谓词命题公式(x)((A(x) B(x)) C(y))中的自由变元为 ________ . 8 .谓词命题公式(x)(P(x) Q(x) R(x，y))中的约束变元为x _______ . 三、公式翻译题 1 .请将语句“今天是天晴”翻译成命题公式
清华大学数值分析A第一次作业
7、设y0=28，按递推公式 y n=y n?1? 1 100 783，n=1,2,… 计算y100，若取≈27.982，试问计算y100将有多大误差？ 答：y100=y99?1 100783=y98?2 100 783=?=y0?100 100 783=28?783 若取783≈27.982，则y100≈28?27.982=0.018，只有2位有效数字，y100的最大误差位0.001 10、设f x=ln?(x? x2?1)，它等价于f x=?ln?(x+ x2?1)。分别计算f30，开方和对数取6位有效数字。试问哪一个公式计算结果可靠？为什么？ 答： x2?1≈29.9833 则对于f x=ln x?2?1，f30≈?4.09235 对于f x=?ln x+2?1，f30≈?4.09407 而f30= ln?(30?2?1) ，约为?4.09407，则f x=?ln?(x+ x2?1)计算结果更可靠。这是因为在公式f x=ln?(x? x2?1)中，存在两相近数相减（x? x2?1）的情况，导致算法数值不稳定。 11、求方程x2+62x+1=0的两个根，使它们具有四位有效数字。 答：x12=?62±622?4 2 =?31±312?1 则 x1=?31?312?1≈?31?30.98=?61.98 x2=?31+312?1= 1 31+312?1 ≈? 1 ≈?0.01613
12.（1）、计算101.1?101，要求具有4位有效数字 答：101.1?101= 101.1+101≈0.1 10.05+10.05 ≈0.004975 14、试导出计算积分I n=x n 4x+1dx 1 的一个递推公式，并讨论所得公式是否计算稳定。 答：I n=x n 4x+1dx 1 0= 1 4 4x+1x n?1?1 4 x n?1 4x+1 dx= 1 1 4 x n?1 1 dx?1 4 x n?1 4x+1 dx 1 = 1 4n ? 1 4 I n?1，n=1，2… I0= 1 dx= ln5 1 记εn为I n的误差，则由递推公式可得 εn=?1 εn?1=?=(? 1 )nε0 当n增大时，εn是减小的，故递推公式是计算稳定的。
《计算机数学基础(2)—离散数学》 谓词逻辑
第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,…表示)；谓词分谓词常项(表
吉林大学离散数学课后习题答案
第二章命题逻辑 §2.2 主要解题方法 2.2.1 证明命题公式恒真或恒假 主要有如下方法： 方法一.真值表方法。即列出公式的真值表，若表中对应公式所在列的每一取值全为1，这说明该公式在它的所有解释下都是真，因此是恒真的；若表中对应公式所在列的每
一取值全为0，这说明该公式在它的所有解释下都为假，因此是恒假的。 真值表法比较烦琐，但只要认真仔细，不会出错。 例2.2.1 说明G= (P∧Q→R)∧(P→Q)→(P→R)是恒真、恒假还是可满足。 解：该公式的真值表如下： 表2.2.1 由于表2.2.1中对应公式G所在列的每一取值全为1，故
G恒真。 方法二.以基本等价式为基础，通过反复对一个公式的等价代换，使之最后转化为一个恒真式或恒假式，从而实现公式恒真或恒假的证明。 例2.2.2 说明G= ((P→R) ∨? R)→ (? (Q→P) ∧ P)是恒真、恒假还是可满足。 解：由(P→R) ∨? R=?P∨ R∨? R=1，以及 ? (Q→P) ∧ P= ?（?Q∨ P）∧ P = Q∧? P∧ P=0 知，((P→R) ∨? R)→ (? (Q→P) ∧ P)=0，故G恒假。 方法三.设命题公式G含n个原子，若求得G的主析取范式包含所有2n个极小项，则G是恒真的；若求得G的主合取范式包含所有2n个极大项，则G是恒假的。 方法四. 对任给要判定的命题公式G，设其中有原子P1，P2，…，P n，令P1取1值，求G的真值，或为1，或为0，或成为新公式G1且其中只有原子P2，…，P n，再令P1取0值，求G真值，如此继续，到最终只含0或1为止，若最终结果全为1，则公式G恒真，若最终结果全为0，则公式G
慕课 离散数学 电子科技大学 课后习题十 答案
作业参考答案——10-特殊图 1.(a)(c)(d)是欧拉图，(a)(b)(c)(d)(e)可以一笔画，(a)(b)(c)(d)(e)(f)(g)是 哈密顿图。 2.根据给定条件建立一个无向图G=
数至少为2，而V2中的每个结点度数至多为2，从而它满足t条件t=1，因此存在从V1到V2的匹配，故可分配。 5.此平面图具有五个面，如下图所示。 a b c d e f g r1r2 r3 r4 r5 ?r1，边界为abca，D(r1)=3; ?r2，边界为acga，D(r2)=3; ?r3，边界为cegc，D(r3)=3; ?r4，边界为cdec，D(r4)=3; ?r5，边界为abcdefega，D(r5)=8;无限面 6.设该连通简单平面图的面数为r，由欧拉公式可得，6?12+r=2，所以 r=8，其8个面分别设为r1,r2,r3,r4,r5,r6,r7,r8。因是简单图，故每个面至少由3条边围成。只要有一个面是由多于3条边所围成的，那就有所有面的次数之和 8∑ i=1 D(r i)>3×8=24。但是，已知所有面的次数之和等于边数的两倍，即2×12=24。因此每个面只能由3条边围成。 2
离散数学作业答案
第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试
3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章
国开放大学离散数学本离散数学作业答案
国开放大学离散数学本离 散数学作业答案 The pony was revised in January 2021
离散数学集合论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业． 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档 3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、填空题
1．设集合{1,2,3},{1,2} ==，则P(A)-P(B )= {{1,2}，{2,3}，{1,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>，<>，<> } ．4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} y x y x∈ ∈ < > = A , , 2 , y {B x 那么R－1＝ {< 6，3>，<8，4> } ． 5．设集合A=｛a, b, c, d｝，A上的二元关系R={
北京大学2017秋课件作业【离散数学】及答案
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〉}。
清华大学杨顶辉数值分析第6次作业
清华大学杨顶辉数值分析第6次作业
9.令*()(21),[0,1]n n T x T x x =-∈，试证*{()}n T x 是在[0,1]上带权 2 ()x x x ρ= -****0123(),(),(),()T x T x T x T x . 证明： 1 1 **2 1 1 * *20 12 2 1**20 ()()()(21)(21)211()()()()()211()22 ()()1()1()()()()()1n m n m n m n m n m n n m n m x T x T x dx x T x dx x x t x x T x T x dx t T t dt t t t T t dt t T x x x T x T x dx t T t t ρρρ---=---=-=++-= --= -???? ?令，则 由切比雪夫多项式1 01=02 m n dt m n m n ππ ≠??? =≠??==??? 所以*{()}n T x 是在[0,1]上带权2 ()x x x ρ= - *00*11* 2 2 2 2*33233()(21)1()(21)21 ()(21)2(21)188()(21)4(21)3(21)3248181 T x T x T x T x x T x T x x x x T x T x x x x x x =-==-=-=-=--=-=-=---=-+- 14.已知实验数据如下： i x 19 25 31 38 44 i y 19.0 32.3 49.0 73.3 97.8 用最小二乘法求形如2y a bx =+的经验公式，并求均方误差 解： 法方程为
谓词逻辑-习题与答案
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
《应用离散数学》方景龙版-2.2 谓词公式及其解释
§2.2 谓词公式及其解释 习题2.2 1. 指出下列谓词公式的指导变元、量词辖域、约束变元和自由变元。 （1）))()((y x Q x P x ，→? （2）)()(y x yQ y x xP ，，?→? （3）)())()((z y x xR z y Q y x P y x ，，，，?∨∧?? 解 （1）x ?中的x 是指导变元；量词x ?的辖域是),()(y x Q x P →；x 是约束变元，y 是自由变元。 （2）x ?中的x ，y ?中的y 都是指导变元；x ?的辖域是)(y x P ，，y ?的辖域是 )(y x Q ，；)(y x P ，中的x 是x ?的约束变元，y 是自由变元；)(y x Q ，中的x 是自由变元， y 是y ?的约束变元。 （3）x ?中的x ，y ?中的y 以及x ?中的x 都是指导变元；x ?的辖域是 ))()((z y Q y x P y ，，∧?，y ?的辖域是)()(z y Q y x P ，，∧，x ?的辖域是)(z y x R ，，；)(y x P ，中的x ，y 都是约束变元；)(z y Q ，中的y 是约束变元；z 是自由变元， )(z y x R ，，中的x 为约束变元，y ，z 是自由变元。 2. 设个体域}21{，=D ，请给出两种不同的解释1I 和2I ，使得下面谓词公式在1I 下都是真命题，而在2I 下都是假命题。 （1）))()((x Q x P x →? （2）))()((x Q x P x ∧? 解（1）解释1I ：个体域}21{，=D ，0:)(,0:)(>>x x Q x x P 。 （2）解释2I ：个体域}21{，=D ，2:)(,0:)(>>x x Q x x P 。 3. 对下面的谓词公式，分别给出一个使其为真和为假的解释。 （1）)))()(()((y x R y Q y x P x ，∧?→? （2）)),()()((y x R y Q x P y x →∧?? 解 （1）成真解释：个体域D ＝{1,2,3},0:)(
吉林大学离散数学课后习题答案
第一章集合论基础 §1.1 基本要求 1. 掌握集合、子集、超集、空集、幂集、集合族的概念。懂得两个集合间相等和包含关系 的定义和性质，能够利用定义证明两个集合相等。熟悉常用的集合表示方法。 2. 掌握集合的基本运算：并、交、余、差、直乘积、对称差的定义以及集合运算满足的基 本算律，能够利用它们来证明更复杂的集合等式。 3. 掌握关系、二元关系、空关系、全域关系、相等关系、逆关系的概念以及关系的性质： 自反性、对称性、反对称性、传递性。会做关系的乘积。了解关系的闭包运算：自反闭包、对称闭包、传递闭包。 4. 掌握等价关系、等价类、商集的概念，了解等价关系和划分的内在联系。 5. 掌握部分序关系、部分序集、全序关系、全序集的概念以及部分序集中的特殊元素：最 大元、最小元、极大元、极小元、上确界、小确界的定义。能画出有限部分序集的Hasse 图，并根据图讨论部分序集的某些性质。 6. 掌握映射、映像、1-1映射等概念，会做映射的乘积。了解可数集合的概念，掌握可数 集合的判定方法。 7. 了解关系在数据库中的应用（数据的增、删、改）以及划分在计算机中的应用。
§1.2 主要解题方法 1.2.1 证明集合的包含关系 方法一.用定义来证明集合的包含关系是最常用也是最基本的一种方法。要证明A?B，首先任取x∈A，再演绎地证出x∈B成立。由于我们选择的元素x是属于A的任何一个，而非特指的一个，故知给出的演绎证明对A中含有的每一个元素都成立。当A是无限集时，因为我们不能对x∈A，逐一地证明x∈B成立，所以证明时的假设“x是任取的”就特别重要。 例1.2.1 设A，B，C，D是任意四个非空集合，若A?C，B?D，则A×B?C×D。 证明：任取(x，y) ∈A×B，往证(x，y) ∈C×D。 由(x，y) ∈A×B知，x∈A，且y∈B。又由A?C，B?D知，x∈C，且y∈D，因此，(x，y) ∈C×D。故，A×B?C×D。 方法二.还有一种证明集合包含关系的方法，基于集合的交和并运算的两个基本性质 A?B?A?B=A?A?B=B 以及一些已经证出的集合等式。现在我们就用此方法将上例再证一次。 由下面例1.2.2证明的结论有（A×B）?（C×D）=（A?C）×（B?D），若A?C，B?D，则A?C=A，B?D=B，因此，（A×B）?（C×D）=A×B。因此，A×B?C×D。 1.2.2 证明集合的相等 方法一.若A，B 是有限集，要证明集合A=B当然可以通过逐一比较两集合所有元素均一一对应相等即可，但当A，B 是无限集时，一般通过证明集合包含关系的方法证得A?B，B?A即可。 例1.2.2 设A，B，C，D是任意四个集合，求证（A×B）?（C×D）=（A?C）×（B?D）。 证明：首先证明（A×B）?（C×D）?（A?C）×（B?D）。任取（x,y）∈（A×B）?（C×D），则（x,y）∈（A×B），且（x,y）∈（C×D），故x∈A，y∈B，x∈C，y∈D，即x∈A?C，y∈B?D，因此，（x,y）∈（A?C）×（B?D）。 由于以上证明的每一步都是等价的，所以上述论证反方向进行也是成立的。故可证得（A?C）×（B?D）?（A×B）?（C×D）。 因此，（A×B）?（C×D）=（A?C）×（B?D）。 方法二. 还有一种证明集合相等的方法，可以通过已证出的集合等式，通过相等变换将待证明的等式左（右）边的集合化到右（左）边的集合，或者两边同时相等变换到同一集合。 例1.2.2 设A，B，C是三个集合，已知A?B=A?C，A?B=A?C，求证B=C。 证法1：使用反证法。假设B≠C，则必存在x，满足x∈B，且x?C，或者x?B，且x∈C。不妨设x∈B，且x?C，
清华大学杨顶辉数值分析第6次作业
9.令*()(21),[0,1]n n T x T x x =-∈，试证*{()}n T x 是在[0,1] 上带权()x ρ=的正交多项式，并求****0123(),(),(),()T x T x T x T x . 证明： 1 1 * *0 1 1 * *011**0 ()()()(21)(21)211()()()()()2()()()()()()()()n m n m n m n m n m n n m n m x T x T x dx x T x dx t x x T x T x dx t T t dt t T t dt T x x T x T x dx t T t ρρρ---=--=-== = ???? ?令，则 由切比雪夫多项式1 01=02 m n dt m n m n ππ ≠??? =≠??==??? 所以*{()}n T x 是在[0,1] 上带权()x ρ= *00*11* 22 2 2*33233()(21)1()(21)21 ()(21)2(21)188()(21)4(21)3(21)3248181 T x T x T x T x x T x T x x x x T x T x x x x x x =-==-=-=-=--=-=-=---=-+- 14.已知实验数据如下： 用最小二乘法求形如2y a bx =+的经验公式，并求均方误差 解： 法方程为
22222(1,)(1,1)(1,)(,)(,1)(,)a y x b x y x x x ?????? =???? ?????? ?? 即 5 5327271.453277277699369321.5a b ??????=???????????? 解得 0.972579 0.050035a b =?? =? 拟合公式为20.9725790.050035y x =+ 均方误差 2 4 2 2 0[]0.015023i i i y a bx σ==--=∑ 21.给出()ln f x x =的函数表如下： 用拉格朗日插值求ln 0.54的近似值并估计误差（计算取1n =及2n =） 解：1n =时，取010.5,0.6x x == 由拉格朗日插值定理有 1 100.60.5 0.693147 0.510826 0.50.(60.60.51.82321)0 1.()6047()52 j j j x x x L x f x l x ==------=-=∑ 所以1ln0.54(0.54)0.620219L ≈=- 误差为ln 0.54(0.620219)= 0.004032ε=-- 2n =时，取0120.4,0.5,0.6x x x === 由拉格朗日插值定理有
离散数学答案
第一章命题逻辑基本概念课后练习题答案 1.将下列命题符号化，并指出真值： （1）p∧q,其中，p:2是素数，q:5是素数,真值为1； （2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1； （3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1； （4）p∧q,其中，p:3是素数，q:3是偶数,真值为0； （5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0. 2.将下列命题符号化，并指出真值： （1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1； （2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1； （3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0； （4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1； （5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0； 3.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨； （2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；. 4.因为p与q不能同时为真. 5.设p:今天是星期一，q:明天是星期二，r:明天是星期三： （1）p→q，真值为1（不会出现前件为真，后件为假的情况）； （2）q→p，真值为1（也不会出现前件为真，后件为假的情况）； （3）p q，真值为1； （4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1. 4. .将下列命题符号化，并指出真值： （1）p∧q,其中，p:2是素数，q:5是素数,真值为1； （2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1； （3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1； （4）p∧q,其中，p:3是素数，q:3是偶数,真值为0； （5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0. 5.将下列命题符号化，并指出真值： （1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1； （2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1； （3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0； （4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1； （5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0； 6.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨； （2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；. 7.因为p与q不能同时为真. 13.设p:今天是星期一，q:明天是星期二，r:明天是星期三： （1）p→q，真值为1（不会出现前件为真，后件为假的情况）； （2）q→p，真值为1（也不会出现前件为真，后件为假的情况）； （3）p q，真值为1； （4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1. 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0
西南大学《离散数学》网上作业题及答案
[0004]《离散数学》网上作业题答案 第1次作业 [论述题]第1次作业 一、填空题 1. 设|A | = 5, |B | = 2, 则可定义A 到B 的函数( )个，其中有( )单射，( )个满射. 2. 令G (x ): x 是金子，F (x ): x 是闪光的，则命题“金子都是闪光的，但闪光的未必是金子”符号化为( ). 3. 设X 是非空集合，则X 的幂集P (X )关于集合的?运算的单位元是( )，零元是( )，P (X )关于集合的?运算的单位元是( ). 4. 6阶非Abel 群的2阶子群共有( )个，3阶子群共有( )个，4阶子群共有( )个. 5. 对于n 阶完全无向图K n , 当n 为( )时是Euler 图，当n ≥ ( )时是Hamilton 图，当n ( )时是平面图. 二、单选题 1. 幂集P (P (P (?))) 为( ) (A){{?}, {?, {?}}}. (B){?, {?, {?}}, {?}}. (C){ ?, {?, {?}}, {{?}}, {?}} (D){ ?, {?, {?}}}. 2. 设R 是集合A 上的偏序关系，则1 -?R R 是( ). (A)偏序关系 (B)等价关系 (C)相容关系 (D)以上答案都不对 3. 下列( )组命题公式是不等值的. (A))(B A →?与B A ?∧. (B) )(B A ??与)()(B A B A ∧?∨?∧. (C))(C B A ∨→与C B A →?∧)(. (D))(C B A ∨→与)(C B A ∨∧?. 4.下列代数结构(G , *)中，( )是群. (A)G = {0, 1, 3, 5}, “*”是模7加法. (B) G = Q , “*”是数的乘法. (C)G = Z , “*”是数的减法. (D) G = {1, 3, 4, 5, 9}, “*”是模11乘法. 5.4阶完全无向图4K 中含3条边的不同构的生成子图有 (A)3 (B)4 (C)5 (D)2