数理逻辑发展教案文档格式.docx
《数理逻辑发展教案文档格式.docx》由会员分享,可在线阅读,更多相关《数理逻辑发展教案文档格式.docx(68页珍藏版)》请在冰点文库上搜索。
?
概念语言——一种按算术的公式语言构成的纯思维公式语言?
(1879)的出版标志着数理逻辑的根底局部——命题演算和谓词演算的正式建立。
皮亚诺(GiuseppePeano,1858~1932):
用一种新的方法陈述的算术原理?
(1889)提出了自然数算术的一个公理系统。
罗素(BertrandRussell,1872~1970):
数学原理?
(与怀特黑合著,1910,1912,1913)从命题演算和谓词演算开始,然后通过一元和二元命题函项定义了类和关系的概念,建立了抽象的类演算和关系演算。
由此出发,在类型论的根底上用连续定义和证明的方式引出了数学〔主要是算术〕中的主要概念和定理。
逻辑演算的开展:
甘岑(G.Gentzen)的自然推理系统(NaturalDeductionSystem),逻辑演算的元理论:
公理的独立性、一致性、完全性等。
各种各样的非经典逻辑的开展:
路易斯(Lewis,1883~1964)的模态逻辑,实质蕴涵怪论和严格蕴涵、相干逻辑等,卢卡西维茨的多值逻辑等。
4.集合论的开展
看待无穷集合的两种观点:
实无穷与潜无穷
康托尔(G.Cantor,1845~1918):
以实无穷的思想为指导,建立了朴素集合论
·
外延原那么〔集合由它的元素决定〕和概括原那么〔每一性质产生一集合〕。
可数集和不可数集,确定无穷集合的本质在于集合本身能与其子集一一对应。
能与正整数集合对应的集合是可数的,否那么是不可数的。
证明了有理数集是可数的,使用对角线法证明了实数集合是不可数的。
超穷基数和超穷序数
朴素集合论的悖论:
罗素悖论
公理集合论的建立:
ZFC系统
6.第三次数学危机与逻辑主义、直觉主义与形式主义
集合论的悖论使得人们觉得数学产生了第三次危机,提出了数学的根底到底是什么这样的问题。
罗素等的逻辑主义:
数学的根底是逻辑,倡导一切数学可从逻辑符号推出,?
一书是他们这一思想的表达。
为解决悖论产生了逻辑类型论。
布劳维尔(Brouwer,1881~1966)的直觉主义:
数学是心灵的构造,只成认可构造的数学,强调构造的能行性,与计算机科学有重要的联系。
坚持潜无穷,强调排中律不能用于无穷集合。
海丁(Heyting)的直觉主义逻辑。
希尔伯特(D.Hilbert)的形式主义:
公理化方法与形式化方法,元数学和证明论,提倡将逻辑演算和数学证明本身形式化,把用普通的语言传达的内容上的数学科学变为用数学符号和逻辑符号按一定法那么排列的一堆公式。
为了消除悖论,要数学建立在公理化根底上,将各门数学形式化,构成形式系统,并证明其一致性,这是希尔伯特的数学纲领。
7.数理逻辑的开展初期
哥德尔(Godel,1906~1978)不完全性定理:
一个足够强大的形式系统,如果是一致的那么不是完全的,即有的判断在其中是不可证的,既不能断定其为假,也不能证明其为真。
各种计算模型:
哥德尔的递归函数理论,邱吉尔的λ演算,图灵机模型
这些计算模型是计算机科学的理论根底,是计算机的理论模型。
三、预备知识
1.集合的根本概念
集合(set):
集合是数学中最根本的概念之一,不能以更简单的概念来定义(define),只能给出它的描述(description)。
一些对象的整体就称为一个集合,这个整体的每个对象称为该集合的一个元素(member或element)。
用大写字母A,B,C等表示集合,用小写字母a,b,c等表示集合的元素
a∈A表示:
a是集合A的元素,或说a属于集合A
a∉A表示:
a不是集合A的元素,或说a不属于集合A
集合中的元素是无序的,不重复的。
通常使用两种方法来给出一个集合:
列元素法:
列出某集合的所有元素,如:
A={0,1,2,3,4,5,6,7,8,9}表示所有小于10的自然数所构成的集合
B={a,b,…,z}表示所有小写英文字母所构成的集合
性质概括法:
使用某个性质来概括集合中的元素,如:
·
A={n|n是小于10的自然数}
C={n|n是质数}表示所有质数所构成的集合
集合由它的元素所决定,换句话说,两个集合A和B相等,记为A=B,如果A和B具有相同的元素,即a属于集合A当且仅当a属于集合B。
子集(subset):
说集合A是集合B的子集,记为A⊆B,如果a属于集合A那么a也属于集合B。
因此A=B当且仅当A⊆B且B⊆A。
说集合A是集合B的真子集(propersubset),如果A⊆B且A不等于B(A≠B)。
空集(emptyset):
约定存在一个没有任何元素的集合,称为空集,记为φ,有时也用{}来表示。
按子集的定义,空集是任何集合的子集(为什么?
)。
幂集(powerset):
集合A的幂集,记为P(A),是A的所有子集所构成的集合,即:
P(A)={B|B⊆A}
例如,A={0,1},那么P(A)={{},{0},{1},{0,1}}
显然,对任意集合A,有φ∈P(A)和A∈P(A)
补集(complementset):
集合A的补集,记为A,是那些不属于集合A的元素所构成的集合,即A={x|x∉A}。
通常来说,是在存在一个全集U的情况下讨论集合的补集。
全集U是所讨论的问题域中所有元素所构成的集合。
集合的并(union):
集合A和B的并A⋃B定义为:
A⋃B={x|x∈A或者x∈B},集合的并可推广到多个集合,设A1,A2,…,An都是集合,它们的并定义为:
A1⋃A2…⋃An={x|存在某个i,使得x∈Ai}
集合的交(intersection):
集合A和B的并A⋂B定义为:
A⋂B={x|x∈A而且x∈B},集合的交也可推广到多个集合,设A1,A2,…,An都是集合,它们的交定义为:
A1⋃A2…⋃An={x|对所有的i,都有x∈Ai}
集合的差(difference):
集合A和B的差A-B定义为:
A-B={x|x∈A而且x∉B}。
2.关系和函数的根本概念
有序对(orderedpair):
设A和B是两个集合,a∈A,b∈B是两个元素,a和b的有序对,记为<
a,b>
,定义为集合{{a},{a,b}}。
设<
a1,b1>
和<
a2,b2>
是两个有序对,可以证明<
=<
当且仅当a1=a2且b1=b2。
(如何证?
)
有序对可推广到n个元素,设A1,A2,…,An是集合,a1∈A1,a2∈A2,…,an∈An是元素,定义有序n元组(orderedn-tuple)<
a1,a2,…,an>
为<
<
a1,a2,…,an-1>
an>
,注意这是一个归纳(inductive)定义,将有序n元组的定义归结为有序n-1元组的定义。
显然有<
b1,b2,…,bn>
当且仅当a1=b1且a2=b2且…且an=bn。
集合的笛卡尔积(cartesianproduct):
两个集合A和B的笛卡尔积A⨯B定义为:
A⨯B={<
|a∈A且b∈B}
例如,设A={a,b,c},B={1,2},那么:
A⨯B={<
a,1>
<
a,2>
b,1>
b,2>
c,1>
c,2>
}
笛卡尔积可推广到多个集合的情况,集合A1,A2,…,An的笛卡尔积定义为:
A1⨯A2⨯…⨯An={<
|a1∈A1且a2∈A2且…且an∈An}
集合之间的关系(relation):
定义n个集合A1,A2,…,An之间的一个n元关系R为集合A1,A2,…,An的笛卡尔积A1⨯A2⨯…⨯An的一个子集。
∈A1⨯A2⨯…⨯An,假设<
∈R,那么称a1,a2,…,an间具有关系R,否那么称它们不具有关系R。
特别地:
当A1=A2=…=An=A时,称R为A上的n元关系。
当n=2时,有R⊆A1⨯A2,称R为A1与A2间的一个二元关系(binaryrelation)。
这时假设<
a1,a2>
∈R那么简记为a1Ra2,否那么〔即<
∉R〕记为a1Ra2。
通常研究得最多的是二元关系,n元关系的许多性质可从二元关系的性质扩充而得到。
如果没有特别指明的话,说R是一个关系那么是指R是一个二元关系。
当n=1时,这时可认为R是集合A上满足某种性质的子集。
关系的一些性质:
设R是A上的二元关系:
说R是自反的(reflexive),如果对任意的a∈A有aRa。
说R是反自反的(irreflexive),如果对任意的a∈A有aRa。
说R是对称的(symmetric),如果对任意的a,b∈A有假设aRb那么bRa。
说R是反对称的(antisymmetric),如果对任意的a,b∈A有假设aRb且bRa那么a=b。
说R是传递的(transitive),如果对任意的a,b,c∈A有假设aRb且bRc那么aRc。
说R是等价关系(equivalence),如果R是自反的、对称的和传递的。
集合之间的函数(function,或说映射mapping):
定义集合A到B的函数f是A和B的笛卡尔积A⨯B的一个子集,且满足假设<
x,y>
∈f及<
x,z>
∈f那么y=z。
因此函数是A和B之间的一个特殊的二元关系。
通常记集合A到B的函数f为f:
A→B。
函数f:
A→B的定义域(domain)dom(f)定义为:
dom(f)={x|存在某个y∈B使得<
∈f}
A→B的值域(range)ran(f)定义为:
ran(f)={y|存在某个x∈A使得<
假设<
∈f,通常记y为f(x),并称y为x在函数f下的像(image),x为y在函数f下的原像。
函数也可推广到n元的情形:
f:
A1⨯A2⨯…⨯An→B,意味着:
f是A1⨯A2⨯…⨯An⨯B的一个子集,且
x1,x2,…,xn,y>
∈f且<
x1,x2,…,xn,z>
∈f那么y=z。
函数的一些性质:
设f:
A→B是集合A到B的函数:
说f是全函数(totalfunction),假设dom(f)=A,否那么称f是偏函数(partialfunction)。
下面如果没有特别指明的话,都是指全函数。
说f是满射(surjection,或说fmapsAontoB),如果ran(f)=B,即对任意的y∈B都有原像。
说f是单射(injection,或说fisone-one),如果有f(x1)=f(x2)那么x1=x2,即对任意的y∈B,如果它有原像的话,那么有唯一的原像。
说f是双射(bijection,或说f是一一对应),如果f既是满射,又是单射,即对任意的y∈B,都有唯一的原像,同样根据全函数的定义,对于任意x∈A都有唯一的像。
这时可以定义f的逆函数(inversefunction),记为f-1:
B→A,f-1(y)=x当且仅当f(x)=y。
显然f-1也是双射。
集合的基数(cardinalnumber)或说势:
集合A的基数记为|A|,且有:
对于有限集合A,令A的基数为A中元素的个数。
定义无限集合,不直接定义基数,而是通过定义两个集合之间的等势关系来刻划集合的基数或势,说集合A和集合B是等势的(equipotent),如果存在一个从A到B的双射。
根据双射的性质,可以证明等势是集合上的一个等价关系。
称与自然数集等势的集合为可列集(enumerable),有限集和可列集统称为可数集(countable)。
设A和B是有限集合,有|P(A)|=2|A|,|A⨯B|=|A|⨯|B|。
3.小结
下面以树的形式给出了以上主要概念之间的关系:
集合
子集集合的补、并、交、差有序对
幂集笛卡尔积
关系
关系的自反、对称、传递性函数
单射、满射、双射
4.归纳定义和归纳证明
一个集合的归纳定义(inductivedefinition)通常分为三步:
归纳基:
一些根本的元素属于该集合;
归纳步:
定义一些规那么〔或者说操作〕,从该集合中已有的元素来生成该集合的新的元素;
最小化:
该集合中的所有元素都是通过根本元素以及所定义的规那么生成的,换句话说,该集合是由根本元素及规那么所生成的最小的集合。
自然数集N的归纳定义:
[1].归纳基:
0是一个自然数,即0∈N。
[2].归纳步:
假设n是自然数,那么n的后继也是自然数。
记n的后继为succ(n),即假设n∈N,那么succ(n)∈N。
为方便起见,后面也记n的后继为n+1。
[3].最小化:
所有的自然都通过步骤[1]和[2]得到,或者说自然数集是通过步骤[1]和[2]得到的最小集合。
这种定义方式可推广到对其他一些概念的定义,例如上述多个集合的并、交、笛卡尔积以及多个元素的有序n元组都可通过递归的方式定义。
例如,对于多个集合的并可定义为:
A1⋃A2={x|x∈A1或者x∈A2}
A1⋃A2…⋃An=(A1⋃A2…⋃An-1)⋃An
这里不需要最小化,因为这里不是定义集合。
数学归纳法:
关于自然数的许多性质都可通过数学归纳法来证明,对于性质R,如果它对0成立,而且如果对于n成立的话,能够得到它对于n+1也成立,那么性质R对所有的自然数成立。
这种证明方法的正确性本身可通过自然数的归纳定义来得到证明:
定义集合S={n∈N|性质R对n成立}
根据上面的定义有0∈S
根据上面的定义有如果n∈S,那么n+1∈S,所以S是满足上面自然数集的归纳定义中的1、2点的一个集合,而自然数集N是满足这两点的最小集合,所以有N⊆S,而显然有S⊆N,所以S=N。
数学归纳法举例:
使用数学归纳法证明1+2+…+n=(n*(n+1))/2
当n=0时显然成立。
如果对于n成立,那么有1+2+…+n=(n*(n+1))/2〔这称为归纳假设〕,现在要证对于n+1也成立。
显然有:
1+2+…+n+(n+1)=(n*(n+1))/2+(n+1)//根据归纳假设
=(n*(n+1)+2*(n+1))/2=((n+1)*((n+1)+1))/2
因此要证的公式对于n+1成立,所以对于所有的自然数成立。
显然在数学归纳法中,对于归纳基改为R对于自然数k成立,归纳步不变的话,那么可证明R对于所有大于k的自然数都成立。
在数学归纳法中,也可将归纳步改为如果R对于所有小于n的自然数成立,那么推出R对于n也成立,即归纳步是假设对于所有小于n的自然数性质R成立来导出性质R对于自然数n成立。
这种形式的数学归纳法通常称为第二数学归纳法。
5.形式系统
形式系统的定义:
一个形式系统S由以下4个集合构成:
一个非空集合∑S,称为形式系统S的字母表或说符号(Symbol)表;
一个由∑S中字母的有限序列〔字符串〕所构成的集合FS,称为形式系统S的公式(Formula)集;
从FS中选取一个子集AS,称为形式系统S的公理(Axiom)集;
FS上有一个局部函数集RS={Rn|Rn:
FS⨯FS⨯…⨯FS→FS,n=1,2,…},称为形式系统S的规那么(Rule)集,其中Rn:
FS⨯FS⨯…⨯FS→FS是n元的局部函数,我们称其为n元规那么。
形式系统中的定理(Theorem):
t∈AS是形式系统S中的定理。
归纳步:
t1,t2,…,tn是形式系统S中的定理,而Rn∈是S中的规那么,那么Rn(t1,t2,…,tn)也是形式系统S中的定理。
对于形式系统中的规那么Rn:
FS⨯FS⨯…⨯FS→FS,通常表示成下面的形式:
t1,t2,…,tn
Rn(t1,t2,…,tn)
形式系统具有两个特征:
形式化实际上是一个可机械实现的过程,在它里面,符号、规那么和演算等被表示得严密、精确。
在形式系统S中,只能使用字母表∑S中的符号,只成认公式集FS中的符号串的合理性,只能由公理集,根据规那么推出有意义的东西来。
形式系统一旦完成,就成了符号串及根据规那么进行的符号串的改写,系统与一切实际意义就毫不相干,或者说已经通过这种符号,从实际问题中抽象出了我们所需要研究的内容。
在形式系统内部,所能认识的只能是符号串及其改写,只能在形式系统外对这种符号串及规那么赋予意义。
对象语言(Objectlanguage)与元语言(Metalanguage):
数理逻辑所研究的是“数学推理〞,而使用的方法也是数学推理,所以有必要区分这两个层次的推理。
把作为研究对象的“推理〞形式化,使用形式语言来表示作为研究对象的“推理〞的前提、结论和规那么等,这种形式语言是我们所研究的对象语言。
另一方面,关于形式系统的性质、规律的表达和作为研究方面的推理方式使用另一种语言来表达,这个语言称为研究的元语言,通常使用半数学化的自然语言。
形式语言的语法(Syntax)与语义(Semantic):
形式语言的语法是构成形式系统的公式集、公理集和规那么集的法那么。
形式语言的语义是关于形式系统的解释和意思。
形式语言本身没有含义,但我们在构造它们时是假想它们能代表某种意义的,特别的当我们在选择形式系统的公理时,总是选择所研究的问题域中那些最为明显或最容易公认为正确的性质。
6.习题
1.令集合A={n|n≤10且n是奇数},B={n|n≤10且n是素数},请答复以下问题:
a)请用列元素的方法列出集合A和集合B,请问集合B是否是集合A的子集?
b)请计算A⋃B、A⋂B、A-B、A⨯B以及P(A)(即A的幂集)。
2.设关系R={<
|a和b是互质的自然数},请问R是自反的吗?
对称的吗?
传递的吗?
为什么?
3.设f:
A→B是函数,R是A上的如下二元关系:
R={<
|a,b∈A,f(a)=f(b)},证明R是A上的一个等价关系。
4.使用数学归纳法证明:
12+22+32+…+n2=(n*(n+1)*(2n+1))/6
5.设有函数f:
N→N⨯N,f(n)=<
n,n+1>
,请问f是不是单射、满射或双射?
*6.设R1和R2都是A上的等价关系,请问R1⋃R2和R1⋂R2是否还是A上的等价关系?
如果是请证明,否那么请举一反例。
*7.设R是集合A上的等价关系,a∈A,可定义:
a)[a]={b∈A|aRb},称[a]为a关于R的等价类;
b)A/R={[a]|a∈A},称A关于R的商集。
设函数f:
A→A/R定义为对任意a∈A有f(a)=[a],请问R满足怎样的条件时f是单射?
*8请给出<
x,y,z>
的集合方式的定义。
假设定义:
[x,y,z]={{x},{x,y},{x,y,z}},那么如果有[x1,y1,z1]=[x2,y2,z2]是否意味着有x1=x2且y1=y2且z1=z2?
第二讲数理逻辑
一、命题逻辑(PropositionalLogic)
1.内容概述
简单命题与复合命题:
什么是命题?
命题联结词及其含义。
命题公式与赋值:
命题逻辑公式的归纳定义,命题公式的真值表。
等值演算:
命题公式的等值赋值,重要的等值式。
命题联结词的完备集:
通过等值演算得到命题联结词的完备集和极小完备集。
命题公式的范式:
析取范式与合取范式。
命题演算系统:
使用命题逻辑公式进行推理的形式系统。
命题演算系统的语义与命题演算系统的元性质:
注意区别形式系统的语法和语义。
2.简单命题与复合命题
命题(proposition):
经典命题逻辑中,称能判断真假但不能既真又假的陈述句为命题。
命题对于命题逻辑来说是一个原始的概念,不能在命题逻辑的范围内给出它的精确定义,只能描述它的性质。
命题必须为陈述句,不