第五章-高级数理逻辑.pptxVIP

第5章 可推导性关系和归纳定义 可推导性关系归纳定义5.1 可推导性关系数理逻辑的含义用数学的方法研究逻辑问题逻辑的核心内容逻辑推理——由前提推出结论前提和结论都是命题命题是能判断真假的陈述句前提与结论之间存在可推导性关系可推导性关系当前提的真蕴含结论的真由前提的真推出结论的真前提到结论的推理是正确的前提T结论前提?结论为永真式演绎推理上述的推理即为演绎推理研究怎样的前提与结论之间有可推导性关系演绎逻辑的例子例所有3的倍数的数字之和是3的倍数（前提）1010的数字之和不是3的倍数（前提）1010不是3的倍数（结论）该推理是正确的，并且推理中的2个前提和1个结论均为真命题. 演绎逻辑的例子例所有中学生打网球。（前提）王君不打网球。（前提）王君不是中学生。（结论）本例的推理也是正确的，并且它的正确性与前例中推理的正确性的依据是完全相同的. 但是本例中的前提和结论未必是真命题.推理是否正确，与推理中前提和结论的真或假是没有关系的可推导性关系只要求前提的真蕴含结论的真，不要求前提和结论为真数理逻辑不研究前提和结论的真或假，而是研究前提的真是否蕴含结论的真决定前提和结论之间的可推导性关系的是它们的逻辑形式逻辑形式表象：前提、结论的真或假语义范畴内因：前提、结论的逻辑形式语法范畴两个例子的逻辑形式相同S中的所有元有R性质 （前提）a没有R性质 （前提）a不是S中的元 （结论）逻辑形式任何三个命题，如果它们分别具有上述的逻辑形式，那么由前两个命题能推导出第三个命题，而不论S是怎样的集合，R是怎样的性质，a是怎样的元。数理逻辑研究推理时涉及对前提和结论的分析，这时所注意的是由内容抽象出的逻辑形式。例X认识Y。（前提）Y是足球队长。（前提）X认识足球队长。（结论）例X认识A班某学生。（前提）A班某学生是足球队长。（前提）X认识足球队长。自然语言上的相似并不保证逻辑形式上的相同形式语言在数理逻辑中要构造一种符号语言来代替自然语言（二义性、不精确性）. 这种人工构造的符号语言称为形式语言形式语言用符号构成公式，用公式表示命题，进而精确地表示命题的逻辑形式形式语言无二义性、精确性语义：涉及符号、表达式的涵义语法：仅涉及表达式的形式结构语义和语法既有联系，又有区别不同层次的语言讨论问题是在某个语言中进行的，但数理逻辑所讨论的对象本身就是语言。因此要涉及两个不同层次的语言。被讨论的对象称为对象语言，也就是所说的形式语言。讨论对象语言时所用的语言称为元语言。所使用的元语言就是自然语言汉语。5.2 归纳定义外延：集所含元的全体内涵：集中的元所共有的性质例：非负偶数集的外延就是{0,2,4,…}，而其内涵就是“被2整除的自然数”例：集{a,b,c}的外延是a,b和c，其内涵为“是a或b或c”可数集：|S|≤|N|， 可数有限()可数无限(=)归纳定义和归纳证明归纳定义是定义集合的一种方法。对于用归纳定义给出的集合，要证明其中所有的元都有某个性质，通常用归纳证明。集合的归纳定义通常包括若干规则，用来生成其中的元，然后再说明，只有由这些规则生成的对象才是这个集合的元。归纳定义的一种的等价的陈述是将所要定义的集合刻画为封闭于这些规则的最小的集。自然数集合N的归纳定义定义1(i) 0∈N。(ii) 对于任何n，如果n∈N，则n’ ∈N（n’是n的后继）。(iii) 只有由（有限次使用）(i)和(ii)生成的n∈N。定义1并不是使用被定义了的N来定义自己。集合由它的外延确定，因此定义N就是要确定它的外延。当其外延尚未确定时，N是没有被定义的。定义1的(i)、(ii)和(iii)中，N的外延是没有确定的，也就是定义1中N不是已经被定义的。定义1才是确定N的外延，即定义了N。合式公式也是归纳定义给出的集合。例 合式公式 定义如下：(1) 单个命题常项或变项 p,q,r,…,pi ,qi ,ri ,…,0,1 是合式公式(2) 若A是合式公式，则 (?A)也是合式公式(3) 若A, B是合式公式，则(A?B), (A?B), (A?B), (A?B)也是合式公式(4) 只有有限次地应用(1)~(3)形成的符号串才是合式公式归纳定义自然数集合的一种等价陈述定义2N是满足以下的(i)和(ii)的S中的最小集：(i) 0∈S。(ii) 对于任何n，如果n∈S，则n’ ∈S。定义2是说，N满足(i)和(ii)，并且对于任何满足(i)和(ii)的S，N?S。归纳证明的定理设R是一个性质，用R(x)表示x有R性质定理1：如果(i) R(0)(ii) 对于任何n∈N，如果R(n)，则R(n’)则对于任何n∈N，R(n)证明：令S={n∈N | R(n)}，S满足刚刚自然数的等价定义. 因此 N ? S，也就是说对于任