lec10一阶逻辑推理理论.ppt

《lec10一阶逻辑推理理论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学第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若该式是永真式，则称推

2、理正确，称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为个体域中任意的个体常项。只有在满足上述条

3、件时，推理规则才成立！在推理过程中①，②两种形式可根据需要选用。例：设定义域为实数，取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.取

4、代y的x不在A(y)中约束出现。例:设定义域为实数，取F(x,y)为x>y，A(y)=xF(x,y)=x(x>y)，A对任意给定的y都是真的。如下推理是否正确:①xF(x,y)前提引入②xxF(x,x)①UGxx(x>x)是假命题，推理出错。出错的原因是违背了条件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)=

5、xF(x,2)=x(x<2)，（真命题）如下推理是否正确:①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(x<2)，（真命题）如下推理是否正确:①xF(x,2)P②yxF(x,y)EG,①√存在量词消去规则（简称EI规则）xA(x)

6、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

7、是奇数，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)是真命题.以下推理是

8、否正确：(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例