命题逻辑真假判断、重言式判定及自然演绎系统证明

一、请判断下列陈述的真假。

1. 命题是为真的陈述句。（√ ）
2. ¬pq∧pq是一个规范的命题公式。（×）
3. 一个析取式为假，当且仅当至少一个析取支为假。（√ ）
4. 一个合取式为假，当且仅当所有合取支都是假的。（√ ）
5. A∧B→¬C和¬A∨¬BC是逻辑等值的。（√ ）
6. 命题'如果学生聪明且勤奋，那么学生考试会及格'与命题'如果学生考试不及格，那么学生不聪明且不勤奋'是逻辑等值的。（√ ）
7. 命题'如果学生聪明且勤奋，那么学生考试会及格'与命题'如果学生聪明，那么如果学生勤奋考试就会及格'是逻辑等值的。（√ ）
8. 如果用简化真值表方法没有推出矛盾，则待验证命题公式是矛盾式。（×）
9. 一个推理是有效的，当且仅当其前提和结论都为真。（×）
10. 一个推理是有效的，当且仅当其前提的合取和结论构成的蕴涵命题公式是重言式。（√ ）
11. NP中证明的层数取决于引入假设的个数。（√ ）
12. 如果在一个证明中引入假设，则最后要通过联结词规则把该假设消除。（√ ）
13. 自然演绎系统下的证明是从前提到结论的等价推理过程。（√ ）
14. 一个推理是有效的，则其在NP系统中是可证明的。（√ ）

二、请用简化真值表方法判断下列命题公式是否为重言式。

1. (pq)∧(¬q∨r)∧¬r∧(¬s∨p)¬s 简化真值表如下： p | q | r | s | (pq)∧(¬q∨r)∧¬r∧(¬s∨p)¬s T | T | T | T | F T | T | T | F | F T | T | F | T | F T | T | F | F | F T | F | T | T | F T | F | T | F | F T | F | F | T | F T | F | F | F | F F | T | T | T | F F | T | T | F | F F | T | F | T | F F | T | F | F | F F | F | T | T | F F | F | T | F | F F | F | F | T | F F | F | F | F | F 根据简化真值表，该命题公式不是重言式。

2. (f∨g(q(ik)))∧q∧(q∨mf)(ik) 简化真值表如下： f | g | q | m | q(ik) | (f∨g(q(ik)))∧q∧(q∨mf)(ik) T | T | T | T | T | T T | T | T | T | F | F T | T | T | F | T | T T | T | T | F | F | F T | T | F | T | T | F T | T | F | T | F | F T | T | F | F | T | F T | T | F | F | F | F T | F | T | T | T | T T | F | T | T | F | F T | F | T | F | T | T T | F | T | F | F | F T | F | F | T | T | F T | F | F | T | F | F T | F | F | F | T | F T | F | F | F | F | F F | T | T | T | T | T F | T | T | T | F | F F | T | T | F | T | T F | T | T | F | F | F F | T | F | T | T | F F | T | F | T | F | F F | T | F | F | T | F F | T | F | F | F | F F | F | T | T | T | T F | F | T | T | F | F F | F | T | F | T | F F | F | T | F | F | F F | F | F | T | T | F F | F | F | T | F | F F | F | F | F | T | F F | F | F | F | F | F 根据简化真值表，该命题公式不是重言式。

四、请在NP系统中证明下列推理。

1. A(BC)B(AC) 证明：

   1. A(BC) 假设
   2. BC 通过合取分离规则，从1中得出
   3. B 通过合取消去规则，从2中得出
   4. AC 通过合取消去规则，从1中得出
   5. B(AC) 通过合取结合规则，从3和4中得出
   6. A(BC)B(AC) 通过假设引入规则，从1和5中得出

2. (A∨B)(C∧D),C((F∨¬F)G)¬A∨G 证明：

   1. (A∨B)(C∧D) 假设
   2. C∧D 通过合取分离规则，从1中得出
   3. C 通过合取消去规则，从2中得出
   4. (F∨¬F)G 假设
   5. G 通过合取消去规则，从4中得出
   6. F∨¬F 通过合取消去规则，从4中得出
   7. A∨B 通过合取分离规则，从1中得出
   8. ¬A∨G 通过合取消去规则，从7和5中得出
   9. C((F∨¬F)G)¬A∨G 通过假设引入规则，从3，6，8中得出

3. A(BA) 证明：

   1. A 假设
   2. BA 假设
   3. A 通过合取消去规则，从2中得出
   4. A(BA) 通过假设引入规则，从2和3中得出

4. (¬AB)((¬A¬B)A) 证明：

   1. ¬AB 假设
   2. (¬A¬B)A 假设
   3. ¬A 通过合取消去规则，从2中得出
   4. ¬AB 通过合取消去规则，从1中得出
   5. (¬AB)((¬A¬B)A) 通过假设引入规则，从1和4中得出