离散数学填空题

填空题

填空题 (本大题共5小题，每小题2分，共10分) 第一章 命题逻辑

1、设P：天上下钉子；Q：我去B城。命题“除非天上下钉子，否则我去B城”符号化为____

________________。﹁P?Q

2.设p：我们勤奋，q：我们好学，r：我们取得好成绩。命题“只要勤奋好学，我们就能取

得好成绩”符号化为_____________。(p∧q)?r

3．设P:天下雨，Q:天刮风，R: 我去书店，则命题“如果天不下雨并且不刮风，我就去书店”

的符号化形式为_______________。(﹁p∧﹁q)?r

4．命题公式(P?R)∧(┐S∨Q)在赋值0101下的真值为____________________。真(注意字母

顺序)

5．已知命题公式G＝?P? Q，则G的主析取范式是__________________．m1∨m2∨m3

6．命题公式A中出现有n个不同命题变元，若A是永假式，则A的主合取范式中含有极大项

的个数为_______________。n

第二章 谓词逻辑（一阶逻辑）

7.设置F(x)：x为整数，G(x)：x是自然数，则命题“并不是每一个整数都是自然数”符号

化为____________________。?x(F(x) ∧﹁G(x))

8.设F(x):x是人，H(x,y):x与y一样高，在一阶逻辑中，命题“人都不一样高”的符号化

形式为___________。?x?y(F(x) ∧F(y) ?﹁H(x,y))(事实上这里默认x与y不一样) 9．设F(x): x是人，G(x): x用右手写字，命题“有的人并不用右手写字”在一阶逻辑中符

号化的形式为_____________________。?x(F(x) ∧﹁G(x))

10．表达式?x?yP（x，y）中谓词的个体域是{a，b，c}，将其中的量词消除，写成与之等价

的命题公为：________。 (p(a,a) ∨p(a,b) ∨p(a,c)) ∧ (p(b,a) ∨p(b,b) ∨p(b,c)) ∧(p(c,a) ∨p(c,b) ∨p(c,c))

11.设谓词的个体域为{a,b,c}，将表达式?xR(x)??xS(x)中的量词消除，写成与之等价的

命题公式是____________。(R(a) ∧R(b) ∧R(c) )∧(S(a) ∨S(b) ∨S(c))

12．谓词公式?x（P(x)∨Q（x）），其中P(x)：x＝1, Q（x）：x＝2，当个体域为{1，2}时，

该公式的真值为________，当个体域为{0，1，2}时，其真值为________。（T，F） 13．有公式A=(?x)(?y)P(x,y)，给定解释I：个体域为实数，P(x,y)：x>y，则A的真值为 。（T）

14.一阶逻辑公式?x(F(x)∧?yG(x,y,z))→?zH(x,z)的自由变元是__________。（x,z） 15．公式?x?y(P(x,y)?Q(y))??xP(x,y)中?x的辖域是?y(P(x,y)?Q(y))，?x的辖域是

P(x,y)。

16.谓词公式?xP(x)??xQ(x)的前束范式是_____________。?x?y(P(x)? Q(y))

第三章 集合的运算

16．A，B是两个集合，A＝{1，2，3，4}，B＝{2，3，5}，则B－A＝{5}，P（B）－P（A）＝

{{5},{2,5},{3,5},{2,3,5}}，P（B）中的元素个数为 8 。

17．全集E＝{1，2，3，4，5}，A＝{1，5}，B＝{1，2，3，4}，C＝{2，5}，则A ? ? B＝

{5}，P（A）? P（C）＝{?,{5}}。

18．设集合A＝{a,b,c}，B＝{b,c,d}，则A⊕B＝_______________。{a,d}

19．设全集E＝{男女合班学生}，子集A＝{男学生}，B＝{戴眼镜的学生}，则A∪B＝__男学

生或者戴眼镜的女学生___，?A∪B＝___女学生或者戴眼镜的男学生__。 第四章 二元关系

20.设集合A＝{1，2},B＝{a,b,c}则A×B＝{<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>}。 21.设f＝{<1，2>，<2，2>，<3，4>}，g＝{<2，5>，<3，1>，<4，2>}，则f?g＝

____________________。{<3,2>,<4,2>}

22．设A、B为非空集合，|A|＝m , |B|＝n ,那么从A到B的不同函数有__n_个。 23．设A＝{a,b,c}，B＝{1,2,3}，则A到B共可产生__6______个不同的双射函数。 24．设f,g都是R到R的映射，其中

g?f?1?1m

f(x)?x?3，g(x)?2x?1，则f?g?f?1?g(x)?__2x-4___，

(x)＝___2x-7_______，＝__2x-10___。

25．设二元关系R＝{<1，2>，<1，3>,<2，4>，<3，2>，<3，3>}，则domR＝_{1,2,3}__，ranR

(x)f?1＝___{2,3,4}_______。

26.Z是整数集合，R是Z上的整除关系，则R具有的性质是___自反性、反对称性和传递性__。 27．设集合A＝{1，2，3}上的二元关系R＝{<1，1>，<1，2>，<2，1>，<2，2>，<3，3>}则

R具有___自反性、对称性和传递性_____性。（自反性、对称性和传递性）

28．设集合A＝{a,b,c,d}，A上的二元关系R＝{,,}，则二元关系R＝

___{,}_________。

29．某集合A上的二元关系R具有对称性，反对称性，自反性和传递性，则此关系R＝_IA_（恒等关系）______。

30.设R是集合A上的二元关系，如果关系R同时具有___自反__性、对称性和___传递__性，

则称R是等价关系。

31．设A＝{a，b，c}，则A上共有____19_____个不同的偏序关系。

32．设f?g是一个复合函数，若f和g都是双射的，则f?g是__双射________

第七章 图的基本概念

33.设G1,G2,G3,G4都是有4结点3条边的无向简单图，则它们之间至少有___2___个是同构

的。

34．设K5是有5个点的完全图，则K5共有____10________条边． 35．在任何图G＝中，奇度结点必有________个。 （偶数） 36.三个结点可构成________个不同构的简单图。（4）

237．设图G＝，若|V|＝1，|E|＝0，则称图G为____平凡图（更准确）_。（零图） 38.设G是一个具有n个顶点的无向完全图，则G有__ n(n-1)/2___条边，所有结点的总度数

为__n(n-1)___。

第八章 特殊的图

39．无向图G具有一条欧拉回路，当且仅当G是__连通图_____，并且所有结点的度数都是___

偶数____。

40．无向图G具有一条欧拉通路，当且仅当G是___连通图_____，且______恰好有两个奇度

定点________。

41．设图G＝为无向简单图，且|V|≥3，若图G中每个结点的度都_________________，

则图G是哈密尔顿图。（?n2）

42．若图G＝是哈密尔顿图，则对于结点集V的每个非空子集S，均有w(G－S)≥|S|，

其中w(G－S)是图G－S的_____________。（连通分枝数）

43.设非连通平面图G有两个连通分支，若G有12个顶点15条边，则G中面的个数为__6_____。 44．简单图G为二部图，当且仅当图G中所有基本回路的长度均为_______。（偶数）

第九章 树

45．设树T有m个顶点，n条边，则T中顶点与边的关系为___m=n+1_________。

46.设G是n阶无向连通带权图，各条边的权均为a(a>0),设T是G的一棵最小生成树，则T

的权W(T)=____a(n-1)_________。

47.设G是二元正则树，G有15个点，其中8个叶结点，则G的总度数为_____28______。 48．以1，1，1，1，2，2，4为无向树的度数列，可以生成___2______棵非同构的无向树。 49.设连通无向图G＝,|V|＝n ,|E|＝m ，T是G的任何一棵生成树，则T的弦有

__m-n+1___条。

50．设树T有1个2度顶点和2个3度顶点，其余的顶点都是树叶，则T中有___6___条边。

本文来源：https://www.bwwdw.com/article/rvn.html