离散数学左孝凌等 上海科学技术文献出版社

3-9集合的划分和覆盖 3-10等价关系与等价类 ………131 3-江L相容关系………………………………………………1B 3-12序关系…………… +!+■h■++4· r+39 第四章函数 147 41函数的概念… t147 4-2逆函数和复合函数 …………151 4-3特征函数与模糊子集 166 44基数的概念 ……16王 45可数集与不可数集 ■bl 164 46基数的比较…………………………………………170 第三篇代数系统………………………………175 第五章代数结构 1代数系统的引入…… ↓↓b卩司司■d↓司 76 鬼运算及其性质 了8 53半群 -B5 54群与子群…… ……"………190 5-6阿贸尔群和循坏群……………………………197 5-6置换群与伯恩赛德定理…………………20 5-?陪集与拉格朗日定理…, ……-208 5-8同态与同构 ………212 5-9环与域 ……*…………222 第六章格与冇尔代数 231 6-1格的概念 h山■山■■■■■■■■■■p画 62分配格 --243 6-3有补格 ■P中■甲自平P音甲自■自■p口 249 6-4布尔代数 252 6-5布尔表达式 261 第四篇图论 ■↓昏晕甲◆昏■“■鼻斷甲■咖 ………………271 第七章图论 ………272 7图的基木概念 272 7-公路与回路… …………280 i 7-3图的矩阵表示 -2g7 r-4欧拉图与汉尔顿图 7平面图 312 7-6对褐图与着色… 317 7-7树与生成树 322 7-8根树及其应用 328 第五篇计算机科学中的应用 日·日日日日日a·日日aaq· 9 第八章形式语诉与宫动机 ■忌■■■■毛■■歌自·■ 340 81串和语言 340 8-2形式文法 甲■血鲁山■"■■■日■q■■■■甲 349 8-3有限状态自动机 59 84两类自动机的转换 暑■P↓↓■q『■「·■↓b吾平h■■+十1■■日m号晶hd■■ 71 8-5有限状态机的简化 378 86有限状态机与则语亡 B86 第九章纠错码初步 旱由早中中■中甲d早 ……396 9-1通讯模型和纠错的基本概念 396 9-2线性分组码的纠错能力 生王 9-8海明码 406 9圣查表译码法 ±15 符号表 …………………19 参考文献∵ ………425 11 第一篇数理逻辑 逻辑学是一门研究思维形式及思维规律的科学。逻辑规律就 是客观事物在人的主观意识中的反映。 逻輯学分为辩证逻辑与形式逻辑两种,前者是以辩证法认识 论的些界观为基础的逻辑学,而后者主要是对思维的形式结构和 规律进行研究的类似于语法的一门工具性学科。思维的形式结构 包括了概☆,判断和推理之间的结构和联系其中概念是思维的基 本单位,通过概念对事物是否具有某种属性进行肯定或否定的回 答,这就是判断;由一个或几个判断推出另一判断的恩维形式,就 是推理。研究推理有很多方法,用数学方法来研究推理的规律称 为数理逻辑。这里所指的数学方法,就是引进一套苻号体系的方 法,所以数理逻辑又称作符号逻辑,它是从景的侧面来研究恩维规 律的。 现代数理逻辑可分为证明论、模型论、递归函数论、公理化集 合论等,这里介绍的是数理逻辑最基本的内容:命题逻辑和谓词逻 辑 第一章命题逻辑 11命题及其表示法 在数理逻辑中,为了表达概念陈述理论和规则,常常需要应 用语言进行描述,但是日常使用的自然语言,往往叙述时不够确 切,也易产生二义性,因此就需要引入一种目标语言这种目标语 言和一些公式符号,就形成了数逻辑的形式符号体系。历谓目 标语言就是表达判断的一些语言的汇集,而判断就是对事物有肯 定或香定的一种思绝形式,因此能表达判断的语言是陈述句,它称 作命题。一个命题总是具有一个值,称为真值。真值只有真 和“假两种,记作Tu(真)和ase(假),分别号和表 示。只有具有确定真值的陈述句才是命题,一切没有判断内容的 句子,无所谓是非的句子如感叹句,疑冋,祈使句等都不館作为 命题。命题有两种类型:第一种类型是不能分解为更简单的陈述 句,称作原子命题:第二种类型是由联结词,标符号和原子命 题复合构成的命题,称作复合命题。所有这些命题都应具有确定 的真值。下面给出实例,说明命题的概念。 (1)中国人民是伟大的 (2)雪是黑的。 (3)1+101=110 (4)别的屋球上有生物。 (5)全体立正! (6)明天是否开大会? (7)天气多好啊! (8)我正在说谎。 (9)我学英语或者我学语。 10)郊果天气好,那么我去嵌步。 在上面这些例子中,(1)、四2)、(4)、(9)、(10是命题。其中 (9)、(10是复合命题,(4)在目前可能无法决定真值,但从事物的 本质而论,它本身是有真假可音的,所以我们承认这也是一个命 题。(5)、(6)、()都不是命题。(68)是悖论。(3)在二进制中为真 在十进制中为假,枚需根据上下文才能确定真值。 在数理逻辑中,我们将使用大写字母A,B,…,P,Q,…或 用带下标的大写字母或用数字,如A4[2】等表示命题,例 P:今天下丽。 P可表示今天下雨这个命题的名。亦可用数字表示命趣,例如 2}:今天下雨。 表示命题的符号称为命题标识符,P和[2]就是标识符 个命题标识符郊表示确定的命题就称为命题常量如果命 题标识符只表示任意命趣的位置标志,就称为命题变元。因为命 题变元可以表示任意命题,所以它不能确定真值故命题变元不是 命题。当命趣变元P用一个特定命题取代时,P才能确定真值 这时也称对P进行指派。当命题变元表示原子命题时。该变元称 为原子变元。 12联结词 在自然语言中,常常使用或”,“与”“但是等一些联结词,对 于这种联结词的使用,一般没有很严格的定义,因此有时显得不很 确切。在数理逻辑中,复合命题是由原子命题与逻辑联结词组合 面成,联结词是复合命题中的重要组成部分,为了便于书写和进行 推演,必须对联结词作出明确规定并符号化。下面介绍各个联结 词 (1)否定 定义121设P为一命题,P的否定是一个新的命题,记 作P。若P为们P为酌若P为矿为T联结词 11234 表示命题的否定。否定联结词有时亦可记作 命题P与其否定P的关系如表1-2.1所示。 装2.1 P E F 例 P:上溽是一个大城市。 刁P:上海并不是一个大城市 或 7P:上海是一个不大的城市。 这两个命题用同一符号P表示,因为在汉语中这两个命题 具有相阿的意义。 “否定的意义仅是修改了命趣的内容,我们仍把它看作为联 结词,它是一个一元运算 (2)合取 定义12两个命题P和息的合取是一个复合命题,记作 ∧。当且仅当P、Q同时为T时,P∧Q为在其他情况下 P∧￠的真值都是 联结词“∧的定义如表1-22所示。 表122 E∧g T 例如 P:今天下雨。 =明天下雨。 上述命题的合取为 P∧Q:今天下蔚而且明天下丽。 尸∧見:今天与明天都下雨。 P∧Q:这两天都下雨。 显然只有当“今天下雨”与明天下雨都是真时,“这两天都下 兩才是真的。 合取的概念与自然语言中的与意义相似,但并不完全相岡。 例如 P:我们去看电影 Q:房间里有十张桌子。 上述命题的合取为 PA:我们去看电影与房间里有十张桌子。 在自然语言中述命题是没有意义的,因为P与Q没有内 在联系,但作为数理逻辑中P和Q的合取PAQ来谎,它仍可成 为一个新的命题只要按照定义,在P、分别取真值后,P八Q的 真值也必确定。 命题联结词“合取甚至可以将两个互为否定的命题联绪在 起。这时,其真值永为F。 命题联结词“合取”也可以将若于个命题联结在一起。 合取”是一个二元运算。 (3)折取 定义128两个命题P和的析取是一个复合命题,记作 PVQ。当且仅当PQ同时为矿时,PVQ的真值为否则 PVQ的真值为f。 联结词”的定义如表128所示。 表183 F 从析取的定义可以看到联结词V与汉语中的“或”的意义也 不全相同,因为汉语中的“或可表示“排斥或,也可表示可兼 或 例1今天晚上我在家看电视或去剧场看戏 例2他可能是100米或400米赛跑的冠军。 在例中的“或是排斥或,例2中的“或”是可兼或”而析 取指的是可兼或”。还有一些汉语中的“或”字,实际不是命题联 结词。 例8他昨天儆了二十或三十道习题。 这个例子中的“或”字,只表示了习薏的近似数目,不能用联结 词“折取”表达例8是个源子命题。 (4)条件 定义124綸定两个命题P和￠,其条件命题是一个复合 命题,记作P,读作如果P,那末或“若P则￠。当且仅 当P的真值为T,Q的真值为F时,P的真值为E否则 P→冷的真值为T。我们称P为前件,Q为后件。 联结词”的定义如表1-2要所示。 、衰1g.4 P-Q F F 例1如果某动物为唯乳动物,则它必胎生。 例2如果我得到这本小说那末我今夜就读完它。 例害如果雪是器的,那末太阳从哲方出。 上述三个例子都可用条件命题P弹表达 在自然语言中,“如果…”与“那末…”之间常常是有因果联系