第五章 一阶逻辑推理
设D为个体域
D中所有的x都有性质F D中有的x有性质F 对D中所有的x而言,如果x有性质F,x就
有性质G D中有的x有性质F的同时有性质G 对于D中所有的x、y而言,如果x有性质F, y有性质G,则x与y就有关系H
对于D中所有的x而言,如果x有性质F,
就存在y有性质G,使得x与y就有关系H 存在着D中x有性质F,并且对D中所有的y 而言,如果y有性质G,则x与y就有关系H
5.3 一阶逻辑的推理理论
定义5.3 自然推理系统F定义如下: 1字母表 同一阶语言P的字母表 2合式公式 同P的合式公式 3推理规则 (1)前提引入规则 (2)结论引入规则 (3)置换规则 (4)假言推理规则 (5)附加规则 (6)化简规则
(7)拒取式规则
人都生活在地球上 有的人长着黑头发 并不是所有的实数都能表示成分数 没有能表示成分数的无理数
将下列命题符号化
任意的偶数x与y都有公约数 存在奇数x与y没有公约数 说所有的火车比所有的汽车都快是不对的 说有的火车比所有的汽车都快是正确的
引例——苏格拉底三段论
所有人的都是会死的 苏格拉底是人 所以苏格拉底是会死的
例5.7求下面公式的前束泛式,填出每一步
的依据 (1) xF(x)xG(x) (3) xF(x)xG(x)
例5.8 求下面公式的前束泛式 (1)xF(x,y)yG(x,y) (2)( x1 F(x1 ,x2 )x2 G(x2 ))x1
H(x1 ,x2 ,x3)
3.代替规则
设A为一个公式,将A中某自由出现的个 体变项的所有出现用A中未曾出现的某个 体变项符号代替,公式A中其余部分不变, 设所得公式为A',则A A'。
例5.1 将下面公式化成与之等值的公式,
使其没有既是約束出现又是自由出现的个 体变项。 (1)xF(x、y、z)yG(x、y、z) (2)x(F(x、y)yG(x、y、z))
例5.5证明下列各等值式。 (1)x(M(x)F(x))x(Mx)F(x)) (2)x(F(x)G(x))x(F(x)G(x)) (3)xy(F(x)G(y)H(x、
y))xy(F(x)G(y)H(x、y) (4)xy(F(x)G(y)L(x、 y))xy(F(x)G(y)L((9)析取三段论规则 (10)构造性二难推理规则 (11)合取引入规则 (12)UI规则 (13)UG规则 (14)EG规则 (15)EI规则
例题
任何自然数都是整数,存在着自然数。所
以存在着整数。个体域为实数集合R。
重要的等值式
消去量词等值式 量词否定等值式 量词辖域收缩与扩张等值式 量词分配等值式
1.置换规则
设(A)是含公式A的公式, (B)是 用公式B取代(A)中所有的A之后的公 式,若AB,则(A) (B)
2.换名规则
设A为一个公式,将A中某量词辖域中某
約束变项的所有出现及相应的指导变元, 改成该量词辖域中未曾出现的某个体变项 符号,公式中其余部分不变,设所得公式 为A',则A A’。
一阶逻辑的前束范式
定义5.2 设A为一阶逻辑公式,若A具有如
下行式:Q1 x1 Q2 x2 …Qk xk B,则称A 为前束范式,其中Qi( 1 ik) 为或 , B为不含量词的公式。
定理5.1
一阶逻辑中任何公式都存在与之等值的前
束范式。
例5.6求下面公式的前束泛式 (1)xF(x)xG(x) (2)xF(x)xG(x)
例5.2 证明 (1)x(A(x)B(x)) ≠ xA(x)xB(x) (2) x(A(x)B(x)) ≠ xA(x)xB(x)
例5.3
设个体域为D={a,b,c},将下面公 式的量词消去 (1)x(F(x)G(x)) (2)x(F(x)yG(y)) (3)xyF(x、y)
第五章 一阶逻辑等值演算与推理
§5.1 一阶逻辑等值式与置换规则 §5.2 一阶逻辑前束范式 §5.3 一阶逻辑的推理理论
引例
没有不犯错误的人。 所有的人都犯错误。 不存在不犯错误的人。 命题符号化。
定义5.1
设A、B是一阶逻辑中任意两个公式,若 AB是永真式,则称A与B等值。记为 AB。