离散数学答案第二章习题解答
习题与解答
1. 将下列命题符号化：
(1) 所有的火车都比某些汽车快。
(2) 任何金属都可以溶解在某种液体中。
(3) 至少有一种金属可以溶解在所有液体中。
(4) 每个人都有自己喜欢的职业。
(5) 有些职业是所有的人都喜欢的。
解 (1) 取论域为所有交通工具的集合。令
x x T :)(是火车， x x C :)(是汽车， x y x F :),(比y 跑得快。
“所有的火车都比某些汽车快”可以符号化为))),()(()((y x F y C y x T x ∧?→?。
(2) 取论域为所有物质的集合。令
x x M :)(是金属， x x L :)(是液体， x y x D :),(可以溶解在y 中。
“任何金属都可以溶解在某种液体中” 可以符号化为))),()(()((y x D y L y x M x ∧?→?。
(3) 论域和谓词与(2)同。“至少有一种金属可以溶解在所有液体中” 可以符号化为))),()(()((y x D y L y x M x →?∧?。
(4) 取论域为所有事物的集合。令
x x M :)(是人， x x J :)(是职业， x y x L :),(喜欢y 。
“每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧?→?
(5)论域和谓词与(4)同。“有些职业是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →?∧?。
2. 取论域为正整数集，用函数+（加法），?（乘法）和谓词<，=将下列命题符号化：
(1) 没有既是奇数，又是偶数的正整数。
(2) 任何两个正整数都有最小公倍数。
(3) 没有最大的素数。
(4) 并非所有的素数都不是偶数。
解 先引进一些谓词如下：
x y x D :),(能被y 整除，),(y x D 可表示为)(x y v v =??。
x x J :)(是奇数，)(x J 可表示为)2(x v v =???。
x x E :)(是偶数，)(x E 可表示为)2(x v v =??。
x x P :)(是素数，)(x P 可表示为)1)(()1(x u u x u v v u x =∨=?=???∧=?。
(1) “没有既是奇数，又是偶数的正整数”可表示为))()((x E x J x ∧??，
并可进一步符号化为))2()2((x v v x v v x =??∧=?????。
(2) “任何两个正整数都有最小公倍数”可表示为
))),(),((),(),((u z u z y u D x u D u y z D x z D z y x =∨<→∧?∧∧???，
并可进一步符号化为
))
)()(()()((u z u z u y v v u x v v u z y v v z x v v z y x =∨<→=??∧=???∧=??∧=?????(3) “没有最大的素数”可表示为)))(()((x y x y y P y x P x =∨<→?∧??，
并可进一步符号化为
))
)1)(()1(()1)(()1((x y x y y u u y u v v u y y x u u x u v v u x x =∨<→=∨=?=???∧=??∧=∨=?=???∧=??? (4) “并非所有的素数都不是偶数”可表示为))()((x E x P x ?→??，并可进一步符号化为
))2()1)(()1((x v v x u u x u v v u x x =???→=∨=?=???∧=???
3. 取论域为实数集合，用函数+，－（减法）和谓词<，=将下列命题符号化：
(1) 没有最大的实数。
(2) 任何两个不同的实数之间必有另一实数。
(3) 函数)(x f 在点a 处连续。
(4) 函数)(x f 恰有一个根。
(5) 函数)(x f 是严格单调递增函数。
解 (1) “没有最大的实数”符号化为)(x y x y y x =∨
(2) “任何两个不同的实数之间必有另一实数”符号化为))((y z z x z y x y x <∧
(3) “函数)(x f 在点a 处连续”的定义是：
任给0>ε，总可以找到0>δ，使得只要δ<-||a x 就有ε<-|)()(|a f x f 。
“函数)(x f 在点a 处连续”符号化为
))))()()()((0(0(εεδδδδεε+<∧<-→+<∧<-?∧
(4) “函数)(x f 恰有一个根”符号化为))0)((0)((x y y f y x f x =→=?∧=?。
(5) “函数)(x f 是严格单调递增函数”符号化为))()((y f x f y x y x <→
4. 指出下列公式中变元的约束出现和自由出现，并对量词的每次出现指出其辖域。
(1) )),(),((a x P x y P x →?
(2) ),()(y x zQ x xP ?→?
(3) )()())()((x Q x xP x R x P x ∧?→∧?
(4) ))),(,()),,(((y x g z xP x y x f P y ?→?
(5) )())()()((x R x xR x Q x P x ∧?∧→?
解 (1) 变元 x 在)),(),((a x P x y P x →?中三次出现都是约束出现，x 的唯一出现的辖域是 P (y , x ) P (x , a )。
(2) 变元 x 在),()(y x zQ x xP ?→?中的头两次出现是约束出现，第三次出现是自由出现。变元 y 在),()(y x zQ x xP ?→?中的唯一出现是自由出现。变元 z 在),()(y x zQ x xP ?→?中的唯一出现是约束出现。x 的唯一出现的辖域是 P (x )，z 的唯一出现的辖域是Q (x , y )。
(3) 变元 x 在)()())()((x Q x xP x R x P x ∧?→∧?中的头五次出现是约束出现，第六次出现是自由出现。x 的第一次出现的辖域是P (x ) R (x )，第二次出现的辖域是P (x )。
(4) 变元 x 在))),(,()),,(((y x g z xP x y x f P y ?→?中的头两次出现是自由出现，后两次出现是约束出现。x 的唯一出现的辖域是 P (z , g (x , y ))， y 的唯一出现的辖域是 P (f (x , y ), x ) xP (z , g (x , y ))。
(5) 变元 x 在)())()()((x R x xR x Q x P x ∧?∧→?中的头五次出现是约束出现，第六次出现是自由出现。x 的唯一出现的辖域是P (x ) Q (x ) xR (x )，
x 的唯一出现的辖
域是R (x )。
5. 归纳证明：若t ，t '是项，则x t t '也是项。
证明 ① 若t 是x ，则x t t '是t '，x t t '是项。
② 若t 是不同于x 的变元y ，则x t t '仍是y ，x t t '是项。
③ 若t 是常元a ，则x t t '仍是a ，x t t '是项。
④若t 是),,(1n t t f Λ，则x t t '是))(,,)((1x t n x t t t f ''Λ，由归纳假设知x t n x t t t '')(,,)(1Λ都是项，
所以x t t '是项。
6. 归纳证明：若t 是项，A 是公式，则x t A 也是公式。
证明 ① 若A 是),,(1n t t P Λ，则x t A 是))(,,)((1x t n x t t t P Λ，由上题知x t n x t t t )(,,)(1Λ都是项，所以x t A 是公式。
② 若A 是B ?，则x t A 是x t B ?，由归纳假设知x t B 是公式，所以x t A 是公式。
③ 若A 是C B →，则x t A 是x t x t C B →，由归纳假设知x t B 和x t C 都是公式，所以x t A 是公式。
④ 若A 是xB ?，则x t A 仍是A ，x t A 是公式。
⑤ 若A 是yB ?，其中y 是不同于x 的变元，则x t A 是x t yB ?，由归纳假设知x t B 是公式，所以x t A 是公式。
7. 给定解释I 和I 中赋值v 如下：
}2,1{=I D ，1=I a ，2=I b ，2)1(=I f ，1)2(=I f
1)2,1()1,1(==I I P P ，0)2,2()1,2(==I I P P ，1)(=x v ，1)(=y v
计算下列公式在解释I 和赋值I 中v 下的真值。
(1) )),(())(,())(,(x y f P b f x P x f a P ∧∧
(2) ),(x y yP x ??
(3) )))(),((),((y f x f P y x P y x →??
解 (1) )))(),(())(,())(,((v x y f P b f x P x f a P I ∧∧
))()),((())(),(()))((,(x v y v f P b f x v P x v f a P I I I I I I I I ∧∧=
)1),1(())2(,1())1(,1(I I I I I I f P f P f P ∧∧= 0011)1,2()1,1()2,1(=∧∧=∧∧=I I I P P P
(2) )))(,((v x y yP x I ??
])2/[))(,((])1/[))(,((x v x y yP I x v x y yP I ?∧?= ]))
2/][1/[))(,((])1/][1/[))(,(((y x v x y P I y x v x y P I ∨=
]))2/][2/[))(,((])1/][2/[))(,(((y x v x y P I y x v x y P I ∨∧
))2,2()2,1(())1,2()1,1((I I I I P P P P ∨∧∨= 1)01()01(=∨∧∨=
(3) )))))((),((),(((v y f x f P y x P y x I →??
)))2(,)1(()2,1(()))1(,)1(()1,1((I I I I I I I I f f P P f f P P →∧→=
)))2(,)2(()2,2(()))1(,)2(()1,2((I I I I I I I I f f P P f f P P →∧→∧
))1,1()2,2(())2,1()1,2(())1,2()2,1(())2,2()1,1((I I I I I I I I P P P P P P P P →∧→∧→∧→=01100)10()10()01()01(=∧∧∧=→∧→∧→∧→=
7. 给定解释I 如下：
},{b a D I =， 1),(),(==b b P a a P I I ， 0),(),(==a b P b a P I I
判断I 是不是以下语句的模型。
(1) ),(y x yP x ??
(2) ),(y x yP x ??
(3) ),(y x yP x ??
(4) ),(y x P y x ???
(5) )),(),((x y P y x P y x →??
(6) ),(x x xP ?
解 (1) )),((y x yP x I ??
1)10()01()),(),(()),(),((=∨∧∨=∨∧∨=b b P a b P b a P a a P I I I I
(2) )),((y x yP x I ??
01001),(),(),(),(=∧∧∧=∧∧∧=b b P a b P b a P a a P I I I I
(3) )),((y x yP x I ??
0)10()01()),(),(()),(),((=∧∨∧=∧∨∧=b b P a b P b a P a a P I I I I
(4) )),((y x P y x I ???
10110),(),(),(),(=∨∨∨=?∨?∨?∨?=b b P a b P b a P a a P I I I I
(5) ))),(),(((x y P y x P y x I →??
)),(),(()),(),((a b P b a P a a P a a P I I I I →∧→=
)),(),(()),(),((b b P b b P b a P a b P I I I I →∧→∧
1)11()00()00()11(=→∧→∧→∧→=
(6) 111),(),()),((=∧=∧=?b b P a a P x x xP I I I
9. 写出一个语句A ，使得A 有模型，并且A 的每个模型的论域至少有三个元素。 解 语句A 为),(),(),(),(a c P c b P b a P x x P x ∧∧∧??。给定解释I '如下。
I D '为自然数集合， 1),(='y x P I 当且仅当y x ≠， 1='I a ，2='I b ，3='I c 则I '是A 的模型，A 有模型。
任取满足语句A 的解释I ，则1),(),(),(===I I I I I I I I I a c P c b P b a P ，又因为1)),((=??x x P x I ，所以I a ，I b ，I c 是论域I D 中三个不同元素，论域I D 中至少有三个元素。
10. 写出一个语句A ，使得A 有模型，并且A 的每个模型的论域有无穷多个元素。
解 语句A 为),()),(),(),((),(y x yP x z x P z y P y x P y x x x P x ??∧→∧??∧??。给定解释I '如下。
I D '为自然数集合， 1),(='y x P I 当且仅当y x <
则I '是A 的模型，A 有模型。
任取满足语句A 的解释I ，取I D d ∈1，因为1)),((=??y x yP x I ，所以有I D d ∈2使得1),(21=d d P I ，又因为1)),((=??x x P x I ，故21d d ≠。因为1)),((=??y x yP x I ，所以有I D d ∈3使得1),(32=d d P I ，又因为1)),((=??x x P x I ，故23d d ≠。因为1))),(),(),(((=→∧??z x P z y P y x P y x I ，所以1),(31=d d P I ，故13d d ≠。因此，1d ，2d ，3d 是论域中的三个不同元素。这个过程可以不断进行下去，得到Λ,,,321d d d 因此，论域 D I 中必然有无穷多个元素。
11. 判断以下公式是不是永真式、永假式、可满足式，并说明理由。
(1) ))()(()()(x Q x P x x xQ x xP ∨?→?∨?
(2) ))()(()()(x Q x P x x xQ x xP ∧?→?∧?
(3) )()())()((x xQ x xP x Q x P x ?∨?→∨?
(4) ),(),(y x yP x x x xP ??→?
(5) ))()(())()((x Q x P x x xQ x xP →?→?→?
(6) ))()(())()((x Q x P x x xQ x xP →?→?→?
(7) ))()(())()((x xQ x xP x Q x P x ?→?→→?
解 (1) ))()(()()(x Q x P x x xQ x xP ∨?→?∨?是永真式。若解释I 使得1))()((=?∨?x xQ x xP I ，则1))((=?x xP I 或1))((=?x xQ I 。
① 若1))((=?x xP I ，则存在I D d ∈使得1)(=d P I ，1)()(=∨d Q d P I I 。
② 若1))((=?x xQ I ，则存在I D d ∈使得1)(=d Q I ，1)()(=∨d Q d P I I 。
因此，1)))()(((=∨?x Q x P x I 。
(2) ))()(()()(x Q x P x x xQ x xP ∧?→?∧?是非永真的可满足式。给定解释I 如下。
}{d D I =， 1)(=d P I ， 1)(=d Q I
则1)))()(()()((=∧?→?∧?x Q x P x x xQ x xP I 。
给定解释I '如下。
},{b a D I ='，1)(='a P I ，0)(='b P I ，0)(='a Q I ，1)(='b Q I
则0)))()(()()((=∧?→?∧?'x Q x P x x xQ x xP I 。
(3) )()())()((x xQ x xP x Q x P x ?∨?→∨?是非永真的可满足式。给定解释I 如下。
}{d D I =， 1)(=d P I ， 1)(=d Q I
则1))()())()(((=?∨?→∨?x xQ x xP x Q x P x I 。
给定解释I '如下。
},{b a D I ='，1)(='a P I ，0)(='b P I ，0)(='a Q I ，1)(='b Q I
则0))()())()(((=?∨?→∨?'x xQ x xP x Q x P x I 。
(4) ),(),(y x yP x x x xP ??→?是非永真的可满足式。给定解释I 如下。
}{d D I =， 1),(=d d P I
则1)),(),((=??→?y x yP x x x xP I 。
给定解释I '如下。
},{b a D I ='，1),(),(==''b b P a a P I I ，0),(),(==''a b P b a P I I
则0)),(),((=??→?'y x yP x x x xP I 。
(5) ))()(())()((x Q x P x x xQ x xP →?→?→?是非永真的可满足式。给定解释I 如下。
}{d D I =， 1)(=d P I ， 1)(=d Q I
则1)))()(())()(((=→?→?→?x Q x P x x xQ x xP I 。
给定解释I '如下。
},{b a D I ='，1)(='a P I ，0)(='b P I ，0)(='a Q I ，1)(='b Q I
则0)))()(())()(((=→?→?→?'x Q x P x x xQ x xP I 。
(6) ))()(())()((x Q x P x x xQ x xP →?→?→?是永真式。若解释I 使得0)))()(((=→?x Q x P x I ，则存在I D d ∈使得0)()(=→d Q d P I I ，因此1)(=d P I 且0)(=d Q I ，1))((=?x xP I 且0))((=?x xQ I ，0)))()(((=?→?x xQ x xP I 。
(7) ))()(())()((x xQ x xP x Q x P x ?→?→→?是永真式。若解释I 使得0)))()(((=?→?x xQ x xP I ，则1))((=?x xP I 且0))((=?x xQ I 。存在I D d ∈使得1)(=d P I ，又因为0))((=?x xQ I ，所以0)(=d Q I ，0)()(=→d Q d P I I 。因此，0)))()(((=→?x Q x P x I 。
12.设A ,B 是任意公式，证明以下公式是永真式。
(1) xA A x
t ?→,其中项t 对于A 中的x 是可代入的。
(2) A x xA ?????
(3) A x xA ?????
(4) xB xA B A x ?∧?→∧?)(
(5) )(B A x xB xA ∨?→?∨?
(6) )()(xB A B A x ?→→→?，其中x 不是A 的自由变元。
解 (1) 任取解释I 和I 中赋值v ，若1))((=v A I x t ,则1))])((/[)(())((==v t I x v A I v A I x t ，所以1))((=?v xA I 。这表明xA A x t ?→是永真式。
(2) 任取解释I 和I 中赋值v ，
1))((=??v xA I
当且仅当 0))((=?v xA I
当且仅当 存在I D d ∈使得0])/[)((=d x v A I
当且仅当 存在I D d ∈使得1])/[)((=?d x v A I 当且仅当 1))((=??v A x I
这表明A x xA ?????是永真式。
(3) 任取解释I 和I 中赋值v ，
0))((=??v xA I
当且仅当 1))((=?v xA I
当且仅当 存在I D d ∈使得1])/[)((=d x v A I
当且仅当 存在I D d ∈使得0])/[)((=?d x v A I 当且仅当 0))((=??v A x I
这表明A x xA ?????是永真式。
(4) 任取解释I 和I 中赋值v ，若1)))(((=∧?v B A x I ，则存在I D d ∈使得1)]/[)((=∧d x v B A I ，1)]/[)(()]/[)((==d x v B I d x v A I ，1))((=?v xA I 且1))((=?v xB I ，1))((=?∧?v xB xA I 。这表明xB xA B A x ?∧?→∧?)(是永真式。
(5) 任取解释I 和I 中赋值v ，若0)))(((=∨?v B A x I ，则存在I D d ∈使得
0)]/[)((=∨d x v B A I ，0)]/[)(()]/[)((==d x v B I d x v A I ，0))((=?∨?v xB xA I 。这表明)(B A x xB xA ∨?→?∨?是永真式。
(6) 任取解释I 和I 中赋值v ，若1))(()))(((==→?v A I v B A x I ，则对于每个I D d ∈，1)]/[)((=→d x v B A I ，因为x 不是A 的自由变元，所以1))(()]/[)((==v A I d x v A I ，因此1)]/[)((=d x v B I ，1))((=?v xB I 。这表明)()(xB A B A x ?→→→?是永真式。
13.设1A 是公式A 的闭包，2A 是A x x n ??Λ1，其中},,{)(V ar 1n x x A Λ=。证明：
(1) A 是永真式当且仅当1A 是永真式；
(2) A 是可满足式当且仅当2A 是可满足式。
证明 (1) （?）首先证明：若A 是永真式，则xA ?是永真式。设A 是永真式。任取解释I 和I 中赋值v ，任取I D d ∈，因为]/[d x v 也是I 中赋值，所以1)]/[)((=d x v A I ，1))((=?v xA I 。xA ?是永真式。若A 是永真式，则A x n ?是永真式，… ，A x x n ??Λ1是永真式。
（?）因为A A x x n →??Λ1是永真式，所以若A x x n ??Λ1是永真式，则A 是永真式。
(2) （?）因为A x x A n ??→Λ1是永真式，所以若解释I 和I 中赋值v 满足A ，则I 和v 满足A x x n ??Λ1。
（?）若解释I 和I 中赋值v 满足A x x n ??Λ1，则有I n D d d ∈,,1Λ使得1])/,,/[)((11=n n d x d x v A I Λ，I 和I 中赋值]/,,/[11n n d x d x v Λ满足A 。
14.判断以下等值式是否成立，并说明理由。
(1) )()())()((x xQ x xP x Q x P x ??????
(2) )()())()((x xQ x xP x Q x P x ?→??→?
(3) )()(x P x xP ??
(4) )()(x xP x xP x ????
(5) )()())()((y yQ x xP y yQ x P x ???????
(6) )()())()((y yQ x xP y yQ x P x ???????
解 (1) 不成立。取解释I 如下。
},{b a D I =， 0)(=a P I ， 1)(=b P I ， 1)(=a Q I ， 0)(=b Q I
则0)))()(((=??x Q x P x I 且1))()((=???x xQ x xP I 。
(2) 不成立。取解释I 如下。
},{b a D I =， 0)(=a P I ， 1)(=b P I ， 1)(=a Q I ， 0)(=b Q I
则0)))()(((=→?x Q x P x I 且1))()((=?→?x xQ x xP I 。
(3) 不成立。取解释I 和I 中赋值v 下。
},{b a D I =， 0)(=a P I ， 1)(=b P I ， b x v =)(
则0)))(((=?v x xP I 且1)))(((=v x P I 。
(4) 成立。任取解释I 和I 中赋值v ，因为x 不是)(x xP ?中的自由变元，所以对于每个I D d ∈，)))(((])/[))(((v x xP I d x v x xP I ?=?。
1)))(((=??v x xP x I
当且仅当对于每个I D d ∈，1])/[))(((=?d x v x xP I 当且仅当1)))(((=?v x xP I
(5) 不成立。取解释I 如下。
},{b a D I =， 0)(=a P I ， 1)(=b P I ， 1)(=a Q I ， 0)(=b Q I
则0)))()(((=???y yQ x P x I 且1))()((=???y yQ x xP I 。
(6) 不成立。取解释I 如下。
},{b a D I =， 1)(=a P I ， 0)(=b P I ， 1)()(==b Q a Q I I
则0)))()(((=???y yQ x P x I 且1))()((=???y yQ x xP I 。
15.设A ,B 是任意公式，证明以下等值式。
(1) x
y A y A x ???，其中y 在A 中不出现。
(2) B x A x B A x ?→??→?)(
(3) B y A x B A y x ?∨??∨??)(，其中x 不是B 的自由变元，y 不是A 的自由变元。
(4) B y A x B A y x ?∧??∧??)(，其中x 不是B 的自由变元，y 不是A 的自由变元。
(5) B y A x B A y x ?→??→??)(，其中x 不是B 的自由变元，y 不是A 的自由变元。
(6) A x y A y x ?????
证明 (1) x y
x y A y A y A x A x ??????????? (2) B x A x B x A x B x A x B A x B A x ?→???∨????∨???∨???→?)()(
(3) B y A x B y A x B A y x ?∨???∨??∨??)()(
(4) B y A x yB A x B A y x ?∧???∧??∧??)()(
(5) B y A x yB A x B A y x ?→???→??→??)()(
(6) 任取解释I 和I 中赋值v ，
0))((=??v yA x I
当且仅当有I D d ∈使得0])/[)((=?d x v yA I
当且仅当有I D c d ∈,使得0])/][/[)((=c y d x v A I
当且仅当有I D c d ∈,使得0])/][/[)((=d x c y v A I
当且仅当有I D c ∈使得0])/[)((=?c y v xA I
当且仅当0))((=??v xA y I
16.判断以下逻辑推论关系是否成立，并说明理由。
(1) )()(|))()((x xQ x xP x Q x P x ?∨?=∨?
(2) ))()((|)()(x Q x P x x xQ x xP ∧?=?∧?
(3) ))()((|))()((x Q x P x x xQ x P x ??=???
(4) ))()((|))()((x Q x P x x xQ x P x →?=?→?
(5) )(|)(,))()((x xQ x xP x Q x P x ?=?→?
(6) ),(|),(x x xP y x yP x ?=??
解 (1) 不成立。取解释I 如下。
},{b a D I =， 0)(=a P I ， 1)(=b P I ， 1)(=a Q I ，
0)(=b Q I 则1)))()(((=∨?x Q x P x I 且0))()((=?∨?x xQ x xP I 。这表明
)()(/|))()((x xQ x xP x Q x P x ?∨?=∨?。
(2) 不成立。取解释I 如下。
},{b a D I =， 0)(=a P I ， 1)(=b P I ， 1)(=a Q I ， 0)(=b Q I
则1))()((=?∧?x xQ x xP I 且0)))()(((=∧?x Q x P x I 。这表明))()((/|)()(x Q x P x x xQ x xP ∧?=?∧?。
(3) 不成立。取解释I 如下。
},{b a D I =， 0)()(==b P a P I I ， 1)(=a Q I ， 0)(=b Q I
则1)))()(((=???x xQ x P x I 且0)))()(((=??x Q x P x I 。这表明))()((/|))()((x Q x P x x xQ x P x ??=???。
(4) 若解释I 使得0)))()(((=→?x Q x P x I ，则有I D d ∈使得0)()(=→d Q d P I I ，1)(=d P I 且0)(=d Q I ，0))((=?x xQ I ，0)))()(((=?→?x xQ x P x I 。这表明))()((|))()((x Q x P x x xQ x P x →?=?→?。
(5) 不成立。取解释I 如下。
},{b a D I =， 1)(=a P I ， 0)(=b P I ， 0)()(==b Q a Q I I
则1))(()))()(((=?=→?x xP I x Q x P x I 且0))((=?x xQ I ，这表明)(/|)(,))()((x xQ x xP x Q x P x ?=?→?。
(6) 不成立。取解释I 如下。
},{b a D I =， 1),(=b a P I ， 0),(),(),(===b b P a b P a a P I I I
则1)),((=??y x yP x I ，但0)),((=?x x xP I 。所以),(/|),(x x xP y x yP x ?=??。
17.设A ,B 是任意公式，证明以下结论。
(1) xB xA B A x ?∧?=∧?|)(
(2) xB xA B A x ?=?→?|,)(
(3) A y x A x y
x ??=?|，其中x 对于A 中的y 是可代入的。
(4) )(|B A x B x A x →?=?→?
证明 (1) 若解释I 和I 中赋值v 使得1)))(((=∧?v B A x I ，则有I D d ∈使得
1])/[)((=∧d x v B A I ，1])/[)((])/[)((==d x v B I d x v A I ，1))((=?v xA I 且1))((=?v xB I ，1))((=?∧?v xB xA I 。这表明xB xA B A x ?∧?=∧?|)(。
(2) 若解释I 和I 中赋值v 使得1))(()))(((=?=→?v xA I v B A x I ，则对于每个I D d ∈，1])/[)((])/[)((==→d x v A I d x v B A I ，1])/[)((=d x v B I ，1))((=?v xB I 。这表明xB xA B A x ?=?→?|,)(。
(3) 若解释I 和I 中赋值v 使得1))((=?v A x I y x ，则有I D d ∈使得1])/[)((=y x v A I y x ，
因为])/][/[)((])])/[)((/][/[)((])/[)((d y d x v A I d x v x I y d x v A I d x v A I y x ==，所以1])/][/[)((=d y d x v A I ，1])/[)((=?d x v yA I ，1))((=??v yA x I 。这表明
A y x A x y x ??=?|。
(4) 若解释I 和I 中赋值v 使得0)))(((=→?v B A x I ，则对于每个I D d ∈，0])/[)((=→d x v B A I ，1])/[)((=d x v A I 且0])/[)((=d x v B I ，因此1))((=?v xA I 且0))((=?v xB I ，0))((=?→?v xB xA I 。所以)(|B A x B x A x →?=?→?。
18.设变元x 既不是公式B 中的自由变元，也不是公式集Γ中任何公式的自由变元，A 是公式。若B A =?Γ|}{，则B A x =??Γ|}{。
证明 设解释I 和I 中赋值v 满足}{A x ??Γ，则1))((=?v xA I ，有I D d ∈使得1])/[)((=d x v A I 。因为x 不是公式集Γ中任何公式的自由变元，所以I 和]/[d x v 也满足Γ，I 和]/[d x v 满足}{A ?Γ。又因为B A =?Γ|}{，所以1])/[)((=d x v B I ，因为x 不是B 中的自由变元，因此1))((=v B I 。这表明B A x =??Γ|}{。
19. 设Γ是公式集合，A 是公式，则A =Γ|当且仅当}{A ??Γ不可满足。
证明 设}{A ??Γ可满足，解释I 和I 中赋值v 满足}{A ??Γ，则I 和v 满足Γ且0))((=v A I ，所以A /|=Γ。
设A /|=Γ，则有解释I 和I 中赋值v 满足Γ且0))((=v A I ，所以I 和v 满足}{A ??Γ。因此，}{A ??Γ可满足。
20.判断以下公式集合是否可满足，并说明理由。
(1) )}({}|)({x xP t t P ???是项
(2) )},(,)),(),(),((,),({y x yP x z x P z y P y x P z y x x x P x ??→∧????? 解 (1) 可满足。取解释I 和I 中赋值v 如下。
}2,1{=I D ， 0)1(=I P ， 1)2(=I P ，
对每个常元a ，1=I
a ；
对每个n 元函数符号f ，1),,(1=n I x x f Λ；
对每个变元x ，1)(=x v 。
可归纳证明：对每个项t ，1))((=v t I 。 I 和v 满足)}({}|)({x xP t t P ???是项。
(2) 可满足。取解释I 和I 中赋值v 如下。
I D 为自然数集， 1),(=y x P I 当且仅当 y x <
则I 和v 满足)},(,)),(),(),((,),({y x yP x z x P z y P y x P z y x x x P x ??→∧?????。
离散数学第二次在线作业
第二次在线作业 1.（ 2.5分）代数系统是指由集合及其上的一元或二元运算符组成的系统 ?正确 ?错误 我的答案：正确此题得分：2.5分 2.（2.5分）设< L*1*2> 是代数系统，其中是*1*2二元运算符，如果*1*2都满足交换律、结合律，并且*1和*2满足吸收律，则称< L*1*2> 是格 ?正确 ?错误 我的答案：正确此题得分：2.5分 3.（2.5分）对实数的普通加法和乘法，0是加法的幂等元，1是乘法的幂等元 ?正确 ?错误 我的答案：正确此题得分：2.5分 4.（2.5分）零元是不可逆的 ?正确 ?错误 我的答案：正确此题得分：2.5分 5.（2.5分）群中每个元素的逆元都是惟一的 ?正确 ?错误 我的答案：正确此题得分：2.5分
6.（2.5分）设abc是阿贝尔群< G+> 的元素，则-(a+b+c)=(-a)+( -b)+( -c) ?正确 ?错误 我的答案：正确此题得分：2.5分 7.（2.5分） < {01234}MAXMIN> 是格 ?正确 ?错误 我的答案：正确此题得分：2.5分 8.（2.5分）一个图的哈密尔顿路是一条通过图中所有结点一次且恰好一次的路 ?正确 ?错误 我的答案：正确此题得分：2.5分 9.（2.5分）在有向图中，结点v的出度deg+(v)表示以v为起点的边的条数，入度deg-(v)表示以v为终点的边的条数 ?正确 ?错误 我的答案：正确此题得分：2.5分 10.（2.5分）一个图的欧拉回路是一条通过图中所有边一次且恰好一次的回路 ?正确 ?错误 我的答案：正确此题得分：2.5分
11.（2.5分）不含回路的连通图是树 ?正确 ?错误 我的答案：正确此题得分：2.5分 12.（2.5分）简单图邻接矩阵主对角线上的元素全为0 ?正确 ?错误 我的答案：正确此题得分：2.5分 13.（2.5分）树一定是连通图 ?正确 ?错误 我的答案：正确此题得分：2.5分 14.（2.5分）无向图的邻接矩阵是对称阵 ?正确 ?错误 我的答案：正确此题得分：2.5分 15.（2.5分）不与任何结点相邻接的结点称为孤立结点 ?正确 ?错误 我的答案：正确此题得分：2.5分
离散数学 第二章练习题答案
一、 选择题 1．下列四个公式正确的是 ①)()())()((x xB x xA x B x A x ?∧??∧? ②)()())()((x xB x xA x B x A x ?∨??∨? ③)()())()((x xB x xA x B x A x ?∨??∨? ④))()(()()(x B x A x x xB x xA ∧???∧? A.①③ B.①④ C.③④ D.②④ 2. 谓词公式)())()((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 3. 谓词公式))()(()(x xQ x Q x x xP ??→??→?的类型是（ ） (A ) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 蕴涵式 4. 设个体域为整数集，下列公式中其真值为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 5. 设个体域{,}A a b =，公式()()xP x xS x ?∧?在中消去量词后应为 ( ) (A) ()()P x S x ∧ (B ) ()()(()())P a P b S a S b ∧∧∨ (C) ()()P a S b ∧ (D) ()()()()P a P b S a S b ∧∧∨ 6. 在谓词演算中，下列各式正确的是( ) (A) (,)(,)x yA x y y xA x y ????? (B ) (,)(,)x yA x y y xA x y ????? (C) (,)(,)x yA x y x yA x y ????? (D) (,)(,)x yA x y y xA x y ????? 7.下列各式不正确的是( ) (A ) (()())()()x P x Q x xP x xQ x ?∨??∨? (B) (()())()()x P x Q x xP x xQ x ?∧??∧? (C) (()())()()x P x Q x xP x xQ x ?∨??∨? (D) (())()x P x Q xP x Q ?∧??∧
山东大学离散数学题库及答案
《离散数学》题库答案 一、选择或填空 (数理逻辑部分) 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q →P (2)?Q=>P →Q (3)P=>P →Q (4)?P ∧(P ∨Q)=>?P 答:(1),(4) 2、下列公式中哪些就是永真式？( ) (1)(┐P ∧Q)→(Q →?R) (2)P →(Q →Q) (3)(P ∧Q)→P (4)P →(P ∨Q) 答:(2),(3),(4) 3、设有下列公式,请问哪几个就是永真蕴涵式?( ) (1)P=>P ∧Q (2) P ∧Q=>P (3) P ∧Q=>P ∨Q (4)P ∧(P →Q)=>Q (5) ?(P →Q)=>P (6) ?P ∧(P ∨Q)=>?P 答:(2),(3),(4),(5),(6) 4、公式?x((A(x)→B(y,x))∧ ?z C(y,z))→D(x)中,自由变元就是( ),约束变元就是( )。 答:x,y, x,z 5、判断下列语句就是不就是命题。若就是,给出命题的真值。( ) (1) 北京就是中华人民共与国的首都。 (2) 陕西师大就是一座工厂。 (3) 您喜欢唱歌不？ (4) 若7+8＞18,则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答:(1) 就是,T (2) 就是,F (3) 不就是 (4) 就是,T (5) 不就是 (6) 不就是 6、命题“存在一些人就是大学生”的否定就是( ),而命题“所有的人都就是要死的”的否定就是( )。 答:所有人都不就是大学生,有些人不会死 7、设P:我生病,Q:我去学校,则下列命题可符号化为( )。 (1) 只有在生病时,我才不去学校 (2) 若我生病,则我不去学校 (3) 当且仅当我生病时,我才不去学校(4) 若我不生病,则我一定去学校 答:(1) P Q →? (2) Q P ?→ (3) Q P ?? (4)Q P →? 8、设个体域为整数集,则下列公式的意义就是( )。 (1) ?x ?y(x+y=0) (2) ?y ?x(x+y=0) 答:(1)对任一整数x 存在整数 y 满足x+y=0(2)存在整数y 对任一整数x 满足x+y=0 9、设全体域D 就是正整数集合,确定下列命题的真值: (1) ?x ?y (xy=y) ( ) (2) ?x ?y(x+y=y) ( ) (3) ?x ?y(x+y=x) ( ) (4) ?x ?y(y=2x) ( ) 答:(1) F (2) F (3)F (4)T 10、设谓词P(x):x 就是奇数,Q(x):x 就是偶数,谓词公式 ?x(P(x)∨Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答:(1) 11、命题“2就是偶数或-3就是负数”的否定就是( )。 答:2不就是偶数且-3不就是负数。 12、永真式的否定就是( ) (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能
《离散数学》第2次作业
一、填空题 1. 设A = {1, 2}, B = {2, 3}, 则A - A =________, A – B =________, B – A =________. 2. 设N 是自然数集合, f 和g 是N 到N 的函数, 且f (n ) = 2n +1，g (n ) = n 2, 那么复合函数(f f ) (n )=________ , (f g ) (n )=________ , (g f ) (n ) =________. 3. 设|X | = n , P (X )为集合X 的幂集, 则| P (X )| = ________. 在代数结构(P (X ), ∪)中，则P (X ) 对∪运算的单位元是________, 零元是________ . 4. 在下图中， _______________________________是其Euler 路 . 5. 设有向图G = (V , E )，V = {v 1，v 2，v 3，v 4}，若G 的邻接矩阵A =???? ??????1001001111011010, 则v 1的出度deg +(v 1) =________, v 1的入度deg -(v 1) =________, 从v 2到v 4长度为2的路有________条. 二、单选题 1. 设A = {{1, 2, 3}, {4, 5}, {6, 7, 8}}, 下列选项正确的是( ) (A) 1∈A (B) {1, 2, 3}?A (C) {{4, 5}}?A (D) ?∈A . 2．集合A = {1, 2, …, 10}上的关系R ={(x , y )|x + y = 10, x , y ∈A }, 则R 的性质是 ( ) (A) 自反的 (B) 对称的 (C) 传递的、对称的 (D) 反自反的、传递的. 3．若R 和S 是集合A 上的两个关系，则下述结论正确的是( ) (A) 若R 和S 是自反的, 则R ∩S 是自反的 (B) 若R 和S 是对称的, 则R S 是对称的 (C) 若R 和S 是反对称的, 则R S 是反对称的 (D) 若R 和S 是传递的, 则R ∪S 是传递的. 4．集合A = {1, 2, 3, 4}上的关系 R = {(1, 4), (2, 3), (3, 1), (4, 3)}, 则下列不是．．t (R )中元素的是( ) (A) (1, 1) (B) (1, 2) (C) (1, 3) (D) (1, 4). 5．设p ：我们划船，q ：我们跑步, 则有命题“我们不能既划船又跑步”符号化为( ) (A) ? p ∧? q (B) ? p ∨? q
离散数学作业
命题逻辑的基本概念 一、单项选择题 1．下列语句中不是命题的有（ ）. A 9+5≤12 B. 1+3=5 C. 我用的电脑CPU 主频是1G 吗D.我要努力学习。 2. 下列语句是真命题为( )． A. 1+2=5当且仅当2是偶数 B. 如果1+2=3，则2是奇数 C. 如果1+2=5，则2是奇数 D. 你上网了吗 3. 设命题公式)(r q p ∧→?,则使公式取真值为1的p ，q ，r 赋值分别是 ( ) 0,0,1)D (0 ,1,0)C (1 ,0,0)B (0 ,0,0)A ( 4. 命题公式q q p →∨ )(为 ( ) (A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式 5. 设p:我将去市里,q ：我有时间． 命题“我将去市里，仅当我有时间时”符号化为为( ) q p q p q p p q ?∨??→→)D ()C ()B ()A (6．设P ：我听课,Q ：我看小说. “我不能一边听课，一边看小说”的符号为（ ） A. Q P ?→ ； B. Q P →?； C. P Q ?∧? ； D. )(Q P ∧? 二、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则32。 （3）只有2<1，才有32。 （4）除非2<1，才有32。 （5）除非2<1，否则32。
离散数学作业答案
离散数学作业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 去工作，
《离散数学》题库及答案
《离散数学》题库与答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( A ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别） 2、下列公式中哪些是永真式？( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4）可用蕴含等值式证明 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式 4、公式x((A(x)B(y，x))z C(y，z))D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z（考察定义在公式x A和x A中，称x为指导变元，A为量词的辖域。在x A和x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y，x)和z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元） 5、判断下列语句是不是命题。若是，给出命题的真值。( )
(1)北京是中华人民共和国的首都。(2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？(4) 若7+8＞18，则三角形有4条边。 (5) 前进！(6) 给我一杯水吧！ 答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是（命题必须满足是陈述句，不能是疑问句或者祈使句。） 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死（命题的否定就是把命题前提中的量词“换成存在，换成”，然后将命题的结论否定，“且变或或变且”） 7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校(2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1）P ?（注意“只有……才……”和“除非……就……”两者都是一个 Q→ 形式的）（2）Q P→ ? P? ?（4）Q P? →（3）Q 8、设个体域为整数集，则下列公式的意义是( )。 (1) x y(x+y=0) (2) y x(x+y=0) 答：（1）对任一整数x存在整数y满足x+y=0 （2）存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值： (1) x y (xy=y) ( ) (2) x y(x+y=y) ( ) (3) x y(x+y=x) ( ) (4) x y(y=2x) ( ) 答：（1）F (反证法：假若存在，则（x- 1）*y=0 对所有的x都成立，显然这个与前提条件相矛盾) （2）F （同理）（3）F （同理）（4）T（对任一整数x存在整数y满足条件y=2x 很明显是正确的）
2013年4月考试离散数学第二次作业
2013年4月考试离散数学第二次作业 一、单项选择题（本大题共50分，共 25 小题，每小题 2 分） 1. 下列语句中为命题的是（） A. 暮春三月，江南草长. B. 这是多么可爱的风景啊！ C. 大家想做什么，就做什么，行吗？ D. 请勿践踏草地！ 2. 2.设G是n个顶点的无向简单图，则下列说法不正确的是（） A. 若G是树，则其边数等于n-1 B. 若G是欧拉图，则G中必有割边 C. 若G中有欧拉路，则G是连通图，且有零个或两个奇度数顶点 D. 若G中任意一对顶点的度数之和大于等于n-1，则G中有汉密尔顿路 3. 集合|A|=3，|B|=2，则A B上不同的函数个数为（）。 A. 3+2个 B. 32个 C. 2*3个 D. 23个 4. 设A-B=φ，则以下正确的是（）。 A. A＝B B. A?B C. B?A D. 以上都不对 5. 设R为实数集，函数f：R→R，f(x)=2x，则f是（） A. 满射函数 B. 入射函数 C. 双射函数 D. 非入射非满射 6. 设B={a,b,c},C={1,2,3,4}，以下哪个关系是从B到C的单射函数？（） A. f={<1,8>,<3,9>,<4,10>,<2,6>,<5,7>} B. f={<1,7>,<2,6>,<4,8>,<1,9>,<5,10>} C. f={<1,7>,<2,7>,<4,9>,<3,8>} D. f={<1,10>,<5,9>,<3,6>,<4,6>,<2,8>} E. f={<1,7>,<5,10>,<2,6>,<4,8>,<3,9>} 7. 下述*运算为实数集上的运算，其中可交换且可结合的运算是（）。 A. a*b=a+2b B. a*b=a+b-ab C. a*b=a D. a*b=|a+b| 8. 在下列命题中，为真的命题是（） A. 汉密顿图一定是欧拉图 B. 无向完全图都是欧拉图 C. 度数为奇数的结点个数为0个或2个的连通无向图G可以一笔画出 D. 有割点的连通图是汉密顿图 9. 设p:小李努力学习，q:小李取得好成绩，命题“只有小李努力学习，他才能取得好成绩”的符号化形式为（）。 A. B. C.
离散数学 第2章 习题解答
第2章习题解答 2.1 本题没有给出个体域,因而使用全总个体域. (1) 令x (是鸟 x F:) (会飞翔. G:) x x 命题符号化为 x F ?. G x→ ) ( )) ( (x (2)令x x (为人. F:) (爱吃糖 G:) x x 命题符号化为 x F x→ G ?? )) ( ) ( (x 或者 F x? x ∧ ? ) )) ( ( (x G (3)令x x (为人. F:) G:) (爱看小说. x x 命题符号化为 x F ?. G x∧ (x ( )) ( ) (4) x (为人. x F:) (爱看电视. G:) x x 命题符号化为 F x? ∧ ??. x G ( ) ( )) (x 分析 1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个体域时，往往要使用特性谓词。（1）-（4）中的) F都是特性谓词。 (x 2°初学者经常犯的错误是，将类似于（1）中的命题符号化为 F x ? G x∧ ( )) ( ) (x
即用合取联结词取代蕴含联结词，这是万万不可的。将（1）中命题叙述得更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。”因而符号化应该使用联结词→而不能使用∧。若使用∧，使（1）中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。”这显然改变了原命题的意义。 3° （2）与（4）中两种符号化公式是等值的，请读者正确的使用量词否定等值式，证明（2），（4）中两公式各为等值的。 2.2 (1)d (a),(b),(c)中均符号化为 )(x xF ? 其中,12)1(:)(22++=+x x x x F 此命题在)(),(),(c b a 中均为真命题。 （2） 在)(),(),(c b a 中均符号化为 )(x xG ? 其中02:)(=+x x G ，此命题在（a ）中为假命题，在(b)(c)中均为真命题。 （3）在)(),(),(c b a 中均符号化为 )(x xH ? 其中.15:)(=x x H 此命题在)(),(b a 中均为假命题，在(c)中为真命题。 分析 1°命题的真值与个体域有关。 2° 有的命题在不同个体域中，符号化的形式不同，考虑命题 “人都呼吸”。 在个体域为人类集合时，应符号化为 )(x xF ? 这里，x x F :)(呼吸，没有引入特性谓词。 在个体域为全总个体域时，应符号化为 ))()((x G x F x →? 这里，x x F :)(为人，且)(x F 为特性谓词。x x G :)(呼吸。 2．3 因题目中未给出个体域，因而应采用全总个体域。
大学本科高等数学《离散数学》试题及答案
本科高等数学离散数学试题及答案 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________，_____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 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 = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。
中石油北京19春《离散数学》第二次在线作业
------------------------------------------------------------------------------------------------------------------------------ 1.（2.5分）代数系统是指由集合及其上的一元或二元运算符组成的系统 正确 错误 正确答案： 2.（2.5分）设< L,*1,*2> 是代数系统，其中是*1,*2二元运算符，如果*1,*2都满足交换律、结合律，并且*1和*2满足吸收律，则称< L,*1,*2> 是格 正确 错误 正确答案： 3.（2.5分）对实数的普通加法和乘法，0是加法的幂等元，1是乘法的幂等元 正确 错误 正确答案： 4.（2.5分）零元是不可逆的 正确 错误 正确答案： 5.（2.5分）群中每个元素的逆元都是惟一的 正确 错误 正确答案： 6.（2.5分）设a,b,c是阿贝尔群< G,+> 的元素，则-(a+b+c)=(-a)+( -b)+( -c) 正确 错误 正确答案： 7.（2.5分） < {0,1,2,3,4},MAX,MIN> 是格 正确 错误 正确答案： 8.（2.5分）一个图的哈密尔顿路是一条通过图中所有结点一次且恰好一次的路 正确 错误 正确答案： 9.（2.5分）在有向图中，结点v的出度deg+(v)表示以v为起点的边的条数，入度deg-(v)表示以v为终点的边的条数 正确 错误 正确答案： 10.（2.5分）一个图的欧拉回路是一条通过图中所有边一次且恰好一次的回路 正确 错误 正确答案： 11.（2.5分）不含回路的连通图是树
电大 离散数学作业7答案
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1或T ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如 果他生病或出差了，我就同意他不参加学习”符号化的结果为 （P ∨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 },那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) ∨A(b)) ∨((B(a) ∧B(b)) ． 6．设个体域D ＝{1, 2, 3}，A (x )为“x 大于3”，则谓词公式(?x )A (x ) 的真值为 0(F) ． 7．谓词命题公式(?x )((A (x )∧B (x )) ∨C (y ))中的自由变元为 y ． 8．谓词命题公式(?x )(P (x ) →Q (x ) ∨R (x ，y ))中的约束变元为 x ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 设P ：今天是晴天。 姓 名： 学 号： 得 分： 教师签名：
中国石油大学大学《离散数学》期末复习题及答案
《离散数学》期末复习题 一、填空题（每空2分，共20分） 1、集合A上的偏序关系的三个性质是、 和。 2、一个集合的幂集是指。 3、集合A={b,c}，B={a,b,c,d,e}，则A?B= 。 4、集合A={1,2,3,4}，B={1,3,5,7,9}，则A?B= 。 5、若A是2元集合, 则2A有个元素。 6、集合A={1,2,3｝，A上的二元运算定义为：a* b = a和b两者的最大值，则 2*3= 。 7、设A={a, b,c,d }, 则∣A∣= 。 8、对实数的普通加法和乘法，是加法的幂等元， 是乘法的幂等元。 9、设a,b,c是阿贝尔群
19、代数系统是指由及其上的或 组成的系统。 20、设
离散数学作业 (2)
离散数学作业布置 第1次作业（P15） 1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 解：（1）p∨(q∧r)=0∨(0∧1)=0 （2）（p?r）∧(﹁q∨s)=（0?1）∧(1∨1)=0∧1 =0 （3）（﹁p∧﹁q∧r）?(p∧q∧﹁r)=（1∧1∧1）? (0∧0∧0)=0 (4)（r∧s）→(p∧q)=（0∧1）→(1∧0)=0→0=1 1.17 判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2 也是无理数。另外只有6能被2整除，6才能被4整除。” 解：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。 1.19 用真值表判断下列公式的类型： （4）(p→q) →(﹁q→﹁p) （5）(p∧r) ? (﹁p∧﹁q) （6）((p→q) ∧(q→r)) →(p→r) 解：（4） p q p→q q p q→p (p→q)→( q→p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式，最后一列全为1 （5）公式类型为可满足式（方法如上例），最后一列至少有一个1 （6）公式类型为永真式（方法如上例，最后一列全为1）。 第2次作业（P38） 2.3 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ﹁(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 解：(1) ﹁(p∧q→q) ?﹁(﹁(p∧q) ∨q) ?(p∧q) ∧﹁q?p∧(q ∧﹁q) ? p∧0 ?0 所以公式类型为矛盾式 (2)（p→(p∨q)）∨(p→r) ? (﹁p∨(p∨q))∨(﹁p∨r) ?﹁p∨p∨q∨r?1 所以公式类型为永真式 (3) (p∨q) → (p∧r) ?￢(p∨q) ∨ (p∧r) ? (￢p∧￢q) ∨(p∧r) 易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111
离散数学 第2章 习题解答
习题 2.1 1．将下列命题符号化。 (1) 4不是奇数。 解：设A(x)：x是奇数。a：4。 “4不是奇数。”符号化为：?A(a) (2) 2是偶数且是质数。 解：设A(x)：x是偶数。B(x)：x是质数。a：2。 “2是偶数且是质数。”符号化为：A(a)∧B(a) (3) 老王是山东人或河北人。 解：设A(x)：x是山东人。B(x)：x是河北人。a：老王。 “老王是山东人或河北人。”符号化为：A(a)∨B(a) (4) 2与3都是偶数。 解：设A(x)：x是偶数。a：2，b：3。 “2与3都是偶数。”符号化为：A(a)∧A(b) (5) 5大于3。 解：设G(x,y)：x大于y。a：5。b：3。 “5大于3。”符号化为：G(a,b) (6) 若m是奇数，则2m不是奇数。 解：设A(x)：x是奇数。a：m。b：2m。 “若m是奇数，则2m不是奇数。”符号化为：A(a)→A(b) (7) 直线A平行于直线B当且仅当直线A不相交于直线B。 解：设C(x,y)：直线x平行于直线y。设D(x,y)：直线x相交于直线y。a：直线A。b：直线B。 “直线A平行于直线B当且仅当直线A不相交于直线B。”符号化为：C(a,b)??D(x,y) (8) 小王既聪明又用功，但身体不好。 解：设A(x)：x聪明。B(x)：x用功。C(x)：x身体好。a：小王。 “小王既聪明又用功，但身体不好。”符号化为：A(a)∧B(a)∧?C(a) (9) 秦岭隔开了渭水和汉水。 解：设A(x,y,z)：x隔开了y和z。a：秦岭。b：渭水。c：汉水。 “秦岭隔开了渭水和汉水。”符号化为：A(a,b,c) (10) 除非小李是东北人，否则她一定怕冷。 解：设A(x)：x是东北人。B(x)：x怕冷。a：小李。 “除非小李是东北人，否则她一定怕冷。”符号化为：B(a)→?A(a) 2．将下列命题符号化。并讨论它们的真值。 (1) 有些实数是有理数。 解：设R(x)：x是实数。Q(x)：x是有理数。 “有些实数是有理数。”符号化为：(?x)(R(x)∧Q(x))
山东大学离散数学题库及答案
《离散数学》题库答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q →P (2)?Q=>P →Q (3)P=>P →Q (4)?P ∧(P ∨Q)=>?P 答：（1），（4） 2、下列公式中哪些是永真式？( ) (1)(┐P ∧Q)→(Q →?R) (2)P →(Q →Q) (3)(P ∧Q)→P (4)P →(P ∨Q) 答：（2），（3），（4） 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P ∧Q (2) P ∧Q=>P (3) P ∧Q=>P ∨Q (4)P ∧(P →Q)=>Q (5) ?(P →Q)=>P (6) ?P ∧(P ∨Q)=>?P 答：（2），（3），（4），（5），（6） 4、公式 x((A(x) B(y ，x)) z C(y ，z))D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1） 是，T （2） 是，F （3） 不是 （4） 是，T （5） 不是 （6） 不是 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死 7、设P ：我生病，Q ：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校 答：（1） P Q →? （2） Q P ?→ （3） Q P ?? （4）Q P →? 8、设个体域为整数集，则下列公式的意义是( )。 (1) x y(x+y=0) (2) y x(x+y=0) 答：（1）对任一整数x 存在整数 y 满足x+y=0（2）存在整数y 对任一整数x 满足x+y=0 9、设全体域D 是正整数集合，确定下列命题的真值： (1) x y (xy=y) ( ) (2) x y(x+y=y) ( ) (3) x y(x+y=x) ( ) (4) x y(y=2x) ( ) 答：（1） F （2） F （3）F （4）T 10、设谓词P(x)：x 是奇数，Q(x)：x 是偶数，谓词公式 x(P(x)Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答：（1） 11、命题“2是偶数或-3是负数”的否定是（ ）。 答：2不是偶数且-3不是负数。 12、永真式的否定是（ ） (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 答：（2） 13、公式(?P ∧Q)∨(?P ∧?Q)化简为（ ），公式 Q →(P ∨(P ∧Q))可化简为（ ）。 答：?P ，Q →P
电大离散数学作业答案作业答案
离散数学作业5 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月5日前完成并上交任课教师（不收电子稿）。并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ． 2．设给定图G (如右由图所示)，则图G 的点割集是 {}f {}c e ,． 3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点 度数之和 等于边数的两倍． 4．无向图G 存在欧拉回路，当且仅当G 连通且 不含奇数度结点 ． 5．设G=
离散数学答案第二章习题解答
习题与解答 1. 将下列命题符号化： (1) 所有的火车都比某些汽车快。 (2) 任何金属都可以溶解在某种液体中。 (3) 至少有一种金属可以溶解在所有液体中。 (4) 每个人都有自己喜欢的职业。 (5) 有些职业是所有的人都喜欢的。 解 (1) 取论域为所有交通工具的集合。令 x x T :)(是火车， x x C :)(是汽车， x y x F :),(比y 跑得快。 “所有的火车都比某些汽车快”可以符号化为))),()(()((y x F y C y x T x ∧?→?。 (2) 取论域为所有物质的集合。令 x x M :)(是金属， x x L :)(是液体， x y x D :),(可以溶解在y 中。 “任何金属都可以溶解在某种液体中” 可以符号化为))),()(()((y x D y L y x M x ∧?→?。 (3) 论域和谓词与(2)同。“至少有一种金属可以溶解在所有液体中” 可以符号化为))),()(()((y x D y L y x M x →?∧?。 (4) 取论域为所有事物的集合。令 x x M :)(是人， x x J :)(是职业， x y x L :),(喜欢y 。 “每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧?→? (5)论域和谓词与(4)同。“有些职业是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →?∧?。 2. 取论域为正整数集，用函数+（加法），?（乘法）和谓词<，=将下列命题符号化： (1) 没有既是奇数，又是偶数的正整数。 (2) 任何两个正整数都有最小公倍数。 (3) 没有最大的素数。 (4) 并非所有的素数都不是偶数。 解 先引进一些谓词如下： x y x D :),(能被y 整除，),(y x D 可表示为)(x y v v =??。 x x J :)(是奇数，)(x J 可表示为)2(x v v =???。 x x E :)(是偶数，)(x E 可表示为)2(x v v =??。 x x P :)(是素数，)(x P 可表示为)1)(()1(x u u x u v v u x =∨=?=???∧=?。
- 离散数学第2章习题解答
- 离散数学 第2章 习题解答
- 离散数学左孝陵版第二章答案
- 离散数学(第二版)最全课后习题答案详解
- 离散数学课后习题答案(第三章)
- 离散数学屈婉玲版第二章习题答案
- 离散数学 第二章 谓词逻辑 习题课
- 最新离散数学-第二章命题逻辑等值演算习题及答案
- 离散数学答案第二章习题解答
- 离散数学课后习题答案(第二章)
- 离散数学课后习题答案_屈婉玲(高等教育出版社)
- 自考离散数学第二章答案
- 离散数学第2章习题解答
- 离散数学章练习题及答案
- 离散数学答案第二章习题解答
- 离散数学答案(尹宝林版)第二章习题解答
- 离散数学答案(尹宝林版)第二章习题解答
- 离散数学第2章答案(刘玉珍 刘永梅)
- 离散数学-第2章-习题解答
- 离散数学 第2章 习题解答