离散数学第01讲

离

散

数

学DsicetreMa temhticsa息信科学工程学院 与作制：者 永 政

蔺散离数学的展发

1世8以前纪 数学,本上是基究研离散对象的量和空间关系的科数 。学

之后因天文学,,理物的学展发如,星行道,轨牛三顿大学力定等研 律,极大地究推动了连续学(数以微积,分学物理方程数, 实复变、 数函为代论)的发展。表离 对散象的研则究处于滞停状态。2世030年纪代, 灵图提计出算的理机模型论——灵机图。这种模型 于实早制造际计算十机多,现年实的算计机的计算能,力 质上本和图机的灵计能力算样一 。由在于算机计内机,器字总是有限的长, 代表离它散数或其它的离散对象 ，此随因着计算科学机和术技迅猛的发展,散数学离就 显得要。重 信科学与息程学院工 2

为什要学离么数散 学

计算机求解的本模式基： 实际问题 数是建模 学 算 设法 计编程现 实离散学数数学建模打为知下基础识、算法为计设提 供体指具导 离散学数结实构际上是通用的就抽象模式的的合， 告集你各种模式诉本的质特征它和们之的间系，关以 及选它用的们略；策诉告你哪些问题是可解的，些是哪当前 在图机模灵上型(最无)优解的哪，是可以些得 近似到/较解的优 简而。之言，散数学离的用就作在于训练用运离散构 结为作题问的象抽型模构造、算、法决解题问能的力信。科学息工程学与 院

3离散

学的数应举用 例

关系型数库的设计(据系代关) 数表达解式(树) 优析化编译的构器造(包闭) 编技术、程序设译计语(代言结构)数 LispP和roog、人l智工、能动推自理机、证器(明数逻辑理 网络)路算法(由图论)游 中的人工戏能算智(图论、树、法博论)弈 家系专统(合论、数理逻集辑—识和知理规推则的算计表达机 软件)工程团队开——发时和间工分优化(图的—论网络划、分)(各种) 算的构法、正造确性证明和效的的评率(估离散数的各学 支分)信息科与工程学院 4学

引

1言

离数散学随着计是机科学算发的展而步建立逐的，它 成于七形十代初期，是一门新兴的工具性年科。学离 散数是学代现数学的个重一分要支是计算， 科机学与技术理的论础，基所以称为计又机算数学 ，是算机计学科技与专术的核业、心干骨程。 课以它究离研散的结构和量相间互关的系为要主 标目，研究对其一般象是限有个或可个元素，因数此 充它分描述计算了科机离散学性特点。的内容 含包数理：逻、集合辑、论代结数与构尔 代布、图论数等。5

信科息与工程学学院

引

学该课程的习目的：

言2一方面它，给继后，课数据结构、编如系译、操作统系 统数据、原理、库软工件程与法方、计算学网络和机人 工智等能提，供要必数学基的础 ；一另方面，过通学习散数学，离可培养以和提高己自 的抽思维象逻辑推和理能，力为后以的、软硬件学习研和 究开发工作，打下坚实的数学础基。

息信科学工与程院学6

引教学要：

言3求通该过课的学程，学习应生了当并解握计掌机科学算中 普遍采用离的数学散的中些一基概本、念基思本想基 本方法、。自要求学通：过反看书及做课后复习，题来深对加课程该的中一 基本概念些的解理，步逐提自己的抽高象思和维逻辑推理 力。能

息信科与学工学程

7

院

引教:材言4

《离数散》 左学凌孝等 海科学上术技献文版出社参书目考:1、《离散数学》耿 云素等高 等教育版出社 、2Disrctee atMehatmiscand tIsA plpcationsiK,enetnhH. R seno,hCinaM ahinecPr ess机械工(出业社)版，McGra wH-ill(991)

信9息科学与工学程院8

本学期引教学求：要

言 5

时上课按 专听心 积课极习复 认作真业 顺考试利信息学科工与程学 院9

引联系方：式言6

办公地:1点28J0 E3ma-li: is_eliyznujn.e@ducn.信息学与科工程学院1

0

一第篇 数逻理

数辑逻理是研究推辑理即研究(人类思维的形 结构式和律)规科学，的源于17世起纪 ，它用采学数符化的方号，因法此称为也符 逻辑。 号 广从上讲，义理逻辑数包四括、论演两 算——即集合论、型论模递、归论证、明 论命和演算、谓词演算，题现在但提到 理数辑逻一般是指命题，算和谓词演演。 本书也算只究研这两个演。算

信息学科与程学院工11

第一篇 理逻数辑

数逻理的辑创始人L是iebnz,为i实现了推理 把变为演算的法，他想把数引入学了形逻辑式。 后，其经多人又努力，渐逐使数理得辑成为逻门 专一门学的科。 个上世30年纪以代，后理数辑进逻入个崭新的 发一展段阶，辑学逻不仅数与学合，结与计还机 算学科等密切关。 1联391Go年del完不全定性的提出，理及递以函归 可数计性的算引，促入了使931年6uTirgn机的 产生十，后年，第台一子电计算机世。问信息科学与工程院 12学

第篇一数理 逻辑 数理辑逻与算计机学控、论、制工人智的相互能渗 透推了其自身的动发，展糊模辑逻概、率逻辑归、逻纳 、时辑逻辑等态都是前比较目热门的究研域。领

本篇我只从语义们出发对数理逻，辑的命题中演算与谓词演算等作简单的、一直的、接非形式的介化绍。信息科学与工学程院13

一第 章题逻辑1-1 命题命及其表示法 基概念本

命:能题够判断真假的陈述句 命题的真。:命值题的判断果结真。只取值两个 ：值真 、,分假用别TF表和示 真命。:题值为真真命的题。 命假：题真值为假的题命 1。、否是陈述为句 2;、是有否确定的唯、的真值。一信科息学工与程学院 14判断命题的两步骤：

个第一

章题逻命辑：例判断下句子是否列为题。命1 、10是自然数。02、太 从西方升阳。 起3、们我要努学习。力4、 ow Hod youd ?o5 、年国今节庆下雨小 6。x、+3> 7、我9在正说。谎8 昨、的晚球并赛没充分展示A有C米兰水的。 9、如果平姚明还在健话，那得中么国男篮至少该杀应入世锦赛前 名。八 10、国能足入杀012世4杯界当仅且2+2>4。当信息学与工程科学院1 5

第一

章命题辑命逻题其及真值的象抽化在本书中，用大英写文字A母，, B …,,QP, …或带标的大下字母写A或i字数1[]2示表题命。 如 A:罗纳：耳是朵星。球P: 是负数。 5P3明天天：晴。 气为皆号化的命符，其题值真次依为、F、T或T。F

息信科与工学学程院

16第一

章命逻辑题题常量：命表确示定命的命题题标符识。 :如A罗：纳耳是朵球星

。命题变元不表：确定示命的题命题标识符。如 ：PB、。等命题元的变派指：用个特一命题取代定题变命信息科学元与程工院 学71

第一章命题 逻辑题命分的简类/原单子题：命不能再分由为解更简单的 述句陈的述句构成陈 。上如中的例题。 复命合命：由简题单命题通过结联词结联成而的 述陈。句

信息学科工与学院程18

第一 命题逻辑章1-2联 结词定义-21.1设P为 题，复合命题“非P命 ”或(“的否P”定)称P为的定否式记 ， 作 P ,符 号 称 为否定结词。 运算规联：则属单于目算符运PT

FPF

息科学信与程学工院T19

本文来源：https://www.bwwdw.com/article/f5vi.html