完整word版，离散数学知识汇总，推荐文档 - 图文

由天下分享时间：2024/9/10 2:02:47 加入收藏我要投稿点赞

离散数学笔记

第一章命题逻辑

合取析取

定义 1. 1.3 否定：当某个命题为真时，其否定为假，当某个命题为假时，其否定为真定义 1. 1.4 条件联结词，表示“如果… …那么……”形式的语句定义 1. 1.5 双条件联结词，表示“当且仅当”形式的语句

定义 1.2.1 合式公式

(1)单个命题变元、命题常元为合式公式，称为原子公式。 (2)若某个字符串 A 是合式公式，则?A、(A)也是合式公式。

(3)若 A、B 是合式公式，则 A ?B、A?B、A? B、A?B 是合式公式。 (4)有限次使用(2)~(3)形成的字符串均为合式公式。

1.3等值式

1.4析取范式与合取范式

将一个普通公式转换为范式的基本步骤

iii

1.6推理

定义 1.6.1 设 A 与 C 是两个命题公式，若 A → C 为永真式、重言式，则称 C 是 A 的有效结论，或称 A 可以逻辑推出 C，记为 A => C。（用等值演算或真值表）

第二章谓词逻辑

2.1、基本概念

?：全称量词 ?：存在量词

一般情况下，如果个体变元的取值范围不做任何限制即为全总个体域时，带 “全称量词”的谓词公式形如\?x(H(x)→B(x))，即量词的后面为条件式，带“存在量词”的谓词公式形如?x(H(x)∨WL(x))，即量词的后面为合取式例题

R(x)表示对象 x 是兔子，T(x)表示对象 x 是乌龟， H(x,y)表示 x 比 y 跑得快，L(x,y)表示x 与 y 一样快，则兔子比乌龟跑得快表示为： ?x?y(R(x)∧T(y)→H(x,y))

有的兔子比所有的乌龟跑得快表示为：?x?y(R(x)∧T(y)→H(x,y))

2.2、谓词公式及其解释

定义 2.2.1、非逻辑符号：个体常元(如 a,b,c)、函数常元(如表示x类的 H(x))。

定义 2.2.2、逻辑符号：个体变元、量词(??)、联结词(﹁∨∧→?)、逗号、括号。定义 2.2.3、项的定义：个体常元、变元及其函数式的表达式称为项(item)。

2?y2的 f(x,y))、谓词常元(如表示人

xn)是 n 元谓词，t1...tn是项，则 R(t)是原子公式。原子公式中的个体变定义 2.2.4、原子公式：设 R(x1...元，可以换成个体变元的表达式(项)，但不能出现任何联结词与量词，只能为单个的谓词公式。

定义 2.2.5 合式公式：(1)原子公式是合式公式；(2)若 A 是合式公式，则(﹁A)也是合式公式；(3)若 A,B 合式，则 A∨B, A∧B, A→B , A?B 合式(4)若 A 合式，则?xA、?xA 合式(5)有限次使用(2)~(4)得到的式子是合式。定义 2.2.6 量词辖域：?xA 和?xA 中的量词?x/?x 的作用范围，A 就是作用范围。

定义 2.2.7 约束变元：在?x 和?x 的辖域 A 中出现的个体变元 x，称为约束变元，这是与量词相关的变元，约束变元的所有出现都称为约束出现。

定义 2.2.8 自由变元：谓词公式中与任何量词都无关的量词，称为自由变元，它的每次出现称为自由出现。一个公式的个体变元不是约束变元，就是自由变元。

注意：为了避免约束变元和自由变元同名出现，一般要对“约束变元”改名，而不对自由变元改名。定义 2.2.9 闭公式是指不含自由变元的谓词公式

从本例(已省)可知，不同的公式在同一个解释下，其真值可能存在，也可能不存在，但是对于没有自由变元的公式(闭公式)，不论做何种解释，其真值肯定存在

谓词公式的类型：重言式(永真式)、矛盾式(永假式)、可满足公式三种类型

定义 2.2.10 在任何解释下，公式的真值总存在并为真，则为重言式或永真式。定义 2.2.11 在任何解释下，公式的真值总存在并为假，则为矛盾式或永假式。

定义 2.2.12 存在个体域并存在一个解释使得公式的真值存在并为真，则为可满足式。

定义 2.2.13 代换实例设 p1,p2,...,pn是命题公式 A0中的命题变元， A0,A1,...,An是 n 个谓词公式，用Ai代替公式 A0 中的pi后得到公式 A，则称 A 为 A0 的代换实例。

如 A(x)∨﹁A(x)，?xA(x) ∨﹁? xA(x)可看成 p ∨﹁ p 的代换实例，A(x) ∧﹁A(x)，?xA(x) ∧﹁ ?x A(x)可看成 p ∧﹁ p 的代换实例。

定理 2.2.1 命题逻辑的永真公式之代换实例是谓词逻辑的永真公式，命题逻辑的永假公式之代换实例是谓词逻辑的永假式。（代换前后是同类型的公式）

2.3、谓词公式的等值演算

定义 2.3.1 设 A、B 是两个合法的谓词公式，如果在任何解释下，这两个公式的真值都相等，则称 A 与 B 等值，记为 A ? B。