离散数学练习题1_离散数学每一章练习题

离散数学练习题1由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“离散数学每一章练习题”。

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

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

5C)张三跟李四是同学吗？D)我在说谎。

2、下列公式不是永真式的是（）．．

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

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

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

A)GHB)H→GC)H => GD)G => H4、下列命题不为真的是（）．

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)二元运算

上有○

A)138B)120C)68D)1246、设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 ×A7、设A={1,2,3,4}，R={，，} 是A上的关系，则R的性质是（）

A)既是对称的也是反对称的 B)既不是对称的也不是反对称的 C)是对称的但不是反对称的D)不是对称的但是反对称的8、设R是A上的关系，则R在A上是传递的当且仅当（）

则这4个运算中满足幂等律的是（）

17、在上述四个运算中有单位元的是（）

18、在上述四个运算中有零元的是（）

19、与命题公式P（QR）等值的公式是()

A)(PQ)RB)(PQ)RC)(PQ)RD)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={,},则f(x)是A)IA  RB)R=R-1C)R∩IA ΦD)R。RR9、设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)＝_{}_，B在f下的完全原像f-1(B)=____。

4、已知公式A中含有3个命题变项p,q,r，并且它的成真赋值为000，011，110，则A的主合取范式为（用极大项表示）__M∧_M∧_M∧_M∧_M，主析取范式为（用极小项表示）

5、公式x(F(x,y)→yG(x,y,z))的前束范式为_

6、列出从集合A={1,2}到B={1}的所有二元关系。

7、设A为集合且∣A∣=n，则A共有nP(A)有n8、设 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。h(x)=__，f。g。h(x)=_____。

9、含有n个命题变项的公式共有_____个不同的赋值，最多可以生成___个不同的真值表；n个命题变项共可产生___n_____个极小项（极大项）；含n个命题变项的所有有穷多个合式公式中，与它们等值的主析取范式（主合取范式）共有___2^2___种不同的情况。

10、已知集合A={,{}}，则A的幂集P(A)＝_____。

n

n

n

五、设A={1,2,3,4}，在A×A上定义二元关系R，，∈A×A，Ru+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)

解:{{，,},{，},{,},{,},{,},{，}}

四、符号化命题，并推理证明(给出每个符号的准确含义，及每一步推理的根据)。（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。

七、在自然推理系统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+abca*(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BP(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BP(A)P(B)