离散数学第一章命题逻辑的推理理论.ppt

*
第一页，共18页
推理的形式结构—问题的引入
推理举例:
(1) 正项级数收敛当且仅当部分和有上界.
(2) 若AÈCÍBÈD，则AÍB且CÍD.
推理: 从前提出发推出结论的思维过程
上面(1)是正确的推理，而(2)是错误的推理.
证明: 描述推理正确的过程.
*
第二页，共18页
推理的形式结构
定义 若对于每组赋值，或者A1ÙA2Ù…Ù Ak 均为假，
或者当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ÞB.
*
第三页，共18页
判断推理是否正确的方法
真值表法
等值演算法 判断推理是否正确
主析取范式法
构造证明法 证明推理正确
说明：当命题变项比较少时，用前3个方法比较方
便, 此时采用形式结构“ A1ÙA2Ù…ÙAk®B” . 而在构
造证明时，采用“前提: A1, A2, … , Ak, 结论: B”.
*
第四页，共18页
实例
例 判断下面推理是否正确
(1) 若今天是1号，则明天是5号. 今天是1号. 所
以明天是5号.
解 设 p：今天是1号，q：明天是5号.
推理的形式结构为: (p®q)Ùp®q
证明（用等值演算法）
(p®q)Ùp®q
Û Ø((ØpÚq)Ùp)Úq
Û ØpÚØqÚq Û 1
得证推理正确
*
第五页，共18页
实例 (续)
(2) 若今天是1号，则明天是5号. 明天是5号. 所以今天是1号.
解 设p：今天是1号，q：明天是5号.
推理的形式结构为: (p®q)Ùq®p
证明（用主析取范式法）
(p®q)Ùq®p
Û (ØpÚq)Ùq®p
Û Ø ((ØpÚq)Ùq)Úp
Û ØqÚp
Û (ØpÙØq)Ú(pÙØq)Ú (pÙØq)Ú(pÙq)
Û m0Úm2Úm3
结果不含m1, 故01是成假赋值，所以推理不正确.
*
第六页，共18页
推理定律——重言蕴涵式
重要的推理定律
A Þ (AÚB) 附加律
(AÙB) Þ A 化简律
(A®B)ÙA Þ B 假言推理
(A®B)ÙØB Þ ØA 拒取式
(AÚB)ÙØB Þ A 析取三段论
(A®B)Ù(B®C) Þ (A®C) 假言三段论
(A«B)Ù(B«C) Þ (A«C) 等价三段论
(A®B)Ù(C®D)Ù(AÚC) Þ (BÚD) 构造性二难
*
第七页，共18页
推理定律 (续)
(A®B)Ù(ØA®B) Þ B 构造性二难（特殊形式）
(A®B)Ù(C®D)Ù( ØBÚØD) Þ (ØAÚØC)
破坏性二难
说明：
A, B, C为元语言符号
若某推理符合某条推理定律，则它自然是正确的
AÛB产生两条推理定律: A Þ B, B Þ A
*
第八页，共18页
推理规则
(1) 前提引入规则
(2) 结论引入规则
(3) 置换规则
(4) 假言推理规则
A®B
A
\ B
(5) 附加规则
A
\AÚB
(6) 化简规则
AÙB
\A
(7) 拒取式规则
A®B
ØB
\ØA
(8) 假言三段