离散数学2.5-6

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

1、2－5谓词演算的等价式与蕴含式谓词公式的解释/赋值在谓词逻辑中存在个体常量、个体变元以及函数，故不能像命题公式那样直接通过真值指派给出解释，而是必须考虑个体变量和函数在个体域中的取值，然后针对变量和函数的具体取值为谓词分别指派真值。定义：设D为谓词公式P的个体域，若对P中的个体常量、函数和谓词按照如下的规定赋值：1)为每个个体常量指派D中的一个特定元素；2)为每个n元函数指派一个从Dn到D的映射；3)为每个n元谓词指派一个从Dn到{F,T}的映射。称这些指派为公式P在D上的一个解释。离散数学变元的约束由于该公式中包含有

2、个体常量b，函数f(x)和两个谓词P和Q，所以首先为个体常量及函数指派值：b指定为：1；f(1)=2,f(2)=1对谓词指派的真值为：P(1)=F,P(2)=TQ(1,1)=T,Q(2,1)=F这里由于已指派b＝1，所以Q(2,2)与Q(1,2)不可能出现，故没有给它们指派真值。设个体域为D＝{1，2}，求公式A=(x)(P(x)→Q(f(x),b))在D上的某一个解释，并指出在此解释下公式A的真值。离散数学2－5谓词演算的等价式与蕴含式定义：给定任何两个谓词公式wffA和wffB，设它们有共同的个体域E，若对A和

3、B的任一组变元进行赋值，所得命题的真值相同，则称谓词公式A和B在E上是等价的，并记做AB。离散数学谓词演算的等价式与蕴含式定义：给定任意谓词公式wffA，其个体域为E，对于A的所有赋值，wffA都为真，则称wffA在E上是有效的（或永真的）。定义：给定任意谓词公式wffA，其个体域为E，对于A的所有赋值，wffA都为假，则称wffA在E上是不可满足的（或永假的）。定义：给定任意谓词公式wffA，其个体域为E，对于A的所有赋值中至少有一种赋值为真，则称wffA在E上是可满足的。离散数学谓词演算的等价式与蕴含式谓词演算的

4、等价式1.命题公式的推广将命题演算中的等价公式表和蕴含式表推广到谓词演算中使用。例：(x)(P(x)→Q(x))(x)(┐P(x)∨Q(x))(x)P(x)∨(y)R(x,y)┐(┐(x)P(x)∧┐(y)R(x,y))(x)H(x,y)∧┐(x)H(x,y)F(x)P(x)→Q(x)离散数学谓词演算的等价式与蕴含式2.量词与联结词┐之间的关系例P(x)表示x来上课个体域为学生1)不是所有学生今天来上课。┐(x)P(x)2)存在一些学生今天没有来上课。(x)┐P(x)3)不存在一些学生今天来

5、上课。┐(x)P(x)4)所有的学生今天都没有来上课。(x)┐P(x)离散数学谓词演算的等价式与蕴含式得到了公式：┐(x)P(x)(x)┐P(x)(x)┐P(x)┐(x)P(x)证明在有限个体域D={a1,a2,…,an}上证明上述的结论(1).(x)A(x)A(a1)A(a2)…A(an)(2).(x)A(x)A(a1)A(a2)…A(an)离散数学规则：将量词前面的┐移到量词的后面去时，存在量词改为全称量词，全称量词改为存在量词，反之，若将量词后面的否定┐移到量词的前面去时，也要

6、作相应的改变，这种量词与┐的关系是普遍成立的。谓词演算的等价式与蕴含式离散数学谓词演算的等价式与蕴含式3.量词作用域的扩张与收缩(1)(x)(A(x)∨B)(x)A(x)∨B(x)(A(x)∧B)(x)A(x)∧B(x)(A(x)∨B)(x)A(x)∨B(x)(A(x)∧B)(x)A(x)∧B离散数学谓词演算的等价式与蕴含式3.量词作用域的扩张与收缩(2)(x)A(x)→B(x)(A(x)→B)(x)A(x)→B(x)(A(x)→B)(x)(B→A(x))B→(x)A(x)(

7、x)(B→A(x))B→(x)A(x)注当谓词的变元与量词的指导变元不同时，也能有类似于上述的公式。例(x)(P(x)∨Q(y))((x)P(x)∨Q(y))离散数学谓词演算的等价式与蕴含式4.量词与命题联结词之间的一些等价式(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)(x)(A(x)∨B(x))(x)A(x)∨(x)B(x)(x)(A(x)→B(x))离散数学谓词演算的等价式与蕴含式5.量词与命题联结词之间的一些蕴含式(x)A(x)∨(x)B(x)(x)(A(x)∨B

8、(x))(x)(┐A(x))∨(x)(┐B(x))(x)(┐A(x)∨┐B(x))┐((x)A(x)∧(x)B(x))┐(x)(A(x)∧B(x))(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)离散数学谓词演算的等价式与蕴含式类似的有：(x)(A(x)→B(x))(x)A(x)→(x)B(