第2章 一阶逻辑().ppt

第2章 一阶逻辑,2.1 一阶逻辑的基本概念 2.2 一阶逻辑公式及解释 2.3 等值演算2.4 一阶逻辑推理理论 2.5 例题选解,一些基本而重要等价式（1）(x)A(x)  A(a1)∧A(a2)∧…∧A(an) D={a1…,an}（2）(x)A(x)  A(a1)∨A(a2)∨…∨A(an)（3）┐┐(x)F(x)  (x)F(x)（4）┐(x)A(x)  (x)┐A(x)（5）┐(x)A(x)  (x)┐A(x)（6）(x)(A(x)∧B(x))  (x)A(x)∧(x)B(x)（7）(x)(A(x)∨B(x))  (x)A(x)∨(x)B(x)（8）(x)(A(x)∨B(x)) <≠> (x)A(x)∨(x)B(x) （9）(x)(A(x)∧B(x)) <≠>  (x)A(x)∧(x)B(x)?（10） ,一些基本而重要蕴含式(x)F(x)  (x)F(x)(x)F(x)∧(y)G(y)  (x)F(x) 化简律的代换实例(x)F(x)  (x)F(x)∨(y)G(y) 附加律的代换实例(x)A(x)∨(x)B(x)  (x)(A(x)∨B(x)) (x)(A(x)∧B(x)) (x)A(x)∧(x)B(x) (x)(A(x)→B(x)) (x)A(x)→(x)B(x) ( x)(A(x)→B(x)) (x)A(x)→(x)B(x),2.4 一阶逻辑推理理论,在一阶逻辑中，由前提A1，A2，…，An推出结论B的形式结构仍然是A1∧A2∧…∧An→B。

如果此式是永真式，则称由前提A1，A2，…，An推出结论B的推理正确，记作A1∧A2∧…∧An B或者A1，A2，…，An B，否则称推理不正确一阶逻辑推理的常用推理规则,前提引入(P)、结论引入(T)、置换规则(T) 假言推理、附加、化简、拒取式、假言三段论、析取三段论、构造性两难、合取引入 US、UG、ES、EG,US规则(universal instantiation)全称量词消去规则（简称UI规则）(x)A(x)  A(y) 或(x)A(x)  A(c)含义： 如果个体域的所有元素都具有性质A，则个体域中的 任一元素具有性质A 成立条件：  (1)y为任意的不在A中约束出现的个体变项  (2)c为任意个体常项 (3)用y或c去取代x时，一定要在x出现的一切地方取代UG规则(universal generalization) A(y) (x)A(x) 成立的条件是： (1)无论A(y)中y取何值，A(y)应该均为真 (2)取代y的x不能在A(y)中约束出现全称量词引入规则,ES规则(existential instantiation)存在量词消去规则（简称EI规则） (x)A(x)  A(c)成立条件：  (1) c是使A为真的个体常项。

(2) c不在A(x)中出现 (3) A(x)中没有其他自由出现的变元EG规则(existential generalization)存在量词引入规则（简称EG规则） A(c)  xA(x) 成立条件：  (1)c是个体常项2)x不出现在A(c)中例2.4.1】 证明推理"所有的自然数均是实数，3是自然数，因此，3是实数 解 设N（x）：x是自然数，R（x）：x是实数，则推理形式化为： x（N（x）→R（x）），N（3） R（3） 下面进行证明 （1） x（N（x）→R（x）） 前提引入 （2）N（3）→R（3） （1）UI （3）N（3） 前提引入 （4）R（3） （2）（3）假言推理,例2. 证明 x（M（x）→ D（x））∧M（s） D（s）这是著名的苏格拉底三段论的论证。

其中 M（x）：x是一个人 D（x）：x是要死的 s：苏格拉底证明 （1）x（M（x）→ D（x）） P （2）M（s）→ D（s） US（1） （3）M（s） P （4）D（s） T（2）（3）,【例2.4.2】 构造下面推理的证明： 前提 x（F（x）→（G（x）∧H（x）））， x（F（x）∧P（x）） 结论 x（P（x）∧H（x））,解 （1） x（F（x）→（G（x）∧H（x））） 前提引入（2）x（F（x）∧P（x）） 前提引入（3）F（c）∧P（c） (2)EI（4）F（c）→（G（c）∧H（c）） （1）UI（5）F（c） （3）化简（6）G（c）∧H（c） （4）（5）假言推理（7）P（c） （3）化简（8）H（c） （6）化简（9）P（c）∧H（c） （7）（8）合取引入（10）x（P（x）∧H（x）） （9）EG,【例2.4.4】 设前提为 xyF（x，y），下面推理是否正确？ （1） xyF（x，y） 前提引入 （2）yF（t，y） （1）UI （3）F（t，c） （2）EI （4） xF（x，c） （3）UG （5）y xF（x，y） （4）EG,解 xyF（x，y） y xF（x，y）的推理并不正确。

取与例2.4.3相同的解释，则由 xyF（x，y）为真，而y xF（x，y）意为"存在着最小实数"，是假命题，知推理不正确之所以出现这样的错误，是第（3）步违反了EI规则成立的条件（3）例2.4.5】 构造下面推理的证明： 前提 x（F（x）→G（x）） 结论 xF（x）→ xG（x） 分析 本题直接证明很困难，注意到结论部分是蕴涵式，应考虑用附加前提证明法证明 （1） x（F（x）→G（x）） 前提引入（2） xF（x） 附加前提引入（3）F（t） （2）UI（4）F（t）→G（t） （3）UI（5）G（t） （3）（4）假言推理（6） xG（x） （5）UG（7） xF（x）→xG（x） CP,【例2.4.6】 构造下面推理的证明： 前提 x（F（x）→G（x）） 结论 x（y（F（y）∧H（x，y）） →z（G（z）∧H（x，z）））,分析 本题直接证明会感到无从下手，而由于结论并非蕴涵式（x的辖域是其后整个公式），附加证明法也不适用，此时我们应考虑归缪法。

证明 （1） x（y（F（y）∧H（x，y）） →z（G（z）∧H（x，z））） 否定结论引入（2）x （y（F（y）∧H（x，y）） →z（G（z）∧H（x，z））） （1）置换,（3） （y（F（y）∧H（a，y）） →z（G（z）∧H（a，z））） （2）EI（4）y（（F（y）∧H（a，y））∧ z（G（z）∧H（a，z））） （3）置换,（5）y（F（y）∧H（a，y）） （4）化简（6）F（b）∧H（a，b） （5）EI（7）F（b） （6）化简（8） x（F（x）→G（x）） 前提引入（9）F（b）→G（b） （8）UI（10）G（b） （7）（9）假言推理（11）  z（G（z）∧ H（a，z）） （4）化简,（12） z（ G（z）∨ H（a，z）） （11）置换（13） G（b）∨ H（a，b） （12）UI（14）H（a，b） （6）化简（15） H（a，b） （14）置换（16） G（b） （13）（15）析取三段论（17）G（b）∧ G（b） （10）（16）合取引入,【例2.5.5】 构造下面推理的证明： 前提 xF（x）∨ xG（x） 结论 x（F（x）∨G（x））证明 （1） xF（x）∨ xG（x） 前提引入（2） x y（F（x）∨G（y）） （1）置换（3） y（F（t）∨G（y）） （2）UI（4）F（t）∨G（t） （3）UI（5） x（F（x）∨G（x）） （4）UG,第二章 谓词逻辑,本章小结,本章是命题逻辑的深入和扩展，通过了解命题逻辑的局限性引入了谓词、量词、个体域、个体等概念；在此基础上定义了谓词公式及对公式的解释、公式的等价、蕴涵和前束范式等内容；然后利用谓词的等价式、蕴涵式、谓词逻辑的推理理论、全称指定规则、全称推广规则、存在指定规则和存在推广规则等进行逻辑推理。