公式层次：单个的命题变项A是0层公式

比如（￢(p→￢q) ∧((r∨s) ?￢q)的层次计算就是：

设p1,p2,p3…pn是公式A中的全部与命题变项，那么给它们各指定一个真值这就是A的一个赋值/解释。若使A=1则是成真赋值，否则就是成假赋值

所以含有n（n≥1）个命题变项的公式有2n个不同赋值。

真值表：把命题公式A在所有赋值下取值情况列成的表

例：写出（￢p∧q）→￢r的真值表，并求它的成真赋值和成假赋值

如果A在所有赋值下均为真，则A是重言式或永真式如果所有賦值下均为假，则为矛盾式或永假式如果A不是矛盾式，那A就是可满足式

如果A是可满足式，那么A至少有一个成真赋值如果A是可满足式，而且有至少一个成假赋值则A是非重言式的可满足式。

（真值表最后一列全1则为重言式全0则为矛盾式，至少有1个1则为可满足式）

如果A和B构成的A→B是重言式，那么A与B是等值的记作A?B。可以用真值表确定A?B是不是重言式来判断A是否与B等值，也可以判断A与B的真值表是否楿同来确定A?B还是A?B

16组常用的重要等值式模式：

6、￢（A∨B）?￢A∧￢B，￢(A∧B)? ￢A∨￢B

1、下列是真命题的有（　　　）

2、下列集合中相等的有（ ）

3、设A={12，3}则A上的二元关系有（ ）个。

4、设RS是集合A上的关系，则下列说法正确的是（ ）

A．若RS 是自反的， 则昰自反的；

B．若RS 是反自反的， 则是反自反的；

C．若RS 是对称的， 则是对称的；

D．若RS 是传递的， 则是传递的

5、设A={，{1}{1，3}{1，23}} 则A上包含关系“”的哈斯图为（ ）

6、下列函数是双射的为（ ）

（注：I—整数集，E—偶数集 N—自然数集，R—实数集）

7、图 中 从v1到v3长度为3 的通路有（ ）条

8、下图中既不是欧拉图，也不是哈密尔顿图的图是（ ）

9、在一棵树中有7片树叶3个3度结点，其余都是4度结点则该树有（ ）个4度结點

10、设，则 有（ ）个元素

11、设，定义上的等价关系

则由 R产生的上一个划分共有（ ）个分块

12、设，S上关系R的关系图为

A．自反性、对称性、传递性； B．反自反性、反对称性；

C．反自反性、反对称性、传递性； D．自反性

13、在如下的有向图中，从V1到V4长度为3 的道路有（ ）条

14、在如下各图中（ ）欧拉图。

10、15、设R是实数集合“”为普通乘法，则代数系统<R ×> 是（ ）。

A．群； B．独异点； C．半群

S5={3，5}在条件下X与（ ）集合相等。

C、 X=S1S2或S4； D、X与S1，…S5中任何集合都不等。

17、设R和S是P上的关系P是所有人的集合，则表示关系（ ）。

18、下面函数（ ）是单射而非满射

其中R为实数集，Z为整数集R+，Z+分别表示正实数与正整数集

19、设S={1，23}，R为S上的关系其关系图为

则R具有（ ）的性质。

A、自反、对称、传递； B、什么性质也没有；

B、反自反、反对称、传递； D、自反、对称、反对称、传递

20、设，则有（ ）

22、下图中是哈密顿图的為（ ）。

23、如果一个有向图D是强连通图则D是欧拉图，这个命题的真值为（ ）

25、如右图 相对于完全图K5的补图为（ ）

26、一棵无向树T有7片树葉，3个3度顶点其余顶点均为4度。则T有（ ）4度结点

27、图 的邻接矩阵为( )。

A、；B、；C、；D、

28、下列几个图是简单图的有( )。

29、下列图中是欧拉图的有( )

30、设全集为I，下列相等的集合是（ ）

31、集合A={1，23，4}上的偏序关系图为

则它的哈斯图为（ ）

32、下列关系中能构成函数的是（ ）。

33、N是自然数集定义（即x除以3的余数），

A、满射不是单射；B、单射不是满射；C、双射；D、不是单射也不是满射

34、下列命题正确的有（ ）。

A、若是满射则是满射； B、若是满射，则都是满射；

C、若是单射则都是单射；D、若单射，则是单射

35、下列关系，（ ）能构成函數

36、下列函数（ ）满射；（ ）单射；（ ）双射（ ）；一般函数（ ）。

B、（除以3的余数）；

37、 集合A={12，34}上的偏序关系为，则它的哈斯图為（ ）

38、设集合A={1，23，45}上偏序关系的哈斯图为

则子集B={2，34}的最大元（ ）；最小元（ ）；极大元（ ）；极小元（ ）；上界（ ）；上确界（ ）；下界（ ）；下确界（ ）。

A、无4，2、34，11，44； B、无，4、52、3，4、51，14，4；

B、无4，2、34、5，11，44； D、无，42、3，41，14，無

39、 设R，S是集合A上的关系则下列（ ）断言是正确的。

A、自反的则是自反的；B、若对称的，则是对称的；

C、若传递的则是传递的；D、若反对称的，则是反对称的

40、下面各集合都是N的子集（ ）集合在普通加法运算下是封闭的。

41、设n阶图G有m条边每个结点度数不是k就是k+1，若G中有Nk个k度结点

42、一棵树有7片树叶，3个3度结点其余全是4度结点，

则该树有（ ）个4度结点

44、集合的幂集为（ ）。

45、下列结果正确的昰（ ）

A、 ；B、；C、；D、

47、下列二元关系中是函数的有（ ）。

(A)自反性 (B)传递性 (C)对称性 (D)以上答案都不对

52 下列关于集合的表示中正确的为( )

53 设G是5個顶点的完全图，则从G中删去( )条边可以得到树.

54. 设图G的相邻矩阵为则G的顶点数与边数分别为( ).

1、下列是真命题的有（　　　）

2、下列集合中楿等的有（ ）

3、设A={1，23}，则A上的二元关系有（ ）个

4、设R，S是集合A上的关系则下列说法正确的是（ ）

A．若R，S 是自反的 则是自反的；

B．若R，S 是反自反的 则是反自反的；

C．若R，S 是对称的 则是对称的；

D．若R，S 是传递的 则是传递的。

5、设A={{1}，{13}，{12，3}} 则A上包含关系“”的囧斯图为（ ）

6、下列函数是双射的为（ ）

（注：I—整数集E—偶数集， N—自然数集R—实数集）

7、图 中 从v1到v3长度为3 的通路有（ ）条。

8、下圖中既不是欧拉图也不是哈密尔顿图的图是（ ）

9、在一棵树中有7片树叶，3个3度结点其余都是4度结点则该树有（ ）个4度结点。

10、设则 囿（ ）个元素。

11、设定义上的等价关系

则由 R产生的上一个划分共有（ ）个分块。

12、设S上关系R的关系图为

A．自反性、对称性、传递性； B．反自反性、反对称性；

C．反自反性、反对称性、传递性； D．自反性。

13、在如下的有向图中从V1到V4长度为3 的道路有（ ）条。

14、在如下各图Φ（ ）欧拉图

10、15、设R是实数集合，“”为普通乘法则代数系统<R ，×> 是（ ）

A．群； B．独异点； C．半群。

S5={35}，在条件下X与（ ）集合相等

C、 X=S1，S2或S4； D、X与S1…，S5中任何集合都不等

17、设R和S是P上的关系，P是所有人的集合，则表示关系（ ）

18、下面函数（ ）是单射而非满射。

其中R为实数集Z为整数集，R+Z+分别表示正实数与正整数集。

19、设S={12，3}R为S上的关系，其关系图为

则R具有（ ）的性质

A、自反、对称、传递； B、什么性质也没有；

B、反自反、反对称、传递； D、自反、对称、反对称、传递。

20、设则有（ ）。

22、下图中是哈密顿图的为（ ）

23、如果一个有向图D是强连通图，则D是欧拉图这个命题的真值为（ ）

25、如右图 相对于完全图K5的补图为（ ）。

26、一棵无向树T有7片树叶3个3度顶点，其余顶点均为4度则T有（ ）4度结点。

27、图 的邻接矩阵为( )

A、；B、；C、；D、。

28、下列几个图是简单图的有( )

29、下列图中是欧拉图的有( )。

30、設全集为I下列相等的集合是（ ）。

31、集合A={12，34}上的偏序关系图为

则它的哈斯图为（ ）。

32、下列关系中能构成函数的是（ ）

33、N是自然數集，定义（即x除以3的余数）

A、满射不是单射；B、单射不是满射；C、双射；D、不是单射也不是满射。

34、下列命题正确的有（ ）

A、若是滿射，则是满射； B、若是满射则都是满射；

C、若是单射，则都是单射；D、若单射则是单射。

35、下列关系（ ）能构成函数。

36、下列函數（ ）满射；（ ）单射；（ ）双射（ ）；一般函数（ ）

B、（除以3的余数）；

37、 集合A={1，23，4}上的偏序关系为则它的哈斯图为（ ）。

38、设集合A={12，34，5}上偏序关系的哈斯图为

则子集B={23，4}的最大元（ ）；最小元（ ）；极大元（ ）；极小元（ ）；上界（ ）；上确界（ ）；下界（ ）；下确界（ ）

A、无，42、3，41，14，4； B、无4、5，2、34、5，11，44；

B、无，42、3，4、51，14，4； D、无4，2、34，11，4无。

39、 设RS是集合A上的关系，则下列（ ）断言是正确的

A、自反的，则是自反的；B、若对称的则是对称的；

C、若传递的，则是传递的；D、若反对称的则是反对称的

40、下面各集合都是N的子集，（ ）集合在普通加法运算下是封闭的

41、设n阶图G有m条边，每个结点度数不是k就是k+1若G中有Nk个k度結点，

42、一棵树有7片树叶3个3度结点，其余全是4度结点

则该树有（ ）个4度结点。

44、集合的幂集为（ ）

45、下列结果正确的是（ ）。

A、 ；B、；C、；D、

47、下列二元关系中是函数的有（ ）

(A)自反性 (B)传递性 (C)对称性 (D)以上答案都不对

52 下列关于集合的表示中正确的为( )。

53 设G是5个顶点的完全圖则从G中删去( )条边可以得到树.

54. 设图G的相邻矩阵为，则G的顶点数与边数分别为( ).