数理逻辑第十五节课06

1、复习基础 85分左右进阶 15分左右1复习.基础1.演绎与归纳有何区别？2复习.基础1.演绎与归纳有何区别？演绎推理有必然性，前件真，后件必然真3复习.基础1.演绎与归纳有何区别？0304 24-36（初步）4复习.基础2.什么是推理？5复习.基础2.什么是推理？一系列命题(proposition)或者陈述句(declarative sentence)的序列，其中一部分组成前提(premises)集，序列的最后一个是结论(conclusion)，用以表明前提集合理地得出或者支持结论6复习.基础2.什么是推理？0304 43邢第5-6面徐第2面，分得更细论说推理7复习.基础3.陈述句与命题的关系

2、？8复习.基础3.陈述句与命题的关系？陈述句是表达命题的句子除了表达命题以外，还有其它的丰富的意思只关注陈述句表达有真假的命题9复习.基础3.陈述句与命题的关系？0304 44-59邢 4-510复习.基础4.根据不同的“逻辑部件”进行相应的形式化、符号化11复习.基础4.根据不同的“逻辑部件”进行相应的形式化、符号化不同的逻辑“部件” 不同“粗细地”外延化情景 不同的形式化12复习.基础4.根据不同的“逻辑部件”进行相应的形式化、符号化不同的逻辑“部件” 不同“粗细地”外延化情景 不同的形式化例子康德不是女人 康德是女人或者柏拉图是男人 柏拉图是男人 男人是战士 柏拉图是男人 柏拉图是战士1

3、3复习.基础4.根据不同的“逻辑部件”进行相应的形式化、符号化不同的逻辑“部件” 不同“粗细地”外延化情景 不同的形式化真值联结词 量词14复习.基础4.根据不同的“逻辑部件”进行相应的形式化、符号化0311 14-24徐命题逻辑 符号化 34-38；60-61 习题2.1-2.3徐谓词逻辑 符号化 248-266；（我们没有详细讲，7.1-7.6）15复习.基础5.元语言与对象语言可以是同一种语言吗？16复习.基础5.元语言与对象语言可以是同一种语言吗？元语言与对象语言可以是同一种17复习.基础5.元语言与对象语言可以是同一种语言吗？元语言与对象语言可以是同一种相应的汉语+部分英语+一些符号

4、 元语言18复习.基础5.元语言与对象语言可以是同一种语言吗？元语言与对象语言可以是同一种相应的汉语+部分英语+一些符号 元语言元语言里可以有推理、使用数学概念、方法19复习.基础5.元语言与对象语言可以是同一种语言吗？0311 53-60邢92-93徐39-4020复习.基础6.命题公式的主联结词21复习.基础6.命题公式的主联结词有五类联结词（1） 否定（并非，不，） （2） 合取（并且，但是， ） （3） 析取（或者，不是-就是， ） （4） 蕴涵（如果-那么，只要， ） （5） 双蕴涵（当且仅当，等价于， ） 22复习.基础6.命题公式的主联结词命题公式的形成0命题变号都是0公式；若是

5、0公式，则()也是0公式；若与是0公式，则()也是0公式；若与是0公式，则()也是0公式；若与是0公式，()也是0公式；若与是0公式， ()也是0公式；只有适合以上七条的是0公式。23复习.基础6.命题公式的主联结词命题公式的形成0命题变号都是0公式；若是0公式，则()也是0公式；若与是0公式，则()也是0公式；若与是0公式，则()也是0公式；若与是0公式，()也是0公式；若与是0公式， ()也是0公式；只有适合以上七条的是0公式。24最后一步用到第2-6条，相应的真值联结词是主联结词复习.基础6.命题公式的主联结词命题公式的形成0命题变号都是0公式；若是0公式，则()也是0公式；若与是0公式

6、，则()也是0公式；若与是0公式，则()也是0公式；若与是0公式，()也是0公式；若与是0公式， ()也是0公式；只有适合以上七条的是0公式。25最后一步用到第2-6条，相应的真值联结词是主联结词可推广到一阶公式复习.基础7.命题公式的语形树26复习.基础7.命题公式的语形树0311 68-75由结构归纳法可证明每个命题公式都有唯一一棵语形树。27复习.基础7.命题公式的语形树0311 68-75由结构归纳法可证明每个命题公式都有唯一一棵语形树。直观上保证“无歧义性”28复习.基础8.命题公式的子公式集29复习.基础8.命题公式的子公式集0311 76-79借助语形树的概念30复习.基础8.命

7、题公式的子公式集0311 76-79借助语形树的概念请试着用递归定义定义命题公式的子公式31复习.基础9.归纳法、归纳定义32复习.基础9.归纳法、归纳定义数学归纳法设P(x)是一个性质，若它满足P(0)对任意的自然数n(P(n)P(n+1)那么，对任意的自然数n(P(n)33复习.基础9.归纳法、归纳定义邢58-63 归纳定义 68-70 项的归纳证明 76-78 公式的归纳证明0513 101-12034复习.基础9.归纳法、归纳定义邢58-63 归纳定义 68-70 项的归纳证明 76-78 公式的归纳证明0513 101-120在用归纳定义方法得到的集合上实施归纳证明，以证明集合中的每

8、个元素都有某性质35复习.基础10.真值函数联结词的真值表36复习.基础10.真值函数联结词的真值表基本真值表-真值函数联结词的“意义”37复习.基础10.真值函数联结词的真值表0318 33-64徐 43特别要注意“实质蕴涵”的真值表38复习.基础11.真值指派与命题公式真值的计算39复习.基础11.真值指派与命题公式真值的计算公式在情景下的真值40复习.基础11.真值指派与命题公式真值的计算公式在情景下的真值外延化情景 真值指派41复习.基础11.真值指派与命题公式真值的计算0318 65-79徐44-48由“每个0公式都有唯一一棵语形树。”以及真值指派、真值函数联结词的“意义”都为函数

9、保证复合命题的真假完全由构成它的简单命题的真假所决定。每个0公式在每个“情景”下有唯一的真值42复习.基础12.重言蕴涵、可满足与重言式43复习.基础12.重言蕴涵、可满足与重言式重言后承（重言蕴涵）-有效的推理形式44复习.基础12.重言蕴涵、可满足与重言式重言后承（重言蕴涵）-有效的推理形式称公式集可满足，若存在真值指派，使得 45复习.基础12.重言蕴涵、可满足与重言式重言后承（重言蕴涵）-有效的推理形式称公式集可满足，若存在真值指派，使得 若对每个真值指派，都有，则称为重言式我们有另一个定义，46复习.基础12.重言蕴涵、可满足与重言式0318 80-90；0325 8-11；徐49-

10、5747复习.基础13.真值表法48复习.基础13.真值表法0325 54-64；徐47-4849复习.基础14.命题逻辑的演算（公理、自然推演）系统50复习.基础51复习.基础14.命题逻辑的演算（公理、自然推演）系统0415 17-136徐113-143一个自然推演系统N52复习.基础14.命题逻辑的演算（公理、自然推演）系统为什么要讲演算系统？53复习.基础14.命题逻辑的演算（公理、自然推演）系统逻辑学的根 正确的推理形式（与重言式）54复习.基础14.命题逻辑的演算（公理、自然推演）系统逻辑学的根 正确的推理形式（与重言式）处理成 55复习.基础14.命题逻辑的演算（公理、自然推演）

11、系统逻辑学的根 正确的推理形式（与重言式）处理成 语形上演算系统H （可靠性与完全性）56复习.基础14.命题逻辑的演算（公理、自然推演）系统逻辑学的根 正确的推理形式（与重言式）处理成 语形上演算系统H （可靠性与完全性）如果考内定理的证明，会给出公理、规则57复习.基础15.命题逻辑中的代入58复习.基础15.命题逻辑中的代入用在代入规则59复习.基础15.命题逻辑中的代入用在代入规则0401 39-44徐81-8560复习.基础16.演算系统的可靠性61复习.基础16.演算系统的可靠性据系统证明的都是对的62复习.基础16.演算系统的可靠性据系统证明的都是对的命题演算系统、谓词演算系统用

12、一种形式的归纳法证63复习.基础16.演算系统的可靠性据系统证明的都是对的命题演算系统、谓词演算系统用一种形式的归纳法证64复习.基础65复习.基础66复习.基础17.会用演绎定理67复习.基础68复习.基础17.会用演绎定理0401 107；0408 42-64徐176-17769复习.基础18.会用反证法与归谬法70复习.基础71复习.基础18.会用反证法与归谬法0408 67-8472复习.基础19-21.集合论初步73复习.基础19-21.集合论初步子集、幂集、并、差映射、单射、满射、双射集合的等势74复习.基础19-21.集合论初步子集、幂集、并、差映射、单射、满射、双射集合的等势重

13、要的是用集合论概念与工具做外延化的工作75复习.基础20.集合论初步0422 61-167；0506 9-173；0513 1-26邢第二章76复习.基础22.一阶语言中的项与公式的定义77复习.基础22.一阶语言中的项与公式的定义语言里用来代表结构的领域里的个体的要素称为项78复习.基础22.一阶语言中的项与公式的定义语言里用来代表结构的领域里的个体的要素称为项用归纳定义方法定义0513 121-12379复习.基础22.一阶语言中的项与公式的定义语言里用来代表结构的领域里的个体的要素称为项用归纳定义方法定义0513 121-123每个项总是从个体变项与个体常项出发，经过有穷步构造得到，而且

14、这种构造途径是唯一的80复习.基础22.一阶语言中的项与公式的定义语言里用来代表结构的领域里的个体的要素称为项用归纳定义方法定义0513 121-123每个项总是从个体变项与个体常项出发，经过有穷步构造得到，而且这种构造途径是唯一的公式类似归纳定义 0520 27-32邢第三章第3、4节81复习.基础23.一阶公式的秩82一阶公式的秩复习.基础23.一阶公式的秩公式的复杂度的度量，可以用于归纳证明83一阶公式的秩复习.基础84一阶公式的秩复习.基础24.量化式中量词的辖域85一阶公式的秩复习.基础24.量化式中量词的辖域对一个量化式（或），称其子公式是量词（或）的辖域。86一阶公式的秩复习.基

15、础24.量化式中量词的辖域对一个量化式（或），称其子公式是量词（或）的辖域。直观上看，一处量词的辖域就是紧跟着它的最短公式0520 72-76邢8287一阶公式的秩复习.基础25.变项的自由出现与约束出现88一阶公式的秩复习.基础25.变项的自由出现与约束出现在公式中，一个变项如果出现在某个形如（或）的量词的某处辖域中，则称在中的这处出现（以及它在这个量词中的出现）是约束的。变项的非约束的出现，称为自由出现。89一阶公式的秩复习.基础25.变项的自由出现与约束出现在公式中，一个变项如果出现在某个形如（或）的量词的某处辖域中，则称在中的这处出现（以及它在这个量词中的出现）是约束的。变项的非约束的

16、出现，称为自由出现。0520 77-79邢8390一阶公式的秩复习.基础26.一阶语言的结构、赋值与解释91一阶公式的秩复习.基础26.一阶语言的结构、赋值与解释单纯就语形而言，项与公式都是符号串；如果我们想要确定它们的意义，就需要按照这些符号的类型，把它们与语言之外的个体、关系、函数等对应起来（用这些符号来代表某些事物）。92一阶公式的秩复习.基础26.一阶语言的结构、赋值与解释要使一个语言中的公式获得意义，我们首先要划定一个个体域A，挑出其中的特指个体，确定其中的性质、关系、函数等，然后把语言中的个体常项、谓词、函数符号等与A中的这些东西对应起来。这个过程就是对语言的解释（当然，我们也需要

17、解释逻辑符号）。可以看出，对一个给定语言的解释主要需要两样东西：一是语言之外的某个世界（包括个体域及其中的性质、关系、函数等）二是语言的非逻辑符号与这个世界之间的某种对应关系，二者合起来称为关于这个语言的一个结构。93一阶公式的秩复习.基础26.一阶语言的结构、赋值与解释0520 102-109邢91-9594一阶公式的秩复习.基础26.一阶语言的结构、赋值与解释结构可以确定闭公式的真假，但是还不足以确定开公式的真假95一阶公式的秩复习.基础26.一阶语言的结构、赋值与解释结构可以确定闭公式的真假，但是还不足以确定开公式的真假但是我们又要谈论其中使用开公式的推理形式的有效性96一阶公式的秩复习

18、.基础26.一阶语言的结构、赋值与解释结构可以确定闭公式的真假，但是还不足以确定开公式的真假但是我们又要谈论其中使用开公式的推理形式的有效性开公式在结构上无法确定真假值的原因在于其中的自由变项不清楚指向什么对象97一阶公式的秩复习.基础26.一阶语言的结构、赋值与解释结构可以确定闭公式的真假，但是还不足以确定开公式的真假但是我们又要谈论其中使用开公式的推理形式的有效性开公式在结构上无法确定真假值的原因在于其中的自由变项不清楚指向什么对象引入赋值与解释98一阶公式的秩复习.基础26.一阶语言的结构、赋值与解释0520 118-119邢95-9799一阶公式的秩复习.基础27.项与公式在解释上的值

19、100一阶公式的秩复习.基础27.项与公式在解释上的值解释实质上是在结构里用个体变项给一些个体起名字（个体变项指称相应的个体）101一阶公式的秩复习.基础27.项与公式在解释上的值解释实质上是在结构里用个体变项给一些个体起名字（个体变项指称相应的个体）借助解释里的赋值，每个项也指称一个个体，进而，每个公式，无论开闭，都有了真假值102一阶公式的秩复习.基础27.项与公式在解释上的值0527 31-38（项）；45-78（公式）邢95（项）；113（公式）103一阶公式的秩复习.基础28.合同引理104一阶公式的秩复习.基础28.合同引理如果有相同论域的两个解释，对一个项（或者公式）的符号有相同

20、的意义，那么这个项（或者公式）在这两个解释上有相同的意义（指向同一个对象，或者有相同的真值）105一阶公式的秩复习.基础106一阶公式的秩复习.基础28.合同引理0527 ； 83-116（公式）邢118-120（一般版本）107一阶公式的秩复习.基础29.语义后承、有效式108一阶公式的秩复习.基础29.语义后承、有效式对“/”有效与否的形式刻画109一阶公式的秩复习.基础29.语义后承、有效式对“/”有效与否的形式刻画0527 119-131（语义后承）；0603 45-94（有效式）邢123-129（语义后承）；130-133（有效式）110一阶公式的秩复习.基础30.闭公式描述结构111一阶公式的秩复习.基础30.闭公式描述结构例子 可以写出一个闭公式，使得对任意的结构= ,，若，则中至多有2个元素112一阶公式的秩复习.基础30.闭公式描述结构例子 可以写出一个闭公式，使得对任意的结构= ,，若，则中至多有2个元素2=113一阶公式的秩复习.基础30.闭公式描述结构例子 可以写出一个闭公式，使得对任意的结构= ,，若，则中至多有2个元素2=0527 136-142邢147-149114一阶公式的秩复习.基础31、32.代换与重言式代换式115一阶公式的秩复习.基础31、32.代换与重言式代换式命题逻辑中的重言式反映了