离散数学重点知识汇总.doc

:当某个命题为真时,其否定为假,当某个命题为假时,,表示“如果……那么……”,表示“当且仅当”(1)单个命题变元、命题常元为合式公式,称为原子公式。(2)若某个字符串A是合式公式,则A、(A)也是合式公式。(3)若A、B是合式公式,则AB、AB、AB、AB是合式公式。(4)有限次使用(2)~(3)形成的字符串均为合式公式。,若A→C为永真式、重言式,则称C是A的有文档收集自网络,仅用于个人学为A=>C。(用等值演算或真值表)、基本概念∀:全称量词∃:存在量词一般情况下,如果个体变元的取值范围不做任何限制即为全总个体域时,带“全称量词”的谓词公式形如"∀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))、、非逻辑符号:个体常元(如a,b,c)、函数常元(如表示的f(x,y))、谓词常元(如表示人类的H(x))。文档收集自网络,、逻辑符号:个体变元、量词(∀∃)、联结词(﹁∨∧→↔)、逗号、括号。、项的定义:个体常元、变元及其函数式的表达式称为项(item)。、原子公式:设R()是n元谓词,是项,则R(t)是原子公式。原子公式中的个体变元,可以换成个体变元的表达式(项),但不能出现任何联结词与量词,只能为单个的谓词公式。文档收集自网络,:(1)原子公式是合式公式;(2)若A是合式公式,则(﹁A)也是合式公式;(3)若A,B合式,则A∨B,A∧B,A→B,A↔B合式(4)若A合式,则∀xA、∃xA合式(5)有限次使用(2)~(4)得到的式子是合式。文档收集自网络,:∀xA和∃xA中的量词∀x/∃x的作用范围,A就是作用范围。:在∀x和∃x的辖域A中出现的个体变元x,称为约束变元,这是与量词相关的变元,约束变元的所有出现都称为约束出现。文档收集自网络,:谓词公式中与任何量词都无关的量词,称为自由变元,它的每次出现称为自由出现。一个公式的个体变元不是约束变元,就是自由变元。文档收集自网络,仅用于个人学习注意:为了避免约束变元和自由变元同名出现,一般要对“约束变元”改名,而不对自由变元改名。(已省)可知,不同的公式在同一个解释下,其真值可能存在,也可能不存在,但是对于没有自由变元的公式(闭公式),不论做何种解释,其真值肯定存在文档收集自网络,仅用于个人学习谓词公式的类型:重言式(永真式)、矛盾式(永假式)、,公式的真值总存在并为真,则为重言式或永真式。,公式的真值总存在并为假,则为矛盾式或永假式。,则为可满足式。,是n个谓词公式,用代替公式中的后得到公式A,则称A为的代换实例。如A(x)∨﹁A(x),∀xA(x)∨﹁∀xA(x)可看成p∨﹁p的代换实例,A(x)∧﹁A(x),∀xA(x)∧﹁∀xA(x)可看成p∧﹁p的代换实例。文档收集自网络,,命题逻辑的永假公式之代换实例是谓词逻辑的永假式。(代换前后是同类型的公式)文档收集自网络,、、B是两个合法的谓词公式,如果在任何解释下,这两个公式的真值都相等,则称A与B等值,记为AóB。文档收集自网络,仅用于个人学习当AóB时,根据定义可知,在任何解释下,公式A与公式B的真值都相同,故A↔B为永真式,故得到如下的定义。文档收集自网络,、B是