3.4 自然演绎推理

离散数学第3章谓词逻辑3.1谓词逻辑概述目录3.2谓词公式与解释3.3谓词公式的等值演算3.4谓词推理量词交换等值式回顾上节课讲了前束范式1将重名的自由变元和约束变元，或者辖域不同的同名约束变元换名。2否定符号后移3量词前移(7)(3)(8)(3)(4)例题：3.16(3)前束范式量词消去设个体域D={a,b,c}，消去下列公式中的量词.(3)

x

y(F(x)→G(y))

x(F(x)→

yG(y))

xF(x)→

yG(y)

(F(a)

F(b)

F(c))→(G(a)

G(b)

G(c))逻辑学中著名的苏格拉底三段论：

凡人都是会死的.

苏格拉底是人.

所以苏格拉底是会死的.【形式逻辑】

形式逻辑产生于古希腊（亚里士多德），研究了概念、判断、三段论推理、证明与反驳的方法等重要课题。【数理逻辑】

是现代逻辑，数理逻辑也称符号逻辑，是用数学方法研究逻辑的一门学科。创始人：十七世纪莱布尼兹逻辑学中著名的苏格拉底三段论：

有所人都是会死的.

苏格拉底是人.

所以苏格拉底是会死的.前提：p，q结论：r推理形式：p

q

r如何在一阶逻辑中正确的表示？如何用命题逻辑表示表示？3.7谓词逻辑的自然演绎推理【自然演绎推理】谓词逻辑中的自然演绎推理是直接运用谓词逻辑中的推理规则由已知条件推出结论的过程。自然演绎推理更接近人们的思维习惯。数学定理的证明基本上都是采用自然演绎推理的方法进行推导的。推导法形式证明推理规则3.7谓词逻辑的自然演绎推理【谓词逻辑中的推理规则】(1)命题逻辑中的所有推理规则；(2)谓词逻辑中的等值代换，包括代换实例、变元换名、量词等值式；(3)推理定律(永真蕴涵式)；(4)UI全称量词消去规则(universalinstantiation)(5)UG全称量词引入规则(universalgeneralization)(6)EI存在量词消去规则(existentialinstantiation)(7)EG存在量词引入规则(existentialgeneralization)怎样进行谓词逻辑推理？谓词逻辑中的推理规则(1)命题逻辑中的所有推理规则(p48)；谓词等值式谓词逻辑特有推理规则(3)【几个推理定律】(1)(2)(3)(4)(5)(6)等值式永真蕴含式UI规则UG规则EI规则EG规则Y可以取到个体域中的任意个体常项U—universalE—existentialI—instantiationG—generalization谓词逻辑推理规则

x(A(x)A(y))y是论域中某个任意的个体变元。谓词逻辑推理规则逻辑学中著名的苏格拉底三段论：

凡人都是要死的.

苏格拉底是人.

所以苏格拉底是要死的.

①

x(M(x)→D(x))

②M(c)→D(c)

③M(c)④D(c)前提引入UI前提引入②

③假言推理谓词推理中常见的错误1(1)

xF(x)→G(x) 前提引入

(2)

F(y)→G(y)(1)UI在公式xF(x)→G(x)中，F(x)中的x是约束变元，G(x)中的变元为自由变元，两者并不同步，不能一次变为同一个y。只有当公式为前束范式时，才能应用EI或者UI规则消去量词。例3.18(1)

x(F(x)→G(x))前提引入(2)

F(c)→G(c)(1)UI

(3)

x(F(x)

H(x))

前提引入(4)

F(c)

H(c) (3)EI(5)

F(c)(4)化简(6)

G(c)(2)(5)假言推理(7)

H(c)(4)化简(8)

G(c)

H(c)

(6)(7)合取(9)

x(G(x)

H(x))

(8)EG谓词推理中常见的错误2孙李周吴王赵钱刘罗福建浙江四川F(x)x是大学生G(x)x是福建人1xF(x)引入F(c)UIc=“吴”

xG(x)引入G(c)EI正确否1xG(x)

引入G(c)EIc=“李”

xF(x)引入F(c)UI正确否5G(d)EI正确否谓词推理中常见的错误2结论推理时，先引入存在量词后，再引入全称量词，使用EI和UI规则消去量词时可以用同一个个体常元C。先引入全称量词，再引入存在量词，使用UI和EI规则消去量词时，不能使用同一个个体常元C。(1)

x(F(x)

G(x)) 前提引入(2)

F(c)

G(c)(1)EI(3)

F(c) (2)化简

(4)

y(H(y)

I(y))

前提引入(5)

H(c)

I(c)

(4)EI(6)

H(c)

(5)化简

(7)

F(c)

H(c)

(3)(6)合取(8)

x(F(x)

H(x))

(7)EG谓词推理中常见的错误3孙李周吴王赵钱刘罗福建浙江四川F(x)x是浙江人G(x)x是四川人1xG(x)

引入G(c)EIc=“赵”

xF(x)引入F(c)EI正确否使用量词规则时必须注意必须对辖域为整个公式的量词使用(UIEIUGEG)规则,不能对出现在公式内部的量词使用它