第三章：谓词逻辑.pptx

第三章 谓词逻辑;第三章 谓词逻辑;§3.1 谓词逻辑的基本概念;§3.1.1 谓词和量词;§3.1.1 谓词和量词;§3.1.1 谓词和量词;§3.1.1 谓词和量词;§3.1.1 谓词和量词;§3.1.1 谓词和量词;§3.1.1 谓词和量词;§3.1.1 谓词和量词;§3.1.1 谓词和量词;§3.1.1 谓词和量词;§3.1.1 谓词和量词;§3.1.1 谓词和量词;§3.1.1 谓词和量词;§3.1.1 谓词和量词;§3.1.2 改名规则 ;§3.1.2 改名规则 ;§3.1.2 改名规则 ;§3.1.2 改名规则 ;例:;§3.2 谓词公式 ;§3.2.1 公式 ;§3.2.1 公式 ;定义3.2.1 项;定义3.2.2 ;定义3.2.3 公式 ;§3.2.2 解释 ;§3.2.2 解释 ;例:;例:;;§3.3 谓词公式的等价关系和蕴含关系 ;§3.3.1 公式的等价和蕴涵 ;§3.3.1 公式的等价和蕴涵 ;§3.3.1 公式的等价和蕴涵 ;§3.3.1 公式的等价和蕴涵 ;设G(x)是一元谓词符号，若公式?xG(x)是恒真公式，则这件事实可被叙述为如下的一个真命题：对任意一元谓词G(x)，命题?xG(x)都是真的。 但是，如果想把这个命题加以否定，则在谓词逻辑中是办不到的。因为： 1) 这个命题的否定，应该是如下命题：有一个一元谓词G(x)，使得命题?xG(x)是假的。 2) 公式?xG(x)的否定是公式?(?xG(x))。而后一个公式表示的命题是：公式?xG(x)是恒假的，亦即，对任意一元谓词G(x)，命题?xG(x)都是假的。 ;1)和2)所表示出的事实相差得太远了。发生这件事的原因是：用 “公式?xG(x)是恒真的”来表达命题 “对任意一元谓词G(x)，命题?xG(x)都是真的”是不确切的。确切地，后一个命题，应该用 “公式?G(?xG(x))是恒真的”来表达。  这个公式中，不仅有关于个体变量x的量词，而且有关于谓词变量(即谓词符号，亦即原子)的量词。由这样的公式组成的系统就称为高阶逻辑。高阶逻辑中，不仅判定问题不可解，甚至连一个完备的公理系统都没有。 ;§3.3.2 谓词演算的推理理论 ;全称特定化规则(US)：?xA(x)? A(y) 这里的A(y)是将A(x)中的x处代以y。要求y在A(x)中不约束出现。这里自由变量y也可以写成个体常量c，这时c为个体域中任意一个确定的个体。这个规则的意思是说，如果个体域的所有元素都具有性质A，则个体域中的任一个元素具有性质A。 存在特定化规则(ES)：?xA(x) ? A(c) ;存在特定化规则(ES)：?xA(x) ? A(c) 这里c是个体域中的某个确定的个体。这个规则是说，如果个体域中存在有性质A的元素，则个体域中必有某一元素c具有性质A。但是，如果?xA(x)中有其它自由变量出现，且x是随其它自由变量的值而变，那么就不存在唯一的c使得A(c)对自由变量的任意值都是成立的。这时，就不能应用存在特定化规则。 ;例如，?x(x=y)中，x、y的论域是实数集合。若使用ES规则，则得c=y，即在实数集中有一实数c，等于任意实数y。结论显然不成立，这是因为A(x)：x=y中的x依赖于自由变量y，此时不能使用ES规则。另外，要注意的是，如果?xP(x)和?xQ(x)都真，则对于某个c和某个d，可以断定 P(c) ?Q(d)必真，但不能断定P(c) ?Q(c)为真。 ; 全称一般化规则(UG)：A(x)??yA(y)这个规则是说，如果个体域中任意一个个体都具有性质A，则个体域中的全体个体都具有性质A。这里要求x必须为自由变量，并且y不出现在A(x)中。 存在一般化规则(EG)：A(c)??yA(y)这个规则是说，如果个体域中某一元素c具有性质A，则个体域中存在着具有性质A的元素。这里要求y不在A(c)中出现。 ;证明： （1）?x(P(x)?Q(x)) 前提 （2）P(c)?Q(c) (1)；US （3）P(c) 前提 （4）Q(c) (2),(3) ;证明：用反证法，假设??xQ(x)成立。 ?x?P(x) 前提 ?P(y) (1)；US ??xQ(x) 假设 ?x?Q(x) (3) ?Q(y) (4)；US ?P(y)??Q(y) (2)，(5) ; ?(P(y) ?Q(y)) (6) ?