离散数学知识汇总

离散数学笔记离散数学笔记 第一章第一章 命题逻辑命题逻辑 合取 析取 定义 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有限次使用23形成的字符串均为合式公式。 1.31.3 等值式等值式 1.41.4 析取范式与合取范式析取范式与合取范式 i 将一个普通公式转换为范式的基本步骤将一个普通公式转换为范式的基本步骤 ii iii 1.61.6 推理推理 定义 1.6.1 设 A 与 C 是两个命题公式， 若 A → C 为永真式、 重言式，则称 C 是 A 的有 效结论，或称 A 可以逻辑推出 C，记为 A C。 （用等值演算或真值表） 第二章第二章 谓词逻辑谓词逻辑 2.12.1、基本概念、基本概念 ∀全称量词 ∃存在量词 一般情况下， 如果个体变元的取值范围不做任何限制即为全总个体域时， 带 “全称量词”的谓词公式形如 “∀xHx→Bx，即量词的后面为条件式，带“存在量词”的谓词公式形如 ∃xHx∨WLx，即量词的后面为 合取式 例题例题 Rx表示对象 x 是兔子，Tx表示对象 x 是乌龟， Hx,y表示 x 比 y 跑得快，Lx,y表示 x 与 y 一样快， 则兔子比乌龟跑得快表示为∀x∀yRx∧Ty→Hx,y 有的兔子比所有的乌龟跑得快表示为∃x∀yRx∧Ty→Hx,y 2.22.2、谓词公式及其解释、谓词公式及其解释 定义 2.2.1、 非逻辑符号 个体常元如 a,b,c、 函数常元如表示x 类的 Hx。 定义 2.2.2、逻辑符号逻辑符号个体变元、量词∀∃、联结词﹁∨∧→↔、逗号、括号。 定义 2.2.3、项项的定义个体常元、变元及其函数式的表达式称为项item。 2y2的 fx,y、 谓词常元如表示人 x n 是 n 元谓词，t1. tn是项，则 Rt是原子公式。原子公式中的个体变 定义 2.2.4、原子公式原子公式设 Rx 1. 元，可以换成个体变元的表达式项，但不能出现任何联结词与量词，只能为单个的谓词公式。 定义 2.2.5 合式公式合式公式 1原子公式是合式公式； 2若 A 是合式公式， 则﹁A也是合式公式； 3若 A,B 合式， 则 A∨B, A∧B, A→B , A↔B 合式4若 A 合式，则∀xA、∃xA 合式5有限次使用24得到的式子是合式。 定义 2.2.6 量词辖域量词辖域∀xA 和∃xA 中的量词∀x/∃x 的作用范围，A 就是作用范围。 定义 2.2.7 约束变元约束变元在∀x 和∃x 的辖域 A 中出现的个体变元 x，称为约束变元，这是与量词相关的变元， 约束变元的所有出现都称为约束出现。 定义 2.2.8 自由变元自由变元谓词公式中与任何量词都无关的量词，称为自由变元，它的每次出现称为自由出现。一 个公式的个体变元不是约束变元，就是自由变元。 注意注意为了避免约束变元和自由变元同名出现，一般要对“约束变元”改名，而不对自由变元改名。 定义 2.2.9 闭公式是指不含自由变元的谓词公式 iv 从本例已省可知， 不同的公式在同一个解释下， 其真值可能存在， 也可能不存在， 但是对于没有自由变 元的公式闭公式，不论做何种解释，其真值肯定存在 谓词公式谓词公式的类型重言式永真式、矛盾式永假式、可满足公式三种类型 定义 2.2.10 在任何解释下，公式的真值总存在并为真，则为重言式或永真式。 定义 2.2.11 在任何解释下，公式的真值总存在并为假，则为矛盾式或永假式。 定义 2.2.12 存在个体域并存在一个解释使得公式的真值存在并为真，则为可满足式。 定义 2.2.13 代换实例 设 p 1, p 2 ,.,p n 是命题公式 A 0 中的命题变元， A 0 ,A 1,.,An 是 n 个谓 词公式，用Ai代替公式 A 0 中的p i 后得到公式 A，则称 A 为 A 0 的代换实例。 如如 Ax∨﹁Ax，∀xAx ∨﹁∀ xAx可看成 p ∨﹁p 的代换实例， Ax ∧﹁Ax，∀xAx ∧﹁ ∀x Ax 可看成 p ∧﹁p 的代换实例。 定理 2.2.1 命题逻辑的永真公式之代换实例是谓词逻辑的永真公式， 命题逻辑的永假公式之代换实例是谓词 逻辑的永假式。 （代换前后是同类型的公式） 2.32.3、谓词公式的等值演算、谓词公式的等值演算 定义 2.3.1 设 A、 B 是两个合法的谓词公式， 如果在任何解释下， 这两个公式的真值都相等， 则称 A 与 B 等 值，记为 A B。 当 AB 时，根据定义可知，在任何解释下，公式 A 与公式 B 的真值都相同，故 A↔B 为永真式，故得 到如下的定义。 定义 2.3.2 设 A、B 是两个合法谓词公式，如果在任何解释下， A↔ B 为永真式， 则 A 与 B 等值，记为 A B。 一、利用代换实例可证明的等值式p↔﹁﹁p 永真，代换实例∀ xFx ↔﹁﹁∀ xFx永真 二、个体域有限时，带全称量词、存在量词公式的等值式 如如若 D{a1,a2,.,an}，则∀ xAx  Aa1∧Aa 2 ∧∧Aa n 三、量词的德摩律 1、﹁∀xAx ∃x﹁Ax2、﹁∃xAx ∀x﹁Ax 四、量词分配律 1、∀xAx∧Bx ∀xAx∧∀xBx2、∃xAx∨Bx ∃xAx∨∃xBx 记忆方法记忆方法∀与∧，一个尖角朝下、一个尖角朝上，相反可才分配。2 式可看成 1 式的对偶式 五、量词作用域的收缩与扩张律 Ax含自由出现的个体变元 x，B 不含有自由出现的 x，则有 1、∀/∃Ax∨B ∀/∃Ax∨B2、∀/∃Ax∧B ∀/∃Ax∧B 对于条件式 Ax ↔B， 利用 “基本等值一” 将其转换为析取式， 再使用德摩律进行演算 六、置换规则 若 B 是公式 A 的子公式，且 B  C，将 B 在 A 中的每次出现，都换成 C 得到的公式记为 D，则 AD 七、约束变元改名规则 将公式 A 中某量词的指导变元及辖域中约束变元每次约束出现，全部换成公式中未出现的字母，所得到的公 v 式记为 B，则 A B 例 证明步骤 2.42.4、谓词公式的范式、谓词公式的范式 从定理证明过程，可得到获取前束范式的步骤 1剔除不起作用的量词； 2如果约束变元与自由变元同名，则约束变元改名； 3如果后面的约束变元与前面的约束变元同名，则后的约