数理逻辑教程

数理逻辑教程2009任世军哈尔滨工业大学计算机学院2009.11目录1命题演算形式化系统71.1命题演算的基本概念..............................................71.1.1命题与联结词..............................................71.2形式语言与命题公式..............................................101.2.1形式语言的定义.............................................101.3命题公式的语义.................................................111.3.1联接符号的含义.............................................111.3.2赋值...................................................111.3.3赋值的计算模式.............................................121.4命题公式的分类.................................................131.5命题演算的语义推理..............................................141.6范式........................................................171.7联结词的扩充与归约..............................................181.8命题演算形式系统PC..............................................211.8.1语言部分.................................................211.8.2推理部分.................................................211.9命题演算形式系统PC的定理..........................................221.10命题演算形式系统PC的基本理论.......................................311.11命题演算形式系统ND..............................................351.12形式系统PC和ND的等价性..........................................382一阶谓词演算412.1一阶谓词演算的基本概念............................................412.1.1谓词和函词...............................................412.1.2变元和常元...............................................4232.1.3量词...................................................432.2谓词公式.....................................................442.2.1n元关系和n元函数...........................................442.2.2全称量词符号和存在量词符号.....................................442.3一阶谓词演算形式系统.............................................442.3.1一阶语言.................................................452.3.2一阶逻辑.................................................462.4一阶谓词演算形式系统的语义.........................................512.5关于FC的重要元定理..............................................532.5.1FC的合理性...............................................532.5.2FC的完备性和其他...........................................543好记性不如烂笔头573.1PC中定理的证明方法..............................................573.2反证法思想在公理系统中定理证明的应用..................................603.3逆否命题在公理系统中定理证明的应用....................................634真值和演绎654.1唯一阅读定理..................................................654.2谓词逻辑部分..................................................66目录5两个人在相互争论，由第三个人来评判哪个人的论断更有效。也就是判断哪个人的辩解符合逻辑。这里逻辑代表的是一个什么样的概念呢？它可以代表不正确，但这也不是很准确。也可以说不合常理，与正常人的想法不一致。其实，不合逻辑的含义是不符合正确的思维规律。所以逻辑是研究思维规律的科学。思维具有三要素。那就是概念、判断和推理。从数学的角度理解：概念指的是特定的子集；判断指的是元素和子集之间的关系；推理指的是对判断的合理的推演。数理逻辑电子教案哈尔滨工业大学计算机学院6目录任世军[e-mail]第一章命题演算形式化系统命题逻辑研究命题的推理演算.这一章研究命题的基本概念,命题连接词,讨论命题公式,重言式以及自然语句的形式化.1.1命题演算的基本概念1.1.1命题与联结词定义1.1.1命题是一个能判断真假的陈述句。有两层意思,首先命题是一个陈述句,命令句感叹句疑问句都不是命题.其次,这个陈述句所表达的内容可以决定是真还是假,而且不是真的就是假的.不能不真又不假,也不能即是真又是假.凡是与实事相符的陈述句（命题）为真语句,而与实事不相符的陈述句（命题）为假语句.即命题有两种可能的取值(又叫真值),是真或者是假,并且只能取其中之一.用T表示真,F表示假.或者用1表示真,0表示假.真、假（T,F或者0,1）又称为真值。命题概念的举例说明:1.雪是白的是一个陈述句,可以决定它的真值.其真值为真.所以是一个命题.2.雪是黑的是一个陈述句,可以决定它的真值.其真值为假.所以是一个命题.3.好大的雪啊不是陈述句,所以不是命题.4.任何一个大偶数可以表成两个素数之和(哥德巴赫猜想)是一个陈述句,或真或假,是命题.5.太阳有第11颗行星也是命题.6.2+2=5.7.2是素数又是偶数.8.陈胜吴广起义之日杭州下雨.9.你上哪儿去？10.这句话是假的。11.x+y078第一章命题演算形式化系统真值的联结词,2是素数又是偶数.即是说2是素数并且2是偶数.这里的并且称之为真值的联结词.原子命题(原子),不含有真值的联结词的命题称之为原子命题(原子).复合命题.非原子命题称为复合命题.复合命题举例:1.雪不是白的(并非雪是白的).2.今晚我去看朋友或者去看电影.3.她不但漂亮而且聪明.4.如果我有车,那么我去接你.5.a是偶素数当且仅当a=2.原子命题的符号表示：用小写的拉丁字母表示。这些符号表示确定的命题时称为命题常元，表示不确定的命题时称为命题变元。取值为0，1。t,f表示真值为1，0的命题常元。1.命题变项为了进行逻辑演算,必须将命题符号化(形式化).数理逻辑中约定用大写的字母表示命题.例如可以用P表示雪是白的,Q表示北京是中国的首都等.当P表示任一命题时,P就称为命题变项(变元).由于命题变项表示的是不确定的命题,所以不能判定其是真还是假.但是在逻辑推演过程中,我们认为它表示的是一个实实在在命题.2.简单命题和复合命题简单命题又称为原子命题.它不包含任何连接词.这样的命题不可再分割.如果再分割就不能成为命题了.例如雪是白的而且1+1=2可以分割成雪是白的和1+1=2两个命题.但是雪是白的不能再分割.所以是原子命题即简单命题.而雪是白的而且1+1=2不是简单命题.把一个或几个简单命题用联接词(如与,或,非)联结所构成的命题称为复合命题,也称为分子命题.复合命题也是陈述句,其真值依赖于构成它本身的原子命题的真值以及构成该复合命题的联结词.命题逻辑讨论的是多个命题联结而成的复合命题的规律性.3.命题联结词和真值表联结词可以将命题联结起来构成复杂的命题.命题联结词起的作用如同加减乘除在实数理论中的位置.这里介绍逻辑联结词:,^,_,,.4否定词否定词是一个一元联结词,也称为否定符号.一个命题P加上否定词就形成了一个新的命题,记作P.这个新命题是原来命题的否定,读作非P.否定词的真值规定如下:若命题P的真值为真,那么P的真值就为假;若P的真值为假,那么P的真值就为真.与之间的真值关系,常常使用称作真值表的一种表格来表示.即PPTFFT或者PP1001任世军[e-mail]1.1命题演算的基本概念9也可以将上表看作是对P的定义,它表明了P的真值如何依赖于P的真值.真值表描述了命题之间的真值关系.直观明了,当命题变项不多时也很容易建立起来.真值表是命题逻辑里研究真值关系的重要工具.例1.1.1昨天张三去看球赛了.该命题用P表示,于是昨天张三没去看球赛了,该新命题便可用P表示.若昨天张三去看球赛了,命题P是真的,那么新命题P必然是假的.反之,若命题P是假的,那么P就是真的.例1.1.2Q:今天是星期三.Q:今天不是星期三.5合取词^合取词^是个二元命题联结词,也称为合取符号.将两个命题P,Q联结起来,构成一个新的命题P^Q,读作P,Q的合取,也读作P与Q,这个新命题的真值与构成它的命题P,Q的真值间的关系,由合取词真值表规定出来.PQP^QFFFFTFTFFTTT该表指出只有当两个命题变项P=T,Q=T时才有P^Q=T,而P,Q只要有一个为F,则P^Q=F.这样P^Q可以用来表示P与Q,或者P并且Q.例1.1.3P:教室里有10名女学生.Q:教室里有15名男学生.于是教室里有10名女学生并且教室里有15名男学生便可以由P^Q来表示.6析取词_析取词_是个二元命题联结词,也称为析取符号.将两个命题P,Q联结起来,构成一个新的命题P_Q,读作P,Q的析取,也读作P或Q,这个新命题的真值与构成它的命题P,Q的真值间的关系,由析取词真值表规定出来.PQP_QFFFFTTTFTTTT该表指出只有当两个命题变项P=F,Q=F时才有P_Q=F,而P,Q只要有一个为T,则P_Q=T.这样P_Q可以用来表示P或Q.例1.1.4P:今天刮风.Q:今天下雨.于是今天刮风或者今天下雨便可以由P_Q来表示.7蕴含词蕴含词也是个二元命题联结词,也称为推断符号.将两个命题P,Q联结起来,构成一个新的命题PQ,读作如果P则Q,也读作P蕴含Q,如果P那么Q,其中P称为前件(前项,条件),Q称为后件(后项,结论).规定只有当P为T,Q为F时,PQ=F.除此之外,PQ=T.数理逻辑电子教案哈尔滨工业大学计算机学院10第一章命题演算形式化系统PQPQFFTFTTTFFTTT图1.1:PQ真值表PQP_QFFTFTTTFFT