离散数学知识汇总-推荐文档.doc

PAGE\*MERGEFORMATxiv

离散数学笔记
第一章命题逻辑
合取
析取
定义1.1.3否定：当某个命题为真时，其否定为假，当某个命题为假时，其否定为真
定义1.1.4条件联结词，表示“如果……那么……”形式的语句
定义1.1.5双条件联结词，表示“当且仅当”形式的语句

定义1.2.1合式公式
(1)单个命题变元、命题常元为合式公式，称为原子公式。
(2)若某个字符串A是合式公式，则A、(A)也是合式公式。
(3)若A、B是合式公式，则AB、AB、AB、AB是合式公式。
(4)有限次使用(2)~(3)形成的字符串均为合式公式。
1.3等值式

1.4析取范式与合取范式

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

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)、函数常元(如表示的f(x,y))、谓词常元(如表示人类的H(x))。
定义2.2.2、逻辑符号：个体变元、量词(∀∃)、联结词(﹁∨∧→↔)、逗号、括号。
定义2.2.3、项的定义：个体常元、变元及其函数式的表达式称为项(item)。
定义2.2.4、原子公式：设R()是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中的量词∀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代换实例设是命题公式中的命题变元，是n个谓
词公式，用代替公式中的后得到公式A，则称A为的代换实例。
如A(x)∨﹁A(x)，∀xA(x)∨﹁∀xA(x)可看成p∨﹁p的代换实例，A(x)∧﹁A(x)，∀xA(x)∧﹁∀xA(x)可看成p∧﹁p的代换实例。
定理2.2.1命题逻辑的永真公式之代换实例是谓词逻辑的永真公式，命题逻辑的永假公式之代换实例是谓词逻辑的永假式。（代换前后是同类型的公式）
2.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永真，代换实例∀xF(x)↔﹁﹁∀xF(x)永真)
二、个体域有限时，带全称量