命题逻辑基本概念.ppt

,离散数学是计算机专业的一门核心基础课程。,离散数学课程地位和作用,离散数学为计算机专业的后继课程如数据结构、操作系统、数据库、编译原理、网络和算法设计等课程提供必要的数学基础。同时离散数学是现代数学的一个重要分支，通过该课程的学习可以提高抽象思维、严格推理以及综合归纳分析能力。,离散数学课程主要内容,一 数理逻辑 命题逻辑 谓词逻辑 二 集合论 集合代数 关系代数 三 代数系统 半群和群 环和域 四 图论,Home,目录,1.2 命题公式及其赋值,1.1 命题与联结词,第一章 命题逻辑的基本概念,1、命题及其真值,命题是命题逻辑研究的基本对象 命题是表达判断的陈述句。 命题所表达得的判断结果称为命题的真值。 当命题为真时，称命题的真值为“真”；用T或1表示“ 当命题为假时，称命题的真值为“假”。用F或0表示 判断一个句子是否是一个命题主要考虑两条： 必须是陈述句 客观上要存在唯一真值,1.1 命题与联结词,深圳市是广东省省会。 x大于y。 外星人曾来过地球。 今天是星期二。 请不要吸烟！ 这朵花真美丽啊！ 我在说假话。,例 判断下列句子是否为命题。,是，假命题 是，真命题 不是，无确定的真值 是，真值客观存在 是，真值根据具体情况而定 不是，疑问句 不是，祈使句 不是，感叹句 不是，悖论,2、原子命题与复合命题,无法继续分解的简单陈述句，称为简单命题或原子命题。 由一个或几个简单命题通过联结词复合而成的命题，称为复合命题。 命题一般用大写英文字母表示。表示命题的符号叫命题标识符。 例如，用表示“是奇数”，记作 “：是奇数”。,否定联结词 合取联结词 析取联结词 条件联结词 双条件联结词,3、命题联结词,定义1 否定联结词,设为命题，复合命题非，叫的否定式，记作。 记号叫否定联结词。 为真当且仅当为假。,例 设：今天是星期一。 则：今天不是星期一。,例 ：经历风雨 则：不经历风雨,设，表示两个命题，复合命题“且”叫命题与的合取，记作。 记号叫合取联结词。 为真，当且仅当，同时为真。,定义2 合取联结词,使用合取联结词时要注意的两点：1、描述合取式的灵活性与多样性。自然语言中的“既又”、“不但而且”、“虽然但是”、“一面一面”等联结词都可以符号化为。2、分清简单命题与复合命题。,例2 将下列命题符号化。,吴颖既用功又聪明。 吴颖不仅用功而且聪明。 吴颖虽然聪明但不用功。 张辉与王丽都是三好学生。 张辉与王丽是同学。,解： p: 吴颖用功。 q: 吴颖聪明。 r: 张辉是三好学生。 s: 王丽是三好学生。 t: 张辉与王丽是同学。,则 (1)pq (2)pq (3)qp (4)rs (5)t,解题要点： 正确理解命题含义。 找出原子命题并符号化。 选择恰当的联结词。,设，为二命题，复合命题 “或”称与的析取， 记作,叫析取联结词. 为假，当且仅当，均为假。,定义3 析取联结词,自然语言中的“或”具有二义性，用它联结的命题有时具有相容性，有时具有排斥性，对应的联结词分别称为相容或和排斥或(排异或)。,解：(1) :小王是跳远冠军. :小王是百米赛跑冠军。 则原命题符号化为:。（相容或） (2) ：小王在宿舍。：小王在图书馆。 则: （）（）。（排斥或） (3) ：小王是计算机系的学生。：小王是广东人。 ：小王是湖南人。：小王是三好学生。 则: （）（）。,例3 将下列命题符号化： (1) 小王是跳远冠军或百米赛跑冠军。 (2) 小王在宿舍或在图书馆。 (3) 小王是计算机系的学生。他是广东人或湖南人，是三好学生。,设,是二命题，复合命题“若,则”称为与的条件命题，记作。其中叫前件，叫后件。 为假当且仅当为真和为假。,定义4 条件联结词,pq的逻辑关系表示q是p的必要条件。 q是p的必要条件有许多不同的叙述方式 只要p，就q ； 因为p，所以q ； p仅当q； 只有q才p ； 除非q才p ； 除非q，否则非p。,解：天下雨，：我骑车上班。 则(1) （天不下雨是骑车上班的充分条件） (2) 或 。 （如果骑车上班，一定是天不下雨。但天不下雨也可能不骑车上班）。 (3) 设：2+24。 ：太阳从西边出来。 则原命题表示为：。其真值为1,例4 将下列命题符号化： (1) 只要天不下雨，我就骑自行车上班。 (2) 只有天不下雨，我才骑自行车上班。 (3) 如果2+24，则太阳从西边出来。,设,为二命题，复合命题“当且仅当”称为与的双条件命题，记作。叫双条件联结词。 为真当且仅当,真值相同。,定义5 双条件联结词,也称等价联结词。 pq的逻辑关系为p与q互为充分必要条件。 (pq)(qp)与pq的逻辑关系完全一致。,说明,例5、将下列命题符号化，并讨论它们的真值。 是无理数当且仅当加拿大位于亚洲。 2+35的充要条件是是无理数。 当王小红心情愉快时，她就唱歌； 反之，当她唱 歌时，一定心情愉快。,解： p：是无理数，q：加拿大位于亚洲。 则 pq， 该命题的真值为0。 p：2+35， q：是无理数。 则 pq， 该命题的真值为1。 p：王小红心情愉快， q：王小红唱歌。 则 pq， 该命题的真值由具体情况而定。,4、关于基本联结词的说明,，称为一个联结词集。 由联结词集,中的一个联结词联结一个或两个原子命题组成的复合命题是最简单的复合命题，可以称它们为基本的复合命题。 基本复合命题的真值见下表：,多次使用联结词集中的联结词，可以组成更为复杂的复合命题。 求复杂复合命题的真值时，除依据上表外，还要规定联结词的优先顺序，将括号也算在内。 本书规定的联结词优先顺序为：( )， ，对于同一优先级的联结词，先出现者先运算。,例6 p：北京比天津人口多。q: 2+2=4。 r：乌鸦是白色的。 求下列复合命题的真值： (1)(pq)(pq)r (2)(qr)(pr) (3)(pr)(pr),解：p、q、r的真值分别为 1、1、0 (1) 1 (2) 1 (3) 0,我们关心的是复合命题中命题之间的真值关系，而不关心命题的内容。,说明,1.2 命题公式及其赋值,1、命题常元和命题变元,命题常元：表示了具体命题的命题符号 常用p,q,r,s,t表示命题变元。 例：p：我是一个学生则p是命题常元 命题变元：没有表示具体命题但可以表示任何命题的命题符号 也用p,q,r,表示命题变元。 p,q,r,既可以表示命题常元，也可以表示命题变元。在使用中，需要由上下文确定它们表示的是常元还是变元。,2、命题公式,定义 命题逻辑的合式公式规定为： (1)任意一个命题常元或变元是合式公式； (2)是合式公式，则（）是合式公式； (3)、是合式公式，则（）、（）， （），（）是合式公式； (4)当且仅当有限次的应用(1)、(2)、(3)生成的式子是合式公式。 合式公式亦称为命题公式，简称公式。,设A为公式，B为A中一部分，若B也是公式，则称B为A的子公式。,合式公式的例子： （(pq)(q r)） (pq)r p(qr) ( A)、(AB)等公式单独出现时，外层括号可以省去，写成A、AB等。 不是合式公式的例子 pqr (p(rq) 公式中不影响运算次序的括号可以省去， 如 (pq)(r) 可以写成 pqr。 (pq) r 可以写成 pq r 但 p(rq) 不能写成 prq,3、公式的层次,定义2: (1)若公式A是单个的命题变项，则称A为0层合式。 (2)称A是n+1(n0)层公式是指下面情况之一： (a) AB，B是n层公式； (b) ABC，其中B,C分别为i层和j层公式，且 n=max(i,j)； (c) ABC，其中B,C的层次及n同(b)； (d) ABC，其中B,C的层次及n同(b)； (e) ABC，其中B,C的层次及n同(b)。 (3)若公式A的层次为k，则称A是k层公式。 例如：(pq)r，(pq)(rs)p) 分别为3层和4层公式,4、公式的赋值或解释,给出现在公式A中的每个命题变元一个真值，但得到的一组值，称为对A的一个赋值或解释。 例：010是公式p(rq)的一个赋值， 110也是公式p(rq)的一个赋值 赋值是按命题变元的字典顺序对应给相应的值。而不是按变元在公式中出现的先后次序。 若一个赋值使A为真，则称这个赋值为A的成真赋值； 若一个赋值使A为假，则称这个赋值为A的成假赋值。,在公式(p1p2p3)(p1p2)中， 000是成真赋值； 110是成真赋值 001是成假赋值； 011是成假赋值。 在(pr)q中， 010为成真赋值， 110为成真赋值。 100是成假赋值 重要结论： 含n(n1)个命题变项的公式共有2n个不同的赋值。,赋值举例,5、真值表,将命题公式A在所有赋值下取值情况列成表，称作A的真值表。,构造真值表的具体步骤如下： (1)找出公式中所含的全体命题变项p1,p2,pn (若无下角标就按字典顺序排列)，列出2n个赋值。本书规定，赋值从000开始，然后按二进制加法依次写出各赋值，直到111为止。 (2)按从低到高的顺序写出公式的各个层次。 (3)对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。,公式A与B具有相同的或不同的真值表，是指真值表的最后一列是否相同，而不考虑构造真值表的中间过程。,说明,例1、求命题公式(p(qr)的真值表。 解：公式的真值表为：,例2、求下列公式的真值表，并求成真赋值和成假赋值。 (1)(pq)r (2)(pp)(qq) (3)(pq)qr,6、公式的类型,定义3、设A为任一命题公式 (1)若A在它的各种赋值下取值均为真,则称A是重言式或永真式。 (2)若A在它的各种赋值下取值均为假,则称A是矛盾式或永假式。 (3)若A至少有一个成真赋值,则称A是可满足式。,真值表可用来判断公式的类型。公式分类如下：,例3、 下列各公式均含两个命题变项p与q，它们中哪些具有相同的真值表? (1) pq (4) (pq)(qp) (2) pq (5) qp (3) (pq),设公式A,B中共含有命题变项p1,p2,pn，而A或B不全含有这些命题变项，比如A中不含pi,pi+1,pn ,称这些命题变项为A的哑元，A的取值与哑元的变化无关，因而在讨论A与B是否有相等的真值表时，将A,B都看成p1,p2,pn的命题公式。,7、哑元,命题与真值（或真假值）。 简单命题与复合命题。 联结词：，。 命题公式（简称公式）。 命题公式的层次和公式的赋值。 真值表。 公式的类型：重言式（永真式），矛盾式（永假式），可满足式。 本章典型习题： 求命题符号化；复合命题的真值与命题公式的赋值；判断公式的类型。,8、小结,例4、将下列命题符号化。,(1)我和他既是