1.数理逻辑习题离散数学

第1章 命题逻辑⼀、单项选择题

1. 下列命题公式等值的是( )

B B A A Q P Q Q P Q B A A B A A Q P Q P ),()D (),()

C ()(),()B (,)A (∧∨?∨∨?∨→→→?→→∨?∧? 2. 设命题公式G ：)(R Q P ∧→?,则使公式G 取真值为1的P ，Q ，R 赋值分别是 ( )0,0,1)D (0,1,0)C (1,0,0)B (0,0,0)A (3. 命题公式Q Q P →∨)(为 ( )

(A) ⽭盾式 (B) 仅可满⾜式 (C) 重⾔式 (D) 合取范式4 命题公式)(Q P →?的主析取范式是( )．(A) Q P ?∧ (B) Q P ∧? (C) Q P ∨? (D) Q P ?∨5. 前提条件P Q P ,?→的有效结论是( )．(A) P (B) ?P (C) Q (D)?Q

6. 设P ：我将去市⾥，Q ：我有时间．命题“我将去市⾥，仅当我有时间时”符号化为( )

Q P Q P Q P P Q ?∨??→→)D ()C ()B ()A (

⼆、填空题 1. 设命题公式G ：P →?(Q →P )，则使公式G 为假的真值指派是2. 设P ：我们划船，G ：我们跑步，那么命题“我们不能既划船，⼜跑步”可符号化为3. 含有三个命题变项P ，Q ，R 的命题公式P ∧Q 的主析取范式是

4. 若命题变元P ，Q ，R 赋值为(1,0,1)，则命题公式G ＝)())((Q P R Q P ∨??→∧的真值是

5. 命题公式P →?(P ∧Q )的类型是 ．

6. 设A ，B 为任意命题公式，C 为重⾔式，若C B C A ∧?∧，那么B A ?是 式(重⾔式、⽭盾式或可满⾜式)三、解答化简计算题

1. 判别下列语句是否命题？如果是命题，指出其真值.(1) 中国是⼀个⼈⼝众多的国家. (2) 存在最⼤的质数.(3) 这座楼可真⾼啊！ (4) 请你跟我⾛! (5) ⽕星上也有⼈.

2.作命题公式))(()(P Q P Q P ∨∧→→的真值表，并判断该公式的类型．3. 试作以下⼆题：(1) 求命题公式(P ∨?Q )→(P ∧Q )的成真赋值．(2) 设命题变元P ,Q ,R 的真值指派为(0,1,1),求命题公式))()(()(Q R Q P R P →?∨→?∧?的真值．4. 化简下式命题公式))()((P Q P Q P ∧?∧?∨∧5. 求命题公式))()((Q P P Q P ∧?∧→→的主合取范式.

6. 求命题公式)()(Q P Q P ?→∧→?的主析取范式，并求该命题公式的成假赋值．7. 求命题公式)()(Q P Q P ?∨?∧∧的真值表.

四、证明题

1. 证明S S P R R Q Q P ∨∧?∧∨?∧→)()()(2. 构造推理证明：S R Q P R S Q P →?∧→∧→→)())((

3. 证明命题公式)()(Q R Q P →∨→与Q R P →∧)(有相同的主析取范式．参考答案

⼀、1. C 2. D 3. B 4. A 5. D 6. B

⼆、1. 1,0；1,1 2. )(Q P ∧?或Q P ?∨? 3. (P ∧Q ∧R )∨(P ∧Q ∧?R )4. 0

5. ⾮永真式的可满⾜式6. 重⾔

三、1. (1) 是命题，真值为1. (2) 是命题，真值为0. (3), (4)不是命题. (5) 是命题.1. 判别下列语句是否命题？如果是命题，指出其真值.(1) 中国是⼀个⼈⼝众多的国家. (2) 存在最⼤的质数.(3) 这座楼可真⾼啊！ (4) 请你跟我⾛! (5) ⽕星上也有⼈.2. 命题公式))(()(P Q P Q P ∨∧→→的真值表

原式为可满⾜式.

3. (1) (P ∨?Q )→(P ∧Q )?(?P ∧Q )∨(P ∧Q )?(?P ∨P )∧Q ?Q可见(P ∨?Q )→(P ∧Q )的成真赋值为(0,1)，(1,1)．(2) ))()(()(Q R Q P R P →?∨?→?∧?0))10()01(()10(?→∨→∧??4. ))()((P Q P Q P ∧?∧?∨∧P Q P Q P ∧?∧?∨∧?)()()()(P P Q P Q P ∧?∧?∨∧∧?0)(∨∧?Q PQ P ∧?

5. ))()((Q P P Q P ∧?∧→→))()((Q P P Q P ∧?∧∨?∨??)())(Q P P Q P Q P ∧?∧∨∧?∧?∨??)00(∧∨??P)(Q Q P ?∧∨??

)()(Q P Q P ?∨?∧∨?? 6. )()()()(Q P Q P Q P Q P ?∨?∧?∧??→∧→?Q P ?∧?

因为成真赋值是（1，0），故成假赋值为（0，0），（0，1），（1，1）7.

四、证明题

1. 证明S S P R R Q Q P ∨∧?∧∨?∧→)()()(①?Q ∨R P②?R P

③?Q T ①，②析取三段论④P →Q P

⑤P ? T ③，④拒取式⑥P ∨?S P

⑦?S ⑤，⑥析取三段论

2. 构造推理证明：S R Q P R S Q P →?∧→∧→→)())((.前提：Q P R S Q P ,)),((→→→结论：S R →证明：① R 附加前提② R →P 前提引⼊③ P ①，②假⾔推理④P →(Q →S ) 前提引⼊⑤ Q →S ③,④假⾔推理⑥ Q 前提引⼊⑦ S ⑤,⑥假⾔推理

3. 证明命题公式)()(Q R Q P →∨→与Q R P →∧)(有相同的主析取范式． 证明.⽅法1．)()(Q R Q P →∨→?)()(Q R Q P ∨?∨∨?∨∧??Q R P )(Q R P →∧)(

因为两命题公式等值，由主合取范式的惟⼀性，可知两命题公式的主合取范式是相同．R P →∧)(有相同的主析取范式． ⽅法2．)()(Q R Q P →∨→?)()(Q R Q P ∨?∨∨?R Q P Q R P ?∨∨??∨?∨??

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

因为它们的主合取范式相同，可知它们的主析取范式也相同．第2章谓词逻辑

证明命题公式)()(Q R Q P →∨→与Q 3 ⼀、 单项选择题

1. 谓词公式)())()((x Q y yR x P x →?∨?中量词?x 的辖域是( )(A) ))()((y yR x P x ?∨? (B) P (x ) (C) )()(y yR x P ?∨ (D) )(x Q2. 谓词公式?xA (x )∧??xA (x )的类型是（ ）(A) 永真式 (B) ⽭盾式

(C) ⾮永真式的可满⾜式 (D) 不属于(A ),(B ),(C )任何类型3 设个体域为整数集，下列公式中其真值为1的是( )(A) )0(=+??y x y x (B) )0(=+??y x x y(C))0(=+??y x y x (D) )0(=+y x y x

4 设L (x )：x 是演员，J (x )：x 是⽼师，A (x ,y )：x 佩服y. 那么命题“所有演员都佩服某些⽼师”符号化为( )

(A) ),()(y x A x xL →? (B) ))),()(()((y x A y J y x L x ∧?→?

(C) )),()()((y x A y J x L y x ∧∧?? (D) )),()()((y x A y J x L y x →∧?? 5. 设个体域是整数集合，P 代表?x ?y ((x(A) P 是真命题 (B) P 是逻辑公式，但不是命题(C) P 是假命题 (D) P 不是逻辑公式

6. 表达式))(),(())(),((z zQ y x R y z Q y x P x ?→?∧∨?中x ?的辖域是( ) (A) P (x ,y ) (B)R (x ,y ) (C)P (x ,y )∧R (x ,y ) (D) P (x ,y)∨Q (z )⼆、 填空题

1. 设个体域D ＝{1,2},那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 .2. 设个体域D ＝{a ,b },公式)),()((y x yH x G x ?→?消去量词化为

3. 设N (x )：x 是⾃然数，Z (y )；y 是整数，则命题“每个⾃然数都是整数，⽽有些整数不是⾃然数”符号化为参考答案

⼀、1. C ；2.. B ；3 A ；4. B ；5. A 6. D

⼆、1. A (1)∨A (2)∨(B (1)∧B (2)) 2. (G (a )→(H (a ,a )∨H (a ,b )))∧ (G (b )→(H (b ,a )∨H (b ,b ))) 3. ))()(())()((x N x Z x x Z x N x∧?∧→?