交大数理逻辑课件5-3-谓词逻辑的等值和推理演算.pptVIP

**集合论起源于16世纪末期。是数学各分支、自然科学及社会科学各领域的最普遍采用的描述工具。*集合：一些离散个体组成的全体调课通知因下周五(11月12日)为广州亚运会开幕式官方放假时间，数理逻辑课程调到下周三(11月10日)5,6节在310305课室上课，特告之。第5章谓词逻辑的等值和推理演算5.1否定型等值式5.2量词分配等值式5.3范式5.4基本的推理公式5.5推理演算5.6谓词逻辑的归结推理法推理规则(1)前提引入规则(2)结论引入规则(3)置换规则(4)假言推理规则(A?B)ùATB(5)附加规则AT(AúB)(6)化简规则(AùB)TA(7)拒取式规则(A?B)ù?BT?A(8)假言三段论规则(A?B)ù(B?C)T(A?C)(9)析取三段论规则(AúB)ù?BTA(10)构造性二难推理规则(A?B)ù(C?D)ù(AúC)T(BúD)(11)合取引入规则A,BTAùB有关量词的推理规则全称量词消去规则（UI规则）全称量词引入规则（UG规则）存在量词引入规则（EG规则）存在量词消去规则（EI规则）使用推理规则的推演算举例前提:(?x)P(x)?(?x)(P(x)∨Q(x))?R(x))，(?x)P(x)结论:(?x)(?y)(R(x)∧R(y))证明:①(?x)P(x)?(?x)(P(x)∨Q(x))?R(x))前提引入②(?x)P(x)前提引入③(?x)(P(x)∨Q(x))?R(x))①②分离④P(c)②EI⑤(P(c)∨Q(c))?R(c)③UI⑥P(c)∨Q(c)④附加规则⑦R(c)⑤⑥分离⑧(?x)R(x)⑦EG⑨(?y)R(y)⑦EG⑩(?x)R(x)∧(?y)R(y)⑧⑨合取规则⑾(?x)(?y)(R(x)∧R(y))⑩置换证明:(?x)(H(x)→M(x)),(?x)H(x)?(?x)M(x)证明: ①(?x)H(x) 前提引入 ②H(c) ①EI ③(?x)(H(x)→M(x))前提引入 ④H(c)→M(c) ③UI ⑤M(c) ②④分离 ⑥(?x)M(x) ⑤EG若把①,②写在③,④的后面，得到如下的推理: ①(?x)(H(x)→M(x))前提引入 ②H(c)→M(c)①UI ③(?x)H(x)前提引入 ④H(c) ③EI ⑤M(c)②④分离 ⑥(?x)M(x)⑤EG这个推理在逻辑上是错误的。因为②中的c为个体域中一个个体,用EI规则由③推到④不能选择②中的c,因为它要选的个体和②中的个体c不一定是同一个个体,故推理是错误的。5.6谓词逻辑的归结推理法归结证明法的出发点证明A?B是定理，等价于证明A∧?B=G是矛盾式归结证明过程建立子句集S将G中的全称量词省略，并将G中的合取词∧用“，”表示，得子句集S如:(?x)