第一章命题逻辑的基本概念概要

《第一章命题逻辑的基本概念概要》由会员分享，可在线阅读，更多相关《第一章命题逻辑的基本概念概要（60页珍藏版）》请在金锄头文库上搜索。

1、离散数学,计算机1501-04 赵曦,教材,离散数学 屈婉玲、耿素云、张立昂， 高等教育出版社， 2015年3月第二版,2,学科地位,3,计算机相关专业，需具备的专业能力： 计算思维能力； 算法设计与分析能力； 程序设计与实现能力； 计算机系统的认知、分析、开发和应用能力，简称系统能力。,4,图1 自动计算、形式化与“计算思维”的关系,5,图2 “计算思维”梯度训练系统,离散数学是现代数学的一个重要分支，是构筑于数学和计算机学科之间的桥梁，是计算机科学的理论基础。 作为核心基础课程，该课程在计算机及相关专业课程体系中扮演着重要的角色，是构筑于数学和计算机学科之间的桥梁，。 它以研究离散量的结构

2、及相互关系为主要目标，充分描述了计算机科学离散性的特点。,6,与后续课程的关系,数理逻辑在人工智能、程序理论和数据库理论等的研究中有重要的应用。 集合论、图论为数据结构和算法分析奠定了数学基础，也为许多问题从算法角度如何加以解决提供了继续抽象和描述的一些重要方法。 代数结构代数结构中的代数方法被广泛应用，如可计算性与计算复杂性、形式语言与自动机、密码学、网络与通信理论、程序理论和形式语义学等计算机分支学科。,7,第一部分 数理逻辑,用数学方法研究推理的一门科学。,要想把这种推理规则应用到各个学科领域中去，就必须使用一种概括性较强，并且又是独立于任何特定的论证或者所涉及的学科的语言。 这种语言是

3、一种符号化的形式语言，它没有二义性。 第一至五章将介绍这套符号化形式体系的制定，以及它在数理逻辑中的应用。,数理逻辑的发展,在17世纪，曾经设想创造一种“通用的科学语言”，能够像数学一样利用公式对推理过程进行计算，但没有实现。是数理逻辑的先驱。,1847年，逻辑的数学分析，建立了“布尔代数”，并创造了一套符号系统，初步奠定了数理逻辑的基础。,10,1879年，概念语言，建立第一个比较严格的逻辑演算系统。,数学原理，当时数理逻辑的成果总结，使得数理逻辑形成了专门的学科。,11,1930年以前，数理逻辑的发展主要是针对纯数学的。从20世纪40年代起，自动化和计算技术的发展要求建立包含数百个甚至数千

4、个继电器的复杂系统，人们难以进行分析和综合。 于是，当时多个国家几乎同时出现了关于继电器接点线路结构的符号方法及数理逻辑的命题演算在其中的应用。 1943年，数理逻辑又应用于所有开关线路的理论中。以后，又在计算机科学和控制论方面获得应用，成为基础理论之一。,12,数理逻辑在计算机科学技术中的应用,数理逻辑是计算理论的基础，而计算理论又是计算机科学的核心基础，在编译原理、复杂性分析中有广泛的应用； 另外，数理逻辑也是形式语言、程序设计方法、机器证明、人工智能等学科的基础。 下面将介绍一些数理逻辑的典型应用，供参考。,13,14,命题逻辑的知识在日常生活和工程技术中都有着广泛的应用。电子计算机是数

5、理逻辑和电子学相结合的产物。实际上，无论是作为计算机雏形的图灵机，还是作为程序设计的语言等，无不涉及它的知识和理论。,命题逻辑的知识逻辑结构,15,1.1,1.2,2.2,2.1,3.1,3.2,16,17,返回,一、命题与真值,18,判断结果惟一的陈述句。,判断的结果。,真值为真的命题。,真值为假的命题。,命题的注意事项,非假即真的陈述句。 一切没有判断内容，不分真假的句子，都不是命题。 陈述句能否分辨真假，和是否知道它的真假，是两回事。 命题不能是疑问句或是祈使句等其他类型的句子。 一个命题的真值只能是真或是假，不能兼而有之。,例 判断下列句子是否为命题：,（7）这种由真能推出假、又由假能

6、推出真，从而既不能为真、也不能为假的陈述句称为悖论。悖论不是命题。,21,（8）、（9）的真值虽然现在还不知道，但它的真值是唯一的，因而是命题。 （10）在二进制中为真，在十进制中为假，需根据上下文才能确定其真值，因而不是命题。,返回,22,返回,不能被分解成更简单命题。 简单命题是最小的基本单位。,由简单命题通过联接词联接而成。,二、命题的分类,23,用p、q、r等表示命题。,用数字1代表真，0代表假。,返回,例如，令 p： 是有理数，则 p 的真值为 0。 q：2 + 5 = 7，则 q 的真值为 1。 注意：书P4 例1.2,三、命题与真值的符号化,24,规定 pq为真当且仅当p与q同时

7、为真.,规定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同时为真。,合取的注意事项,描述合取式的灵活性与多样性。 自然语言中的“既，又”

8、，“不但，而且”，“虽然，但是”，“一面，一面”等都表示两件事情同时成立，因而都可以符号化为。 分清简单命题与复合命题 不要见到“与”、“和”就使用联结词。,例1.3 将下列命题符号化：,解：令 p：吴颖用功. q：吴颖聪明. r : 张辉是三好学生. s :王丽是三好学生. t : 张辉与王丽是同学.,3. 析取式与析取联结词“”,29,设p，q为两个命题，复合命题“p或q”称作p与q的析取式，记作pq，称作析取联结词。 规定pq为假当且仅当p与q同时为假。,“或”的含义,30,例1.4 将下列命题符号化：,相容或pq与排斥或(pq) (pq)的区别在于，当p与q同为真时，pq为真，(pq)

9、 (pq) 为假。因而，当命题p与q不能同为真时，两者相同。 .,4. 蕴涵式与蕴涵联结词“”,32,设p，q为两个命题，复合命题“如果p，则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件。 称作蕴涵联结词。 规定pq为假当且仅当 p 为真 q 为假。,pq 的逻辑关系,33,p为 q 的充分条件，q 为 p 的必要条件。 常出现的错误：不分充分与必要条件。,“如果 p，则 q ” 的不同表述法： 若 p，就 q 只要 p，就 q 因为 p，所以 q p 仅当 q 只有 q 才 p 除非 q 才 p 或 除非 q, 否则非 p,以上各种叙述方法表面看有所不同，但都表示

10、q是p的必要条件，因而都应符合化为pq。,例：设 p:天冷，q:小王穿羽绒服， 将下列命题符号化：,pq,pq,pq,qp,qp,pq,qp,qp,35,注意： 1.在自然语言中，前提是假的，不论结论真假，整个语句的意义无法判断。在逻辑中，当前件p为假时， pq为真，称为善意推定。 2. p与q不一定有内在联系。,5. 等价式与等价联结词”,36,设p，q为两个命题，复合命题 “p当且仅当q”称作p与q的等价式，记作pq，称作等价联结词。 规定pq为真当且仅当p与q同时为真或同时为假。,等价的注意事项,pq 的逻辑关系：p与q互为充分必要条件。 pq为真 当且仅当 p与q同真或同假。 p q与

11、(p q)(q p)等值。 p与q不一定有内在联系。,联结词的总结,38,返回,39,p为真当且仅当p为假。,pq为真当且仅当p与q同时为真。,返回,pq为假当且仅当p与q同时为假。,为真当且仅当p与q的真值相异。,pq为假当且仅当p为真，q为假。,pq为真当且仅当p与q的真值相同。,五、基本复合命题,40,返回,基本复合命题以及多次使用常用联结词集S中的联结词复合而成的命题。,联结词的优先顺序为：, , , , ; 如果出现的联结词同级，又无括号时，则按从左到右的顺序运算； 若遇有括号时，应该先进行括号中的运算。,六、复合命题,41,返回,一、命题常项与命题变项,42,简单命题，其真值是确定

12、的，称为命题常项。取值1或0的变量p，q，r。,真值不确定（取值1或0）的陈述句。用p，q，r表示。,43,注意： 1. 命题变项不是命题。 2. 命题变项与命题常项的关系如同数学 中变量与常量的关系。 3. p，q，r既可以表示命题常项，也 可以表示命题变项。通常可以由上下 文确定。,返回,二、合式公式及其层次,44,将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串称为合式公式。,对合式公式进行分层，可准确地求出公式的真值。,1. 合式公式,45,递归定义如下： (1) 单个命题常项或变项是合式公式； (2) 若A是合式公式，则 (A)是合式公式； (3) 若A, B是合式公式，则

13、(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的

14、层次及n同(b)。 (3) 若公式A的层次为k，则称A是k层公式。,47,48,公式的层次 举例,返回,三、命题的赋值与真值表,49,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,

15、r, ， A赋值123是指p=1，q=2 , r=3 ,注意：含n （n1）个命题变项的公式有2n个 赋值。,例：求下列公式的成真赋值和成假赋值。,52,1. ( p q r ) 2. ( p q)(p r),2. 真值表,将命题公式A在所有赋值下取值情况列成表，称作A的真值表。 构造真值表的步骤如下： (1) 列出所有命题变项，列出所有可能赋值； (2) 按从低到高的顺序写出各层次； (3) 对应每个赋值，计算命题公式各层次的 真值，直到计算出命题公式的真值。,53,54,例：给出公式的真值表,A= (qp) qp,B = (pq) q,55,C= (pq) r,返回,四、公式的类型,56,

16、根据公式在各种赋值下的取值情况，可将公式进行分类。设A为任一命题公式：,A在它的各种赋值下取值均为真。,A在它的各种赋值下取值均为假。,若A不是矛盾式，则称A为可满足式。,57,注意： 若公式A是可满足式，则A至少存在一 个成真赋值。 重言式一定是可满足式，但反之不真。 若公式A是可满足式，且它至少存在 一个成假赋值，则称A为非重言式的 可满足式。,判断公式类型的方法,1. 观察法 2. 真值表法,58,若真值表的最后一列全为1，则公式为永真式。 若真值表的最后一列全为0，则公式为永假式。 若真值表的最后一列至少有一个1，则公式为可满足式。,例：分别用观察法和真值表发判断下面公式的类型。 1. p r (q