lec10一阶逻辑推理理论

离散数学第10课一阶逻辑推理理论内容回顾一阶逻辑合式公式及解释一阶逻辑等值式及前束范式上节课练习：求下列公式的前束范式﹁(xF(x,y)yG(x,y))xF(x,y)∧yG(x,y)xF(x,y)∧yG(x,y)xF(x,t)∧yG(s,y)x(F(x,t)∧yG(s,y))xy(F(x,t)∧G(s,y))今日内容一阶逻辑推理理论推理形式的定义量词引入和消去规则一阶逻辑下的推理证明一阶逻辑推理理论在一阶逻辑中，推理的形式结构仍为A1∧A2∧…∧Ak→B若该式是永真式，则称推理正确，称B是A1，A2，…，Ak的逻辑结论此时将该式记为A1∧A2∧…∧AkB命题逻辑中的推理规则及在一阶逻辑中的代换实例，在一阶逻辑中仍然成立一阶逻辑中新增加4条推理规则消去和引入规则:全称量词消去规则全称量词引入规则存在量词引入规则存在量词消去规则全称量词消去规则（简称UI规则）这条规则含以下两种形式：xA(x)A(y)①xA(x)A(c)②两式成立的条件是1.x是A(x)中自由出现的个体变项；2.在①式中，y为任意的不在A(x)中约束出现的个体变项；3.在②式中，c为个体域中任意的个体常项。只有在满足上述条件时，推理规则才成立！在推理过程中①，②两种形式可根据需要选用。例：设定义域为实数，取F(x,y)为x＞y，A(x)=yF(x,y)，xA(x)xyF(x,y)公式xA(x)是真命题。考虑如下推理是否正确:①xyF(x,y)前提引入②yF(y,y)①UI规则yF(y,y)是假命题，推理不正确出错的原因是违背了条件：xA(x)A(y)中，y应为任意的不在A(x)中约束出现的个体变项。全称量词引入规则（简称UG规则）A(y)xA(x)③公式成立的条件是1.y在A(y)中自由出现，且y取任何值时A均为真2.取代y的x不在A(y)中约束出现。例:设定义域为实数，取F(x,y)为xy，A(y)=xF(x,y)=x(xy)，A对任意给定的y都是真的。如下推理是否正确:①xF(x,y)前提引入②xxF(x,x)①UGxx(xx)是假命题，推理出错。出错的原因是违背了条件2：取代y的x不在A(y)中约束出现②zxF(x,z)①UG√存在量词引入规则（简称EG规则）A(c)xA(x)④公式成立的条件是1.c是特定的个体常项；2.取代c的x不能已在A(c)中出现过。例1:设定义域为实数，取F(x,y)为x＜y，A(2)=xF(x,2)=x(x2)，（真命题）如下推理是否正确:①xF(x,2)前提引入②xxF(x,x)①EG假命题，推理出错。出错的原因是违背了条件2,x已在A(2)中出现过。存在量词引入规则（简称EG规则）A(c)xA(x)④公式成立的条件是1.c是特定的个体常项；2.取代c的x不能已在A(c)中出现过。例1:设定义域为实数，取F(x,y)为x＜y，A(2)=xF(x,2)=x(x2)，（真命题）如下推理是否正确:①xF(x,2)P②yxF(x,y)EG,①√存在量词消去规则（简称EI规则）xA(x)A(c)⑤公式成立的条件是1.c是使A为真的特定的个体常项；2.c不曾在A(x)中出现过；3.A(x)中除x外没有其他自由出现的个体变项。例:在自然数集中，设F(x)为x是奇数，G(x)是x是偶数，则xF(x)∧xG(x)是真命题.以下推论是否正确：(1)xF(x)∧xG(x)前提引入(2)xF(x)(1)化简规则(3)xG(x)(1)化简规则(4)F(a)(2)ES规则(5)G(a)(3)ES规则(6)F(a)∧G(a)(4)(5)合取规则(7)x(F(x)∧G(x))(6)EG规则例:在自然数集中，设F(x)为x是奇数，G(x)是x是偶数，则xF(x)∧xG(x)是真命题.以下推论是否正确：(1)xF(x)∧xG(x)前提引入(2)xF(x)(1)化简规则(3)xG(x)(1)化简规则(4)F(a)(2)EI规则(5)G(a)(3)EI规则×(6)F(a)∧G(a)(4)(5)合取规则(7)x(F(x)∧G(x))(6)EG规则出错的原因是存在量词消去规则xA(x)A(c)时违背了条件：c是使A为真的特定的个体常项例:在自然数集中，设F(x)为x是奇数，G(x)是x是偶数，则xF(x)∧xG(x)是真命题.以下推理是否正确：(1)xF(x)∧xG(x)前提引入(2)xF(x)(1)化简规则(3)xG(x)(1)化简规则(4)F(a)(2)EI(5)G(b)(3)EI(6)F(a)∧G(b)(4)(5)合取规则(7)x(F(x)∧G(x))(6)EG例:在自然数集中，设F(x)为x是奇数，G(x)是x是偶数，则xF(x)∧xG(x)是真命题.以下推理是否正确：(1)xF(x)∧xG(x)前提引入(2)xF(x)(1)化简规则(3)xG(x)(1)化简规则(4)F(a)(2)EI(5)G(b)(3)EI(6)F(a)∧G(b)(4)(5)合取规则(7)x(F(x)∧G(x))(6)EG×(7)x(F(x)∧G(b))(6)EG(8)xy(F(x)∧G(y))(7)EG在应用以上4条量词规则时，要特别注意！！一阶逻辑推理实例命题逻辑中的推理规则及在一阶逻辑中的代换实例，在一阶逻辑推理中仍然使用量词消去和引入规则例1:证明苏格拉底三段论“凡人都是要死的。苏格拉底是人.所以苏格拉底是要死的。”命题符号化：F（x）：x是人（特性谓词）；G（x）：x是要死的；a：苏格拉底前提：x（F(x)→G(x)），F(a)结论：G(a)证明：（1）x（F(x)→G(x)）前提引入（2）F(a)→G(a)UI(1)（3）F(a)前提引入（4）G(a)(2)(3)假言推理例2:所有的有理数都是实数，有的有理数是整数。所以，有的实数是整数。请在一阶逻辑中证明上述推理的正确性。证明：命题符号化：F(x)：x为有理数；G(x)：x为实数；H(x)：x为整数前提:x(F(x)→G(x))，x(F(x)∧H(x))结论:x(G(x)∧H(x))前提:x(F(x)→G(x))，x(F(x)∧H(x))结论:x(G(x)∧H(x))证明：①x(F(x)∧H(x))前提引入②F（c）∧H(c)EI①③x(F(x)→G(x))前提引入④F(c)→G(c)UI③⑤F(c)②化简⑥G(c)④⑤假言推理⑦H(c)②化简⑧G(c)∧H(c)⑥⑦合取⑨x(G(x)∧H(x))EG⑧将证明的步骤改为：证明：①x(F(x)→G(x))前提引入②F(c)→G(c)UI①③x(F(x)∧H(x))前提引入④F（c）∧H(c)EI③⑤F(c)②化简⑥G(c)④⑤假言推理⑦H(c)②化简⑧G(c)∧H(c)⑥⑦合取⑨x(G(x)∧H(x))EG⑧哪步存在错误？例3:请在一阶逻辑中证明下述推理的正确性。不存在能表示出分数的无理数，有理数都能表示成分数，因此，有理数都不是无理数。解：命题符号化：设F(x):x为无理数；G(x):x为有理数；H(x)：x能表示成分数。前提：┐∃x(F(x)∧H(x)),∀x(G(x)→H(x))结论：∀x(G(x)→┐F(x))前提：x（F(x)∧H(x)），x（G(x)→H(x)）结论：x（G(x)→F(x)）证明:（1）x（F(x)∧H(x)）前提引入（2）x（F(x)∨H(x)）(1)置换规则（3）x（H(x)→F(x)）(2)置换规则（4）H(y)→F(y)UI（3）（5）x（G(x)→H(x)）前提引入（6）G(y)→H(y)UI（5）（7）G(y)→F(y)(4)(6）假言三段论（8）x（G(x)→F(x)）UG（7）课堂练习：前提：x(F(x)→(G(y)∧R(x)))，xF(x)结论：x(F(x)∧R(x))证明：①xF(x)前提引入②F（c）EI①③x(F(x)→(G(y)∧R(x)))前提引入④F(c)→(G(y)∧R(c))UI③⑤G(y)∧R(c)②④假言推理⑥R(c)⑤化简⑦F(c)∧R(c)②⑥合取⑧x(F(x)∧R(x))EG⑦课堂练习：在一阶逻辑中构造下面推理的证明：大熊猫都产在中国，欢欢是大熊猫。所以，欢欢产在中国。本章学习了研究一阶逻辑的必要性一阶逻辑的基本概念及一阶命题符号化个体词：个体常项、个体变项、个体域、全总个体域谓词：谓词常项、谓词变项、特性谓词、谓词的元数量词：全称量词、存在量词一阶命题的符号化一阶逻辑合式公式及解释公式：字母表、项、原子公式、合式公式、闭式约束关系：指导变项、辖域、约束出现、自由出现解释、换名规则、代替规则一阶逻辑等值式和规范型等值的定义命题逻辑等值式的引入关于量词的等值式命题的规范型：前束范式：存在但不唯一一阶逻辑推理论推理形式的定义命题逻辑推理理论的引入量词引入和消去规则作业一阶逻辑中构造下面推理的证明：任何自然数都是整数，存在着自然数，所以存在着整数。个体域为实数集R。