离散数学简介

  • 离散数学是以离散变量为研究对象的一门科学
  • 离散数学是近代数学的一个分支
  • 离散数学的研究对象是世间一切事物之间的关系

  • 离散数学所采用的研究方法有集合、代数、图、数理逻辑等

    学习内容

  • 数理逻辑

数理逻辑是用数学的方法研究推理的形式结构和推理的逻辑规律的学科。本书主要介绍命题演算、谓词演算

  • 集合论

研究集合的一般性质的数学分支学科，是现代数学的基础。对从事计算机科学的人来说，集合论是不可缺少的理论基础。本书介绍集合、关系和函数

  • 代数系统 ( 《离散数学2》 课程的内容）

代数系统带有运算的集合，是现代数学的分支近世代数研究的主要对象。他的研究方法和结果在构造可计算模型、研究算术计算的复杂性、刻画抽象数据结构均有巨大的理论和实际意义。本书主要讨论代数系统、半群、 群、环、域、格、布尔代数

  • 图论

图论以离散对象的二元关系结构为研究对象，在网络理论、信息论、控制论和计算机领域都有着广泛的应用。本书主要接收图论的基本概念、基本理论及典型应用。

1 命题逻辑

1.1 命题符号化及联结词

1.1.1 命题简介

  • 命题：能判断真假的陈述句。
  • 真值：一个命题总具有一个值，即真（用 1 或 T 表示）或假（用 0 或 F 表示）。
  • 一切没有判断内容的句子，无所谓是非的句子，如感叹句、疑问句、祈使句等都不是命题。
  • 判断一个句子是否是命题的关键：是否是陈述句；真值是否唯一
  • 简单命题（原子命题）：不能分解为更简单的陈述句。

  • 复合命题：由联结词、标点符号把几个原子命题联结起来的命题。

    1.1.2 命题的表示

  • 使用小写英文字母p，q，r…或带下标的小写字母pi，qi，ri…或用数字如[12]表示。

  • 命题标识符：表示命题的符号。如p，A，[12]等。
  • 命题符号化：将命题的符号放在该命题的前面。
  • 命题常量：真值确定的简单命题
  • 命题变元：真值变化的简单陈述句。 注意：命题变元不是命题。 例：p:x+y>5，一个符号表示的是命题常项还是命题变项由上下文决定
  • 指派：当命题变元p用一个特定命题取代时，p才能确定真值，这时称对p进行指派。

  • 原子变元：当命题变元表示原子命题时，该变元称为原子变元。

    1.1.3 联结词

  • 联结词，也称真值联结词或逻辑联结词或逻辑运算符

  • 假设p，q为两个命题，常用的5个联结词有

（1）否定┐
定义1.1 ：设p为一个命题， p的否定是一个新命题，记作┐p。自然语言常用联结词：“不”，“无”，“没有”，“并非”等
image.png
（2）合取∧
定义1.2 ：两个命题p和q的合取是一个复合命题，记作p∧q。自然语言中常用的联结词： “且”，“既…又…”，“不仅…而且…”，“虽然···但是”，“…和…”等
image.png
（3）析取∨
定义1.3 ： 两个命题p和q的析取是一个复合命题，记作pVq。自然语言中常用联结词：“可兼或”，有些或不是联结词。
image.png
（4）蕴涵（条件）→
定义1.4 ： 给定两个命题p和q， 其条件命题是一个复合命题。 记作p→q， 读作 “如果p，那么q”或 ‘若p则q” ，称p为前件，q为后件。
image.png
（5）等价（双条件）<->
定义1.5 ： 给定两个命题p和q， 其等价命题是一个复合命题，记作 P<->q，读作 “p当且仅当q。自然语言： 当且仅当。
image.png

  • 注意：在数理逻辑中只要p和q是命题，复合命题p<->q，p → q就有意义，不需要p和q必然有联系。

    1.2 命题公式及分类

    1.2.1 命题公式与翻译

  • 命题公式：由命题常项或命题变项组成的复合命题形式。

  • 定义1.6 合式公式：

（1）单个命题常项或变项p，q，r…p，q，r…0，1是合式公式
（2）如果A是合式公式，则（┐A）也是合式公式
（3）如果A，B是合式公式，则（A∧B）（AvB）（A→B）（A<->B）也是合式公式
（4）当且仅当能够有限次地应用（1） （2）（3）所得到的符号串才是合式公式

  • 为了减少括号的数量，规定：

    • 联结词一元运算优于二元运算
    • 最外层括号省去

      1.2.2 复合命题符号化的步骤

  • 分析出简单命题符号化

  • 用联结词连接简单命题

    1.2.3 命题公式层次的定义

  • 若A是单个命题（常项或变项），p，q，r…pi，qi，ri..0，1，则称A是0层公式。

  • 称A是n+1(n≥0）层公式是指A符合下列情况之一：

（1）A=B，B是n层公式；
（2）A=B∧C，其中B，C分别为i层和j层公式，且n=max（ij）
（3）A=BVC，其中B，C的层次同（2）
（4）A= B→C，其中B，C的层次同（2）
（5）A=B<->C，其中B，C的层次同（2）

  • 若A的最高层次为k，则称A是K层公式

    1.2.4 对一个公式的解释和赋值定义如下

  • 设A为一个命题公式，p1，p2，…pn为出现在A中的所有的命题变项。给p1,p2,..，pn指定一组真值，称为对A的一个赋值或真值指派。

  • 若指定的一组值使A的值为真，则称这组值为A的成真赋值，若使A的值为假，则称这组值为A的成假赋值。

例：公式A =（p∧q）→r，110是A的一个赋值，即另p=1，q=1，r=0，110是一个成假赋值；那么111，011，010是A的成真赋值。

1.2.5 真值表与等价公式

  • 真值表：在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它汇成列表，就是命题公式的真值表。
  • 含 n 个命题变项的命题公式，共有 2 组赋值。
  • 将命题公式 A 在所有赋值之下取值的情况列成表，称为 A 的真值表。

  • 构造真值表的步骤：

    • 找出命题公式中所含的所有命题变项，列出所有可能赋值
    • 从低到高写出层次
    • 计算命题公式的值

      1.2.6 命题公式的分类

      定义 1.9 设 A 是一个命题公式

  • 若 A 在它的各种赋值下取值为真，则称 A 为重言式或永真式

  • 若 A 在它的各种赋值下取值为假，则称 A 为矛盾式或永假式
  • 若 A 至少存在一组赋值是成真赋值，则称 A 为可满足式
  • 重言式是可满足式，可满足式不一定是重言式

  • 判断命题公式类型的一种方法之一是真值表

    1.3 等值演算

    1.3.1 等价的或逻辑相等

  • n 个命题变项只能生成image.png个真值不同的命题公式

  • 定义 1.10：设 A，B 为两个命题公式，若等价式A<->B是重言式，则称 A 与 B 是等值的，记作 A<=>B
    • A<=>B不是命题公式
    • 通过判断 A与B真值表是否相同，来判断 A与B是否等值

image.png
image.png

1.3.2 等值演算

  • 根据已知的等值式推演出另外一些等值式的过程称为等值演算。
  • 定理 1.1（置换定理）：设Φ（A）是含命题公式 A 的命题公式，Φ（B）是用命题公式 B 置换了Φ（A）中的 A 之后得到的命题公式。如果 A<=>B，则Φ（A）<=> Φ（B）。
  • 等价代换实际上是根据已知的合式公式推演出另外一些合式公式的过程。
  • 等价代换的用途
    • 验证两个公式等值
    • 判别命题公式类型
    • 解决实际问题
  • 验证两个公式等值

image.png

  • 判别命题公式类型

image.png

  • 判别命题公式类型

image.png