离散数学考试题及答案

离散数学 考试题(后附详细答案)

一、命题符号化（共6小题，每小题3分，共计18分） 1. 用命题逻辑把下列命题符号化

a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。 设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（?P?Q）?(P?R?S)

b) 我今天进城，除非下雨。 设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：?Q→P或?P→Q c) 仅当你走，我将留下。 设P表示命题“你走”，Q表示命题“我留下”，命题符号化为： Q→P 2. 用谓词逻辑把下列命题符号化 a) 有些实数不是有理数 设R(x)表示“x是实数”，Q(x)表示“x是有理数”，命题符号化为：

?x(R(x) ??Q(x)) 或 ??x(R(x) →Q(x))

b) 对于所有非零实数x，总存在y使得xy=1。 设R(x)表示“x是实数”，E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为： ?x(R(x) ??E(x,0) →?y(R(y) ?E(f(x,y),1))))

c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=

离散数学 考试题(后附详细答案)

一、命题符号化（共6小题，每小题3分，共计18分） 1. 用命题逻辑把下列命题符号化

a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。 设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（?P?Q）?(P?R?S)

b) 我今天进城，除非下雨。 设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：?Q→P或?P→Q c) 仅当你走，我将留下。 设P表示命题“你走”，Q表示命题“我留下”，命题符号化为： Q→P 2. 用谓词逻辑把下列命题符号化 a) 有些实数不是有理数 设R(x)表示“x是实数”，Q(x)表示“x是有理数”，命题符号化为：

?x(R(x) ??Q(x)) 或 ??x(R(x) →Q(x))

b) 对于所有非零实数x，总存在y使得xy=1。 设R(x)表示“x是实数”，E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为： ?x(R(x) ??E(x,0) →?y(R(y) ?E(f(x,y),1))))

c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=

离散数学 考试题(后附详细答案)

一、命题符号化（共6小题，每小题3分，共计18分） 1. 用命题逻辑把下列命题符号化

a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。 b) 我今天进城，除非下雨。 c) 仅当你走，我将留下。 2. 用谓词逻辑把下列命题符号化 a) 有些实数不是有理数

b) 对于所有非零实数x，总存在y使得xy=1。

c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b. 二、简答题（共6道题，共32分）

1. 求命题公式(P→(Q→R))?(R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋

值。（5分） 2. 设个体域为{1,2,3}，求下列命题的真值（4分） a) ?x?y(x+y=4)

b) ?y?x (x+y=4)

3. 求?x(F(x)→G(x))→(?xF(x)→?xG(x))的前束范式。（4分） 4. 判断下面命题的真假，并说明原因。（每小题2分，共4分） a) （A?B）－C=(A-B) ?(A-C)

b) 若f是从集合A到集合B的入射函数，则|A|≤|B| 5. a) b) 6.

设A是有穷集，|A|=5，问（每小题2分，共4分） A上有多少种不同的等价关系？

离散数学考试试题(A卷及答案）

一、证明题（10分）

1) (P∧Q∧A?C)∧(A?P∨Q∨C)? (A∧(P?Q))?C。P<->Q=(p->Q)合取（Q->p）

证明: (P∧Q∧A?C)∧(A?P∨Q∨C)

?(?P∨?Q∨?A∨C)∧(?A∨P∨Q∨C)

?((?P∨?Q∨?A)∧(?A∨P∨Q))∨C反用分配律 ??((P∧Q∧A)∨(A∧?P∧?Q))∨C

??( A∧((P∧Q)∨(?P∧?Q)))∨C再反用分配律 ??( A∧(P?Q))∨C ?(A∧(P?Q))?C

2) ?(P?Q)? ?P??Q。

证明：?(P?Q)??(?(P∧Q))??(?P∨?Q))??P??Q。

二、分别用真值表法和公式法求(P?(Q∨R))∧(?P∨(Q?R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。

主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。 主析取范式可由 析取范式经等值演算法算得。 证明：

公式法：因为(P?(Q∨R))∧(?P∨(Q?R))

?(?P∨Q∨R)∧(?P∨(Q∧R)∨(?Q∧?R))

?(?P∨Q∨R)∧(((?P∨Q)∧(?P∨R))∨(?Q∧?R))分配律

离散数学考试试题(A卷及答案）

一、证明题（10分）

1) (P∧Q∧A?C)∧(A?P∨Q∨C)? (A∧(P?Q))?C。P<->Q=(p->Q)合取（Q->p）

证明: (P∧Q∧A?C)∧(A?P∨Q∨C)

?(?P∨?Q∨?A∨C)∧(?A∨P∨Q∨C)

?((?P∨?Q∨?A)∧(?A∨P∨Q))∨C反用分配律 ??((P∧Q∧A)∨(A∧?P∧?Q))∨C

??( A∧((P∧Q)∨(?P∧?Q)))∨C再反用分配律 ??( A∧(P?Q))∨C ?(A∧(P?Q))?C

2) ?(P?Q)? ?P??Q。

证明：?(P?Q)??(?(P∧Q))??(?P∨?Q))??P??Q。

二、分别用真值表法和公式法求(P?(Q∨R))∧(?P∨(Q?R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。

主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。 主析取范式可由 析取范式经等值演算法算得。 证明：

公式法：因为(P?(Q∨R))∧(?P∨(Q?R))

?(?P∨Q∨R)∧(?P∨(Q∧R)∨(?Q∧?R))

?(?P∨Q∨R)∧(((?P∨Q)∧(?P∨R))∨(?Q∧?R))分配律

1. 写出命题公式 ﹁（P →（P∨ Q））的真值表。

P?Q?(P?Q)?(?P??Q)2.证明

3. 证明以下蕴涵关系成立： ?P?(P?Q)?Q

4. 写出下列式子的主析取范式： ?(P?Q)?(P?R)

5. 构造下列推理的论证：p∨q, p→?r, s→t, ?s→r, ?t ? q

6. 用反证法证明：p→(?(r∧s)→?q), p, ?s ? ?q

7. 请将下列命题符号化：

所有鱼都生活在水中。

8. 请将下列命题符号化：

存在着不是有理数的实数。

9. 请将下列命题符号化：

尽管有人聪明，但并非一切人都聪明。

10. 请将下列命题符号化：

对于所有的正实数x,y，都有x+y≥x。

11. 请将下列命题符号化：

每个人都要参加一些课外活动。

12. 请将下列命题符号化：

某些人对某些药物过敏。 13. 求?y(P(x)?Q(y))??yR(y)的对偶式:

14. 求下列谓词公式的前束范式： ?x?y(?zP(x,z)?P(y,z))??uQ(x,y,u)

15. 证明：

16. 用反证法

一、填空题

1 设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; (B)＝ __________________________ .

2. 设有限集合A, |A| = n, 则 | (A×A)| = __________________________.

3. 设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________.

4. 已知命题公式G＝ (P Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________.

6 设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A B＝_________________________; A B＝_________________________;A－B＝ _____________________

《离散数学》试题及答案

一、填空题

1 设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝ {3} ; {3},{1,3},{2,3},{1,2,3}} .

2. 设有限集合A, |A| = n, 则 |?(A×A)| = 2 .

3. 设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是?1= {(a,1), (b,1)}, ?2= {(a,2), (b,2)},?3= {(a,1), (b,2)}, ?4= {(a,2), (b,1)}, 其中双射的是 ?3, ?4 .

4. 已知命题公式G＝?(P?Q)∧R，则G的主析取范式是 (P∧?Q∧R) 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为 12 ，分枝点数为 3 .

6 设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝ {4} ; A?B＝{1,2,3,4}; A－B＝ {1,2} .

7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是 自反性 , 对

一、填空题

1 设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝__{3}__________________;

?(A) - ?(B)＝ ___________________{3},{1,3},{2,3},{123}______ .

2. 设有限集合A, |A| = n, 则 |?(A×A)| = _____2^(n^2)_____________________.

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}

《离散数学》试题及答案

一、填空题

1 设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝ {3} ; {3},{1,3},{2,3},{1,2,3}} .

2. 设有限集合A, |A| = n, 则 |?(A×A)| = 2 .

3. 设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是?1= {(a,1), (b,1)}, ?2= {(a,2), (b,2)},?3= {(a,1), (b,2)}, ?4= {(a,2), (b,1)}, 其中双射的是 ?3, ?4 .

4. 已知命题公式G＝?(P?Q)∧R，则G的主析取范式是 (P∧?Q∧R) 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为 12 ，分枝点数为 3 .

6 设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝ {4} ; A?B＝{1,2,3,4}; A－B＝ {1,2} .

7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是 自反性 , 对