命题逻辑的推理理论.ppt

.
第三章 命题逻辑的推理理论
推理的形式结构
自然推理系统P
.
关于“推理”
推理：指从前提出发推出结论的思维过程，
前提是已知命题公式集合，
结论是从前提出发应用推理规则推出的命题公式。
数理逻辑的主要任务是用数学的方法来研究数学中的推理。
.
推理的形式结构—问题的引入
推理举例:
(1) 正项级数收敛当且仅当部分和上有界.
(2) 若AÈCÍBÈD，则AÍB且CÍD.
推理: 从前提出发推出结论的思维过程
上面(1)是正确的推理，而(2)是错误的推理.
证明: 描述推理正确或错误的过程.
.
推理的形式结构
定义 设A1，A2 ，…，Ak，B都是命题公式,
若对于A1，A2 ，…，Ak，B中出现的命题变
项的任意一组赋值，A1ÙA2Ù…Ù Ak 均为假，
或当A1ÙA2Ù…ÙAk为真时, B也为真, 则称由
A1,A2,…, Ak推B的推理正确 ,并称B是有效的
结论； 否则推理不正确（错误）.
.
说明（1）：
由前提A1，A2 ，…，Ak推结论B的推理是否正确与诸前提的排列次序无关。
因而前提中的公式不一定是序列，而是一个有限公式集合，记为 Г。
可将由Г推B的推理记为Г┞B，若推理是正确的，则记为Г|=B，否则记为 Г| B。
这里可以称Г┞B 和{A1，A2 ，…，Ak} ┞B 为推理的形式结构。
.
说明（2）
设A1，A2 ，…，Ak，B中共出现n个命题变项，对于任一组赋值 a1a2…an （ai＝0或1， i＝1，2，…n），前提和结论的取值情况有以下四种：
（1） A1ÙA2Ù…ÙAk 为0，B为0；
（2） A1ÙA2Ù…ÙAk 为0，B为1；
（3） A1ÙA2Ù…ÙAk 为1，B为0；
（4） A1ÙA2Ù…ÙAk 为1，B为1。
由定义可知，只要不出现（3）中的情况，推理就是正确的，因而判断推理正确与否，就是判断是否会出现（3）中的情况。
.
判断下列推理是否正确
（1） {p， p ® q } ┞ q
（2） {p， q ® p } ┞ q
解：只要写出前提的合取式与结论的真值表，看是否出现前提为真，而结论为假的情况即可。
由下面真值表可看出，（1）推理正确，（2）推理不正确。
.
p q p Ù（ p ® q ） q
0 0 0 0
0 1 0 1
1 0 0 0
1 1 1 1
p q p Ù（ q ® p ） q
0 0 0 0
0 1 0 1
1 0 1 0
1 1 1 1
.
命题公式A1，A2 ，…，Ak推B的推
理正确当且仅当：
（A1ÙA2Ù…ÙAk ）® B 为重言式。
证明：必要性
若命题公式A1，A2 ，…，Ak推B的推
理正确，则不会出现A1ÙA2Ù…ÙAk为真，
而B为假的情况，因而在任何赋值下，
蕴涵式（A1ÙA2Ù…ÙAk ）® B 均为真，故
为重言式。
.
证明：充分性
若蕴涵式（A1ÙA2Ù…ÙAk ）® B 为
重言式，则对于任何赋值此重言式均为真，
因而不会出现前件为真后件为假的情况。即
在任何赋值下，或者A1ÙA2Ù…ÙAk为假，
或者A1ÙA2Ù…ÙAk和B同时为真，这正符合
。