第一章命题逻辑

1.1命题符号化及联结词[教学重点]命题的概念和六个联结词的定义[教学目的]1：使学生了解逻辑的框架，命题逻辑的基本要素是命题。2：通过示例理解命题的概念。3：通过示例理解合取、析取、异或、蕴涵、等价的含义，了解逻辑语言的精确性，为学习逻辑学打好基础。4：学会命题符号化的方法。[教学准备][教学方法]讲述法[课时安排]二课时。[教学过程]讲述：逻辑是解决推理方法的学科，中心是推理，基本要素是命题，称为命题逻辑。数理逻辑则是用数学方法研究推理；首先要理解命题是什么，然后了解怎样用数学方法描述命题，甚至逻辑推理。后者是命题符号化的问题。板书：第一章命题基本概念1.1命题及其符号化讲述：首先讨论命题。板书：一命题A)概念：能判断真假的陈述句。判断要点：a陈述句；b或真或假，唯一真值；讲述：例：(1)地球是圆的；真的陈述句，是命题(2)2+3=5；真的陈述句，是命题(3)你知道命题逻辑吗？非陈述句，故非命题(4)3-x=5；陈述句,但真假随x的变化而变化，非命题(5)请安静！非陈述句，故非命题(6)火星表面的温度是800C；现时不知真假的陈述句，但只能要么真要么假，故是命题(7)明天是晴天；尽管要到第二天才能得知其真假，但的确是要么真要么假，故是命题(8)我正在说谎；无法得知其真假，这是悖论注意到(4)不是命题，后续章节中会提到，这被称为谓词，命题函数或命题变项。板书：B)命题的真值表示：真：1或T假：0或FC)分类：a简单命题，通常用p,q,r,…,等表示命题变项和命题常项；b复合命题，由简单命题和联结词构成；讲述：简单命题可以简单地用单个字母表示，但复合命题还包含了联结词，多个命题变项由联结词联结起来成为复合命题。所以还需要考虑联结词的问题。板书：二逻辑联结词讲述：首先最为简单的一种情况，就是日常语言中所说的“不”，这是对原有意思的的否定，所以称为否定式板书：1)否定式和否定联结词：命题p的非或否定，称为p的否定式，表示为p；符号即为否定联结词。用表格表示：ppTFFT讲述：严格说，p不是复合命题。示例：p：今天天气好；p：今天天气不好p：2＋51；p：2+5≤1；在此情形下，p为真，p为假。讲述：问题：北京和上海都是中国的直辖市。显然这个句子可分成两个句子，中间由“和”、“且”之类的联结词联结。这类的联结词我们统称为“合取”。板书：2）合取式和合取联结词p且q称为qp,的合取式，记为qp；符号即为合取联结词。pqp∧qTTTTFFFTFFFF逻辑“与”。讲述：相应的日常用语还有一些。板书：“既…又…”，“不但(仅)…而且…”，“虽然…但是…”。讲述：例：1)p:今天大太阳，q:今天热，p∧q:今天大太阳且热；2)p:今天上课有人迟到，q:2+51,p∧q:今天上课有人迟到且2+51；3)p:李平聪明，q:李平用功，p∧q:李平虽然聪明，但不用功；讲述：注意到2)中的结果，我们可以用逻辑联结词来联结两个日常生活中无关的命题。另外也要注意日常语言中的“和”，不一定都能用∧表示。示例：“新闻和报纸不分家”，“我和你是同学”。讲述：“或”也是非常常用的联结词。例：(1)文文或华华今天出差。(2)他今天骑车或走路来上课。讲述：(1)一般情况下两个人可能同时去出差，即可以同时为真，是相容的，所以是“相容或”。板书：相容或讲述：(2)在这两种情况下，或者发生一种，或者都不发生(如他今天是乘公共车来上课的)，但不可能二者同时发生，即不可能二者同时为真，所以是“相斥或”。在自然语言中类似的“相斥或”是很多的，又如“刘苘或李兰是三班班长”。板书：相斥或我们可以看到在日常语言中，“或”具有多义性，但我们用符号表示时，却必须避免这种歧义性。通常把相容或称为“析取”，而相斥或则称为“异或”。板书：3）析取式和析取联结词p或者q称为p，q的析取式，记为p∨q；符号即为析取联结词。pqp∨qTTTTFTFTTFFF逻辑“或”讲述：“如果…则…”也是一类常见的联结词。这是有条件和结论的一类，称为“条件式”，也称为“蕴涵式”。板书：4）蕴涵式和蕴涵联结词如果p则q称作p、q的蕴涵式，记为qp。为蕴涵联结词，p、q分别为蕴涵式的前件和后件。讲述：示例:一位父亲对儿子说：“如果星期天天气好，就一定带你去动物园。”问：在什么情况下父亲食言？父亲的可能情况有如下四种：(1)星期天天气好，带儿子去了动物园；(2)星期天天气好，却没带儿子去动物园；(3)星期天天气不好，却带儿子去了动物园；(4)星期天天气不好，也没带儿子去动物园。显然，(1),(4)两种情况父亲都没有食言；(3)这种情况和父亲原来的话没有相抵触的地方，当然也不算食言；只有(2)这种情况，答应的事却没有做，应该算是食言了。(2)对应着“前件真后件假”的情况，使得蕴涵式为假，而其它三种情况都使得蕴涵式为真。板书：pqpqTTTTFFFTTFFT讲述：这里注意到：在蕴涵式pq中，p是q的充分条件，q是p的必要条件。这类的联结词还有：板书：pq：“只要p就q”，“p仅当q”，“只有q才p”等讲述：蕴涵式的一个应用：数学归纳法(1)证明P(n0)成立；(2)证明当k≥n0时P(k)P(k+1)总是成立。在(2)中，P(k)P(k+1)总是成立，意味着P(k)P(k+1)的真值为T，从而只可能是上述表中的第1,2,4种情形，而(1)中证明了前件为真，所以后件也一定为真。讲述：前面讲述描述了充分条件或必要条件的表示，现在我们可以表示充要条件了：“p是q的充要条件”，“p是q的充分条件”且“p是q的必要条件”，可以用蕴涵和合取两者描述。板书：pq∧qp讲述：这个表达式较为复杂，所以用一个联结词“等价”简单表示。自然语言中通常表述为“当且仅当”板书：5）等价式和等价联结词p当且仅当q称作p、q的等价式，记为qp。称为等价联结词。pqqpTTTTFFFTFFFT讲述：以上介绍了五种常用的逻辑联结词以及与之相关的复合命题。这些联结词反映了复合命题及其支命题之间抽象的逻辑关系。复合命题的符号化一般可以根据上述定义进行，基本步骤如下：板书：符号化基本步骤：1)找出各个支命题，并逐个符号化；2)找出各个连接词，符号成相应联结词；3)用联结词将各支命题逐个联结起来；示例：将下列命题符号化：(1)辱骂和恐吓决不是战斗；(2)李瑞和李珊是姐妹；(3)除非天气好，否则我是不会去公园的；(5)李明是计算机系的学生，他住在312室或313室．讲述：分析并符号化，强调在进行命题符号化以前，必须明确含义，删除歧义，这是命题翻译的关键之点。(1)p：辱骂是战斗；q：恐吓是战斗。符号化为p∧q。(2)p：李瑞和李珊是姐妹。符号化为p。(3)p：今天天气好；q：我去公园。符号化为qp。(4)p：李明是计算机系的学生；q：李明住在312室；r：李明住在313室。因为李明不可能既住在312室又住在313室，符号化为p∧((q∧r)∨(q∧r))或者p∧(q∨r)讲述：最后，复习一下本节所讲述的内容。作业：1.2命题公式和真值赋值[教学重点]合式公式及层次，解释的含义，真值表的构成。[教学目的]1：使学生了解合式公式和公式层次的定义，理解递归定义法的方法。2：学会描述公式的形成过程。3：理解解释的含义，领会公式分类的要点。4：使学生了解并学会应用真值表的构成方法。5：复习并进一步理解命题逻辑的基本概念。[教学准备][教学方法]讲述法[课时安排]二课时。[教学过程]讲述：复习并示例：判断是否式命题，如果是，则符号化。1)922+97+1；2)x+563)理发师只给所有那些不给自己理发的人理发；（罗素悖论）4)李兰现在在宿舍或在图书馆里；5)蓝色和黄色可以调配成绿色；6)如果晚上小王做完了做业并且没有其他事情，他就看电视或看电影。问题：在6)中获得一个长串的字符串，这里当然表示了一个命题，但是不是任何一个字符串能表示一个命题呢？或者称为命题公式呢？抽象地说，命题公式是由命题常项、命题变项、联结词、括号等组成的符号串，但并不是由这些符号任意组成的符号串都是命题公式。板书1.2合式公式及其解释讲述：首先自然先要了解什么公式。板书：一合式公式1)合式公式：(1)p,q,r,…,1,0是合式公式；(2)如果A是合式公式，则A也是；(3)如果A和B是合式公式，则p、pq、pq、pq、pq也是；(4)有限次应用(1)-(3)构成的符号串才是合式公式。讲述：上述定义方法称为递归定义法（递归就是一个过程直接或间接地调用自己），递归法定义是离散数学中常用的方法。其中，（1）是递归定义的基础，直接规定简单的内容；（2）,（3）是递归定义的归纳，规定了是由简单到复杂的过程；（4）是递归定义的界限，规定了满足前述（1）~（3）条件的最小范围。（递归算法在计算机中容易实现，如C语言中的汉诺塔、n的阶乘、求两个数的最小公约数就是用递归的方法实现的）板书：递归定义法：递归基础、递归归纳、递归界限讲述在一个复杂的公式中，为了避免歧义需要引进许多的括号，但如果括号太多会使人眼花缭乱，如((p(qr))((pq)(rs)))，共有6对括号，书写简单，可以省略括号板书：省略括号的约定：(1)公式最外层的括号可以省略；(2)规定联结词的运算优先级别由高到低是：、、、、，若无括号，优先级高的先运算；(3)若同一个联结词连续多次出现且无括号，则按从左到右的顺序运算。讲述：按照上述约定，((p(qr))((pq)(rs)))省略了三对括号简化为p(qr)(pq)(rs)。省略括号只是让公式书写简便，但并不能改变其复杂性。示例(1)(((pq)∧(qr))(p∨r))p、q是公式，(pq)是公式；q、r是公式，(qr)是公式；((pq)∧(qr))是公式；p、r是公式，(p∨r)是公式；(((pq)∧(qr))(p∨r))是公式。这样一个命题公式的形成过程简单表述为：p，q，(pq)；q，r，(qr)；((pq)∧(qr))；p，r，(p∨r)；(((pq)∧(qr))(p∨r))。(2)((p∧q)qr)p，q，(p∧q)；q，r，qr不是；((p∧q)qr)不是。讲述：显然，有些公式的字符串很长，有些很短，甚至只有单个字母，这样公式的复杂性必然有所不同，为了描述这种复杂性，引入公式层次来描述。板书：二合式公式的层次：(1)如果A是单个命题常项或命题变项p,q,r,s,…,0,1，则称A是0层公式；(2)称A是n+1(n0)层公式，是指A符合下列情况之一：(a)A=B，B是n层公式；(b)A=(BC)，其中B、C分别是i层和j层公式，且n=max(i,j)；(c)A=(BC)，其中B、C的层次同(b)；(d)A=(BC)，其中B、C的层次同(b)；(e)A=(BC)，其中B、C的层次同(b)；示例：(1)(pq)∨(r∧(p∨s))(2)q(p∨s)(1)p,s是0层公式，p∨s是1层公式;r是0层公式,r∧(p∨s)是2层公式；p,q是0层公式，但pq是1层公式；(pq)∨(r∧(p∨s))是3层公式。公式层次是3。(2)q是0层公式,q是1层公式；p,s是0层公式，p∨s是1层公式;(p∨s)是2层公式；但q(p∨s)不是公式。讲述：一般来说，一个含有命题变项的命题公式，其真值是不确定的。只有给其每个命题变项都指定确定的真值，命题公式才会有确定的真值。给定一个真值，就是给命题变项一个赋值，相当于给定一个日常语言中某个具体的句子，即给定一个解释。板书：三真值赋值令A是一命题公式，p1,p2,…pn是出现在A中的所有命题变项，给p1,p2,…pn指定一组真值，称为对A的一个赋值或解释。成真赋值：若指定的一组值使得A的值为真，称这组值为A的成真赋值；成假赋值：若指定的一组值使得A的值为假，称这组值为A的成假赋值。一个含有n个命题变项的命题公式，共有2n个赋值。示例例已知A是含命题变项p,q,r的命题公式，