离散数学 谓词逻辑2.ppt

《离散数学 谓词逻辑2.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章谓词逻辑谓词演算的推理理论等价式与永真蕴含式2主要内容等价式与永真蕴含式谓词推理理论3谓词公式的等价给定两个谓词公式A和B，设它们有共同的个体域E，如果对A和B的任一组变元（个体词）进行赋值，所得命题的真值相同，则称谓词公式A和B在E上等价记做A⇔B4谓词公式的等价与命题公式的等价举例PQPQPQTTTTTFFFFTTTFFTTPQPQF(x)W(x)F(x)W(x)X的范围是：所有正整数xF(x)W(x)F(x)W(x)1T/F?T/F?2T/F？T/F?………5命题演算中等价公式的推广应用用同一谓词公式代替两个等价命题公式中的同一命题变元，所得到的谓

2、词公式也等价。例如：(x)F(x)W(x)(x)F(x)W(x)PQPQ(x)F(x)G(x)QPQ(x)F(x)G(x)P()6等价变换基本规则1．置换规则2．约束元的换名规则3．自由元的代入规则7等价演算的基本规则(1)1.置换规则：设P(A)是含公式A的公式，若AB,则用公式B取代P(A)中所有的A之后的公式P(B)与P(A)等价。例：(x)(A(x)→B)(x)(רA(x)∨B)8等价替换基本规则(2)2．约束元的换名规则设A为一公式，将A中某量词辖域中某约束变量的指导变元及相应的约束变元改成该量词辖域中未曾出现过的某个体变量符号，公式的其余部

3、分不变，所得公式与A等价.例：ㄱ(x)(P(x,y)Q(x))xR(x)ㄱ(z)(P(z,y)Q(z))xR(x)9等价替换基本规则(3)3．自由元的代入规则设A为一公式，将A中某个自由出现的个体变元的所有出现用A中未曾出现过的个体变元符号代替，A中其余部分不变，所得公式与A等价.例：ㄱ(x)(P(x,y)Q(x))xR(x)ㄱ(x)(P(x,w)Q(x))xR(x)10常用等价式1：否定与量词量词与否定联结词┐的关系：(1)┐(∀x)P(x)⇔(∃x)┐P(x)(2)┐(∃x)P(x)⇔(∀x)┐P(x)证法一:(1)“并非对任意x，P(X)是真”等

4、价于“至少存在一个x，使P(X)为假”。(2)“并非存在一个x，使P(X)为真”等价于“对所有的x，P(X)为假”。注意：出现在量词前面的否定，不是否定该量词本身，而是否定被量化了的整个公式。11证法2：设个体域为{a1，a2，……………，an}┐(x)P(x)┐(P(a1)P(a2)……………P(an))┐P(a1)┐P(a2)……………┐P(an)(x)┐P(x)12常用等价式2：量词的分配公式（1）1)∀对∧可分配：∀x(A(x)∧B(x))⇔∀xA(x)∧∀xB(x)设x的个体域为{a1，a2，…，an}∀x(A(x)∧B(x))⇔(A(a1)∧B(a1))

5、∧(A(a2)∧B(a2))∧…∧(A(an)∧B(an))⇔(A(a1)∧A(a2)∧…∧A(an))∧(B(a1)∧B(a2)∧…∧B(an))⇔∀xA(x)∧∀xB(x)13量词的分配公式∀x(A(x)∨B(x))⇔∀xA(x)∨∀xB(x)？举例：令x的个体域为正整数。A(x)：x是奇数B(x)：x是偶数∀x(A(x)∨B(x))所有正整数是奇数或者偶数。∀xA(x)∨∀xB(x)所有正整数都是奇数或者所有正整数都是偶数。14常用等价式2：量词的分配公式（2）2)∃对∨可分配：∃x(A(x)∨B(x))⇔∃xA(x)∨∃xB(x)设x的个体域为{a1，a2，…，an}∃x(A

6、(x)∨B(x))⇔(A(a1)∨B(a1))∨(A(a2)∨B(a2))∨…∨(A(an)∨B(an))⇔(A(a1)∨A(a2)∨…∨A(an))∨(B(a1)∨B(a2)∨…∨B(an))⇔∃xA(x)∨∃xB(x)15析取、合取与量词(x)(A(x)B(x))⇔(x)A(x)(x)B(x)？举例：令x的个体域为正整数。A(x)：x是奇数B(x)：x是偶数x(A(x)B(x))存在既是奇数又是偶数的正整数。xA(x)xB(x)存在为奇数的正整数且存在为偶数的正整数。16常用等价式2：析取、合取与量词量词与联结词∧，∨的关系总结：1)∀x(A(x)∧B(x))

7、⇔∀xA(x)∧∀xB(x)∀x(A(x)∨B(x))⇔∀xA(x)∨∀xB(x)2)∃x(A(x)∨B(x))⇔∃xA(x)∨∃xB(x)∃x(A(x)∧B(x))⇔∃xA(x)∧∃xB(x)17常用等价式3：量词辖域收缩与扩张设A(x)是任意一个含个体变量x的公式，B中不含x，(P:288)1.(∀x)A(x)∨B⇔(∀x)(A(x)∨B)(∀x)A(x)∧B⇔(∀x)(A(x)∧B)(补充)2.(∃x)A(x)∨B⇔(∃x)(