第6讲推理形式结构.pptVIP

真值表 等值演算 (p∧q)→r? p→(q→r) 解： (p∧q)→r ? ?(p∧q)∨r （蕴涵等值式） ? (?p∨?q)∨r （德●摩根律） ? ?p∨?q∨r （结合律） p→(q→r) ? ?p ∨ (? q∨r) （蕴涵等值式） ? ?p∨?q∨r （结合律） 标准型(范式) ——同一真值函数所对应的所有命题公式具有相同的标准型 析取范式 合取范式 主析取范式(极小项) 主合取范式(极大项) 其他联结词 不可兼或?: p?q ? ┐(p?q ) 蕴涵否定?: p?q ? ┐(p?q ) 与非?: p?q ? ┐(p∧q ) 或非?: p?q ? ┐(p∨q ) 新的联结词都可以用常用的五个联结词表示 其他联结词 不可兼或?,蕴涵否定?,与非?,或非? 联结词完备集举例 {∧，∨，?，→，?}是完备集 {∧，∨，? }是完备集 A?B? (A→B)∧(B→A)　　　　　　　 A→B?┐A∨B {┐，∨}和{┐，∧}都是完备集 A∨B?┐(┐A∧┐B) A∧B?┐(┐A∨┐B) {?，→}是完备集 A∨B ?┐ A→B 非完备集举例 {┐，?}不是完备集 可以归纳证明任何一个仅含“?”和“┐”的二元合式公式真值中1和0 的个数都是偶数。 {?}，{∧}，{∨}， {→}，{?}都不是完备集 {∧ ， ∨ ，→ ，?}不是完备集 联结词完备集举例续2 {┐，?}不是完备集 {┐，→}是完备集 {?}是完备集 p∧q?┐(p↑q) ┐p?p↑p 同理： {?}也是完备集 p∨q?┐(p↓q) ┐p?p↓p 推理 推理：从前提出发推出结论的思维过程 前提：已知命题公式的集合 结论：从前提出发应用推理规则推出的命题公式 推理举例 (1)如果小明认真听讲，那么小明能够得到优秀。小明认真听讲。所以小明能够得到优秀。 解：p:　小明认真听讲　　q:　小明能够得到优秀 前提：p→q　,p 　 结论：q 什么是有效的推理形式？ 直观上，有效的推理应该保证：如果前提正确，则结论也应该正确。 有效的推理 定义： 设A1，A2 ，…， An，B都是合式公式，称推理“A1，A2 ，…， An推出B”是有效的或正确的，如果对A1，A2，…，An， B中出现的命题变元的任一指派, 若A1，A2 ，…， An都真, 则B亦真；否则，称“A1，A2，…， An推出B”是无效的或不合理的。 推理举例2 (2)下午小王或去看电影或去游泳。他没去看电影。所以，他去游泳了。 设： p：小王下午去看电影 q：小王下午去游泳 前提： p ? q， ?p 结论： q 推理举例3 (3) 如果今天是星期日，那么明天是星期一。今天不是星期日。所以明天不是星期一。 解：设　p:今天星期日　　　　q:明天星期一　前提：p→q，┐p　　结论：┐q 说明 推理是否有效与前提中命题公式的排列次序无关。即：若“A1，A2 ，…， An推出B”是有效的，则对1，2，…，n的任一个排列i1, i2, …, in,“ 推出B”也是有效的。 前提是一个集合Γ ＝{A1，A2 ，…， An}，而不是一个序列。 由Γ推出B的推理记为Γ├ B，若推理是有效的，则记为Γ╞ B，否则，记为Γ╞B，其中Γ ＝{A1，A2 ，…， An}。 推理举例4（1） ┐p1 ∨ p2， p1 → (p2 ∧ p3)， p4 → p2， p3 → p4 ├ p2 ∨ p4 推理举例4（2） p1 → (p2 →p3)，p2 ├ p1 →p3 推理举例5 p ∨ q, ┐q，(p →q) →r推出r是无效的 定理 定理3.1 推理形式“A1，A2 ，…， An推出B” 有效 当且仅当 命题公式(A1 ∧ A2 ∧ … ∧ An)→ B是重言式。 推理的形式结构 前提： A1，A2 ，…， An 结论： B 推理的形式结构： (A1 ∧ A2 ∧ … ∧ An)→ B {A1 ， A2 ， … ， An} ├ B Γ├ B 有效推理 {A1 ， A2 ， … ， An} ├ B有效，记为 {A1 ， A2 ， … ， An} ╞ B，也记为 {A1 ， A2 ， … ， An} ? B 有效推理术语 推出： A?B 读作：A推出B 含义：当A为真时，B也为真 A?B 当且仅当 A→B是重言式 例如： (p∨q )∧?p ?q 类比 类比用A?B表示A?B为永真式　　用A?B表示A→B为永真式 (注：“?”不是联结词，只是蕴涵式为永