《离散数学》复习练习题带答案（三）.pdf

《《离散数学》复习练习题带答案（三）.pdf》由会员分享，可在线阅读，更多相关《《离散数学》复习练习题带答案（三）.pdf（64页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、离散数学试题带答案一、选择题1、G是一棵根树，则（）。A、G一定是连通的B、G 一定是强连通的C、G只有一个顶点的出度为02、下面哪个语句不是命题（）。A、中国将成功举办2008年奥运会C、我说的不是真话D、G只有一个顶点的入度为1B、一亿年前地球发生了大灾难D、哈密顿图是连通的3、设R是实数集合，在上定义二元运算*:a,bGR,a*b=a+b-ab,则下面的论断中正确的是（）。A、。是*的零元C、。是*的幺元4、下面说法中正确的是（）。A、所有可数集合都是等势的C、有些无限集合没有可数子集B、1是*的幺元D、*没有等募元B、任何集合都有与其等势的真子集D、有理数集合是不可数集合5、无向完全图

2、心的不同构的生成子图有（）个。A.6 B.5 C.4 D.36、下面哪一种图不一定是无向树？A、无回路的连通图B、有n个顶点n-l条边的连通图C、每对顶点间都有通路的图D、连通但删去一条边则不连通的图7、设集合A=1,2,3,4,5,6,7,8 ,则下列各式为真的是（）。A.IsA B.4,5uAC.1,2,3 g D.0eA8、在有界格中，若一个元素有补元，则补元（）。A、必惟一 B、不惟一C、不一定惟一 D、可能惟一9、设集合A=1,2,3,1 0,下面定义的哪种运算关于集合A是不封闭的？（）A、x*y=maxx,yB、x*y=minx,yC、x*y=GCD（x,y）,即x,y的最大公约数

3、D、x*y=LCM（x,y）,即x,y的最小公倍数1 0 110、集合X 中的关系R,其矩阵是知=1 1 01 1 1则关于R 的论述中正确的是（）oA R 是对称的C、R 是反自反的B、R 是反对称的D、R 中有7 个元素1 1.下列各组数中，哪个可以构成无向图的度数列（）。A.1,1,1,2,2B.2,2,2,2,3C.1,2,2,4,6D.2,3,3,312.*是定义在Z 上的二元运算，/x,ye Z,x*y=xy+x-y,则*的幺元和零元分别是()。A.不存在，0B.0,1C.1,不存在D.不存在，不存在1 3.设N,N 为自然数，且1 若X 为奇数/（X）=-若x 为偶数1 2则/（

4、0）和/（）分 别 是（）.A.0,0B.0,0C.0,0D.0,01 4.下列命题公式中是矛盾式的有(A.(一-1)一-1B.Tq p)A pc.(-/一 (q 1 )D.(v g)厂1 5.下列各Hasse图中，是格的有（）。B.1 6 .下列命题公式中是永假式的有(A.(一 1)一 pB.)(/)A C.(1 (P)D.(p v q)r1 7 .设命题公式T P Z Q-r P)，记作G,则使G的真值指派为0的 P,Q的 取 值 是()。A.(0,0)B,(O,1)C.(1,O)D.(1,1)1 8 .与命题公式P f (Q f R)等值的公式是()。A.(P v Q).R B.(PAQ

5、)-R C.(P f Q)f R D.P-(QVR)1 9 .命题公式(PAQ)-P是()。A.永真式 B.永假式 C.可满足式 D.合取范式2 0 .设命题公式Go-KP-(Q -l P)，则 G与 H的 关 系 是()。A.QTH B.H TG C.H=G D.G=H2 1 .谓词公式 。(幻 牛/?(刃)-。(%)中 量 词 网 的 辖 域 是()。A V x(P(x)v 火(y)B.P(x)C.P(x)v 中火(y)D.Q(x)22.设个体域为整数集，下列公式中其值为1 的是(底A.+y =0)B.+y=0)C.V x V y(x +y =0)D.+y =0)2 3 .设 L(x)：x

6、是演员，J(x)：x是老师，A(x,y)：x佩 服 y.那么命题“所有演员都佩服某些老师”符号化为()。A.V x L(x)A(x,y)B.V x(L(x)T 寺(J(y)A A(X,y)C.V x H (L(x)A J(y)A A(x,y)D.V?日 y(L(x)A J(y)A(x,y)2 4.在谓词演算中，P(a)是V x P(x)的有效结论，根 据 是()。A.U S 规则 B.U G 规则 C.ES 规则 D.EG 规则2 5 .在 图 G =中，结点总度数与边数的关系是()。A.deg(Vi)=2 I E I B.deg(vi)=|E I C.d e g(v)=2|f|D.d e g

7、(v)=26.设G是有n个结点的无向完全图，则图G的边数为（）；设D是 有n个结点的有向完全图，则图D的边数为（）。A.n（n 1）B.n（n+l）C.n（n 1）/2 D.n（n+l）/227.仅有一个孤立结点的图称为（）。A.零图 B.平凡图 C.补图 D.子图28.设G=为无向简单图，|v|=n,A（G）为G的最大度，则 有（）。A.A（G）n B.A（G）n D.A（G）n29.图G与G，的结点和边分别存在一一对应关系，是G丝G，（同构）的（）。A.充分条件 B.必要条件 C.充分必要条件 D.既非充分也非必要条件30.设V=a,c,d ,则与V能构成强连通图的边集合是（）A.E =,

8、Q.E -,C.E -,D.E =,31.相邻矩阵具有对称性的图一定是（）。A.有 向 图B.无向图 C.混 合 图D.简单图32.无向图G是欧拉图，当且仅当（）。A.G的所有结点的度数全为偶数 B.G的所有结点的度数全为奇数C.G连通且所有结点的度数全为偶数D.G连通且所有结点的度数全为奇数33.设G=，M =，=加为连通平面图且有r个面，则r=（）A.m-n+2 B.n-m-2 C.n+m-2 D.m+n+234.设G是由5个结点组成的完全图，则从G中删去（）条边可以得到树。A.4 B.5 C.6 D.1035.由5个结点可构成的根树中，其叉数m最多为（）。A.2 B.3 C.5 D.43

9、6.下图是（）。A.完 全 图B.哈密顿图 C.欧拉图 D.平面图图37.设集合A=l,2,3,.,10,在集合A上定义的运算，不是封闭的为()。A.Va,beA,a*b=lcma,b(最小公倍数)B.Va,bcA,a*b=gcda,b(最大公约数)C.Va,beA,a*b=maxa,b D.Va,bcA,a*b=mina,b38.在自然数N上定义的二元运算，满足结合律的是()。A.a,b=a-b B.a,b=a+2b C.a b=maxa,b D.ab=I a-b I39.下列代数系统(G,*)中，其中*是加法运算.()不是群。A.G为整数集合 B.G为偶数集合C.G为有理数集合 D.G为自

10、然数集合40.设6，6,6 是三个置换，其中 01=(1 2)(2 3)(1 3),02=(2 4)(14),c3=(l 3 2 4)则6可以表成()。2 2A.eTj B.Q1O2 C.(72 D.6O14 1.下列图表示的偏序集中，是格的为()。A.=0 B.a+b=C.a+b=a4 3.布尔代数式+S +c)=()oA.a+b B.b+c C.b+c D.b+cD.a+b=144.设集合人=1,2,B=a,b,c,C=c,d,则 AX(BcC)=()。A.,B.,C.,D.,45.设 A=0,a,B=l,a,3,则 AuB 的恒等关系是()。A.,B.,C.,D.,46.设 A=a,b,

11、c,R=a,a,则 R 具有性质()。A.自反的 B.反自反的 C.反对称的 D.等价的47.设集合 A=%,。2，。3，。4，B=仿,d，d,c r 是从 A 到 B 的函数，cr=,则。是()。A.双 射B.满 射 但 不 是 单 射C.单射但不是满射 D.非单射也非满射48.下列式子中正确的是()oA.0=O B.0S 0 C.0ea,b D.0e049.有向图的邻接矩阵中，行元素之和是对应结点的()，列元素之和是对应结点的()。A.度 数B.出 度C.最 大 度 数D.入度50.给定无向图如下所示，下面给出的顶点集子集中，不是点割集的是()。A.b,d B.dC.e D.f,h51.谓

12、词公式m xA(x)人-G x A(x)的类型是(A.永真式 B.矛盾式C.非永真式的可满足式 I).不属于(A),(B),(C)任何类型52.谓 词 公 式V yP(y)取真值为1的充分必要条件是()。A.对任意y,使P(y)都取真值1B.存在一个yO,使P(y0)取真值1C.存在某些y,使P(y)都取真值1D.存在y。，使P(yo)取真值05 3.设G是群，当6有()个元素时，不能肯定G是交换群。A.4B.5C.6D.75 4.若集合A=a,b,c,0 为空集合，则下列表示正确的是(兀A.a e A B.a u A C.a a A D.0 e A5 5 .设 A,B,C都是集合，如果A c

13、 C=B c C,贝|有()。A.A=B B.Aw B C.当 A-C=B-C 时,有 A=B D.当 C=U 时，有 A w B5 6 .设&=0,S2=0 ,8=P(0 ),S”=P(0),以下命题为假的是()。A.S2 eS.t B.Si c S3,C.S.i c S2 D.S(e S35 7 .设G是有6个元素的循环群，a 是生成元素，则 G的 子 集()是子群。A.a B.a,e C.e,a3 D.e,a,a25 8 .设集合A=a,b,c,d,e,半序关系R 的哈斯图如下，假设A的子集B=c,d,e,则元素c 为 B的()。A.下界 B.最大下界C.最小上界 D.以上答案都不对5

14、9 .设 G Vx m yP(x,y)-Q(z,w),下面三个命题为真的是()=A.G 是前束范式 B.G 不是前束范式C.G 不是一阶公式 D.G 是永真式6 0 .对任意集合S,S u0=S,满足()。A.幕等律 B.零一律 C.同一律 D.互补律6 1 .设命题公式G：P F(QAR),则使公式G取真值为1的 P,Q,R 赋值分别是()。A.0,0,0B.0,0,1C.0,1,0D.1,0,06 2 .设 a是集合A的元素，则 以 下 正 确 的 是()。A.a 三 B.q AC.a AD.a e A6 3.设集合A 1,2,3,4 ,B：2,4,6,9 ,那么集合A,B的对称差AB=(

15、)。A.1,3B.2,4,6C.1,3,6,9)D.1,2,3,4,6,964.有向完全图D=,则图D的边数是（）。A.I E|（I E|-1）/2B.I V|（|V|-1）/2C.I E|（|E|-1）D.I V|（|V|-1）65.设 G是有n 个结点，m条边的连通阻，必须删去6 的（）条边，才能确定G的一棵生成树。A.m -n+1B.n-mC.m+n+1D.n m+166.设N为自然数集合，在下面4种运算下不构成代数系统的是（）。A.x。y=x+y2xy B.x y=x+yC.xy=x,y D.xoy=|x|+|y|-0 1 1 O1 0 0 11 0 0 067.已知图G的 相 邻 矩

16、 阵 为1 ，则6有（）。A.6个点，度为4 B.5个点，度为6C.4个点，度为3 D.4个点，度为668.设集合A=1,2,3,.,1 0,半序关系4是A上的整除关系，则半序集（A,4）上的元素10是集合A的（）。A.最大元 B.最小元 C.极大元 D.极小元二、填空题1.代 数 格（L,x,0）中的运算x和 满 足 的 算 律 有、。2、A是含有3个元素的集合，在A上可以定义 个不同的等价关系。3、R是实数集合，R中的关系8=。2,x 从R到R的函数（填“是 或 不是4、G 是群，|G|1,则G中的零元。5、当n是_ _ _ _ _ _ _ _ _ _ _ _值时，无向完全图4是欧拉图。6

17、、I是整数集合，代数系统（又是通常乘法）的幺元是,-1的逆元是7、元素数目不超过 的格一定是链。8、公式T PVQ)C(PAQ)的主合取范式为。9、-C P fQ,P vR的有效结论是。10、已知公式A(p,q,r)的主合取范式为MOA M3 A M5,它的主析取范式为(写成编码形式)。11,is A=a,b,B=0,l,2,那么可定义 种不同的从A到B的单射。12.已知集合人=0,1,2 ,则A的基集合p(A)=o13、设是分配格，若对任意的a,c,c G A,如果有a/b=a/c,aV b=aV c成立，则a bo14、仅 当n 时，心为平面图。15.p q的主合取范式是。16.语 句“我

18、在说谎 命题。(填“是”或“不是”)。17.设 A=a,b,c,d,R 是定义在 A 上 的 关 系，R=,则 r(R)=18.一个树林G有三棵树，G的顶点数是2 0,则G的边数为19.P(P(0)=。2 0.整数加法群中1的阶是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。0 2 1 0-2 1.设有向图0=的邻接矩阵为A(D)=:；，那么|E|=0 0 1 122.语 句“这句话是错的 命题。(填“是”或“不是23.设命题公式G=PA(QVR),则使G取真值为1的指派是,。24.已知命题公式为G=(PAQ)-R,则命题公式G的析取范式是_ _ _ _ _ _ _ _

19、_ _ _ _ _ 25.公式 V x(P(x)f Q(x,y)v 壬/?(y,z)S(x)的自由变元是,约束变元是 o26.谓词逻辑公式V xP(x)-B xQ(x)的前束范式是 o27.设个体域口=a,b,消去公式中的量词，则D xP(x)A m x Q(x)O _28.换名规则施于 变元，代入规则施于 变元。29.设图G=和G，=若,则G，是G的真子图，若,则G是G的生成子图。30.在无向图中，结点间的连通关系具有 性，性，性，是关系.。3 1.无环有向图D 的关联矩阵M(D)中，第 i 行值为1 的元素个数为结点M 的,第 j列值为-1 的元素个数为结点巧的.3 2 .设 G是完全二叉

20、树，G有 15个结点，其中有8 个是树叶，则 G有 条边，G的总度数是,G的分支点数是,G中度数为3的结点数是3 3 .连通有向图D 含有欧拉回路的充分必要条件是-3 4 .设 G是有 n个结点的简单图，若 G中每对结点的度数之和，则 G 一定是哈密顿图.。3 5.设 G是有n个结点，m条边的连通图，要确定G的一颗生成树，必须删去G的 条边.。3 6.一个有向树T称为根树，若,其中，称为树根，_ 称为树叶.3 7 .在代数系统(N,+)中，其单位元是,有 逆 元.。3 8.设 A 是非空集合，集合代数(P(A),u,c)中，P(A)对运算u 的 单 位 元 是,P(A)对运算C 的单位元是 o

21、3 9 .把置换|1 2 3 4 5 6表成轮换的乘积是，(2 3 1 4 6 5)表成对换的乘积是。4 0 .设 G是由6 个元素构成的循环群，a是 G的一个生成元素，则 G有 个子群,G的生成元是4 1.非空集合L,其上定义二元运算。和，如果 是交换群，(L,)是，而且_满足分配律，则 L 对二元运算。和构成环。4 2 .设 L是一个集合，和。是 L上两个二元运算，如果这两个二元运算满足 律，律和 律，则(L,。)是格。4 3 .在布尔代数中，有a v(a 匕)=avb成立.则该式的对偶式 也一定成立。4 4 .设 R“R?是集合 A=1,2,3,4 上的二元关系，其中 R.=,R2=,则

22、 心&=4 5.设 R,S都是集合A 上的等价关系，则对称闭包s(R c S)=_4 6.图 的 通 路 中 边 的 数 目 称 为.结点不重复的通路是 通路.边不重复的通路是 通路。4 7 .将 谓 词 公 式V x(P(x)-R(x)v Q(x,z)A BxR(x)f 壬S(x,z)中的约束变元换名4 8.写出下列集合的子集：B=0;C=04 9 .设全集合 E=1,2,3,4,5,A=1,2,3 ,B=2,5,AcB=,B=Au B=o50.设 A,B代表集合，命题A-B=0oA=B的真值为。51.设集合 A=a,b,c,B=a,b,那么 P(A)-P(B)=,P(B)-P(A)=_ 5

23、2.设人=,e,.n 选择适当的符号填在各小题的横线上.(1)(1,2,3,4)N;(2)V2 Q,Q Z53.关于格的命题P：aA(b V c),求 P 的对偶命题P*=。54.计算Z6的所有理想。55.求 Vx(P T Q(x)v R(e)的真值。56.判定公式(PfQ)ZR-Q)(Pv R)rQ)的类型_。57.将 命 题 公 式 八 Q A(R-P)化为只含v和的 尽 可 能 简 单 的 等 值 式。58.设 n(A)=m,则A上有 个不同的自反关系。59.设集合 A=a,b,c,d,A 上的关系 R=(a,a),(a,c),(b,d),则关系 R2=。60.设 集 合 A 中有4 个

24、元素，则 A上的不同的等价关系的个数为 个。三、判断题1.空间中的平行六面体是平面图。()2、每个顶点的度都是偶数的无向图一定是欧拉图。()3、顶点数目相同，边数也相同的两个无向图一定同构。()4、函数的逆关系还是函数。()5、A,B,C 都是集合，如果 AUB=AUC,则 B=C。()6、设 R是环，A,B是 R的两个理想，且 B包含于A,则 A/B是 R/B的理想，并且R/B/(A/B)同构于 R/A。()7.p/x p 的 对 偶 是 i pvq ()8,设 G 是有r 个面的连通平面图，顶点数和边数分别是n 和 m,则 n-m+r=2。()9.n 阶有向完全图有n(n-1)条边。()1

25、0.在代数系统S,*中，若 x*y =x*z,贝！I y=z。()11.设无向图T 是树，则 T 中一定没有简单回路。()12.能够画在一张平面上的图是平面图。13.设S,*是代数系统，B是 S 的非空子集，则8,*是S,*的子代数。()14.循环群的子群仍然是循环群。()15.格不一定是布尔代数。()16.1+101=110 是 命 题。()1 7 .“全体立正是命题”。（）1 8 .“明天是否开大会？”是 命 题。（）1 9 .“如果天气好，那么我去散步”是命题。（）2 0 .判断（Z,4）是否为格？其中4 是数的小于或等于关系。（）2 1 .设 R是实数集，“十”为数的加法，“义”定义为

26、=试 问 R对二元运算+和X是否构成环。（）2 2 .设集合A=1 8 的正整数因子,4 为整除关系，说明A,。是否是偏序关系。（）2 3 .0D0 =。是对的。（）24.。是。的子集。（）2 5 .如果 S=T=S u M,则 丁=乩（）2 6 .己知 S=2,a,3,4,R=a,3,4,1,贝！|ae S。（）2 7 .整数集合Z和普通的减法运算是封闭的。（）2 8 .在 R中定义二元运算：*,a*b=a+b+ab,对于任意a,b属 于 R,则 R,*是独异点。（）2 9 .整数集合 1,2,3,4,6,1 2 关于整除关系构成了偏序集，并且该偏序集是格。（）-、选择题1.A2.C3.C4

27、.A.5.D6.C7.D8.C9.D10.D11.B12.D13.B14.B15.B16.B17.C18.B19.A20.D21.C22.A23.D24.A25.C26cA 27.B28.A29.B30.A31.B32.C33.A34.C35.D36.B37.A38.C39.D40.D41.C42.D43.B44.B45.C46.A47.B48.D49.B,D50.A51.B52.A53.D54.B55.C56.A57.C58.C59.B60.C61.D62.B63.C64.D65.A66.A67.D68.C二、填空题1.交换律、结合律、吸收律2.53.不是4.不存在5.奇数6.1,-17.3

28、8 .(P v 1。)A(PVQ)9.R1 0.m l V m 2 V m 4 V m 6 V m 71 1.61 2、p(A)=0,0,1,2,0,1,0,2,1,2,A 1 3、=1 4、奇数1 5 .q1 6 .不是1 7、,1 8、1 71 9、6，4 2 0、无限2 1、72 2.不是2 3.(1,0,0,)(1,0,1)(1,1,1)2 4.P v Q v R2 5.y,x x,z26.3%(-iP(%)v Q(x)2 7.P(a)A PS)A(Q(a)v Q(b)2 8.约 束 自 由2 9.V c V E E;V =V,E E3 0.自 反 性 对 称 性 传 递 性 等 价.

29、3 1.出 度 入 度3 2.1 4 2 8 7 63 3.D中每个结点的入度=出度.3 4.大于或等于n3 5.m+1 n3 6.若有向图T恰有一个结点的入度为0,其余结点入度为1 入度为0的结点 入度为1的结点.3 7.0 仅有单位元0.3 8.0 A.3 9.(1 2 3)(5 6)(1 3)(1 2)(5 6)(不唯一)4 0.4 a,a4 1.(L,O)半 群 二元运算对运算O4 2.交 换 律 结 合 律 吸 收 律43.a b)=a 八b44.,45.RnS4 6.通 路 出 度 初 级 简 单.47.V“(P()T /?(“)v Q(,z)A 3v7?(v)f 3wS(x,w)

30、48.0,0 049.2,1,3,4,1,3,4,5)50.051.c,a,c,b,c,a,b,c；052.c g z53.(aAb)V(aAc)54.0,0,3,0,2,4 0,1,2,3,4,555.15 6.永真式57.i(P v 0 v i(P v /?)58 2 j59.R2=(a,a),(a,c)60.15三、判断题1.正确(从同构的角度说明理由)2.错误(举反例)3.错误(举反例)4.错误(从同构的角度说明理由)5.错误(举反例)6.正确7.错误8.正确9.正确10.错误11.正确12.错误13.错误1 4 .正确1 5 .正确1 6 .否1 7 .否1 8 .否1 9 .是2

31、0 .是2 1 .否2 2 .是2 3 .错误2 4 .真2 5 .假2 6 .错误2 7 .正确2 8.是29.是离散数学试题一.填空题1 .(P V 0 A-1P T 0从公式分类角度来看，它为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _式。2 .公式P-(Q-R)在联结词全功能集 V 中等值形式为。3 .关于命题变项P,Q,R的命题公式的主析取范式是m vm xjm vm vm.,则主台取范。4 .尸 八 r P 从公式分类角度来看，它为 式已 次 公 式 均 的 主 合 取 范 式 为 M AM AM,它的主析取范式为(写成5 .编码形式)ocF T。

32、的对偶式为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _o6.7 .全体小项的析取式必为 式。8.P,Q为两个命题，则德摩根律可表示为7.全体小项的析取式必为 式。9 .P,Q为两个命题，则吸收律可表示为。1 0 .设 P：我有钱，Q：我去看电影。命题“虽然我有钱，但是我不去看电影 符号化为1 1 .设P：我生病，Q：我去学校。命题“如果我生病，那么我不去学校”符号化为.俞段公式P V 伽 r R）断 概 趣 o1 2 .命题公式（P V 0 A R 的 对 偶 式 为 01 3 .一个命题公式改产,0国的成真指派为0 0 0,0 0 1,0 1 0,1 0 0,1

33、 1 0,则其主合1 4 .取范式为 o1 5 .设P、Q为两个命题，交换律可表示为。郢愉题P 蹦账 施 P6。的真值为。1 6 .1 7 .命 题“如果你不看电影，那么我也不看电影（P：你看电影，Q：我看电影）的符号化为。公式r（P V 0 A 什V r（g A r S）的 对偶公式为 01 8.设P，Q 的真值为0，R，S 的真值为1,则川即曲）川 加 司出的真值为。公式（F n町v（S n R）vd的主合取范式为.2 0.2 1.P：你努力，Q：你失败。命 题“除非你努力，否则你将失败”的翻译为若对命题P 赋值I,Q赋 值 1 喻题r（PT。的真值为。22.命题公式r（PT的 主 合 取

34、 范 式 的 编 码 表 示 为。2 3.2 4.一个重言式和一个矛盾式的合取是 o2 5.全体小项的析取式为。2 6.命 题“如果你不看电影，那么我也不看电影（P：你看电影，Q：我看电影）的符号化为O若对命题P 赋值1,Q 赋值0,则命题P6。的真值为。27.28.设P：它占据空间，Q：它有质量，R：它不断运动，S：它叫做物质。命 题”占据空间的，有质量的而且不断运动的叫做物质”的符号化为。设A,B 是两命题公式，力。8当且仅当。2 9.要证RTC为 赧H 1，如“.，%的有獭论，运用C P规则，即 是 要 证30.二.选择题下列哪个公式为永真蕴含式（）。A.-,Q=Q-*-nP B.l Q

35、=P Q C.P=P Q D.-,PA（PVQ）=P1.下面哪个联结词不可交换（）oA.A B.C.v D.O2.3.在除之外的四大联结词中，满足结合律的有几个（）。A.2 B.3 C.4 D.14.判断下列语句哪个是命题（）。A.你喜欢唱歌吗？B.若 7+8 1 8,则三角形有4 条边。C.前进！D.给我一杯水吧！设P：张三可以做这件事，q：李四可以做这件事，命题“张三或李四可以做这件事”的符号化形式为（）。A.p v q B.p v q C.p q D.p-*q6.设P：我将去镇上，Q：我有时间，则命题“我将去镇上，仅当我有时间时“可符号化为（）。A.p vq B.p V-iq C.p q

36、 D.p-*q命题公式p v q是（7 A.矛盾式；B,可满足式；C重言式；D.等价式。8 .永真式的否定是（）A.永 真 式 B.永 假 式 C,可 满 足 式 D.A-D 均有可能9.下 面哪一个是假命题（）。A.如果2 是偶数，那么一个公式的析取范式唯一。B.如果2 是偶数，那么一个公式的析取范式不唯一。C.如果2 是奇数，那么一个公式的析取范式唯一。D.如果2 是奇数，那么一个公式的析取范式不唯一。10.设 p:天下大雨，q:小王乘公共汽车上班，命题“只有天下大雨，小王才乘公共汽车上班”的符号化形式为（）。A.p f q B.q p C.p-*n q D.-|pq11.设p：小李努力学

37、习，q：小李取得好成绩，命 题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（）。A.p f q B.q f p C.-j q-p D.-j p f q12.下面4个推理定律中，不正确的为（）。A.A=（AVB）（附加律）B.（AVB）A-1 A=B（析取三段论）C.（A f B）/A=B（假言推理）D.（A-B）A-|B=A（拒取式）13.使命题公式p f（pA q）为假的赋值是（）。A.10 B.01 C.00 D.1114.令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）。A.pA-i q B.pV-i qC.pAq D.p f-i q15.一个公

38、式在等价意义下，下面哪个写法是唯一的（）。A.析取范式 B.合取范式C.主析取范式 D.以上答案都不对16.令p：今天下雨了，q：我上学，则命题“因为今天下雨了，所以我不上学了”可符号化 为（）A.p f-i q B.pV-i qC.pAq D.pA-i q1 7.下列各组公式中哪组互为对偶（）。（P为原子命题，A为复合命题）A.P,P B.P,-i PC.A,（A*）*D.A,A18.若解释I 使公式A 为真，使公式工T B 也为真，则解释I 使公式B 为（A.真 B.假 C.可满足 D.与解释I 无关.命题公式（尸 一 QVF）中极小项的个数为（A,0 B,I C,2 D.319.命 题

39、公 式（尸中成真赋值的个数为（20A,0 B,1 C,2 D.321.下面命题公式（）不是重言式。B.（F 八。）-FC.-i(P A-i0 A(-iP V g)D C P-0)一(F v 2)22.下面哪个命题公式是重言式（A.（FTQ）/Q 7R）C.?V 0 A -|（P A-1 0B(P A g)PD-I(FV0AP命题公式尸7 v尸）是（）。A,矛盾式 B.可满足式 C.重言式 D.等价式23.24.设P：2x2=5,Q：雪是黑的，R：2x48,S：太阳从东方升起，下列（）命题的真值为真。A.F 旦八&B.R-F/S C.STQAR D.（FA&）V 9A$）2 5.下列语句哪个是命

40、题（）。A.9+512 B.x+3=5C.我用的计算机CPU主频是1G吗？D 我正在说谎。命 题“我不能一边听课，一边看小说”的符号化为（工A.F i g B.Y T Q C.-IP D.（F/XQ）26.27.若公式（产 八 的 主 析 取 范 式 为 切。】v/u VM】o v/u,则它的主合取范式为C XA.WO O 1A WO 11A W1 1 O A wmB.ooo 八 公010 八凶loo 八.101C,财001八凶011人凶110八M uD.ooo人肉61。八加100八 活U H28.n 个命题变元可产生（）个互不等价的大项。A.n B.n2 C.2n D.2n29.下列各命题中

41、真值为真的命题有（）。A.2+2=4当且仅当3 是奇数 B.2+2=4当且仅当3 不是奇数C.2+2W4当且仅当3 是 奇 数 D.2+2W5当且仅当3 不是奇数30.下列语句哪个不是命题（）oA.雪是黑的。B.天气多好啊！C.今天下雨。D 我学英语，或者我学日语。三.判断题1.“我正在说谎。”是一个命题。（）2.一个命题标识符如表示确定的命题，就称为命题常量。（）3.“她昨天做了一顿或两顿饭。”是个原子命题。（）4.命题公式是没有真假值的，仅当在一个公式中命题变元用确定的命题代入时，才得到一个命题。（）5.如果A 和 B 是合式公式，那么（A-B）是合式公式。（）6.原子谓词公式是合式公式。

42、（）7.一般来说，n 个命题变元组成的命题公式共有2n中真值情况。（）8 .任何两个重言式的合取或析取，仍然是一个重言式。（）9.重言式和矛盾式的析取是重言式。（）10.在真值表中，一个公式的真值为F 的指派所对应的大项的析取，即为此公式的主析取范式。（）11.从假的命题出发，能证明任何命题。（）12.全体小项的析取式永为假。（）13.连接词t 和 I 是可交换的，也是可结合的。（）14.P Q=）PP/Q。（）15.由 n 个命题变元组成不等值的命题公式的个数为2n。（）四.计 算 题求公式（PQ）AR的主析取范式和主合取范式。1.2.求公式（P/R）v（Q/R）的主析取范式和主合取范式03

43、.求公式（i Pf Q）八（Rv P）的主析取范式和主合取范式。4,求公式Q r （P V R）的主析取范式和主合取范式。5 求公式P（P/（Q P）的主析取范式和主合取范式。6.求公式-1 （P-Q）V（RAP）的主析取范式和主合取范式。7,求公式P v（PQ）的主析取范式和主合取范式8,求公式P f Q 的主析取范式和主合取范式。9,求公式PAQ的主析取范式和主合取范式口1 0求 公 式（Pv R）TQ的主析取范式和主合取范式。11 求 公 式（P-Q）T R 的主析取范式和主合取范式。1 2.求公式（P-Q）A（P R）的主析取范式和主合取范式。13.设P：2+2=4,中3+3=7,4+

44、4=8,求下列个复合命题的真值。(P/Q)-r R(2)(P-一R)一 (Q R)(3)(PV-|Q)-(Q f R)(4)-1 Q r (Pr R)(PVQ)f (-1 PAQAR)14.求公式(F T 0)R的 主 合 取 范 式(化 成 的 形 式)15.含有命题变项P,Q,R的命题公式F的所有成真赋值为：000,001,110,111(1)画出真值表(2)写出主析取范式(3)指出公式的类型五.证明题1 证明(W VR)f V,V-CVS,S-*U,2,用真值表法证明P-Q=(P-Q)A(Q-P)3.用求主范式的方法证明(P-Q)A(P-R)=(Pf (QAR)第2章一.填空题设个体域为

45、整数集合Z,命题Wxmy(x+y=3)的真值为 o2设个体域口=1,2 ,命题Wxmy(x+y=3)的真值为。3量词否定等值式-IVXN(X)Q。量词否定等值式 王 仁)=。4.5.设O(x):x是奇数，Z(x):x是整数，则语句“不是所有整数都是奇数”的符号化形式为 o6.设M(x):x是人，H(x):x要呼吸，则语句“所有的人都是要呼吸的”的符号化形式为。7.个体域为1,2 ,命题Wxmy(x+y=4)的真值为。8 谓词公式(TxXP依)-Q(x)VR(x,y)中的约束变元为。9.设F(x)表示x 是火车，G(y)表示y 是汽车，H(x,y)表示x 比y 快，命题“某些汽车比所有火车慢”可

46、表示为10.设C(x)表示x 是运动员，G(x)表示x 是强壮的。命题“没有一个运动员不是强壮的”可符号化为。11.对于谓词公式其中F(x):x=l,Q(x):x=2,当论域为1,2时,其真值为。12.设G(x):x是金子，尸(x):x是闪光的，则命题“金子是闪光的，但闪光的不一定是金子”可符号化为。13.谓词公式Vx(G(x)T F(z)A 3yF(y)A Q。)中的自由变元为。14谓词公式3x(G 3 T P八攵Q(z)中的约束变元为。谓词公式(Vz)(P(z)-*Q(z)V R(x,y)中 的 自 由 变 元 为。2、论域D=1,2 ,指定谓词PP(I,DP(l,2)P(2,l)P(2,

47、2)TTFF京 则公式V妇真值为 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。1O.17.谓词公式Vx(P(x)T g(x)A R(y)中V x的辖域为。18.谓词公式V/(x)一 十0 8 y)的前束范式为。19.设个体域为自然数集，命题“不存在最大自然数”符号化为。20.设e a)：x为偶数，尸(x)：x为素数，则 命 题“至多有一个偶素数”形式化为。n个命题变元有 个互不等价的极小项。21.22.n3 E 心 v-u 42 V V-lA,=v-4按 De-Mcrgan 定理，口 =。23.设P(x)：x是大象，Q(x)：x是老鼠，R

48、(x,y)：x比y重，则命题“大象比老鼠重的符号化为。24公式(F v Q)人(尸v 9/S)的对偶公式为。25.若对命题P赋值1,Q赋值0,则命题F-2的真值为。二.选择题给定推理 Vx(砥x)-G(x)咐 一 G。)3xF(x)WG。)VxG(x)PUSPESTIUGXZr(F(x)T G(x)=XfxG(x)推理过程中错在(A.-B.-C.-D.-下列等价关系正确的是()。A.Vx(F(x)vg(x)o VxP(x)v fxQ(c)B.3x(P(x)v Q(xy)=3xP(x)v3xg(x)C.Vr(P(x)-Q)=XfxP(x)QD.3x(P(x)g)=3rp(r)7 Q谓词公式依伊(

49、x)v 十&T Q(x)中量词Vx的作用域是()。A.V x(P(x)v ByR)B.P(x)C.(P(x)v3(y D.P(x),g(x)4.设谓词P(x)：X是奇数，Q(x)：X是偶数，谓词公式五(P(x)9(x)在哪个个体域中为真？()A自然数 B实数 C复数 D以上均成立5.谓词公式W x(P(x)v m y R(y)-Q(x)中变元x是(A.自由变元 B.约束变元C,既不是自由变元也不是约束变元 D.既是自由变元也是约束变元若客体域为整数域，下列公式中真值为真的是()。A Vx 3 y(x+.y =0)B.W c(x+y =0)C.fx fy(x+y=0)D.-i 3 x 3 y(x

50、+7 =0)6.7.谓词公式也(尸g(x)中 的 丫 是()。A.自由变元 B.约束变元C.既是自由变元又是约束变元 D.既不是自由变元又不是约束变元设B不含有x,下列一阶逻辑等值式不用旗的是(兀A.依(2(x)八 8)Q Vx z 4(r)A BB.t t c(4(x)3)=Vx 4(x)BC.X Z x(4(x)A B(x)=Vx/4 8 A VXS(X)D.3 x(l(x)v B(x)=3 x (x)v 3 x B(x)8.9.谓词公式W x(P(x,y)A m x Q(x,z)i R(x,y,z)中量词mx辖域是()。A,Q(x,z)-R(x,y,z)C.Q(x,z)B.R(x,y,z