离散数学题目及答案蔡英

数理逻辑习题

判断题

1．任何命题公式存在惟一的特异析取范式 （ √ ） 2． 公式p?(?p?q)是永真式 （ √ ） 3．命题公式(p?q)?p是永真式 （ √ ） 4．命题公式p??q?r的成真赋值为010 （ × ） 5．?xA(x)?B??x(A(x)?B) （ √ ）

6．命题“如果1＋2＝3，则雪是黑的”是真命题 （ × ） 7．p?(p?q)?p （ √ ）

8．?x(F(x)?G(x))是永真式 （ × ） 9．“我正在撒谎”是命题 （ × ） 10． ?xF(x)??xG(x)是永真式（ √ ）

11．命题“如果1＋2＝0，则雪是黑的”是假命题 （ × ） 12．p?(p?q)?p （ √ ）

13．?x(F(x)?G(x))是永假式 （ × ）

14．每个命题公式都有唯一的特异（主）合取范式 （ √ ） 15．若p:雪是黑色的，则公式p?q是永真式 （ √ ） 16．每个逻辑公式都有唯一的前束范式 （ × ） 17．公式p?q的特异（主）析取式为?p?q （ × ） 18．命题公式 ?p?(q?r)的成假赋值是110 （ √ ） 19．一阶逻辑公式?x(F(x)?G(x,y))是闭式（ × ）

单项选择题

数理逻辑习题

判断题

1．任何命题公式存在惟一的特异析取范式 （ √ ） 2． 公式p?(?p?q)是永真式 （ √ ） 3．命题公式(p?q)?p是永真式 （ √ ） 4．命题公式p??q?r的成真赋值为010 （ × ） 5．?xA(x)?B??x(A(x)?B) （ √ ）

6．命题“如果1＋2＝3，则雪是黑的”是真命题 （ × ） 7．p?(p?q)?p （ √ ）

8．?x(F(x)?G(x))是永真式 （ × ） 9．“我正在撒谎”是命题 （ × ） 10． ?xF(x)??xG(x)是永真式（ √ ）

11．命题“如果1＋2＝0，则雪是黑的”是假命题 （ × ） 12．p?(p?q)?p （ √ ）

13．?x(F(x)?G(x))是永假式 （ × ）

14．每个命题公式都有唯一的特异（主）合取范式 （ √ ） 15．若p:雪是黑色的，则公式p?q是永真式 （ √ ） 16．每个逻辑公式都有唯一的前束范式 （ × ） 17．公式p?q的特异（主）析取式为?p?q （ × ） 18．命题公式 ?p?(q?r)的成假赋值是110 （ √ ） 19．一阶逻辑公式?x(F(x)?G(x,y))是闭式（ × ）

单项选择题

《离散数学》题库答案

一、选择或填空 （数理逻辑部分）

1、下列哪些公式为永真蕴含式？( )

(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），（5），（6）

4、公式?x((A(x)?B(y，x))? ?z C(y，z))?D(x)中，自由变元是( 变元是( )。

答：x,y, x,z

5、判断下列语句是不是命题。若是，给出命题的真值。( (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。

1

)，约束)

(3) 你喜欢唱歌吗？ (4) 若7+

离散数学试题1

一、单项选择题(本大题共15小题，每小题1分，共15分)

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列句子为命题的是( ) A.走，看电影去

C.空集是任意集合的真子集

B.x+y>0 D.你明天能来吗?

2.下列式子不是谓词合式公式的是( ) ．．A.(?x)(P(x)→(?x)(Q(x) ∧A(x，y))) C.(?x)P(x)→R(y)

3.下列式子为重言式的是( ) A.P→P∨Q C.﹁ (P Q)

B.(﹁P∧Q)∧(P∨﹁Q) D.(P∨Q) (P→Q) B.(?x)∧(?y)∨P(x，y) D.(?x)P(x)∧Q(y，z)

4.设个体域为实数集，特定元素a=0，函数f(x，y)=x-y，特定谓词F(x，y)为x

A.(?x)(?y)F(x，f(f(x，y)，y)) B.(?x)(?y)(﹁F(f(x，y)，x))

C.(?x)(?y)(?z)(F(x，y)→F(f(x，z)，f(y，z))) D.(?x)F(f(a，x)，a)

5.对于公式(?x)(?y)P(x，y)∨Q(x，z)∧(?x)P

一、填空题

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、下列哪些公式为永真蕴含式？( )

(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

《离散数学》题库答案

一、选择或填空 （数理逻辑部分）

1、下列哪些公式为永真蕴含式？( )

(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），（5），（6）

4、公式?x((A(x)?B(y，x))? ?z C(y，z))?D(x)中，自由变元是( 变元是( )。

答：x,y, x,z

5、判断下列语句是不是命题。若是，给出命题的真值。( (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。

1

)，约束)

(3) 你喜欢唱歌吗？ (4) 若7+

《离散数学》试题及答案

一、填空题

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所具有的关系的三个特性是 自反性 , 对