离散数学复习2.

1第二章谓词逻辑2.1谓词演算的基本概念2.2谓词演算的关系式2.3前束范式2.4谓词演算的推理2§2.1.1谓词与个体考察以下2个原子命题：（1）李华是工程师。（2）何威是工程师。若对这两个原子命题进行内部结构分析，就会发现它们之间既有相异之处又有相同之处。相异之处：主语不同相同之处：谓语共享将相同部分从这类命题中分离（抽象）出来进行研究并符号化。引入一个符号表示“x是工程师”。Ｇ(x)或Ｇ(·)3§2.1.1谓词与个体像Ｇ(·)这样抽象形式，实际上就是上述几个语句中描述主语性质的谓语结构的抽象形式或描述主语所涉及对象之间的关系的抽象形式。上述中的抽象形式就是谓词。语句中的主语或对象称为个体。个体是指可以独立存在的。谓词是用来刻划个体的性质或关系的。通常用大写字母F,G,H等表示谓词，用小写字母a,b,c等表示个体。在原子命题中引进谓词和个体的概念，这种以命题中的谓词为基础的分析研究，称为谓词逻辑(或称谓词演算)。4§2.1.1谓词与个体个体的变化范围，称为个体域。将宇宙间一切事物（所有个体）所组成的个体域称为全总个体域。以某一个个体域为变域的变元，称为个体变元。习惯用小写的x,y,z等表示。与个体变元相对的是个体常元，它指某个确定的个体，习惯用小写的a,b,c等表示。5§2.1.1谓词与个体仅含一个个体变元的谓词，称为一元谓词。含有n个个体变元的谓词，称为n元谓词。含有0个个体变元的谓词（但可能包含多个个体常元），称为0元谓词。一般地，一元谓词刻画了个体的性质，多元谓词刻画了个体之间的关系。注意：谓词不是命题，只有当确定的个体“填入”后，才成为命题。Ｔ(x)Ｄ(x，y)Ｆ(a,b,c)“张华是大学生”可表示为F(a)6§2.1.2量词)(xxF全称量词记作“x”，其含意是：“所有的x”、“每一个x”、“凡是x”、“任意的x”等等。表示对个体域中的所有个体其谓词F(x)均为真。7§2.1.2量词)(xxF存在量词记作“”，其含意是：“存在着x”、“有些x”等等。表示个体域中存在某些个体其谓词F(x)均为真。x8函数在谓词逻辑中，个体与个体间有一定的关系，这种关系称为函数。)(xf),(yxf),,(21nxxxf一元函数二元函数多元函数例：李平的妈妈是医生。D(x)：x是医生；a：李平；f(a)：李平的妈妈；句子符号化为：D(f(a))9用谓词和量词表示句子的步骤：参考题目给出的个体域，如果没有指明，假设为全总个体域；确定句子中的谓词和个体变元；在全总个体域下，句子中的名词（人、数、动物等）都需要使用特性谓词表示；多元谓词使用多个不同的个体变元。根据句子中特性谓词前的修饰词选择量词；：“所有的”、“凡是”、“一切”、“任意”、“每一个”等词，或省略的情况：“存在”、“有些”、“某些”、“几个”等词根据量词确定谓词之间的关系；所限定的个体变元所在的特性谓词和其他谓词之间使用条件连接词。所限定的个体变元所在的特性谓词和其他谓词之间使用合取连接词。10例1.没有不犯错的人))()(((xWxMxM(x)：x是人W(x)：x犯错11例2.对于所有的正实数x,y，都有x+y≥x。)),()()((yxPySxSyxS(x)：x是正实数P(x，y)：x+y≥x12练习课后题1.29（8）（9）（10）13§2.1.3谓词逻辑公式（公式）谓词逻辑公式中所使用的符号有以下七种:(1)个体常量符:(2)个体变量符:(3)函数符:(4)谓词符:(5)联结词符:(7)括号(,)(6)量词符:,,,,,一个谓词逻辑公式中是由上述符号按一定规则所组成的符号串。a,b,c,…x,y,z…f,g,h…F,G,H…14§2.1.3谓词公式（续）例如，下列各式是谓词公式。但下列各式不是谓词公式。)))()(((yRxQy)P(x,y)x)(()y)y)Q(x,()x(P(x)(y)x,P((y)x)((E(y)x)()x(x)P())z,y(RQ(x))z,y,x(P)(z(y)x)((15练习：下列哪些是谓词公式：)())(.(7))()((.6))((.5)))(()),(((.4))()((.3)),(),),,(((.2),(.1xPxxyPxPxZPyxzxPxyxPxyyQxPxyxQzyyxpAyxyxP16§2.1.4自由变元和约束变元由于全称量词的作用，使得命题函数中的x不再起变元的作用，或者说，量词约束了x的变元作用，在这种情况下，称变量x为“约束出现”，并称x为约束变元。又如在这个谓词公式中，易见，x是约束元，但y不是约束元，称y是“自由出现”，并称y为自由变元。量词后括号中的内容称为量词的作用域或辖域。Q(x))x)(P(x)()Q(x)y),(P(xx)(x)Q(x)y),(P(xx17换名规则在对约束元换名时，应遵循以下两种规则（约束元换名规则）：（1）对约束元（如x）换名时，更改的名称范围是或中的x以及量词作用域中所出现的所有x，在量词作用域外的部分不换名。（2）换名时一定要更改为作用域中没有出现的变量名称xx18例1解：在这个谓词公式中，x既是约束元又是自由元，y也是约束元又是自由元。若把约束元x换名为u，约束元y换名为v，经换名后，谓词公式可写成为于是可知，u，v是约束元，x，y是自由元。y)))R(x,(Q(y)y)((Q(x)))y)(P(x,x)(()))R(x,)(Q()(()))Q(y),(P()((vvvuuu19代入规则对于谓词公式中的自由变元，也可以更改，这种更改称为代入，代入时应对谓词公式中出现该自由变元的每一处都进行。这称为自由元代入规则．例如，可更改为y)R(x,P(x)x)(y)R(z,P(x)x)(20例1（续）对下列谓词公式中自由元进行代入，使得一个变量在谓词公式中只呈一种形式（约束元或自由元）出现。y)))R(x,(Q(y)y)((Q(x)))y)(P(x,x)((21谓词关系式将命题公式的等价关系可以推广为谓词公式的等价关系：QPQP)(),(xxQxxP)()()()(xxQxxPxxQxxP例如：命题公式将P和Q分别替换为：公式就可变为：22谓词公式（等价或蕴含）关系式由于量词的引入，谓词公式多了如下公式：)()]([.8)()]([.7)()]([.6)()]([.5)()()(.4)()()(.3)()()]()([.2)()()]()([.1xxBAxBAxxxBAxBAxxxBAxBAxxxBAxBAxxAxxAxxAxxAxxxBxxAxBxAxxxBxxAxBxAx存在服从对∨的分配律全称服从对∧的分配律全称量词变为存在量词存在量词变为全称量词否定深入5、6、7、8其中的A是没有出现约束变元x的谓词公式。量词作用域的扩张和收缩23关系式))(()(.14))(()(.13))(()(.12))(()(.11)()())()((.10))()(()()(.9xBAxxxBAxBAxxxBABxAxBxxABxAxBxxAxxBxxAxBxAxxBxAxxxBxxA全称对∨不服从分配律存在对∧不服从分配律24对偶定义设A是命题公式，且A中仅有联结词﹁，∨，∧，量词，。在A中把∨，∧，F，T，，，分别换成∧，∨，T，F，，后所得的命题公式称为A的对偶公式。25对偶例：的对偶式：))((BxAx))((BxAx26练习：写出对偶式)()(xyyRxP)()(xyyRxP27§2.3前束范式定义:一个公式，如果量词均非否定地在全式的开头，且公式除量词外，最多只含￢∧∨，则称此公式叫前束范式。例：xyz(¬Q(x,y)R(z))(前束范式)(x)P(x)∧(y)Q(y),(x)(P(x)(y)Q(x,y))))(),()()()((zRyxQzxy))(),()()((yQyxPyxXXXX28前束范式求解的一般步骤（不唯一）：1.运用基本等价公式，把各种联结词转换成基本联结词：¬、和∧2.运用E1、E8、E9、E24、E25、E26等将公式中的¬深入到各谓词变元的前面。3.利用换名、代入规则，使所有的约束变元均不同名，且自由变元与约束变元也不同名。4.利用E27、E28、E29、E30、E31、E32扩大量词的作用域至整个公式。29前束范式例：把xP(x)R(x)变成前束范式xP(x)R(x)yP(y)R(x)y(P(y)R(x))例：把xP(x)xQ(x)变成前束范式。xP(x)xQ(x)¬xP(x)xQ(x)x¬P(x)xQ(x)x(¬P(x)Q(x))30前束范式例.将公式((x)P(x)∨(y)Q(y))(x)R(x)化归为前束范式原式¬((x)P(x)∨(y)Q(y))∨(x)R(x)((x)¬P(x)∧(y)¬Q(y))∨(x)R(x)((x)¬P(x)∧(y)¬Q(y))∨(z)R(z)(x)(y)(z)[(¬P(x)∧¬Q(y))∨R(z)]量词前移31练习课后题1.32（2）32第三章集合3.1集合的基本概念3.2集合的运算及基本公式3.3幂集3.4包含排斥原理3.5集合的直积333.1.1集合的表示一般用大写的英文字母A,B,C,…来代表集合，|A|表示集合中元素的个数；用小写的英文字母a,b,c,…来代表集合中的元素。一些特殊集合的表示：Ｎ代表自然数集合，Ｚ代表整数集合，Ｑ代表有理数集合，Ｒ代表实数集合，Ｃ代表复数集合．343.1.1元素与集合的关系如果b是集合A中的元素，称b属于A，并记作如果b不是集合A中的元素，称b不属于A，并记作AbAb例如：QNZZN2,1,1,5,135练习：列出下列集合的元素(1){x,|x∈N⋀∃t(t∈{2,3}⋀x=2t)}(2){x,|x∈N⋀∃t∃s(t∈{0,1}⋀s∈{3,4}⋀txs)}(3){x,|x∈N⋀∀t(t整除2→x≠t)}{4,6}{1,2,3}N-{1,2}36空集和全集不含有任何元素的集合称为空集，记作Ø研究对象的全体称为全集，记作E。E={x|P(x)∨￢P(x)}注意：全集是个相对性的概念，由于研究的问题不同，所取的全集也不同，即使是同一个问题也可以有不同的全集．37【例】确定下列命题是否正确？(1)(2)(3)(4)(5)(6)(7)(8)}{}{}},,{,,,{}cbacbab{a,}}b,a{,c,b,a{}b{a,}}}b,a{{,b,a{}b{a,}}}b,a{{,b,a{}b{a,√√X√√√X√38§3.2集合的运算及其基本公式1.并运算∪2.交运算∩3.差集4.补集5.布尔和39§3.2集合的运算及其基本公式3.差集：设A，B是集合，由所有属于A但不属于B的元素构成的集合称为A对B的差集，记作：A-B例如:A={1，2，3，4}，B={3，4，5}差集A–B={1,2},B–AAB={5}40§3.2集合的运算及其基本公式4.补集集合A的补集A可定义为A=E–A={x|¬(x∈A)}A41§3.2集合的运算及其基本公式5.布尔和（对称差）集合A,B的布尔和（对称差）A+B定义为：A+B=(A-B)∪(B-A)ABA+B=(A∪B)-(A∩B)42练习：3.E={0,1,2,3,4,5,6,7,8,9},A={2,4,5,6,8},B={1,4,5,