《随机过程》第4章离散部分习题及参考答案
湖南大学本科课程《随机过程》第4章习题及参考答案
主讲教师：何松华 教授
30．设X(n)为均值为0、方差为σ2的离散白噪声，通过一个单位脉冲响应为h(n)的线性时不变离散时间线性系统，Y(n)为其输出，试证：
2[()()](0)E X n Y n h σ=，22
20
()Y n h n σσ
∞
==∑
证：根据离散白噪声性质，2
2
0()[()()]()0
X m R m E X n m X n m m σσδ?==+==?
≠?
()()()()()m Y n X n h n X n m h m ∞
==?=-∑
220
[()()]{()()()][()()]()
()()()()(0)
m m X m m E X n Y n E X n X n m h m E X n X n m h m R m h m m h m h σδσ∞∞
==∞∞
===-=-===∑∑∑∑
1212122
2
11220
2
1
2
1
2
212100
00
[()]{()()()()]
[()()]()()[()()]()
Y m m m m m m E Y n E X n m h m X n m h m E X n m X n m h m h m m m h m h m σσ
δ∞∞
==∞∞∞∞
======--=
--=-∑∑∑∑∑∑
(对于求和区间内的每个m 1,在m 2的区间内存在唯一的m 2=m 1,使得21()0m m δ-≠)
12
2
2110
()()()m n h m h m h n σ
σ
∞
∞
====∑∑(求和变量置换) 31．均值为0、方差为σ2的离散白噪声X(n)通过单位脉冲响应分别为h 1(n)=a n u(n)以及h 2(n)=b n u(n)的级联系统(|a|<1,|b|<1)，输出为W(n)，求σW 2。 解：该级联系统的单位脉冲响应为
12121
1
1
00()()()()()()()
1(/)()
1/n m m m m m
n n n n
n
n m m n n
m m h n h n h n h n m h m a u n m b u m b b a a
b
a b a a u n a b a a b
∞
∞
-=-∞=-∞+++-===?=
-=---??
====
?--??
∑
∑∑∑
参照题30的结果可以得到
2
112222221121
2000222222222()[()2()()]()2(1)[]()111(1)(1)(1)
n n n n n W n n n a b h n a ab b a b a b a ab b ab a b a ab b a b ab σσσσσσ++∞
∞
∞+++===??-===-+??--??+=-+=-------∑∑∑
32．设离散系统的单位脉冲响应为()() (1)n h n na u n a -=>，输入为自相关函数为
2()()X X R m m σδ=的白噪声，求系统输出Y(n)的自相关函数和功率谱密度。 解：根据离散时间随机过程通过离散时间线性系统理论，有
122
1
12121200
2122100
()()()()
[()]Y X
m m m m
X
m m R m R
m m m h m h m m m m m a m a σ
δ∞∞
==∞
∞
--===
-+=
-+∑∑∑∑
注：对比因果连续系统的输出过程与输入过程相关函数的关系
12120
()()()()Y X R R h h ττττττ∞
∞
=-+?
?
不妨设0m ≥，则只有当m 1≥m 时，求和区间内存在脉冲点21m m m =-，因此
11
11111()211222211()()[]
m m m Y X m m m m m X m m
m m
R m m m m a a a m a m m a σ
σ∞
---=∞
∞
--===
-=-∑∑∑
令：1
1
1121
1
()m m m m
m m
x m a
m q
∞
∞
-===
=
∑∑，则
111
2
(1){}{}1(1)
m m m m m m d d q mq m q x q q q dq dq q q +∞=--=?=?=--∑ 令：1
1112
221
1
()
m m m m
m m
y m
a m
q ∞
∞
-===
=
∑∑，则
1
111222122
3
(1){}{}
(1)(221)(21)(1)m m m m m m m m d d mq m q y q m q q dq dq q m q m m q m m q
q +∞=++--=?=?----+-+=
-∑
2212221
2
32
1
2
42
223
23
(221)(21)(1)()[](1)(1)(1)(1)(1)(1)
(1)(1)m m m m m m
Y X m m m
m
X X m q m m q m m q m q m m q R m a q q m q
m q
a m a m a a q a σσσ+++++----+-+--=---+--+--==--
考虑到相关函数的偶函数特性，得到：
422||
23
(||1)(||1)
()(1)
m Y X a m a m R m a
a σ-+--=- 下面求功率谱密度函数，采用频域法。
-100
22
0()() ()
1{}{}1(1)()j n
n j n
n j n n n n j j n j n j j j n H j h n e
na e
np e p a d d pe ae p p e p dp dp pe pe a e ωωωω
ω
ωωωωω∞
∞
∞
----===--∞
----======?
=?==---∑∑∑∑
2
2222222
22
22
()|()|()()(|cos()sin()|)[12cos()]j X Y X X j X a ae G H j G a e a j a
a a ω
ωσωωωσωωσω--===
--+=
+-
可以通过相关函数的傅立叶变换进行验证。典型双边序列的离散时间傅立叶变换对：
2||
||2
1
(||1)12cos()m m m a a
a a a a ω∞
--=-∞
-?=>+-∑ 222||
222
1
2(1)cos()4||12cos()[12cos()]
m d a a a a m a
a da a a a a ωωω-??-+-?-?= ?+-+-?? 242242422
||
||
||232323
2422422222322
23222
22
()()(||1)(||1)()||(1)(1)(1)()()2(1)cos()41
(1)[12cos()](1)12cos()
[12cos()]m m m X X Y X X X X a a a a a m a m R m a
m a a
a a a a a a a a a a a a a a a a a a a a σσσσσωωωσω----++--==+----++--?+-+--+-=
+-
33．序列X(n)和Y(n)满足差分方程
()()()Y n X n a X n a =+--
其中a 为整常数，试用X(n)的相关函数表示Y(n)的相关函数。 解：
1212112212121212(,)[()()]{[()()][()()]}(,)(,)(,)(,)
Y X X X X R n n E Y n Y n E X n a X n a X n a X n a R n a n a R n a n a R n a n a R n a n a ==+--+--=++--+-+-+--
当X(n)为平稳随机过程时，则Y(n)也为平稳的，且有
()2()(2)(2)Y X X X R m R m R m a R m a =---+
34．实值一阶自回归过程X(n)满足差分方程
1()(1)()X n a X n V n +-=
其中a 1为常数，V(n)为方差为σ2的白噪声，输入从n=0开始，(1)0X -=。
(1)证明：若V(n)均值非零，则X(n)非平稳；(2)证明：若V(n)均值为零、|a 1|<1，则当n 足够大时，2221[()]/(1)V E X n a σ=-；(3)若V(n)均值为零，|a 1|<1，求X(n)的自相关函数的平稳解。
证：(1) 采用Wold 分解方法
2111231111
11100
()()(1)()(1)(2)()(1)(2)(3)...()()()
(1)()()
n
n
m
n m m m X n V n a X n V n a V n a X n V n a V n a V n a X n a V n m a X a V n m +===--=--+-=--+---==--+--=--∑∑
1111001
[1()]
[()][()()]()1n n
n
m
m
V V m m m a E X n E a V n m a m a +==--=--=-=
+∑∑ 显然，若V(n)均值非零，则X(n)的均值函数不是一个常数，是非平稳的。 (2) 若V(n)均值为零，则X(n)的均值为常数0，则
2
10[()][()][()()]n
m m E X n Var X n Var a V n m ===--∑
根据相互独立随机变量的和的方差等于方差之和的性质，得到
2
2110
2
2(1)
221120
1
[()][()()]()[()]
[1]
()1n n
m
m m m n n
m V V m E X n Var a V n m a Var V n m a
a a
σσ==+==--=---==
-∑∑∑
显然，若输入从n=0开始，则即使在V(n)均值为零的情况下，方差也不为常数，X(n)是非平稳的，当|a 1|<1且n 足够大时，渐近平稳，2
2
21
[()]1V E X n a
σ=-。
(3) 不妨假设时刻差m ≥0，则根据Wold 分解得到
1
2121
2121
21211120
1
1120021
11200
(,)[()()]{[()()][()()]}
()
()[()()]()
()()
n m
n
m m X m m n m
n
m m m m n m
n
m m V m m R n m n E X n m X n E a V n m m a V n m a a E V n m m V n m a a m m m σδ+==+==+==+=+=-+---=--+--=
---+∑∑∑∑∑∑
根据求和区间内的脉冲点21m m m =-的存在条件：1n m m m +≥≥，得到：
1
1111()
2221
111
22(1)21
1121
(,)()
()()
()
[1]
()1n m
n m
m m m m m
X V V m m m m
m n m
V R n m n a a a a
a
a a a
σσσ++--==+-+=--=--=--∑∑
当n 足够大时，输出过程是渐近平稳的，自相关函数的平稳解为：
212
1()()1m
V X a R m a σ-=
-
35．考察如下的二阶自回归过程X(n)
12()(1)(2)()X n a X n a X n V n =----+
(1)若已知随机过程的相关函数值(0)X R 、(1)X R 、(2)X R ，试写出用于计算系数a 1,a 2以及零均值白色噪声()V n 的方差2V σ的Yule-Walker 方程；(2)反过来，若已知a 1= -1,a 2=0.5,
20.5V σ=，求(0)X R 、(1)X R 、(2)X R 的值；(3)求相关函数的通解。
解：(1)按题意为求平稳解。根据回归方程(离散时间因果系统的差分方程)可知：对于任意的n ，()X n 只与V(n)以及V(n-m) (m>0)有关，即系统的输出只与当前时刻以及过去时刻的输入有关，则有：
212[()()]{[(1)(2)()]()}[()()]V E X n V n E a X n a X n V n V n E V n V n σ=----+==
((1)X n -、(2)X n -与V (n)无关)
换成另外一种写法，根据12()()(1)(2)V n X n a X n a X n =+-+-得到
212[()()]{()[()(1)(2)]}V E X n V n E X n X n a X n a X n σ=+-+-=
即：212(0)(1)(2)X X X V R a R a R σ++= (1)
差分方程两边分别乘X(n-1)、取数学期望，并利用V(n)与X(n-1)的不相关性以及相关函数的偶函数特性得到：
12(1)(0)(1)0X X X R a R a R ++= (2)
同理，差分方程两边分别乘X(n-1)、取数学期望
12(2)(1)(0)0X X X R a R a R ++= (3)
(1)(2)(3)式联立，即得到二阶AR 模型的Yule-Walker 方程(三个方程可以求解三个未知数2V σ,a 1,a 2)
2
12(0)(1)(2)1(1)(0)(1)0(2)(1)(0)0X X X V X X X X X X R R R R R R a R R R a σ????????????=?
?????????????????
(2)Yule-Walker 方程可以写成如下的等效形式
2121
22
11
(0)10(1)01(2)0X V X X a a R a a
R a a R σ??
??????????+=?
?????????????????
代入a 1,a 2, 2V σ的具体数值，得到
1
(0)110.50.5 1.2(1)1 1.5000.8(2)0.51100.2X X X R R R --????????
????????=-=????????????????-????????
(3) 当m>2时，差分方程两边分别乘X(n-m )、取数学期望,可得：
()(1)0.5(2)0X X X R m R m R m --+-=
上述差分方程的特征方程：1210.50z z ---+=，两个根为0.50.5j ±(
，相角为
4
π
)，根据差分方程理论，则相关函数的通解为：
() [cos()sin()] (2)44m
X R m A m B m m p ππ=+>= 代入(3)(2)0.5(1)0.2X X X R R R =-=-、(4)(3)0.5(2)0.3X X X R R R =-=-，求得： 1.2A =，
0.4B =，于是
()[1.2cos()+0.4sin()] (2)44m
X R m m m m ππ=> 显然R X (0)=1.2、R X (1)=0.8、R X (2)=0.2也满足上式；考虑到相关函数的实、偶函数特性以及m<0的情况，得：
||
()[1.2cos(||)+0.4sin(||)] (-)44m X R m m m m ππ=∞<<∞ 36．察如下的二阶自回归过程X(n)
12()(1)(2)()X n b X n b X n V n =---+
零均值白色噪声()V n 的方差为2V σ
，1|2b <；求：(1)X(n)的功率谱密度；(2)根据Wold 分解求X(n)的自相关函数；(3)求Yule-Walker 方程 解：(1)方程两边取离散时间傅立叶变换并利用其移位特性，得到
212()()()()j j j j j j X e b e X e b e X e V e ωωωωωω--=-+
则系统的传递函数为：
212()1
()()1j j j j j X e H e V e b e b e
ωω
ωωω
--==-+ 根据离散时间随机过程通过离散时间线性系统理论，有
2
2
22
122
2
12122
2212122
2212122()()|()||1||[1cos()cos(2)][sins()sin(2)]|[1cos()cos(2)][sins()sin(2)][12(1)cos()2cos(2)
j V X V j j V V
V G G H e b e b e b b j b b b b b b b b b b b ωωωσωωσωωωωσωωωωσωω--==-+=-++-=-++-=
+++--
(2) 同理，自回归方程两边取Z 变换，得到
12111212()()
()1(1)((1))
V z V z X z b z b z z z z z ----=
=
-+-- 其中，z 1,z 2为系统特征方程121210b z b z ---+=的根
1z =
，2z =，根据题意，1,2||1z <，系统稳定。 作部分分式分解以及级数展开，得到
122111211221
()()11z z z X z V z z z z z z z z z --??=-??----?? 1112
1
2
12121
1120
12
()()()()()
1()()
i
i
i i i i i i z z X z z z V z z z
V z z z z z z
z z V z z z ∞
∞
--==∞
++-==
---=--∑∑∑
两边取逆Z 变换并根据z 变换的移位性质，得到
1
1120
121()()()i i i X n z z V n i z z ∞++==---∑ 1111
1212
0012121111
12122
00
1221111
12122
1211()[()()]()()()()1()()[()()]()()()()()i i j j X i j i i j j i j i i j j V j R m E X n m X n E z z V n m i z z V n j z z z z z z z z E V n m i V n j z z z z z z m i j z z σδ∞∞++++==∞∞
++++==++++=??=+=-+---??--??
=--+---=---+-∑∑∑∑00
i ∞∞
=∑∑ 不妨设m ≥0，则根据单位脉冲函数的求和性质得到
2
11111
212212222221111221221122122
222211
1
212121221222
121212
()()()()[()()]()()[()]()111i i i m i m V X i m
m i m i m m i
V i m
m
m m
m m m m V V R m z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z σσσσ∞
++-+-+=∞
-+-+-+-+=-+-+-+-+=---=+-+-=
+-+----=∑∑211
1222121212
[]()(1)11m m z z z z z z z z ++-----
考虑到相关函数的偶函数特性，得到：
2||1||1
1222
121212
()[]()(1)11m m V X z z R m z z z z z z σ++=----- (1) 参照题35的方法得到：
2
12(0)(1)(2)1(1)(0)(1)0(2)(1)(0)0X X X V X X X X X X R R R R R R b R R R b σ????????????-=?
?????????????????
37．考察如下的二阶MA 模型，输入X(n)的功率谱密度为2X σ，求Y(n)的自相关函数和功率谱密度。
12()()(1)(2)Y n X n a X n a X n =+-+-
解：
1212212111222122212()[()()]
{[()(1)(2)][()(1)(2)]}()(1)(2)(1)()(1) (2)(1)()
(2)(1)(1)(1Y X X X X X X X X X X X R m E Y n m Y n E X n m a X n m a X n m X n a X n a X n R m a R m a R m a R m a R m a a R m a R m a a R m a R m a R m a a R m =+=+++-++-+-+-=+++++-++++-+-+=-++-+22121222221212122)()(1)(1)(2)(2)(1)(1)(1)()(1)(1)(2)X X X a a R m a a R m a R m a m a a m a a m a a m a m δδδδδ+++++++=-++-++++++++
先考察m ≥0的情况，则(1)0m δ+=、(2)0m δ+=，于是
2221212()(2)(1)(1)(1)() (0)Y R m a m a a m a a m m δδδ=-++-+++≥
考虑到相关函数的偶函数特性，得到
2221212()(||2)(1)(||1)(1)()Y R m a m a a m a a m δδδ=-++-+++
根据差分方程得到系统的传递函数为
212()1j j j H e a e a e ωωω--=++
根据随机过程通过线性系统特性，得到
2222
122212122
2
2
1212222
12122()|()|()|1||[1cos()cos(2)][sin()sin(2)]|{[1cos()cos(2)][sin()sin(2)]}[12(1)cos()2cos(2)]j j j Y X X X X X G H e G a e a e a a j a a a a a a a a a a a ωωωωωσωωωωσωωωωσωωσ--==++=++++=++++=+++++
38、考察如下的ARMA 模型
()0.9(1)()0.2(1)X n X n V n V n --=--
其中V(n)为零均值、单位方差离散白色噪声，求X(n)的自相关函数。 解：方法1。显然该系统的Z 变换形式的传递函数为
1
1
10.2()10.9z H z z ---=-
根据离散时间随机过程通过线性系统理论，输出随机过程Y(n)的相关函数的Z 变换(Z 变换形式的功率谱)为
11
110.210.2()()()() (0.9<||1/0.9)10.910.9X V z z
G z H z H z G z z z z
-----==<--
作部分分式分解
1
() (0.9<||1/0.9)10.910.9X B C
G z A z z z
-=+
+<-- 根据恒等关系
111(10.9)(10.9)(10.9)(10.9)(10.2)(10.2)A z z B z C z z z -----+-+-=--
得到536171A =-
、574
171
B C == 110000
53657415741
()17117110.917110.9536574574536574574(0.9)(0.9)0.90.9171171171171171171X m m m m m m m m i i G z z z
z z z z -∞∞∞-∞
----=====-
++
--=-++=-++∑∑∑∑ 取逆Z 变换得到(第2项对应右边序列，第3项对应左边序列)
536574574()()0.9()0.9()171171171
m m
X R m m u m u m δ-=-
++- 05365745745742
(0)0.91711711711719
X R =-++=?+
当m>0时，574()0.9171
m
X R m =，考虑到相关函数的偶函数特性，得到： ||
2574()()0.9 (-)9171
m X R m m m δ=+∞<<∞
方法2：当m>1时，则X(n-m)与V(n),V(n-1)无关，差分方程两边同乘X(n-m)并取数学期望，得到
()0.9(1)0 (1)X X R m R m m --=>
该差分方程的解为：
1()0.9 (1)m X R m A m =?>
其中A 1由初始条件(2)X R 确定，考虑到
1110.210.20.210.2()10.910.90.910.9X z z z z
G z z z z z
------==?----
根据逆Z 变换关系及留数定理
111()()Res[()]2m m X X X R m z G z dz z G z j
π--=
=?
0.210.2(2)Res 0.910.9X z z R z z z --??
=???--??
(单位圆内只有1个极点z=0.9)
(0.90.2)(10.20.9)574
0.90.910.90.9190--?=
?=?-?
215740.90.9190A ?=?，574
171
A = 考虑到
0.210.2(0.90.2)(10.20.9)574574
(1)Res 0.90.910.910.90.9190171X z z R z z ----???=?=
==???---???
10.210.2(0)Res 0.910.9X z z R z z z ---??
=???--??(单位圆内有2个极点z=0.9,z=0)
(0.90.2)(10.20.9)100.210.205742
10.90.90.900.910.901719
--?--?=
?+?=+-?--?
综合得到
||2574()()0.9 (-)9171
m X R m m m δ=+∞<<∞
方法3：系统的传递函数为
1111
10.20.7()110.910.9z z H z z z -----==+--
取逆Z 变换得到系统的单位脉冲响应为
1()()0.70.9(1)n h n n u n δ-=+?-
根据离散时间随机过程通过线性系统理论
121212121200
1
11
2
1
12200
()()()()
()[()0.70.9
(1)][()0.70.9(1)]
X V
m m m m m m R m R
m m m h m h m m m m m u m m u m δδδ∞∞
==∞
∞
--===
-+=
-++?-+?-∑∑∑∑
先考虑m ≥0的情况，脉冲点21m m m =-的出现条件：1m m ≥
1111
11
111()[()0.70.9
(1)][()0.70.9(1)]m m m X m m
R m m u m m m u m m δδ∞
---==
+?--+?--∑
11111
2
1
10
2
1222
21
(0)[()0.70.9
(1)]0.968
1[0.70.9]1(0.7/0.9)10.919
m X m m m R m u m δ∞
-=∞
-==
+?-=+?=+=
-∑∑
对于m>0，有
1111111
11111
1
1
2(1)1
2
2
()0.70.9
[()0.70.9(1)]
0.70.90.70.90.70.90.9574
0.70.9
(0.7/0.9)0.9
0.910.9171
m m m X m m
m m m m m m m m m
m R m m m u m m δ∞
---=∞
----=++--=
??-+?--=?+
???=?+=?-∑∑
考虑到0682574
(0)0.9199171
X R =
=+?以及相关函数的偶函数特性，得到 ||
2574()()0.9 (-)9171
m X R m m m δ=+∞<<∞
方法4：根据推广的Yule-Walker 方程求解
()0.9(1)()0.2(1)X n X n V n V n --=--
根据V(n)的白色噪声特性、系统的因果特性以及输入输出的联合平稳特性，得到：
2[()()]{[()0.2(1)0.9(1)]()}[()]1E X n V n E V n V n X n V n E V n =--+-==
22[()(1)]{[()0.2(1)0.9(1)](1)}0.2[(1)]0.9[(1)(1)]0.2[()]0.9[()()]0.20.90.7
E X n V n E V n V n X n V n E V n E X n V n E V n E X n V n -=--+--=--+--=-+=-+=
差分方程两边分别同乘X(n)或X(n-1)，取数学期望并利用上述相关特性，得到一阶情况下的推广的Y-W 方程为：
(0)0.9(1)[()()]0.2[()(1)]10.20.70.86X X R R E X n V n E X n V n -=--=-?= (1)0.9(0)[(1)()]0.2[(1)(1)]00.210.2X X R R E X n V n E X n V n -=----=-?=-
以上两式联立求得：68(0)19X R =
、574(1)190
X R =。 对于m>1，差分方程两边同乘X(n-m)并取数学期望得到
()0.9(1)[()()]0.2[()(1)]00.200X X R m R m E X n m V n E X n m V n --=----=-?=
()0.9 (1)m X R m A m =?>
根据递推关系：2574(2)0.9(1)0.90.9190X X R R A ==?
=?，574
171
A = 考虑到0682574(0)0.9199171X R =
=+?，1574574(1)0.9190171X R ==?以及相关函数的偶函数特性，得到：||
2574()()0.9 (-)9171
m X R m m m δ=+
∞<<∞。
离散数学题库及答案
数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( A )。 (A) 您打算考硕士研究生不？ (B) 太阳系以外的星球上有生物。 (C) 离散数学就是计算机系的一门必修课。 (D) 雪就是黑色的。 ?命题公式P→(P∨?P)的类型就是( A ) (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A就是重言式,那么A的否定式就是( A ) A、矛盾式 B、重言式 C、可满足式 D、不能确定 ?以下命题公式中,为永假式的就是( C ) A、p→(p∨q∨r) B、(p→┐p)→┐p C、┐(q→q)∧p D、┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值就是( D ) A、 00,11 B、 00,01,11 C、10,11 D、 10 ?谓词公式) x xP∧ ?中,变元x就是 ( B ) R , ( x ) (y A、自由变元 B、既就是自由变元也就是约束变元 C、约束变元 D、既不就是自由变元也不就是约束变元 ?命题公式P→(Q∨?Q)的类型就是( A )。 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 ?设B不含变元x,) x x→ ?等值于( A ) A ) ( (B A、B (D、B x xA→ x ?) ( ( ?C、B x∧ A ?) (B、) ?) xA→ x ) ( A x (B x∨ ?下列语句中就是真命题的就是( D )。 A.您就是杰克不？ B.凡石头都可练成金。 C.如果2+2=4,那么雪就是黑的。 D.如果1+2=4,那么雪就是黑的。 ?从集合分类的角度瞧,命题公式可分为( B ) A、永真式、矛盾式 B、永真式、可满足式、矛盾式 C、可满足式、矛盾式 D、永真式、可满足式 ?命题公式﹁p∨﹁q等价于( D )。 A、﹁p∨q B、﹁(p∨q) C、﹁p∧q D、 p→﹁q ?一个公式在等价意义下,下面写法唯一的就是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ?下列含有命题p,q,r的公式中,就是主析取范式的就是( D )。
《离散数学》考试题库及答案(三)
《离散数学》考试题库及答案 一、 填空 10% （每小题 2分） 1、 若P ，Q 为二命题，Q P ?真值为1，当且仅当 。 2、 对公式),()),(),((y x xR z x zQ y x yP ?∨?∧?中自由变元进行代入的 公 式 为 。 3、 )) (()(x xG x xF ??∧?的 前 束 范 式为 。 4、 设x 是谓词合式公式A 的一个客体变元，A 的论域为D ，A （x ）关于y 的自由的， 则 被称为全称量词消去规则，记为US 。 5、 与非门的逻辑网络为 。 二、 选择 30% （每小题 3分） 1、 下列各符号串，不是合式公式的有（ ）。 A 、R Q P ?∧∧)(； B 、)()((S R Q P ∧→→； C 、R Q P ∧∨∨； D 、S R Q P ∨∧∨?))((。 2、 下列语句是命题的有（ ）。 A 、2是素数； B 、x+5 > 6； C 、地球外的星球上也有人； D 、这朵花多好看呀！。 3、 下列公式是重言式的有（ ）。 A 、)(Q P ??； B 、Q Q P →∧)(； C 、P P Q ∧→?)(； D 、P Q P ?→)( 4、 下列问题成立的有（ ）。 A 、 若C B C A ∨?∨，则B A ?； B 、若C B C A ∧?∧，则B A ?； C 、若B A ???，则B A ?； D 、若B A ?，则B A ???。 5、 命题逻辑演绎的CP 规则为（ ）。 A 、 在推演过程中可随便使用前提； B 、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果； C 、如果要演绎出的公式为C B →形式，那么将B 作为前提，设法演绎出C ；
离散数学作业答案
离散数学作业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、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统
二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。
离散数学习题
第一章习题 1.1判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题。（1）2是无理数。 （2）5能被2整除。 （3）现在开会吗？ （4）x+5>0 （5）这朵花真是好看！ （6）2是素数当且仅当三角形有三条边。 （7）雪是黑色的当且仅当太阳是从东方升起。 （8）2000年10月1日天气晴好。 （9）太阳系以外的星球上有生物。 （10）小李在宿舍里。 （11）全体起立。 （12）4是2的倍数或是3的倍数。 （13）4是偶数且是奇数。 （14）李明和王华是同学。 （15）蓝色和黄色可以调配成绿色。 1..2 将上题中的命题符号化，并讨论他们的真值。 1.3判断下列各命题的真值。 （1）若2+2=4，则3+3=6； （2）若2+2=4，则3+3≠6； （3）若2+2≠=4，则3+3=6； （4）若2+2≠=4，则3+3≠=6； （5）2+2=4，当且仅当3+3=6； （6）2+2=4，当且仅当3+3≠6； （7）2+2≠4，当且仅当3+3=6； （8）2+2≠4，当且仅当3+3≠6； 1.4将下列命题符号化，并讨论其真值。 （1）如果今天是1号，则明天是2号； （2）如果今天是1号，则明天是3号； 1.5将下列命题符号化。 （1）2是偶数不是素数； （2）小王不但聪明而且用功； （3）虽然天气冷。老王还是来了； （4）他一边吃饭，一边看电视； （5）如果天下大雨，他就乘公交汽车来； （6）只有天下大雨，他才乘公交汽车来； （7）除非天下大雨，否则他不乘公交汽车来； （8）不经一事，不长一智； 1.5设p,q的真值为0 ，r,s的真值为1，求下列命题公式的真值。（1）p∨(q∧r);
离散数学习题三 含答案
离散数学习题三 11、填充下面推理证明中没有写出的推理规则。 前提：p s r r q q ,,,p →∨?∨? 结论：s 证明：① p 前提引入 ②q ∨?p 前提引入 ③ q （①②析取三段论） ④r q ∨? 前提引入 ⑤ r （③④析取三段论） ⑥s r → 前提引入 ⑦ s （⑤⑥假言推理） 12、填充下面推理证明中没有写出的推理规则。 前提：s)(r q r),(q p →→→→ 结论：s q)(p →∧ 证明：①q)(p ∧ （附加前提） ② p （①化简规则） ③ q （①化简规则） ④r)(q p →→ 前提引入 ⑤r q → （②④假言推理） ⑥ r （③⑤假言推理） ⑦s)(r q →→ 前提引入 ⑧s)(r → （③⑦假言推理） ⑨ s （⑥⑧假言推理） 13、前提：s r ,q p q,q)p (→∨∧→? 结论1：r 结论2：s 结论3：s ∨r （1）证明从此前提出发，推出结论1，结论2，结论3的推理都是正确的。 （2）证明从此前提出发，推任何结论的推理都是正确的。 证明：（1）①r s))r (q)(p q)q)p (((→→∨∨∨∧→? 1r s))r (q)p (q)q)p ((?∨?∧∨?∧?∨?∨∨??
②s ∨ → ∨ → ? ((→ ∨ ∧ s)) p( q) r( q) q) (p ∧ ? ? ∨ ∨ ∧ ? ? ? ∨ ∨ ? q) r( q) ∨ s 1 p s)) p ( q) ((? ③s) ∨ ∨ → ∨ ?r → → ∧ (p q) s)) ((∨ ( r( q) q) p( ? ∧ ∨ ∧ ? ? ? ?r ∨ ∨ ? ∨ ∨ r( q) ∨ s 1 p s)) ((? p q) ( q) 即结论1，结论2，结论3的推理都是正确的。 （2）s) ∨ ∧ ∧ ∧ → (→ ? r( p( (p q) q) q) ∧ ? ∨ ? ∧ ? ∨ ∧ ∧ ∧ ? ? ? ∨ ? ∨ ∧ ∧ (∨ (p q) p( q) ( s) r s) q r p ( q) q) ( q) (p ∨ ? ∧ 0? ? ∨ ∧ s) (p r ( q) 即推任何结论的推理都是正确的。 14、在自然推理系统P中构造下面推理的证明： （1）前提：q → p， → (q r) p, r→ 结论：s 证明：①r) →前提引入 p→ (q ②p 前提引入 ③r) (q→①②假言推理 ④q 前提引入 ⑤r③④假言推理 r→⑤附加律 ⑥s 15、在自然推理系统P中用附加前提法证明下面的推理： 前提：q → ， →s p→ (q p, r) s→ 结论：r 证明： ①s 附加前提引入 ②p s前提引入 → ③p①②假言推理 ④r) →前提引入 p→ (q ⑤r q→③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 即根据附加前提证明法，推理正确。
离散数学例题整理
第一章 定律证明: (1) A?B=B?A (交换律) 证?x x∈A?B ? x∈A 或x∈B, 自然有x∈B 或x∈A ? x∈B?A 得证A?B?B?A. 同理可证B?A?A?B. (2) A?(B?C)=(A?B)?(A?C) (分配律) 证?x x∈A?(B?C) ? x∈A或(x∈B且x∈C ) ?(x∈A或x∈B)且(x∈A或x∈C) ?x∈(A?B)?(A?C) 得证A?(B?C)?(A?B)?(A?C). 类似可证(A?B)?(A?C)?A?(B?C). (3) A?E=E (零律) 证根据并的定义, 有E?A?E. 根据全集的定义, 又有A? E?E. (4) A?E=A (同一律) 证根据交的定义, 有A?E?A. 又, ?x x∈A, 根据全集E的定义, x∈E, 从而x∈A且x∈E, ?x∈A?E 得证A?A?E. 例4 证明A?(A?B)=A（吸收律） 证利用例3证明的4条等式证明 A?(A?B) = (A?E)?(A?B) (同一律) = A?(E?B) (分配律) = A?(B?E) (交换律) = A?E (零律) = A (同一律) 例5 证明(A-B)-C=(A-C)-(B-C) 证(A-C)-(B-C) = (A ?~C) ? ~(B ? ~C) (补交转换律) = (A ?~C) ? (~B ? ~~C) (德摩根律) = (A ?~C) ? (~B ? C) (双重否定律) = (A ?~C? ~B)?(A ?~C? C) (分配律) = (A ?~C? ~B)?(A ??) (矛盾律) = A ?~C? ~B (零律,同一律) = (A ?~B) ? ~C (交换律,结合律)
电大 离散数学作业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 ：今天是晴天。 姓 名： 学 号： 得 分： 教师签名：
离散数学试题及答案(1)
离散数学试题及答案 一、填空题 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变成完全图。
离散数学题目大汇总
离散数学试题一（A 卷答案） 一、（10分）证明(A ∨B )(P ∨Q )，P ，(B A )∨P A 。 二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4 种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。 三、（10分）指出下列推理中，在哪些步骤上有错误为什么给出正确的推理形式。 (1)x (P (x ) Q (x )) P (2)P (y )Q (y ) T (1)，US (3)xP (x ) P (4)P (y ) T (3)，ES (5)Q (y ) T (2)(4)，I (6)xQ (x ) T (5)，EG 四、（10分）设A ＝{a ，b ，c}，试给出A 上的一个二元关系R ，使其同时不满足自反性、反自反性、 五、（15分）设函数g ：A →B ，f ：B →C ， (1)若f o g 是满射，则f 是满射。 (2)若f o g 是单射，则g 是单射。 六、（15分）设R 是集合A 上的一个具有传递和自反性质的关系，T 是A 上的关系，使得T R 且R ，证明T 是一个等价关系。 七、（15分）若
离散数学复习题及标准答案
1. 写出命题公式 ﹁（P →（P ∨ Q)）的真值表。 答案： 2.证明 答案: 3. 证明以下蕴涵关系成立： 答案： ４. 写出下列式子的主析取范式: 答案： )()(Q P Q P Q P ?∧?∨∧??Q)P (Q)(P P)(Q P)P (Q)(Q Q)P (P)Q)P ((Q)Q)P (P) Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)()()(R P Q P ∨∧∧?
5． 构造下列推理的论证:p ∨q, ｐ→?r ， s →t, ?s →ｒ， ?t ? ｑ 答案: ①s →ｔ 前提 ②t 前提 ③ｓ ①②拒取式I12 ④s →ｒ 前提 ⑤ｒ ③④假言推理I １１ ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论Ｉ10 6. 用反证法证明:ｐ→(?(r ∧s ）→?q ）, p, ?s ? ?q ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??) )(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨
７. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F （ x )：ｘ是鱼 Ｗ（ x )：x 生活在水中 ))((W(x)F(x)x →? 8． 请将下列命题符号化: 存在着不是有理数的实数。 答案: 令 Q ( ｘ ):x 是有理数 R （ x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令Ｍ(ｘ)：x 是人 Ｃ（x):x 是聪明的 则上述命题符号化为 １０. 请将下列命题符号化： 对于所有的正实数x,y ，都有x+y ≥ｘ。 答案: 令P(x):x 是正实数 Ｓ（ｘ,y): x+y ≥x １１． 请将下列命题符号化： 每个人都要参加一些课外活动。 答案: 令P(x ）:x 是人 Q （ｙ）: y 是课外活动 S(ｘ,ｙ）:ｘ参加y ))) ()((())()((x C x M x x C x M x →??∧∧?)) ,()()((y x S y P x P y x →∧??))(),()((y Q y x S x P y x ∧→??
离散数学章练习题及答案
离散数学练习题 第一章 一．填空 1.公式) ∨ ? ∧的成真赋值为 01；10 ? p∧ ( (q ) p q 2.设p, r为真命题，q, s 为假命题，则复合命题) ? ? →的真值为 0 p→ ( q (s ) r 3.公式) ∨ ? p∧ q ?与共同的成真赋值为 01；10 ? ∧ p ( ) ) (q q p ( 4.设A为任意的公式，B为重言式，则B A∨的类型为重言式 5．设p, q均为命题，在不能同时为真条件下，p与q的排斥也可以写成p与q的相容或。 二．将下列命题符合化 1. 7不是无理数是不对的。 解：) ? ?，其中p: 7是无理数；或p，其中p: 7是无理数。 (p 2.小刘既不怕吃苦，又很爱钻研。 解：其中 ?p: 小刘怕吃苦，q：小刘很爱钻研 p∧ ,q 3.只有不怕困难，才能战胜困难。 解：p →，其中p: 怕困难，q: 战胜困难 q? 或q →，其中p: 怕困难， q: 战胜困难 p? 4.只要别人有困难，老王就帮助别人，除非困难解决了。 解：) → ?，其中p: 别人有困难，q:老王帮助别人，r: 困难解决了 p (q r→ 或：q ?) (，其中p:别人有困难，q: 老王帮助别人，r: 困难解决了r→ ∧ p 5.整数n是整数当且仅当n能被2整除。 解：q p?，其中p: 整数n是偶数，q: 整数n能被2整除 三、求复合命题的真值 P：2能整除5， q：旧金山是美国的首都， r：在中国一年分四季 1. )) p∧ → q ∨ r → ∧ ((q r ( ) ( ) p 2.r ?) → (( → (( ∨ ) ( )) p r p ∨ p q ? ∧ ? q∧ 解：p, q 为假命题，r为真命题 1.)) p∧ → q ∨的真值为0 r → ∧ ( ) ( ) ((q p r
离散数学复习题及答案
1. 写出命题公式 ﹁（P →（P ∨ Q ））的真值表。 答案： 2.证明 答案： 3. 证明以下蕴涵关系成立： 答案： 4. 写出下列式子的主析取范式： 答案： )()(Q P Q P Q P ?∧?∨∧??Q)P (Q)(P P) (Q P)P (Q)(Q Q)P (P) Q)P ((Q)Q)P (P)Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)()()(R P Q P ∨∧∧?
5. 构造下列推理的论证：p ∨q, p →?r, s →t, ?s →r, ?t ? q 答案： ①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →(?(r ∧s)→?q), p, ?s ? ?q ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??))(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨
7. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F( x )：x 是鱼 W( x )：x 生活在水中 ))((W(x)F(x)x →? 8. 请将下列命题符号化： 存在着不是有理数的实数。 答案： 令 Q ( x )：x 是有理数 R ( x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令M(x)：x 是人 C(x)：x 是聪明的 则上述命题符号化为 10. 请将下列命题符号化： 对于所有的正实数x,y ，都有x+y ≥x 。 答案： 令P(x):x 是正实数 S(x,y): x+y ≥x 11. 请将下列命题符号化： 每个人都要参加一些课外活动。 答案： 令P(x):x 是人 Q(y): y 是课外活动 S(x,y):x 参加y )))()((())()((x C x M x x C x M x →??∧∧?)),()()((y x S y P x P y x →∧??))(),()((y Q y x S x P y x ∧→??
离散数学作业答案完整版
离散数学作业答案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数 理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题 目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识 点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地 完成集合论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答 过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。并在03任务界 面下方点击“保存”和“交卷”按钮，完成并上交任课教师。 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)- A B P(B )={{3},{1,3},{2,3},{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 ，其中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.6设A 、7.设R 8.9.设集合 R 1?R 2 R 1210.11设A ∩13.14.设一阶逻辑公式G=?xP(x)??xQ(x)，则G 的前束范式是_______________________________. 16.设谓词的定义域为{a ,b },将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是__________________________________________________________________________. 17.设集合A ＝{1,2,3,4}，A 上的二元关系R ＝{(1,1),(1,2),(2,3)},S ＝{(1,3),(2,3),(3,2)}。则R ?S ＝_____________________________________________________, R 2＝______________________________________________________. 二、选择题
《离散数学》题库及答案
《离散数学》题库与答案 一、选择或填空 （数理逻辑部分） 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) 给我一杯水吧！
最新离散数学习题答案
离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是 p q ∧ （9）只有天下大雨，他才乘班车上班 解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p → （11）下雪路滑，他迟到了 解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r ∧→ 15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起. 求下列复合命题的真值： （4）()(())p q r p q r ∧∧???∨?→ 解：p=1，q=1，r=0， ()(110)1p q r ∧∧??∧∧??， (())((11)0)(00)1p q r ?∨?→??∨?→?→? ()(())111p q r p q r ∴∧∧???∨?→??? 19、用真值表判断下列公式的类型： （2）()p p q →?→? 解：列出公式的真值表，如下所示： 20、求下列公式的成真赋值：
（4）()p q q ?∨→ 解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是： ()10p q q ?∨??????00 p q ????? 所以公式的成真赋值有：01，10，11。 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）()()p q q r ?→∧∧ 解：原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧ ()()p q r p q r ??∧∧∨∧∧37m m ?∨，此即公式的主析取范式， 所以成真赋值为011，111。 6、求下列公式的主合取范式，并求成假赋值： （2）()()p q p r ∧∨?∨ 解：原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?，此即公式的主合取范式， 所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）()p q r ∧∨ 解：原式()(()())p q r r p p q q r ?∧∧?∨∨?∨∧?∨∧ ()()()()()()p q r p q r p q r p q r p q r p q r ?∧∧?∨∧∧∨?∧?∧∨?∧∧∨∧?∧∨∧∧ ()()()()()p q r p q r p q r p q r p q r ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ?∨∨∨∨，此即主析取范式。 主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，4M ，故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式：
离散数学作业7答案(数理逻辑部分)
离散数学数理逻辑部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分．作业应手工书写答题，字迹工整，解答题要有解答过程，完成后上交任课教师（不收电子稿）． 一、填空题 1．命题公式() →∨的真值是 1 ． P Q P 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},那么谓词公式) xA? ∨ x ?消去量词后的等值式为 yB ( ) (y (A(a)∨A(b))∨(B(a) ∧B(b))． 6．设个体域D＝{1, 2, 3}，A(x)为“x大于3”，则谓词公式(?x)A(x) 的真值为0 ． 7．谓词命题公式(?x)((A(x)∧B(x)) ∨C(y))中的自由变元为y ．8．谓词命题公式(?x)(P(x) →Q(x) ∨R(x，y))中的约束变元为x ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 解：
国开放大学离散数学本离散数学作业答案
国开放大学离散数学本离 散数学作业答案 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={