第一章-命题逻辑的基本概念资料课件

离散数学离散数学计算机计算机1501-04赵曦赵曦教材离散数学屈婉玲、耿素云、张立昂，高等教育出版社，2015年3月第二版2学科地位3计算机相关专业，需具备的专业能力：计算思维能力；算法设计与分析能力；程序设计与实现能力；计算机系统的认知、分析、开发和应用能力，简称系统能力。4被有效地自动计算形式化“计算思维”图1自动计算、形式化与“计算思维”的关系5中学数学数学分析离散数学形式语言与自动机理论具体、静止变量、运动离散、抽象（基本运算系统）形式、模型（计算系统）实数抽象集合孤立、单一的计算（实例计算）一般、形式化的计算（类计算、模型计算）运算范围特征图2“计算思维”梯度训练系统离散数学是现代数学的一个重要分支，是构筑于数学和计算机学科之间的桥梁，是计算机科学的理论基础。作为核心基础课程，该课程在计算机及相关专业课程体系中扮演着重要的角色，是构筑于数学和计算机学科之间的桥梁，。它以研究离散量的结构及相互关系为主要目标，充分描述了计算机科学离散性的特点。6与后续课程的关系数理逻辑在人工智能、程序理论和数据库理论等的研究中有重要的应用。集合论、图论为数据结构和算法分析奠定了数学基础，也为许多问题从算法角度如何加以解决提供了继续抽象和描述的一些重要方法。代数结构代数结构中的代数方法被广泛应用，如可计算性与计算复杂性、形式语言与自动机、密码学、网络与通信理论、程序理论和形式语义学等计算机分支学科。7第一部分数理逻辑数理逻辑命题逻辑一阶逻辑用数学方法研究推理的一门科学。要想把这种推理规则应用到各个学科领域中去，就必须使用一种概括性较强，并且又是独立于任何特定的论证或者所涉及的学科的语言。这种语言是一种符号化的形式语言，它没有二义性。第一至五章将介绍这套符号化形式体系的制定，以及它在数理逻辑中的应用。数理逻辑的发展数理逻辑的发展在17世纪，曾经设想创造一种“通用的科学语言”，能够像数学一样利用公式对推理过程进行计算，但没有实现。是数理逻辑的先驱。1847年，逻辑的数学分析，建立了“布尔代数”，并创造了一套符号系统，初步奠定了数理逻辑的基础。101879年，概念语言，建立第一个比较严格的逻辑演算系统。数学原理，当时数理逻辑的成果总结，使得数理逻辑形成了专门的学科。111930年以前，数理逻辑的发展主要是针对纯数学的。从20世纪40年代起，自动化和计算技术的发展要求建立包含数百个甚至数千个继电器的复杂系统，人们难以进行分析和综合。于是，当时多个国家几乎同时出现了关于继电器接点线路结构的符号方法及数理逻辑的命题演算在其中的应用。1943年，数理逻辑又应用于所有开关线路的理论中。以后，又在计算机科学和控制论方面获得应用，成为基础理论之一。12数理逻辑在计算机科学技术中的应用数理逻辑在计算机科学技术中的应用数理逻辑是计算理论的基础，而计算理论又是计算机科学的核心基础，在编译原理、复杂性分析中有广泛的应用；另外，数理逻辑也是形式语言、程序设计方法、机器证明、人工智能等学科的基础。下面将介绍一些数理逻辑的典型应用，供参考。1314命题逻辑的知识在日常生活和工程技术中都有着广泛的应用。电子计算机是数理逻辑和电子学相结合的产物。实际上，无论是作为计算机雏形的图灵机，还是作为程序设计的语言等，无不涉及它的知识和理论。命题逻辑的知识逻辑结构命题逻辑的知识逻辑结构151.11.22.22.13.13.216第一章命题逻辑的基本概念1.1命题与联结词1.2命题公式及其赋值171.1命题与联结词一、命题与真值二、命题的分类三、命题与真值的符号化四、常用联结词及其符号五、基本复合命题六、复合命题返回一、命题与真值181.命题2.命题的真值3.真命题4.假命题判断结果惟一的陈述句。判断结果惟一的陈述句。判断的结果。判断的结果。真值为真的命题。真值为真的命题。真值为假的命题。真值为假的命题。命题的注意事项非假即真的陈述句。一切没有判断内容，不分真假的句子，都不是命题。陈述句能否分辨真假，和是否知道它的真假，是两回事。命题不能是疑问句或是祈使句等其他类型的句子。一个命题的真值只能是真或是假，不能兼而有之。例判断下列句子是否为命题：序号序号句子句子是否为命题是否为命题原因原因(1)是无理数.真命题(2)2+5 8.假命题(3)x+5 3.真值不确定(4)你有铅笔吗？疑问句(5)这只兔子跑得真快呀！感叹句(6)请不要讲话！祈使句(7)我正在说谎话.悖论（7）这种由真能推出假、又由假能推出真，从而既不能为真、也不能为假的陈述句称为悖论。悖论不是命题。21（8）、（9）的真值虽然现在还不知道，但它的真值是唯一的，因而是命题。（10）在二进制中为真，在十进制中为假，需根据上下文才能确定其真值，因而不是命题。序号序号句子句子是否为命题是否为命题原因原因(8)明年10月1日是晴天.真值唯一(9)地球外的星球上有人.真值唯一(10)111100.真值不确定返回221.简单命题（原子命题）2.复合命题返回不能被分解成更简单命题。不能被分解成更简单命题。简单命题是最小的基本单位。简单命题是最小的基本单位。由简单命题通过联接词联接而成。由简单命题通过联接词联接而成。二、命题的分类231.命题的符号化2.真值的符号化用用p、q、r等表示命题。等表示命题。用数字用数字1代表真，代表真，0代表假。代表假。返回例如，令例如，令 p：是有理数，则是有理数，则 p 的真值为的真值为 0。q：2+5=7，则，则 q 的真值为的真值为 1。注意：书注意：书P4 例例1.2三、命题与真值的符号化241.否定（定义1.1）2.合取（定义1.2）3.析取（定义1.3）4.蕴涵（定义1.4）5.等价（定义1.5）规定规定 pq为真当且仅当为真当且仅当p与与q同时为真同时为真.规规定定pq为为假假当当且且仅仅当当p与与q同同时时为假为假.规定规定pq为假当且仅当为假当且仅当 p 为真为真 q 为假为假.规规定定pq为为真真当当且且仅仅当当p与与q同同时时为真或同时为假为真或同时为假.四、常用联结词及其符号规定规定 p为真当且仅当为真当且仅当p为假为假.25 设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作p。符号称作否定联结词。规定p 为真当且仅当p为假。1.否定式与否定联结词“”2.合取式与合取联结词“”26 设p，q为两个命题，复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作pq，称作合取联结词。规定 pq为真当且仅当p与q同时为真。合取的注意事项描述合取式的灵活性与多样性。自然语言中的“既，又”，“不但，而且”，“虽然，但是”，“一面，一面”等都表示两件事情同时成立，因而都可以符号化为。分清简单命题与复合命题不要见到“与”、“和”就使用联结词。例1.3将下列命题符号化：序号序号命题命题符号化符号化命题种类命题种类(1)吴颖既用功又聪明.pq复合命题(2)吴颖不仅用功而且聪明.pq复合命题(3)吴颖虽然聪明，但不用功.q p复合命题(4)张辉与王丽都是三好生.rs复合命题(5)张辉与王丽是同学.t简单命题解：令 p：吴颖用功.q：吴颖聪明.r:张辉是三好学生.s:王丽是三好学生.t:张辉与王丽是同学.3.析取式与析取联结词“”29 设p，q为两个命题，复合命题“p或q”称作p与q的析取式，记作pq，称作析取联结词。规定pq为假当且仅当p与q同时为假。“或”的含义30或的含义例表达的意思联结词排斥或人固有一死，或重于泰山或轻于鸿毛。非此即彼，不可兼得。相容或ab=0即a=0或b=0或a=b=0二者至少有一个发生，不排除二者都发生的情况。非联结词表示近似数或 去书店需走8分钟或10分钟。近似数“8至10分钟”例1.4将下列命题符号化：序号序号命题命题符号化符号化命题种类命题种类(1)张晓静爱唱歌或爱听音乐.pq相容或(2)张晓静只能挑选202或203房间.(rs)(rs)排斥或(3)张晓静是江西人或安徽人.(tu)(tu)或tu排斥或 相容或pq与排斥或(pq)(pq)的区别在于，当p与q同为真时，pq为真，(pq)(pq)为假。因而，当命题p与q不能同为真时，两者相同。.4.蕴涵式与蕴涵联结词“”32 设p，q为两个命题，复合命题“如果p，则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件。称作蕴涵联结词。规定pq为假当且仅当 p 为真 q 为假。pq 的逻辑关系33p为 q 的充分条件，q 为 p 的必要条件。常出现的错误：不分充分与必要条件。“如果 p，则 q”的不同表述法：若 p，就 q 只要 p，就 q 因为 p，所以 q p 仅当 q 只有 q 才 p 除非 q 才 p 或 除非 q,否则非 p 以上各种叙述方法表面看有所不同，但都表示q是p的必要条件，因而都应符合化为pq。例：设 p:天冷，q:小王穿羽绒服，将下列命题符号化：序号序号句子句子符号化符号化(1)只要天冷，小王就穿羽绒服.(2)因为天冷，所以小王穿羽绒服.(3)若小王不穿羽绒服，则天不冷.(4)只有天冷，小王才穿羽绒服.(5)除非天冷，小王才穿羽绒服.(6)除非小王穿羽绒服，否则天不冷.(7)如果天不冷，则小王不穿羽绒服.(8)小王穿羽绒服仅当天冷的时候.pqpqpqqp qp pqqp qp 35注意：1.在自然语言中，前提是假的，不论结论真假，整个语句的意义无法判断。在逻辑中，当前件p为假时，pq为真，称为善意推定。2.p与q不一定有内在联系。P QP QF F TF T TT F FT T T5.等价式与等价联结词”36 设p，q为两个命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq，称作等价联结词。规定pq为真当且仅当p与q同时为真或同时为假。等价的注意事项 pq 的逻辑关系：p与q互为充分必要条件。pq为真 当且仅当 p与q同真或同假。p q与(p q)(q p)等值。p与q不一定有内在联系。联结词的总结38 p q p p qp qp q p q 0 010011 0 110110 1 000100 1 101111返回391.否定式p2.合取式pq3.析取式pq4.析取式(p q)(pq)5.蕴涵式pq6.等价式pq p为真当且仅当为真当且仅当p为假。为假。pq为真当且仅当为真当且仅当p与与q同时为真。同时为真。返回pq为假当且仅当为假当且仅当p与与q同时为假。同时为假。为真当且仅当为真当且仅当p与与q的真值相异。的真值相异。pq为假当且仅当为假当且仅当p为真，为真，q为假。为假。pq为真当且仅当为真当且仅当p与与q的真值相同。的真值相同。五、基本复合命题401.复合命题2.联结词的优先顺序返回 基本复合命题以及多次使用常用联结词基本复合命题以及多次使用常用联结词集集S中的联结词复合而成的命题。中的联结词复合而成的命题。联结词的优先顺序为：联结词的优先顺序为：,;如果出现的联结词同级，又无括号时，如果出现的联结词同级，又无括号时，则按从左到右的顺序运算；则按从左到右的顺序运算；若遇有括号时，应该先进行括号中的运若遇有括号时，应该先进行括号中的运算。算。六、复合命题411.2命题公式及其赋值一、命题常项与命题变项二、合式公式及其层次三、公式的赋值与真值表四、公式的类型返回一、命题常项与命题变项421.命题常项2.命题变项 简单命题，其真值是确定的，称为命题简单命题，其真值是确定的，称为命题常项。取值常项。取值1或或0的变量的变量p，q，r。真值不确定（取值真值不确定（取值1或或0）的陈述句。用）的陈述句。用p，q，r表示。表示。43注意：注意：1.命题变项不是命题。命题变项不是命题。2.命题变项与命题常项的关系如同数学命题变项与命题常项的关系如同数学 中变量与常量的关系。中变量与常量的关系。3.p，q，r既可以表示命题常项，也既可以表示命题常项，也 可以表示命题变项。通常可以由上下可以表示命题变项。通常可以由上下 文确定。文确定。返回二、合式公式及其层次441.合式公式（定义1.6）2.公式的层次（定义1.7）将命题变项用联结词和圆括号按一将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串称为合式公定的逻辑关系联结起来的符号串称为合式公式。式。对合式公式进行分层，可准确地求对合式公式进行分层，可准确地求出公式的真值。出公式的真值。1.合式公式45递归定义如下：(1)单个命题常项或变项是合式公式；(2)若A是合式公式，则(A)是合式公式；(3)若A,B是合式公式，则(AB),(AB),(AB),(AB)是合式公式；(4)有限次地应用(1)(3)形成的符号串是合式 公式。46注意：注意：设设A合式公式，合式公式，B为为A的一部分，若的一部分，若 B也是合式公式，则称也是合式公式，则称B为为A的子公的子公 式。式。不影响运算次序的括号可以省去。不影响运算次序的括号可以省去。2.公式的层次(1)若公式A是单个的命题变项，称A为0层公式。(2)称A是n+1(n0)层公式是指下面情况之一：(a)A=B，B是n层公式；(b)A=BC，其中B，C分别为i层和j层公式，且n=max(i,j)；(c)A=BC，其中B，C的层次及n同(b)；(d)A=BC，其中B，C的层次及n同(b)；(e)A=BC，其中B，C的层次及n同(b)。(3)若公式A的层次为k，则称A是k层公式。4748公式的层次举例序号序号合式公式合式公式层次层次(1)p0(2)p1(3)pq 2(4)(pq)r 3(5)(p q)r)(r s)4返回三、命题的赋值与真值表491.公式的赋值（定义1.8）成真赋值（定义1.8）成假赋值（定义1.8）2.真值表（定义1.9）1.公式的赋值 设p1,p2,pn是出现在公式A中的全部命题变项，给p1,p2,pn各指定一个真值（0或1），称为对A的一个赋值或解释。50成真赋值:使公式A为真的赋值。成假赋值:使公式A为假的赋值。本书对公式赋值的记法51 赋值=12n之间不加标点符号，i=0或1。1.若A中出现的命题变项为p1,p2,pn，A赋值12n是指 p1=1,p2=2,pn=n 2.若A中出现的命题变项(按字母顺序)为 p,q,r,，A赋值123是指p=1，q=2,r=3 注意：含注意：含n（n1）个命题变项的公式有个命题变项的公式有2n个个 赋值。赋值。例：求下列公式的成真赋值和成假赋值。521.(p q r)2.(p q)(p r)2.真值表 将命题公式A在所有赋值下取值情况列成表，称作A的真值表。构造真值表的步骤如下：(1)列出所有命题变项，列出所有可能赋值；(2)按从低到高的顺序写出各层次；(3)对应每个赋值，计算命题公式各层次的 真值，直到计算出命题公式的真值。5354例：给出公式的真值表A=(qp)qp p q qp (qp)q (qp)qp 0 00 11 01 1 1011 0001 1111B=(pq)q p q ppq(pq)(pq)q0 00 11 01 1 110011010010000055C=(pq)r p q r pq r (pq)r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 0011111 1 1010101 0 11101010返回四、公式的类型561.重言式（永真式）（定义1.10）2.矛盾式（永假式）（定义1.10）3.可满足式（定义1.10）根据公式在各种赋值下的取值情况，可将公式进行分类。设A为任一命题公式：A在它的各种赋值下取值均为真。在它的各种赋值下取值均为真。A在它的各种赋值下取值均为假。在它的各种赋值下取值均为假。若若A不是矛盾式，则称不是矛盾式，则称A为可满足式。为可满足式。57注意：注意：若公式若公式A是可满足式，则是可满足式，则A至少存在一至少存在一 个成真赋值。个成真赋值。重言式一定是可满足式，但反之不真。重言式一定是可满足式，但反之不真。若公式若公式A是可满足式，且它至少存在是可满足式，且它至少存在 一个成假赋值，则称一个成假赋值，则称A为非重言式的为非重言式的 可满足式。可满足式。判断公式类型的方法1.观察法2.真值表法58l若真值表的最后一列全为1，则公式为永真式。l若真值表的最后一列全为0，则公式为永假式。l若真值表的最后一列至少有一个1，则公式为可满足式。例：分别用观察法和真值表发判断下面公式的类型。1.p r (q p)2.(p q)(q p)r 3.(p q)(p r)返回60命题公式的记忆图