文档库 最新最全的文档下载
当前位置:文档库 › 离散证明题

离散证明题

离散证明题
离散证明题

离散数学证明题专项训练

——09软件2班 金信冬

1. 设是群,具有幺元e ,如果对G 的任意元素a ,都有 a2=e, 则是交换群

证明:由条件e a =2,所以1-=a a ,则对任意的a ,b ,

11-*-=*b a b a

另外,由e b a =*2)(,得e b a b a b a =***=*)()(2)(,

两边同时左乘以1-a ,右乘以1-b ,利用结合律,得11-*-=*b a a b 所以a b b a *=*,是交换群

2.试证明:R S Q P S R Q P →?∧∨?∧→→)())(( 证明

(1) S

CP 规则 (2) ?S ∨P

P

(3) P

(1),(2)析取三段论

(4) P →(Q →R) P (5)Q →R (3),(4)假言推理 (6)Q

P

(7)R

(5),(6)假言推理

3.设 A,B 为两个集合,证明 A —B=A 当且仅当A ∩B= ?

证明:A —B=A

A ∩~B=A =>A ∩~

B ∩B=A ∩B

=>A∩B= ?

A∩B= ?

=>(A∩B)∪~B=~B

=>A∪~B=~B

=>A∩(A∪~B)=A∩~B

=>A∪(A∩~B)=A-B

=>A=A-B

4. 设R,S都是非空集合A上的二元关系,且他们是对称的,证明:RoS具有对称性当且仅当 RoS=SoR.

证明:

1)必要性

对于任意∈RoS

<=>RoS

<=>存在z(∈S ∧∈R)

<=>存在z(∈S ∧∈R)

<=>∈SoR

所以RoS=SoR.

2)充分性

对于任意∈RoS

<=> ∈SoR

<=>存在z(∈R ∧∈S)

<=>存在z(∈S ∧∈R)

<=>∈RoS

所以:RoS具有对称性。

5、(7分)A={(0,0),(0,1),(1,0),(1,3),(2,2),(2,3),(3,1)}, R={<(a,b),(c,d)>| (a,b),(c,d)∈A 且a+b=c+d }. (1)证明:R 是A 上的等价关系. (2)给出R 确定的对A 的划分(分类).

5、证明:(1)(5分)

自反性。对于),(),(,

),(b a R b a b a b a A b a +=+∈? 自反性成立

对称性。对于d c b a d c R b a A d c b a +=+∈?),,(),(,),(),,(如果

),(),(b a R d c b a d c 所以+=+ 对称性成立

传递性。),,(),(),

,(),(,),(),,(),,(y x R d c d c R b a A y x d c b a 如果∈?

),(),(,

,,y x R b a y x b a y x d c d c b a 从而

所以

+=++=++=+

传递性成立

(2)A/R={{(0,0)},{(0,1),(1,0)},{(1,3),(2,2),(3,1)},{(2,3)}}

6、(6分)设>< ,G 是群, },|{x y y x G y G x x S =∈?∈=且对于, 证明S 是G 的子群.

6、证明:(每步各2分) (1)S 不空:>< ,G 是群,设e 是>< ,G 的单位元,那么

S e ye ey G y ∈=∈?,,都有

,所以 S 不空。

(2)22112

1,,,

,yx y x yx y x G y S x x ==∈?∈?都有那么对于

)()()()()()(212121212121x x y x yx x y x yx x y x x y x x =====那么 所以,,2

1S x x ∈

(3)1111,

,,----==∈?∈?yxx x xyx x yx xy S y S x 都有那么对于

y x yx 11--=即

所以,S x

∈-1

S 是G 的子群.

7、(15分)设函数g :A →B ,f :B →C , (1)若f g 是满射,则f 是满射。 (2)若f g 是单射,则g 是单射。

证明 因为g :A →B ,f :B →C ,由定理5.5知,f g 为A 到C 的函数。

(1)对任意的z ∈C ,因f g 是满射,则存在x ∈A 使f g (x )=z ,即f (g (x ))=z 。由g :A →B 可知g (x )∈

B ,于是有y =g (x )∈B ,使得f (y )=z 。因此,f 是满射。

(2)对任意的x 1、x 2∈A ,若x 1≠x 2,则由f g 是单射得f g (x 1)≠f g (x 2),于是f (g (x 1))≠f (g (x 2)),必有

g (x 1)≠g (x 2)。所以,g 是单射。

8.(15分)设R 是集合A 上的一个具有传递和自反性质的关系,T 是A 上的关系,使得∈T ?∈R 且∈R ,证明T 是一个等价关系。

证明 因R 自反,任意a ∈A ,有∈R ,由T 的定义,有∈T ,故T 自反。 若∈T ,即∈R 且∈R ,也就是∈R 且∈R ,从而

T ,故T 对称。

∈T ,∈T ,即∈R 且∈R ,∈R 且∈R ,因R 传递,由∈R 和∈R 可得∈R ,由∈R 和∈R 可得∈R ,由∈R 和∈R 可得∈T ,故T 传递。

9、(15分)若是群,H是G的非空子集,则的子群?对任意的a、b∈H有a*b-1∈H。

证明必要性:对任意的a、b∈H,由的子群,必有b-1∈H,从而a*b-1∈H。

充分性:由H非空,必存在a∈H。于是e=a*a-1∈H。

任取a∈H,由e、a∈H得a-1=e*a-1∈H。

对于任意的a、b∈H,有a*b=a*(b-1)-1∈H,即a*b∈H。

又因为H是G非空子集,所以*在H上满足结合律。

综上可知,的子群。

10. (6分) G是一个群, H是G的子群. ?g1,g2?G, (g1,g2) ?R ? g1g2-1?H. 证明R 是G上等价关系.

证明: ◆对于任意的a?G,∵ a·a-1=e?H,

∴ (a,a) ? R,故R是自反的。

◆对于任意的a,b?G,若(a,b) ? R,

∴ a·b-1?H,∴(a·b-1)-1=b·a-1?H,

∴ (b,a) ? R,故R是对称的。

◆对于任意的a,b,c?G,若(a,b) ? R,(b,c) ? R,

∴ a·b-1?H且 b·c-1?H,

∴ (a·b-1)·(b·c-1)=a·c-1?H,

∴ (a,c) ? R,故R是传递的。

11.已知 f: A→B, g: B→C, f是单射,g是单射,证明g°f 是单射. 若g°f是满射,证明g是满射.

证明: (1) 对于任意的x1,x2?A, 若g°f (x1)= g°f (x2), 即有 g(f(x1))= g(f(x2)).

由于g是单射,故有f(x1)=f(x2). 由于f是单射,故有x1=x2. 因而, g°f 是单射.

(2) 对于任意z?C, 存在x?A, 使得

g°f (x)=z ,即 g(f(x))=z. 故存在 y=f(x) ?B, 使得g(y)=z.故 g是满射.

12. (8分) (G, ·)是一个群,取定u ? G. ?g 1,g 2?G ,定义: g 1*g 2= g 1·u -1·g 2. 证明: (G,*)是群。 证明: (1) 封闭性 (2) 可以结合性 (3) 幺元 e *

=u.

事实上, g*e *=g*u=g·u -1·u=g·e=g

e **g=u*g=u·u -1·g=e·g=g

(4) 逆元

对于?g ?G, 在代数运算*下的逆元记为g *-1

于是, g *-1=u·g -1·u 这里, g -1是在代数运算·下的逆元

13. 已知(G, *),(A, △)是两个群,f: G →A 是群同态的。

证明: (1) f(e G )=e A (e G ∈G 是幺元, e A ∈A 是幺元).

(2) ?g ?G, f(g -1)=(f(g))-1.

证明: (1) f(e G *e G )=f(e G ),

又f(e G *e G )=f(e G ) △ f(e G ),所以 f(e G ) △ f(e G )=f(e G *e G ) =f(e G )=f(e G )△e A ,

根据群的左消去律, 有 f (e G ) = e A 。

(2) 对于任意的g ?G ,f(g*g -1)=f(g) △ f(g -1), 又f(g*g -1)=f(e G )=e A ,所以 f(g) △ f(g -1)=e A = f(g) △(f(g))-1,

由左消去律,f(g -1) = (f(g))-1。

14.设是一个代数系统,*是R 上二元运算,

b a b a b a R

b a ?++=∈?*,,则0是幺元且是独异点。(10分)

R a ∈? ,000*,00*0?++==?++=a a a a a a a

即 为幺元00**0∴==a a a

R b a ∈?,,由于+,·在R 封闭。所以R b a b a b a ∈?++=*即*在R 上封闭。 R c b a ∈?,,

)

*(**)*()*(*)(*)(*)*(c b a c b a c b a c b c a b a c b a c b a c b a c b c a b a c b a c b a b a c b a b a c b a b a c b a =??+?+?+?+++=??+?+?+?+++=??++++?++=?++=所以

因此 , 〈R ,*〉是独异点。

15.设,是半群,e 是左幺元且A x

A x ∈?∈??,,使得e x x =*?, 则是群。(10分)

(1)c b c a b

a A c

b a ==∈?则若**,,,

c

b c e b e c a a b a a c a a b a a a

c a b a ==∴==?∴=:**,*)*?(*)*?()*(*?)*(*??**:即使事实上

(2) e 是之幺元。

事实上:由于e 是左幺元,现证e 是右幺元。

为右幺元

即由使e x e x x x e e e e x x e x x x

A e x A x ∴=====?∈∈?,*)1(*?**)*?()*(*??,*,

(3)A x

A x ∈∈?-1

,则

x x e x x x x e x x x e x e x x x x x x x A x ??**??***)*?(**)?*(:有逆元故有事实上∴=======∈?

由(2),(3)知:为群

离散数学题库

常熟理工学院20 ~20 学年第学期 《离散数学》考试试卷(试卷库01卷) 试题总分: 100 分考试时限:120 分钟 题号一二三四五总分阅卷人得分 一、单项选择题(每题2分,共20分) 1.下列表达式正确的有( ) (A)(B)(C)(D) 2.设P:2×2=5,Q:雪是黑的,R:2×4=8,S:太阳从东方升起,下列( )命题的真值为 真。 (A)(B)(C)(D) 3.集合A={1,2,…,10}上的关系R={|x+y=10,x,y A},则R 的性质为( ) (A)自反的(B)对称的(C)传递的,对称的(D)传递的 4.设,,其中表示模3加法,*表示模2乘法,在集合上 定义如下运算: 有称为的积代数,则的积代数幺元是( ) (A)<0,0> (B)<0,1> (C)<1,0> (D)<1,1> 5.下图中既不是Eular图,也不是Hamilton图的图是( ) 6.设为无向图,,则G一定是( ) (A)完全图(B)树(C)简单图(D)多重图 7.设P:我将去镇上,Q:我有时间。命题“我将去镇上,仅当我有时间”符号化为()。 (A) P Q (B)Q P (C)P Q (D) 8.在有n个结点的连通图中,其边数() (A)最多有n-1条(B)最多有n 条(C)至少有n-1条(D)至少有n条 9.设A-B=,则有() (A)B=(B)B(C)A B (D)A B 10.设集合A上有3个元素,则A上的不同的等价关系的个数为() (A)5 (B)7 (C)3 (D)6 二、填空题(每题2分,共20分)

1.n个命题变元组成的命题公式共有种不同的等价公式。 2.设〈L,≤〉为有界格,a为L中任意元素,如果存在元素b∈L,使,则称b是a 的补元。 3.设*,Δ是定义在集合A上的两个可交换二元运算,如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。 4.设T是一棵树,则T是一个连通且的图。 5.一个公式的等价式称作该公式的主合取范式是指它仅由组成。 6.量词否定等价式? ("x)P(x) ?,? ($x)P(x) ?。 7.二叉树有5个度为2的结点,则它的叶子结点数为。 8.设是一个群,是阿贝尔群的充要条件是。9.集合S={α,β,γ,δ}上的二元运算*为 * αβγδ αδαβγ βαβγδ γβγγγ δαδγδ 那么,代数系统中的幺元是,α的逆元是。 10.设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>} = 。 = 。 三、判断题(每题1分,共10分) 1.命题公式是一个矛盾式。() 2.,若,则必有。() 3.设S为集合X上的二元关系,则S是传递的当且仅当(S S)S。() 4.任何一棵二叉树的结点可对应一个前缀码。() 5.代数系统中一个元素的左逆元一定等于该元素的右逆元。() 6.一个有限平面图,面的次数之和等于该图的边数。() 7.A′B = B′A () 8.设*定义在集合A上的一个二元运算,如果A中有关于运算*的左零元θl和右零θr,则A中 有零元。() 9.一个循环群的生成元不是唯一的。() 10.任何一个前缀码都对应一棵二叉树。() 四、解答题(5小题,共30分) 1.(5分)什么是欧拉路?如何用欧拉路判定一个图G是否可一笔画出? 2.(8分)求公式 (P∨Q)R 的主析取范式和主合取范式。

离散数学题库及答案

数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( 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 )。

离散数学第四章二元关系和函数知识点总结

集合论部分 第四章、二元关系和函数 集合的笛卡儿积与二元关系有序对 定义由两个客体x 和y,按照一定的顺序组成的 二元组称为有序对,记作 实例:点的直角坐标(3,4) 有序对性质 有序性 (当x y时) 相等的充分必要条件是= x=u y=v 例1 <2, x+5> = <3y4, y>,求x, y. 解 3y 4 = 2, x+5 = y y = 2, x = 3 定义一个有序n (n3) 元组 是一个 有序对,其中第一个元素是一个有序n-1元组,即 = < , x n> 当n=1时, 形式上可以看成有序 1 元组. 实例 n 维向量是有序 n元组. 笛卡儿积及其性质 定义设A,B为集合,A与B 的笛卡儿积记作A B,即A B ={ | x A y B } 例2 A={1,2,3}, B={a,b,c} A B ={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>, <3,a>,<3,b>,<3,c>} B A ={,,,,,, , ,} A={}, P(A)A={<,>, <{},>} 性质:

不适合交换律A B B A (A B, A, B) 不适合结合律 (A B)C A(B C) (A, B)对于并或交运算满足分配律 A(B C)=(A B)(A C) (B C)A=(B A)(C A) A(B C)=(A B)(A C) (B C)A=(B A)(C A) 若A或B中有一个为空集,则A B就是空集. A=B= 若|A|=m, |B|=n, 则 |A B|=mn 证明A(B C)=(A B)(A C) 证任取 ∈A×(B∪C) x∈A∧y∈B∪C x∈A∧(y∈B∨y∈C) (x∈A∧y∈B)∨(x∈A∧y∈C) ∈A×B∨∈A×C ∈(A×B)∪(A×C) 所以有A×(B∪C) = (A×B)∪(A×C). 例3 (1) 证明A=B C=D A C=B D (2) A C=B D是否推出A=B C=D 为什么 解 (1) 任取 A C x A y C x B y D B D (2) 不一定. 反例如下: A={1},B={2}, C=D=, 则A C=B D 但是A B.

离散数学期末考试试题(有几套带答案)

离散数学试题(A卷及答案) 一、证明题(10分) 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R)?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R?T∧R(置换)?R 2)?x(A(x)→B(x))??xA(x)→?xB(x) 证明:?x(A(x)→B(x))??x(?A(x)∨B(x))??x?A(x)∨?xB(x)???xA(x)∨?xB(x)??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式(10分) 证明:(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?(?P∧(?Q∨?R))∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题(10分) 1)C∨D, (C∨D)→?E, ?E→(A ∧?B), (A∧?B)→(R∨S)?R∨S 证明:(1) (C∨D)→?E (2) ?E→(A∧?B) (3) (C∨D)→(A∧?B) (4) (A∧?B)→(R∨S) (5) (C∨D)→(R∨S) (6) C∨D

(7) R∨S 2) ?x(P(x)→Q(y)∧R(x)),?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明(1)?xP(x) (2)P(a) (3)?x(P(x)→Q(y)∧R(x)) (4)P(a)→Q(y)∧R(a) (5)Q(y)∧R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)∧R(a) (10)?x(P(x)∧R(x)) (11)Q(y)∧?x(P(x)∧R(x)) 四、设m是一个取定的正整数,证明:在任取m+1个整数中,至少有两个整数,它们的差是m的整数倍 证明设 1 a,2a,…,1+m a为任取的m+1个整数,用m去除它们所得余数 只能是0,1,…,m-1,由抽屉原理可知, 1 a,2a,…,1+m a这m+1个整 数中至少存在两个数 s a和t a,它们被m除所得余数相同,因此s a和t a的差是m的整数倍。 五、已知A、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C) (15分)证明∵x∈ A-(B∪C)? x∈ A∧x?(B∪C)? x∈ A∧(x?B∧x?C)?(x∈ A∧x?B)∧(x∈ A∧x?C)? x∈(A-B)∧x∈(A-C)? x∈(A-B)∩(A-C)∴A-(B∪C)=(A-B)∩(A-C) 六、已知R、S是N上的关系,其定义如下:R={| x,y∈N∧y=x2},S={| x,y∈N∧y=x+1}。求R-1、R*S、S*R、R{1,2}、S[{1,2}](10分) 解:R-1={| x,y∈N∧y=x2},R*S={| x,y∈N∧y=x2+1},S*R={| x,y∈N∧y=(x+1)2}, 七、若f:A→B和g:B→C是双射,则(gf)-1=f-1g-1(10分)。 证明:因为f、g是双射,所以gf:A→C是双射,所以gf有逆函数

离散数学证明题

离散数学证明题离散数学证明题:链为分配格 证明设a,b均是链A的元素,因为链中任意两个元素均可比较,即有a≤b或a≤b,如果a ≤b,则a,b的最大下界是a,最小上界是b,如果b≤a,则a,b的最大下界是b,最小上界是a,故链一定是格,下面证明分配律成立即可,对A中任意元素a,b,c分下面两种情况讨论: ⑴b≤a或c≤a ⑵a≤b且a≤c 如果是第⑴种情况,则a∪(b∩c)=a=(a∪b)∩(a∪c) 如果是第⑵种情况,则a∪(b∩c)=b∩c=(a∪b)∩(a∪c) 无论那种情况分配律均成立,故A是分配格. 一.线性插值(一次插值) 已知函数f(x)在区间[xk ,xk+1 ]的端点上的函数值yk =f(xk ), yk+1 = f(xk+1 ),求一个一次函数y=P1 (x)使得yk =f(xk ),yk+1 =f(xk+1 ), 其几何意义是已知平面上两点(xk ,yk ),(xk+1 ,yk+1 ),求一条直线过该已知两点。 1. 插值函数和插值基函数 由直线的点斜式公式可知: 把此式按照 yk 和yk+1 写成两项: 记 并称它们为一次插值基函数。该基函数的特点如下表: 从而 P1 (x) = yk lk (x) + yk+1 lk+1 (x) 此形式称之为拉格朗日型插值多项式。其中, 插值基函数与yk 、yk+1 无关,而由插值结点xk 、xk+1 所决定。一次插值多项式是插值基函数的线性组合, 相应的组合系数是该点的函数值yk 、yk+1 . 例1: 已知lg10=1,lg20=1.3010, 利用插值一次多项式求lg12的近似值。 解: f(x)=lgx,f(10)=1,f(20)=1.3010, 设 x0 =10 ,x1 =20 ,y0 =1 ,y1 =1.3010 则插值基函数为: 于是, 拉格朗日型一次插值多项式为: 故 : 即lg12 由lg10 和lg20 两个值的线性插值得到,且具有两位有效数字(精确值lg12=1.0792). 二.二次插值多项式 已知函数y=f(x)在点xk-1 ,xk ,xk+1 上的函数值yk-1 =f(xk-1 ),yk =f(xk ), yk+1 =f(xk+1 ), 求一个次数不超过二次的多项式P2 (x), 使其满足, P2 (xk-1 )=yk-1 , P2 (xk )=yk , P2 (xk+1 )=yk+1 . 其几何意义为:已知平面上的三个点 (xk-1 ,yk-1 ),(xk ,yk ),(xk+1 ,yk+1 ), 求一个二次抛物线, 使得该抛物线经过这三点。 1.插值基本多项式 有三个插值结点xk-1 ,xk ,xk+1 构造三个插值基本多项式,要求满足: (1) 基本多项式为二次多项式; (2) 它们的函数值满足下表: 因为lk-1 (xk )= 0,lk-1 (xk+1 )=0, 故有因子(x-xk )(x-xk+1 ), 而其已经是一个二次多项式, 仅相差一个常数倍, 可设 lk-1 (x)=a(x-xk )(x-xk+1 ),

离散数学试题与答案

试卷二试题与参考答案 一、填空 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、设代数系统,其中A={a,b,c}, 则幺元就是 ;就是否有幂等 性 ;就是否有对称性 。 6、4阶群必就是 群或 群。 7、下面偏序格就是分配格的就是 。 8、n 个结点的无向完全图K n 的边数为 ,欧拉图的充要条件就是 。 * a b c a b c a b c b b c c c b

二、选择 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. 写出命题公式 ﹁(P →(P ∨ Q ))的真值表。 答案: 2.证明 答案: 3. 证明以下蕴涵关系成立: 答案: 4. 写出下列式子的主析取范式: 答案: 5. 构造下列推理的论证:p ∨q, p →r, s →t, s →r, t 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 ?∧∧?∨) ()(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 ∨∧∧?

①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 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. 请将下列命题符号化: 每个人都要参加一些课外活动。 答案: ))) ()((())()((x C x M x x C x M x →??∧∧?)) ,()()((y x S y P x P y x →∧??

离散数学证明题

离散数学证明题 离散数学证明题离散数学证明题:链为分配格 证明设a,b均是链A的元素,因为链中任意两个元素均可比较,即有a≤b或a≤b,如果a≤b,则a,b的最大下界是a,最小上界是b,如果b≤a,则a,b的最大下界是b,最小上界是a,故链一定是格,下面证明分配律成立即可,对A中任意元素a,b,c分下面两种情况讨论: ⑴b≤a或c≤a ⑵a≤b且a≤c 如果是第⑴种情况,则a∪(b∩c)=a=(a∪b)∩(a∪c) 如果是第⑵种情况,则a∪(b∩c)=b∩c=(a∪b)∩(a∪c) 无论那种情况分配律均成立,故A是分配格. 一.线性插值(一次插值) 已知函数f(x)在区间[xk ,xk+1 ]的端点上的函数值yk =f(xk ), yk+1 = f(xk+1 ),求一个一次函数y=P1 (x)使得yk =f(xk ),yk+1 =f(xk+1 ), 其几何意义是已知平面上两点(xk ,yk ),(xk+1 ,yk+1 ),求一条直线过该已知两点。 1. 插值函数和插值基函数 由直线的点斜式公式可知: 把此式按照 yk 和yk+1 写成两项: 记

并称它们为一次插值基函数。该基函数的特点如下表: 从而 P1 (x) = yk lk (x) + yk+1 lk+1 (x) 此形式称之为拉格朗日型插值多项式。其中, 插值基函数与yk 、yk+1 无关,而由插值结点xk 、xk+1 所决定。一次插值多项式是插值基函数的线性组合, 相应的组合系数是该点的函数值yk 、yk+1 . 例1: 已知lg10=1,lg20=1.3010, 利用插值一次多项式求lg12的近似值。 解: f(x)=lgx,f(10)=1,f(20)=1.3010, 设 x0 =10 ,x1 =20 ,y0 =1 ,y1 =1.3010 则插值基函数为: 于是, 拉格朗日型一次插值多项式为: 故 : 即lg12 由lg10 和lg20 两个值的线性插值得到,且具有两位有效数字(精确值lg12=1.0792). 二.二次插值多项式 已知函数y=f(x)在点xk-1 ,xk ,xk+1 上的函数值yk-1 =f(xk-1 ),yk =f(xk ), yk+1 =f(xk+1 ), 求一个次数不超过二次的多项式P2 (x), 使其满足, P2 (xk-1 )=yk-1 , P2 (xk )=yk , P2 (xk+1 )=yk+1 . 其几何意义为:已知平面上的三个点 (xk-1 ,yk-1 ),(xk ,yk ),(xk+1 ,yk+1 ),

离散数学试题及答案(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变成完全图。

电大离散数学证明题参考题

五、证明题 1.设G 是一个n 阶无向简单图,n 是大于等于3的奇数.证明图G 与它的补图G 中的奇数度顶点个数相等. 证明:设,G V E =<>,,G V E '=<>.则E '是由n 阶无向完全图n K 的边删去E 所得到的.所以对于任意结 点u V ∈,u 在G 和G 中的度数之和等于u 在n K 中的度数.由于n 是大于等于3的奇数,从而n K 的每个结点都是偶数度的( 1 (2)n -≥度),于是若u V ∈在G 中是奇数度结点,则它在G 中也是奇数度结点.故图G 与它的补图G 中的奇数度结点个数相等. 2.设连通图G 有k 个奇数度的结点,证明在图G 中至少要添加 2 k 条边才能使其成为欧拉图. 证明:由定理3.1.2,任何图中度数为奇数的结点必是偶数,可知k 是偶数. 又根据定理4.1.1的推论,图G 是欧拉图的充分必要条件是图G 不含奇数度结点.因此只要在每对奇数度结点之间各加一条边,使图G 的所有结点的度数变为偶数,成为欧拉图. 故最少要加2 k 条边到图G 才能使其成为欧拉图. 五、证明题 1.试证明集合等式:A ? (B ?C )=(A ?B ) ? (A ?C ). 证:若x ∈A ? (B ?C ),则x ∈A 或x ∈B ?C , 即x ∈A 或x ∈B 且x ∈A 或x ∈C . 即x ∈A ?B 且x ∈A ?C , 即x ∈T =(A ?B ) ? (A ?C ), 所以A ? (B ?C )? (A ?B ) ? (A ?C ). 反之,若x ∈(A ?B ) ? (A ?C ),则x ∈A ?B 且x ∈A ?C , 即x ∈A 或x ∈B 且x ∈A 或x ∈C , 即x ∈A 或x ∈B ?C , 即x ∈A ? (B ?C ), 所以(A ?B ) ? (A ?C )? A ? (B ?C ). 因此.A ? (B ?C )=(A ?B ) ? (A ?C ). 2.对任意三个集合A , B 和C ,试证明:若A ?B = A ?C ,且A ≠?,则B = C . 证明:设x ∈A ,y ∈B ,则∈A ?B , 因为A ?B = A ?C ,故∈ A ?C ,则有y ∈C , 所以B ? C . 设x ∈A ,z ∈C ,则∈ A ?C , 因为A ?B = A ?C ,故∈A ?B ,则有z ∈B ,所以C ?B . 故得B = C . 3、设A ,B 是任意集合,试证明:若A ?A=B ?B ,则A=B . 许多同学不会做,是不应该的.我们看一看 证明:设x ∈A ,则∈A ?A , 因为A ?A=B ?B ,故∈B ?B ,则有x ∈B ,所以A ?B . 设x ∈B ,则∈B ?B , 因为A ?A=B ?B ,故∈A ?A ,则有x ∈A ,所以B ?A . 故得A=B .

离散数学章练习题及答案

离散数学练习题 第一章 一.填空 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

离散数学函数复习题答案

第6章 函数 一、选择题(每题3分) 1、设{,,},{1,2,3}A a b c B ==,则下列关系中能构成A 到B 函数的是( C ) A 、1{,1,,2,,3}f a a a =<><><> B 、2{,1,,1,,2}f a b b =<><><> C 、4{,1,,1,,1}f a b c =<><><> D 、1{,1,,2,,2,,3}f a a b c =<><><><> 2、设R Z N 、、分别为实数集、整数集,自然数集,则下列关系中能构成函数的是( B ) A 、)}10(),(|,{<+∧∈>< C 、)}(),(|,{2x y R y x y x =∧∈>< D 、{,|(,)(mod 3)}x y x y Z x y <>∈∧≡ 3、设Z 为整数集,则二元关系{,23}f a b a Z b Z b a =<>∈∧∈∧=+ ( B ) A 、不能构成Z 上的函数 B 、能构成Z 上的函数 C 、能构成Z 上的单射 D 、能构成Z 上的满射 4、设f 为自然数集N 上的函数,且1()0 x f x x ?=? ?若为奇数若为偶数 ,则f ( D ) A 、为单射而非满 B 、为满射而非单射 C 、为双射 D 、既非单射又非满射 5、设f 为整数集Z 上的函数,且()f x 为x 除以5的余数 ,则f ( D ) A 、为单射而非满 B 、为满射而非单射 C 、为双射 D 、既非单射又非满射 6、设R Z 、分别为实数集、整数集,则下列函数为满射而非单射的是( C ) A 、:,()6f R R f x x →=+ B 、2 :,()(6)f R R f x x →=+ C 、:,()[]f R Z f x x →= D 、6 :, ()6f R R f x x x →=+ 7、设R R Z +、、分别为实数集、非负实数集、正整数集,下列函数为单射而非满射的是( B ) A 、2 :,()71f R R f x x x →=-+- B 、x x f R Z f ln )(,:=→+ ; C 、:, ()f R R f x x →= D 、:,()71f R R f x x →=+ 8、设Z N E 、、分别为整数集,自然数集,偶数集,则下列函数是双射的为( A ) A 、f : Z E → , ()2f x x = B 、f : Z E → , ()8f x x = C 、f : Z Z →, ()8f x = D 、f : N N N →?, (),1f n n n =<+> 9、设3,4X Y ==,则从X 到Y 可以生成不同的单射个数为( B ). A 、12 B 、24 C 、64 D 、81 10、设3,2X Y ==,则从X 到Y 可以生成不同的满射个数为( B ). A 、6 B 、8 C 、9 D 、64 11、设函数:f B C →,:g A B →都是单射,则:f g A C → ( A ) A 、是单射 B 、是满射 C 、是双射 D 、既非单射又非满射 12、设函数:f B C →,:g A B →都是满射,则:f g A C → ( B ) A 、是单射 B 、是满射 C 、是双射 D 、既非单射又非满射 13、设函数:f B C →,:g A B →都是双射,则:f g A C → ( C ) A 、是单射 B 、是满射 C 、是双射 D 、既非单射又非满射 14、设函数:f B C →,:g A B →,若:f g A C → 是单射,则( B ) A 、f 是单射 B 、g 是单射 C 、f 是满射 D 、g 是满射 15、设函数:f B C →,:g A B →,若:f g A C → 是满射,则( C ) A 、f 是单射 B 、g 是单射 C 、f 是满射 D 、g 是满射 16、设函数:f B C →,:g A B →,若:f g A C → 是双射,则( D ) A 、,f g 都是单射 B 、,f g 都是满射 C 、f 是单射, g 是满射 D 、f 是满射, g 是单射

离散数学期末考试试题及答案

离散数学试题(B卷答案1) 一、证明题(10分) 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R) ?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R) ?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R ?T∧R(置换)?R 2) ?x (A(x)→B(x))??xA(x)→?xB(x) 证明:?x(A(x)→B(x))??x(?A(x)∨B(x)) ??x?A(x)∨?xB(x) ???xA(x)∨?xB(x) ??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式(10分)。 证明:(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?(?P∧(?Q∨?R))∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题(10分) 1)C∨D, (C∨D)→?E,?E→(A∧?B), (A∧?B)→(R∨S)?R∨S 证明:(1) (C∨D)→?E P (2) ?E→(A∧?B) P (3) (C∨D)→(A∧?B) T(1)(2),I (4) (A∧?B)→(R∨S) P (5) (C∨D)→(R∨S) T(3)(4), I (6) C∨D P (7) R∨S T(5),I 2) ?x(P(x)→Q(y)∧R(x)),?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明(1)?xP(x) P

《离散数学》题库及答案

《离散数学》题库与答案 一、选择或填空 (数理逻辑部分) 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) 给我一杯水吧!

离散数学及答案

全国2010年7月自学考试离散数学试题 课程代码:02324 一、单项选择题(本大题共15小题,每小题1分,共15分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列句子不是..命题的是( D ) A .中华人民共和国的首都是北京 B .张三是学生 C .雪是黑色的 D .太好了! 2.下列式子不是..谓词合式公式的是( B ) A .(?x )P (x )→R (y ) B .(?x ) ┐P (x )?(?x )(P (x )→Q (x )) C .(?x )(?y )(P (x )∧Q (y ))→(?x )R (x ) D .(?x )(P (x ,y )→Q (x ,z ))∨(?z )R (x ,z ) 3.下列式子为重言式的是( ) A .(┐P ∧R )→Q B .P ∨Q ∧R →┐R C .P ∨(P ∧Q ) D .(┐P ∨Q )?(P →Q ) 4.在指定的解释下,下列公式为真的是( ) A .(?x )(P (x )∨Q (x )),P (x ):x =1,Q (x ):x =2,论域:{1,2} B .(?x )(P (x )∧Q (x )),P (x ):x =1,Q (x ):x =2,论域: {1,2} C .(?x )(P (x ) →Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} D .(?x )(P (x )→Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} 5.对于公式(?x ) (?y )(P (x )∧Q (y ))→(?x )R (x ,y ),下列说法正确的是( ) A .y 是自由变元 B .y 是约束变元 C .(?x )的辖域是R(x , y ) D .(?x )的辖域是(?y )(P (x )∧Q (y ))→(?x )R (x ,y ) 6.设论域为{1,2},与公式(?x )A (x )等价的是( ) A .A (1)∨A (2) B .A (1)→A (2) C .A (1)∧A (2) D .A (2)→A (1) 7.设Z +是正整数集,R 是实数集,f :Z +→R , f (n )=log 2n ,则f ( ) A .仅是入射 B .仅是满射 C .是双射 D .不是函数 8.下列关系矩阵所对应的关系具有反对称性的是( ) A .???? ? ?????001110101 B .???? ? ?????101110001

离散数学题目5

离散数学试题(A卷答案) 一、(10分)证明?(A∨B)→?(P∨Q),P,(B→A)∨?P A。 证明:(1)?(A∨B)→?(P∨Q)P (2)(P∨Q)→(A∨B) T(1),E (3)P P (4)A∨B T(2)(3),I (5)(B→A)∨?P P (6)B→A T(3)(5),I (7)A∨?B T(6),E (8)(A∨B)∧(A∨?B) T(4)(7),I (9)A∧(B∨?B) T(8),E (10)A T(9),E 二、(10分)甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛,下列4种判断都是正确的: (1)甲和乙只有一人参加; (2)丙参加,丁必参加; (3)乙或丁至多参加一人; (4)丁不参加,甲也不会参加。 请推出哪两个人参加了围棋比赛。 解符号化命题,设A:甲参加了比赛;B:乙参加了比赛;C:丙参加了比赛;D:丁参加了比赛。 依题意有, (1)甲和乙只有一人参加,符号化为A⊕B?(?A∧B)∨(A∧?B); (2)丙参加,丁必参加,符号化为C→D; (3)乙或丁至多参加一人,符号化为?(B∧D); (4)丁不参加,甲也不会参加,符号化为?D→?A。 所以原命题为:(A⊕B)∧(C→D)∧(?(B∧D))∧(?D→?A) ?((?A∧B)∨(A∧?B))∧(?C∨D)∧(?B∨?D)∧(D∨?A) ?((?A∧B∧?C)∨(A∧?B∧?C)∨(?A∧B∧D)∨(A∧?B∧D))∧((?B∧D)∨(?B∧?A)∨(?D∧?A)) ?(A∧?B∧?C∧D)∨(A∧?B∧D)∨(?A∧B∧?C∧?D)?T 但依据题意条件,有且仅有两人参加竞赛,故?A∧B∧?C∧?D为F。所以只有:(A∧?B∧?C∧ D)∨(A∧?B∧D)?T,即甲、丁参加了围棋比赛。 三、(10分)指出下列推理中,在哪些步骤上有错误?为什么?给出正确的推理形式。 (1)?x(P(x)→Q(x)) P