离散数学练习题1

1、下列句子是简单命题的是（ ）

A) 3是素数。 B) 2x+3<5

C) 张三跟李四是同学吗？ D) 我在说谎。 2、下列公式不是永真式的是（ ） ．．

A) ((p∧q))→p)∨r B) p→(p∨q∨r)

C) ┓(q→r) ∧r D) (p→q)→(┓q→┓p)

3、设命题公式G<=>┓(p→q)，H<=>p→(q →┓p)，则G与H的关系是( ) 。

A) G<=>H B) H→G C) H => G D) G => H

4、下列命题不为真的是（ ） ．

A) Φ ? Φ B) Φ∈Φ

C) {a,b}∈{a,b,c,{a,b}}} D) {a,b}?{a,b,c,{a,b}}

5、1到300之间（包含1 和1000）不能被3、5和7整除的数有（ ）个。

13、下列运算在指定集合上不符合交换律的是（）。

A) 复数C集合上的普通加法 B) n阶实矩阵上的乘法 C) 集合S的幂集上的∪ D) 集合S的幂集上的? 14、下列集合对所给的二元运算封闭的是（）

A) 正实数集合R+和。运算，其中。运算定义如下：?a,b∈R+，a。b=ab-a-b B) n∈Z+，nZ={nZ|z∈Z}，nZ关于普通的加法运算 C) S={2x-1|x∈Z+}关于普通的加法运算

D) S={x|x=2n, n∈Z+}，S关于普通的加法运算

15、设V=,其中*定义如下： ?a，b∈Z, a*b=a+b-2 ,则能构成的代数系统是（）。

A) 半群、独异点、群 B) 半群、独异点 C) 半群 D) 二元运算

16、令S={a,b}，S上有4个二元运算：*，○ ，· 和□，分别由下列四个表确定： * a b ○ a b · a b □ a b

a a a a a b a b a a a b b a a b b a b a a b a b A) 138 B) 120 C) 68 D) 124

6、设A, C, B, D为任意集合，以下命题一定为真的是（ ）

A) A∪B= A∪C =>B=C B) A×C= A×B =>B= C

C) A∪(B×C) = (A∪B)×(A∪C) D) 存在集合A,使得A ? A ×A

7、设A={1,2,3,4}，R={<1,3>,<1,4>,<2,3>,<2,4>,<3,4>} 是A上的关系，则R的性质是（ ）

A) 既是对称的也是反对称的 B) 既不是对称的也不是反对称的 C) 是对称的但不是反对称的 D) 不是对称的但是反对称的

8、设R是A上的关系，则R在A上是传递的当且仅当（ ）

A) B) C) D) 则这4个运算中满足幂等律的是（ ）

17、在上述四个运算中有单位元的是（ ） 18、在上述四个运算中有零元的是（ ） 19、与命题公式P?（Q?R）等值的公式是( )

A) (P?Q)?R B) (P?Q)?R C) (P?Q)?R D) P?(Q?R)

20、下列集合都是N的子集，能够构成代数系统V=的子代数的是（ ）

A)｛x| x∈N∧x与5互为素数｝ B) ｛x| x∈N∧x是30的因子｝ C) {x| x∈N∧x是30的倍数} D) {x|x=2k+1, k∈N }

二、填空题(1分/空，共20分。请将正确答案填在相应的横线上。)

1、公式┓(p∨q) →p的成假赋值为 00__,公式┓(q→p) ∧p的成真赋值为____无_____。 2、设Ａ，Ｂ为任意命题公式，Ｃ为重言式，若Ａ∧Ｃ<=>Ｂ∧Ｃ，那么Ａ<->Ｂ是 重言式 （重言式、矛盾式或可满足式）。

3、f：N->N×N，f(x)=,A={5},B={<2,3>,<7,8>},则f(x)是___单 射_（单射，满射，A) IA ? R B) R=R-1 C) R∩IA ?Φ D) R。R?R

9、设A={1,2,3,4,5,6,7,8},R为A上的等价关系R={|x,y ∈ A ∧ x=y(mod 3)}

其中， x=y(mod 3)叫做x与y模3相等，即x除以3的余数与y除以3的余数相等。则1的等价类，即[1]，为（ ）

A) {1,4,7} B) {2,5,8} C) {3,6} D) {1,2,3,4,5,6,7,8} 10、当集合A=Φ且B≠Φ时，则BA结果为（ ）

A) Φ B) {Φ} C) {Φ, {Φ}} D) 错误运算 11、函数f:R→R,f(x)= x2-2x+1,则f(x)是（）函数。

A) 单射 B) 满射 C) 双射 D) 不是单射，也不是满射

12、设X={a,b,c,d},Y={1,2,3}，f={,,}，则以下命题正确的是( )

A) f是从X到Y的二元关系，但不是从X到Y的函数 B) f是从X到Y的函数，但不是满射的，也不是单射的 C) f是从X到Y的满射，但不是单射 D) f是从X到Y的双射

双射）函数，A在f下的像f(A)＝_{<5,6>}_，B在f下的完全原像f-1(B)=_{2,7}___。

4、已知公式A中含有3个命题变项p,q,r，并且它的成真赋值为000，011，110，则A的主合取范式为（用极大项表示）__M1∧_M2∧_M4∧_M5∧_M7_____，主析取范式为（用极小项表示）__m0∨m3∨_ m6_。

5、公式?x(F(x,y)→?yG(x,y,z))的前束范式为_?x?y(F(x,u)→G(x,y,z))_或_?x?t(F(x,y)→ G(x,t,z))___。

第 1 页 共 3 页

6、列出从集合A={1,2}到B={1}的所有二元关系 φ，{<1,1>}，{<2,1>}，{<1,1>,<2,1>} 。 7、设A为集合且∣A∣=n，则A共有 2n 个子集，P(A)有2^2n 个子集。 8、设 f，g，h ∈RR 且f(x)=x+3, g(x)=2x+1, h(x)=x/2, 则复合函数

⑦ ?x (F(x)∧G(x)→H(x)) 前提引入 ⑧ F(a)∧G(a)→H(a) T ⑦UI ⑨ F(a)∧G(a) T ③ ⑥合取 (10)H(a) T ⑧ ⑨ 假言推理

f。g(x)= 2x+7 ，g。h(x)=__( 2x+1)/2_ ，f。g。h (x)=____(2x+7)/2____。

9、含有n个命题变项的公式共有___2 __个不同的赋值，最多可以生成_2^2 ___个不同的真值表；n个命题变项共可产生___2n ______个极小项（极大项）；含n个命题变项的所有有穷多个合式公式中，与它们等值的主析取范式（主合取范式）共有___2^2 ____种不同的情况。 10、已知集合A={?,{?}}，则A的幂集P(A)＝_{?，{?}，{{?}}，{?,{?}}}_____。

n

n

n

五、设A={1,2,3,4}，在A×A上定义二元关系R，?，∈A×A，

R<=>u+y=x+v

(1) 证明R是A×A上的等价关系

(2) 确定由R引起的对A×A的划分。(5分)

三、利用公式的主合取范式判断下列公式是否等值。（5分）

p→(q→r)与? (p∧q) ∨r p→(q→r)

<=>?p∨(?q∨r) <=>?p∨?q∨r <=>M6

?(p∧q)∨r

<=>(?p∨?q) ∨r <=>?p∨?q)∨r <=>M6

(1)证明: ? ∈ A×A => x+y=y+x => ∈ R ∴R是自反的 ? ∈ A×A ,

R => x+v=y+u => R ∴R是对称的 ? ,∈ A×A ,

R ∧ R => x+v=y+u ∧ u+n=v+m

=> x+v+u+n=y+u+v+m => x+n=y+m => R ∧ ∴R是传递的

(2)

解:{{<1,1>,<2,2>,<3,3>,<4,4>},{<1,2>,<2,3>,<3,4>},{<1,3>,<2,4>},{<1,4>,<4,1>},{<3,1>,<4,2>},{<2,1>,<3,2>,<4,3>}}

四、符号化命题，并推理证明(给出每个符号的准确含义，及每一步推理的根据)。（5分）

每个科学工作者都是刻苦钻研的。每个刻苦钻研而又聪明的人在他的事业中都将获得成功。华有为是科学工作者并且是聪明的，所以华有为在他的事业中将获得成功。

六、A= {1,2,3,4,6,8,12}，R是A上的整除关系，请作出偏序集的哈斯图，给出关系矩阵，并

求出A的极大元、极小元、最大元和最小元。若B={2,3,4}，求出B的上界，下界，最小上界，最大下界。（5分）

解:

首先符号化：M(x)：x是科学工作者；F(x)：x是刻苦钻研的；G(x)：x是聪明的；H(x)：x

在事业中获得成功；a：华有为。

前提： ?x(M(x)→F(x)）， ?x (F(x)∧G(x)→H(x)),M(a) ∧ G(a)

结论：H(a)

证明：① M(a) ∧ G(a) 前提引入 ② M(a) T ①化简规则 ③ G(a) T ①化简规则 ④ ?x(M(x)→F(x)） 前提引入 ⑤ M(a)→F(a) T ④

⑥ F(a) T ② ⑤ 假言推理

解:A的极大元为8、12,极小元为1， 无最大元，最小元为1。

B的上界为12，下界为1，

最小上界为12，最大下界为1。

2 1 4 8 126 3 第 2 页 共 3 页

七、在自然推理系统P中构造下面推理的证明。（5分） (1) 前提：(p∨q) →(r∧s), (s∨t) →u

结论：p→u (2) 前提：?x(F(x) →(G(a) ∧ R(x)))， ?x F(x).

九、证明下列恒等式 A-(B∪C) = (A-B)∩(A-C)。（5分） 证明：A-(B∪C)

结论： ?x (F(x) ∧ R(x)).

(1)证明： ① p 附加前提引入规则 ② p ∨ q ①附加规则 ③ (p ∨ q) →( r ∧ s) 前提引入

④ r ∧ s ②③ 假言推理 ⑤ s ④化简规则 ⑥ s ∨ t ⑤附加规则 ⑦ (s ∨ t) → u 前提引入

⑧ u ⑥ ⑦假言推理

(2)证明：① ?x F(x) 前提引入 ② F(b) ① EI ③ ?x(F(x) →(G(a) ∧ R(x))) 前提引入 ④ F(b) →(G(a) ∧ R(b)) ③ UI

⑤ G(a) ∧ R(b) ② ④假言推理 ⑥ R(b) ⑤化简 ⑦ F(b) ∧ R(b) ②⑥合取 ⑧?x (F(x) ∧ R(x)) ⑦EG

八、设有理数集合Q上的 * 运算定义如下： ?a，b∈Q, a*b=a+b-ab 。请指出该运算的性质，并求出其单位元、零元及所有可能的逆元。（5分）

解：(1)因为a*b=a+b-ab =b+a-ba=b*a，所以运算满足交换律。

(2)因为(a*b)*c=( a+b-ab)*c= a+b-ab+c-( a+b-ab)c=a+b+c-ab-bc-ac+abc a*(b*c)=a*(b+c-bc)=a+b+c-bc- a(b+c-bc)= a+b+c-ab-bc-ac+abc 故运算满足结合律。

(3)任意x∈Q，因为x*x=x+x-xx=2x+x2≠x，故不满足幂等律 (4)因为对?a∈Q，有a*0=a+0-a0=a，所以0是单位元。 (5) 因为对?a∈Q，有a*1=a+1-a=1，所以1是零元。

(6) 对?a∈Q，令a*x=a+x-ax=0，则有x=a/(a-1)。所以当a≠1时，其逆元为a=a/(a-1)，1没有逆元。

-1

＝A∩～(B∪C) ＝A∩～B∩～C = A∩A∩～B∩～C ＝(A∩～B)∩(A∩～C) =(A-B)∩(A-C)

十、设A,B为任意集合，证明：A?B<=>P(A) ?P(B)。（5分） 证明：先证明充分性（=>）

?X∈P(A)=> X?A=> X?B=> X∈P(B) 再证明必要性（<=）

?x∈A=> {x}?A=> {x}∈P(A)=> {x}∈P(B)=> {x}?B=>x∈B 综上所述，A?B<=>P(A) ?P(B)

第 3 页 共 3 页