离散数学 一阶逻辑等值演算

《离散数学 一阶逻辑等值演算》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1主要内容一阶逻辑等值式与基本的等值式置换规则、换名规则、代替规则前束范式自然推理系统NL及其推理规则第五章一阶逻辑等值演算与推理25.1一阶逻辑等值式与置换规则定义5.1设A,B是两个谓词公式,如果AB是永真式,则称A与B等值,记作AB,并称AB是等值式利用永真式判断，与命题公式的等值相同：真值表、演算基本等值式:1.第一组命题逻辑中16组基本等值式的代换实例例如，xF(x)xF(x),xF(x)yG(y)xF(x)yG(y)等基本等值式第二组2.消去量词等值式（个体域为有穷集合）设D

2、={a1,a2,…,an}由前述的量词的定义及所表示的逻辑意义能够得出①xA(x)A(a1)A(a2)…A(an)逻辑意义：对任何x具有性质A，相当于对每一个x都具有性质A②xA(x)A(a1)A(a2)…A(an)逻辑意义：对一些x具有性质A，只要存在有x具有性质A即可（析取的意义）3例：设个体域D={a,b,c}消去下列公式中的量词1、∀x（F(x)→G(x))2、∀xF(x)∨∃xG(x)3、∃x∀yF(x,y)45例给定解释I如下：(a)个体域D＝{2，3}(b)D中特定元素a=2。(c)D

3、上特定函数f(x)为：f(2)=3，f(3)＝2．(d)D上的特定谓词G(x，y)为：G(2，2)＝G(2，3)＝G(3，2)=1，G(3，3)＝0．L(x，y)为：L(2，2)＝L(3，3)＝1，L(2，3)=L(3，2)=0．F(x)为：F(2)＝0，F(3)＝1．在I下求下列各式的真值．(1)∀x(F(x)∧G(x，a))(2)∃x(F(f(x))∧G(x，f(x)))(3)∀x∃yL(x，y)∃y∀xL(x，y)上面两例说明量词的次序不能随意颠倒（交换量词的次序，其真值可能改变）63.量词否定等值式设A(x)是

4、任意的含自由出现个体变项x的公式，则(1)┑∀xA(x)⇔∃x┑A(x)(2)┑∃xA(x)⇔∀x┑A(x)(1)式直观解释是：“并不是所有的x都有性质A”与“存在x没有性质A”是一回事(逻辑意义相同)(2)式，“不存在有性质A的x”“所有x都没有性质A”是一回事(逻辑意义相同)该式可理解为是德摩根律在无限项下的推广如：在自然数集中“任何自然数均为偶数是不对的”┑∀xA(x)与“有不是偶数的自然数”∃x┑A(x)逻辑意义是相同的74.量词辖域收缩与扩张等值式A(x)是含x自由出现的公式，B中不含x的自由出现(1)关于全

5、称量词的：∀x(A(x)∨B)⇔∀xA(x)∨B∀x(A(x)∧B)⇔∀xA(x)∧B∀x(A(x)→B)⇔∃xA(x)→B∀x(B→A(x))⇔B→∀xA(x)(2)关于存在量词的：∃x(A(x)∨B)⇔∃xA(x)∨B∃x(A(x)∧B)⇔∃xA(x)∧B∃x(A(x)→B)⇔∀xA(x)→B∃x(B→A(x))⇔B→∃xA(x)注：其中的B中不含变元x，可以是B（y）形式的量词的辖域可以扩充（或收缩）到与个体变项无关的部分量词的辖域不可以扩充（或收缩）到相同的自由个体变项的部分5．量词分配等值式设A(x)，B(x

6、)是任意的含自由出现个体变项x的公式，则(1)∀x(A(x)∧B(x))⇔∀xA(x)∧∀xB(x)全称量词对合取可分配(2)∃x(A(x)∨B(x))⇔∃xA(x)∨∃xB(x)存在量词对析取可分配注：这两个等值式很重要，因为全称量词对析取（对）不可分配，存在量词对合取（对）不可分配例：设：A(x):x是奇数B(x):x是偶数个体域D为整数那么∀x(A(x)∨B(x))是为真的但∀xA(x)∨∀xB(x)是为假的它们是不等值的另外∃x(A(x)∧B(x))是为假的，而∃xA(x)∧∃xB(x)是为真的，所以它

7、们也不等值。注：前面提出：多个量词出现时，它们的顺序不能随意调换但有∀x∀yA(x，y)⇔∀y∀xA(x，y)∃x∃yA(x，y)⇔∃y∃xA(x，y)二、等值演算规则1、置换规则（等值代换）设Φ(A)是含公式A的公式，若A⇔B，则Φ(A)⇔Φ(B)．一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同，只是在这里A，B是一阶逻辑公式．对于公式中出现有双重身份的变元（即自由又约束)的处理：2、换名规则（约束变元的换名）－目的是使每个变元性质唯一设A为一公式，将A中某量词辖域中某约束变项的所有出现及相应的指导变元，改

8、成该量词辖域中未曾出现过的某个体变项符号，公式中其余部分不变，设所得公式为A’，则A’⇔A例：∀xA(x)∨B(x)由于公式中的x即是自由的又是约束的，可利用此规则进行换名为：∀tA(t)∨B(x)⇔∀xA(x)∨B(x)后可利用量词的扩充得到：∀tA(t)∨B(x)⇔∀t(A(t)∨B(x))例：∀xF(x，y，z)→∃yG(x