第1章---数理逻辑-new.ppt

离散数学 第一章 数理逻辑 离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。 在萨维尔村，理发师挂出一块招牌：“我只给村里所有那些不给自己理发的人理发。”有人问他：“你给不给自己理发？”理发师顿时无言以对。 这是一个矛盾推理：如果理发师不给自己理发，他就属于招牌上的那一类人。有言在先，他应该给自己理发。 反之，如果这个理发师给他自己理发，根据招牌所言，他只给村中不给自己理发的人理发，他不能给自己理发。 因此，无论这个理发师怎么回答，都不能排除内在的矛盾。这个悖论是罗素在一九○二年提出来的，所以又叫“罗素悖论”。 1.2 重 言 式 定理 1.2 - 1 设A和A*是对偶式。P 1, P2,…, Pn是出现于A和A *中的所有命题变元, 于是 1.3 范 式 我们把“5”“张明”“北京” “7” “3” “2”叫做个体, 代表个体的变元叫个体变元。刻画个体的性质或几个个体间关系的模式叫谓词。 “是质数” “生于” “ := :×…”都是谓词。谓词一般用大写字母P, Q, R, …表示, 个体用小写字母a, b, c, …等表示。 单独的个体和谓词不能构成命题, 故不能将它们分开以表示命题。设F表示“是质数”, 则“x是质数”表示为F(x); G表示“生于”, 则“x生于y”表示为G(x, y); H表示“…= …×…”, 则“x=yz”表示为H(x, y, z)。 F(x) , G(x, y) , H(x, y, z) 等叫谓词命名式, 简称谓词。 一个个体变元的谓词叫一元谓词, 两个个体变元的谓词叫二元谓词, 一般地, n个个体变元的谓词叫n元谓词, 记为P(x1, x2, …, x n)。 一般谓词用设定的字母表示, 常用的谓词则用特定的符号表示。 例如: x＜y, 可写成＜(x, y)或L(x, y)(L表示小于) x=yz, 可写成=(x, y, z)(要事先说明) 但最常用的仍写成x＜y, x=yz, 称为谓词的中缀记法。不管怎样记法, 变元的次序是重要的, 例如＜(x, y)与＜(y, x)不一样。 一个字母代表一特定谓词, 例如F代表“是质数”, 则称此字母为谓词常元。若字母代表任意谓词, 则称此字母为谓词变元。 我们通常不加区分, 但一般从上下文可看出它的含义。 谓词命名式中个体变元的取值范围叫做论述域或个体域。容易看出, 空集不能作为论述域, 所以, 以后谈到论述域都至少有一个个体。例 1(a)的论述域是正整数, (c)的论述域是实数, (b)中x的变域是人类, y的变域是地名集, 所以论述域分别是人类和地名集。 谓词命名式中, 若谓词是常元, 个体变元代以论述域中的某一个体, 就成为一个命题。例如F(5)是真, F(4)是假, G(张明, 北京)是真(假定张明生于北京), 所以谓词命名式是一个命题函数。 设x+y=z表示为P(x, y, z), 若取定x为 3, 即P(3, y, z), 可改记为P′(y, z) 成为二元谓词, 再取定y为 4, 即P′(4, z), 可改记为P″(z), 成为一元谓词, 再取定z为 5, 即P″(5), 可改记为P’’’而成为命题。 可见命题是 0 元谓词, 所以谓词是命题概念的扩充, 命题是谓词的一种特殊情况。 1.6.2 量词 1. 全称量词  x读做“对一切x” , “对任一x”或“对每一x”, 这里是全称量词, x标记所作用的个体变元。 xP(x)表示“对一切x, P(x)是真”  x P(x)表示“对一切x, P(x)是真”  xP(x)表示“并非对一切x, P(x)是真”  x P(x)表示“并非对一切x,  P(x)是真” 2. 存在量词 