第1章命题逻辑的基本概念.ppt

1,离散数学,2010.9,2,绪论,离散数学与高等数学的区别1.研究对象：高等数学：连续量离散数学：离散量2.处理方法高等数学：无限过程离散数学：有限过程,3,二.离散数学的主要内容,数理逻辑：用数学方法研究判断和推理理论集合论初步：集合基本运算，二元关系理论数论：研究整数的性质代数结构：研究集合及其上面的运算性质图论：图的基本理论,4,二.学习离散数学的意义,1.掌握离散量的处理方法，为后续课程作准备。2.为学习电气信息类课程奠定数学基础。3.训练离散思维能力。,5,第一部分数理逻辑,数理逻辑是逻辑学的一个分支。而逻辑学是研究人的思维形式和规律的科学。数理逻辑：用数学的方法研究推理，是研究推理中前提和结论的形式关系的科学。推理：由一个或几个判断推出一个新判断的思维形式。数学方法：建立一套符号体系，对具体事务进行抽象的形式研究方法。数理逻辑也称为符号逻辑。本部分主要内容：命题逻辑和谓词逻辑,6,第一章命题逻辑基本概念,研究主要内容：以命题为单位构成的前提和结论之间的可推导关系。具体内容命题与联结词命题公式及其赋值,7,1.1命题与联结词,命题的概念（1）命题定义：凡是能够确定或能够分辨出真假的陈述句。且真假值二者必居其一。例1.1判断下列句子是否为命题我是大学生。2不是偶数。请进！火星上有水。你考试了吗？我说的都是假的月亮真圆啊！张三和李四都是运动员。2是素数且为偶数。,8,（2）命题的取值及其表示真（T或1），假（F或0），（3）命题的分类原子命题：命题本身不能再分解成为其它的命题。复合命题：命题可能分解成为其它的命题。2.命题标识符命题的符号表示用特定的符号表示命题及其它成分命题通常用大写字母p,q,r或打下标的符号pi,qi等字符表示。例如p:我是学生。q:2是整数。,9,3.命题联结词,联结词是连结命题的符号，也称为命题运算符。复合命题：用联结词将原子命题联结起来形成的命题。例如：张三和李四都是运动员。常用的联结词：,设p,q为命题，各联结词的定义如下：（1）否定联结词p称为p的否定式复合命题。p的值由p的值确定，见表例1.2设p:我是学生。则p表示：我不是学生。,10,（2）合取联结词pq称为p与q的合取式复合命题。“p与q”pq定义：当且仅当p和q的值均为真时，pq为真。（见下表）,例1.31）张明聪明且努力。2）张明既聪明又努力。3）张明虽然聪明但不努力。,11,（3）析取联结词pq称为p与q的析取式复合命题。“p或q”pq定义：当且仅当p和q的值均为假时，pq为假。例1.41）李明学习英语或法语。2）她正在教室里学习或在操场上打篮球。3）2是素数或3不是素数。4）他做了二十或三十道题。,12,（4）蕴涵联结词pq称为p与q的条件式复合命题。“p蕴涵q”pq定义：当且仅当p为真，q为假时，pq为假。定义见右表：,例1.51）如果明天下雨，我就不去学校。pq2）只要明天下雨，我就不去学校。pq3）除非明天下雨，否则我将去学校。pq4）只有明天下雨，我才去学校。qp设p：明天下雨，q：我去学校。,13,（5）等价联结词,pq称为p与q的等价式。“p当且仅当q”。定义为当且仅当p和q的值相等时，pq为真。,例1.61）a是偶数当且仅当a被2整除。2）三角形全等当且仅当它们对应边相等。3）太阳从东方升起，当且仅当雪是白的。,14,4.联结词的优先级,在一个命题中，可以使用多个联结词，此外，还可以使用括号，当一个命题中出现多个联结词时，规定联结词的优先顺序如下：（），,同一优先级，从左到右顺序进行。例如：如果我去上海，一定去参观东方明珠电视塔，也去南京路购物。设p:我去上海q:我参观东方明珠电视塔r:我去南京路购物则命题符号化为：p(qr)根据联结词的优先级可以简化为pqr,15,练习,将下列命题符号化1.2和3均为整数。2.选李明或张宏当班长。3.只要明天天气好，我就去郊游。4.1+1=10当且仅当数采用二进制。,命题符号化：1.pq其中p:2为整数,q:3整为偶数2.pq,p:选李明当班长,q:选张宏当班长3.pq,p:明天天气好,q:我去郊游4.pq,p:1+1=10,q:数采用二进制,16,1.2命题公式及其赋值,1.命题公式的定义像其它数学公式一样，命题也有公式的概念。命题常项（元）：如果一个命题标识符p，表示一个确定的命题，则称其为命题常元。命题变项（元）：如果p表示任意命题或不确定的命题，就称其为命题变元。注意：命题变元不是命题。描述性定义：用联结词、圆括号按一定逻辑关系将命题变项联结起来的字符串，称为命题逻辑中的合式公式。简称公式。,17,科学定义,定义1.6合式公式是按下列规则形成的字符串：（1）原子命题变元是一个合式公式；（2）若A是合式公式，则（A）是合式公式；（3）若A和B是合式公式，则（AB)，(AB),(AB)，(AB)都是合式公式;(4)经过有限次地使用（1）（2）（3）所得到的结果都是合式公式。,例如p,(p),(pq)r),(pq)s）都是公式；而(pq)r），(p(s)）不是公式。,18,公式的简化处理,在不出现歧义的情况下可以省略括号。规则如下：(1)最外层的括号可以省略；不影响运算顺序的括号也可省略。(2)如果只作用于其后的原子命题变元，则括号省略。如：(p)可以写成p；(pq)r)可以写成pqr可以写成(pq)s,19,2.命题的赋值或解释,定义1.8设p1，p2，,pn是出现在公式A中的全部命题变项，给p1，p2，,pn各指定一个真值，称为对A的一个赋值或解释。若指定的一组值使A的真值为1，则称这组值为A的成真赋值，若使A的真值为0，则称这组值为A的成假赋值。在含有n个命题变项的公式共有2n个不同的赋值。,例1.7写出(pq)r所有的赋值,定义1.9将命题公式A在所有赋值下取值情况列成表，成为A的真值表。,命题的真值表,20,例如：公式pq的真值表为,构造真值表的方法：命题变元按字典顺序或按下标升序排列；对公式的每个赋值，以二进制从小到大排列；先求最内层子公式的值，逐渐向外展开直到求出整个公式的值。,21,例1.8求(pq)s的真值表,22,3.公式分类,