离散数学知识汇集

《离散数学知识汇集》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学笔记第一章命题逻辑合取析取定义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

2、.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)表

3、示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)是原子公式。原子公式中的个体

4、变元，可以换成个体变元的表达式(项)，但不能出现任何联结词与量词，只能为单个的谓词公式。定义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自由变

5、元：谓词公式中与任何量词都无关的量词，称为自由变元，它的每次出现称为自由出现。一个公式的个体变元不是约束变元，就是自由变元。注意：为了避免约束变元和自由变元同名出现，一般要对“约束变元”改名，而不对自由变元改名。定义2.2.9闭公式是指不含自由变元的谓词公式从本例(已省)可知，不同的公式在同一个解释下，其真值可能存在，也可能不存在，资料但是对于没有自由变元的公式(闭公式)，不论做何种解释，其真值肯定存在谓词公式的类型：重言式(永真式)、矛盾式(永假式)、可满足公式三种类型定义2.2.10在任何解释下，公式的真值总存在并为真，则为重言式或永真式。定义2.2.

6、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、谓词公

7、式的等值演算定义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)永真)二、个体域有限时，带全称量词、存在量词公式的等值式如：若D={}，则∀xA(x)óA()∧A()∧…∧A()三、量词的德摩律1、﹁∀xA(

8、x)ó∃x﹁A(x)2、﹁∃xA(x)ó∀x﹁A(x)四、量词分配