离散数学知识汇总VIP专享VIP免费

i离散数学笔记第一章 命题逻辑合取析取定义 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析取范式与合取范式ii将一个普通公式转换为范式的基本步骤iiiiv1.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 2类的 H(x))。 y 2 的 f(x,y))、 谓词常元(如表示人定义 2.2.2、逻辑符号：个体变元、量词(∀∃)、联结词(﹁∨∧→↔)、逗号、括号。定义 2.2.3、项的定义：个体常元、变元及其函数式的表达式称为项(item)。定义 2.2.4、原子公式：设 R( x1 ...x n )是 n 元谓词，t1 ...t n 是项，则 R(t)是原子公式。原子公式中的个体变元，可以换成个体变元的表达式(项)，但不能出现任何联结词与量词，只能为单个的谓词公式。定义 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 中...