离散数学之等值演算

第二章作业 评分要求：1. 每小题6分: 结果正确1分; 方法格式正确3分; 计算过程2分. 合计48分2. 给出每小题得分(注意: 写出扣分理由)3. 总得分在采分点1处正确设置.一. 证明下面等值式(真值表法, 解逻辑方程法, 等值演算法, 三种方法每种方法至少使用一次):说明证1. p ⇔(p ∧q)∨(p ∧¬q)解逻辑方程法设 p ↔((p ∧q)∨(p ∧¬q)) =0, 分两种情况讨论:⎩⎨⎧=⌝∧∨∧=0)()(1)1(q p q p p 或者 ⎩⎨⎧=⌝∧∨∧=1)()(0)2(q p q p p (1)(2)两种情况均无解, 从而, p ↔(p ∧q)∨(p ∧¬q)无成假赋值, 为永真式.等值演算法(p ∧q)∨(p ∧¬q)⇔ p ∧(q ∨¬q)∧对∨的分配率⇔ p ∧1 排中律⇔ p 同一律真值表法用真值表法和解逻辑方程法证明相当于证明为永真式1. (¬p→q)→(¬q∨p)解(¬p→q)→(¬q∨p)⇔(p∨q)→(¬q∨p)蕴含等值式⇔(¬p∧¬q)∨(¬q∨p)蕴含等值式, 德摩根律⇔(¬p∧¬q)∨¬q ∨p结合律⇔p∨¬q吸收律, 交换律⇔M1因此, 该式的主析取范式为m0∨m2∨m32. (¬p→q)∧(q∧r)解逻辑方程法设(¬p→q)∧(q∧r) =1, 则¬p→q=1且q∧r=1,解得q=1, r=1, p=0 或者q=1, r=1, p=1, 从而所求主析取范式为m3∨m7, 主合取范式为M0∧M1∧M2∧M4∧M5∧M6等值演算法(¬p→q)∧(q∧r)⇔ (p∨q)∧(q∧r) 蕴含等值式⇔ (p∧q∧r)∨(q∧r) ∧对∨分配律, 幂等律⇔ (p∧q∧r) ∨ (p∧q∧r)∨(⌝p∧q∧r) 同一律, 矛盾律, ∧对∨分配律⇔m7∨ m3主合取范式为M0∧M1∧M2∧M4∧M5∧M63. (p↔q)→r解逻辑方程法设(p↔q)→r =0, 解得p=q=1, r=0 或者p=q=0, r=0, 从而所求主合取范式为M0∧M6, 主析取范式为m1∨m2∨m3∨m4∨m5∨m7等值演算法(p↔q)→r⇔ ((p→q)∧(q→p))→r 等价等值式⇔⌝((p→q)∧(q→p))∨r 蕴含等值式⇔ (p∧⌝q)∨(q∧⌝p)∨r 德摩根律, 蕴含等值式的否定(参见PPT)⇔ (p∨q∨r)∧(⌝q∨⌝p∨r) ∨对∧分配律, 矛盾律, 同一律⇔M0∧ M6主析取范式为m1∨m2∨m3∨m4∨m5∨m74. (p→q)∧(q→r)解等值演算法(p→q)∧(q→r)⇔ (⌝p∨q)∧(⌝q∨r) 蕴含等值式⇔ (⌝p∧⌝q)∨(⌝p∧r)∨(q∧r) ∧对∨分配律, 矛盾律, 同一律⇔ (⌝p∧⌝q∧r)∨(⌝p∧⌝q∧⌝r) ∨ (⌝p∧q∧r)∨(⌝p∧⌝q∧r) ∨ (p∧q∧r)∨(⌝p∧q∧r)⇔m1∨ m0∨ m3∨ m7主合取范式为M2∧ M4∧ M5∧ M6.解逻辑方程法设(p → q) ∧ (q → r) = 1, 则p → q =1 且q → r =1.前者解得: p=0, q=0; 或者p=0, q=1; 或者p=1, q=1.后者解得: q=0, r=0; 或者q=0, r=1; 或者q=1, r=1.综上可得成真赋值为000, 001, 011, 111, 从而主析取范式为m0∨ m1∨ m3∨ m7, 主合取范式为M2∧ M4∧ M5∧ M6.真值表法公式(p → q) ∧ (q从而主析取范式为m0∨ m1∨ m3∨ m7, 主合取范式为M2∧ M4∧ M5∧ M6.。

命题逻辑等值演算等值式定理：设A，B两个命题公式（即前面的合式公式），若A，B构成的等价式A↔B为重言式，则A与B是等值的，记作A⇔B(可以说该式子为等值式模式)常用的16组等值式模式：双重否定律：A⇔﹁﹁A幂定律：A⇔A∧A，A⇔A∨A交换律:A∨B⇔B∨A,A∧B⇔B∧A结合律：(A∨B)∨C⇔A(B∨C)(A∧B)∧C⇔A(B∧C)分配律:A∨(B∧C)⇔(A∨B)∧(A∨C)A∧(B∨C)⇔(A∧B)∨(A∧C)德摩根律：﹁(A∨B)⇔﹁A∧﹁B﹁(A∧B)⇔﹁A∨﹁B吸收律：A∨(A∧B)⇔A，A∧(A∨B)⇔A零律：A∨1⇔1,A∧0⇔0同一律:A∨0⇔A,A∧1⇔1排中律:A∨﹁A⇔1矛盾律:A∧﹁A⇔0蕴涵等值式: A→B⇔﹁A∨B等价等值式: A↔B⇔(A→B)∧(B→A)假言易位:A→B⇔﹁B→﹁A(这里可以用逆否命题的概念证明)等价否定等值式:A↔B⇔﹁A↔﹁B(或写成﹁B↔﹁A，这里可以用逆否命题的概念证明)归谬(miu)论：(A→B)∧(A→﹁B)⇔﹁A(此处可以通过蕴涵等值式，交换律以及结合律进行结合证明)上述等值式模式可以通过真值表证明等值式的验证1.等值演算法（即通过等值式模式对原式进行变形）举例:(p∨q)→r⇔(p→r)∧(q→r)证明时可以从左边开始演算也可以从右边开始演算，无硬性要求，这里我们从右边开始演算。

(p→r)∧(q→r)⇔(﹁p∨r)∧(﹁q∨r) //蕴涵等值式⇔(﹁p∧﹁q)∨r //分配律⇔﹁(p∨q)∨r //德摩根律⇔(p∨q)→r //蕴涵等值式2.真值表法（我在第一章的最后有叙述，这里不再重述）3.观察法（也可称为带入法，此处适合用以证明两式不等值的情况）关于等值演算法的补充：等值演算法可以用以证明公式的类型。

1.当最后结果为1时为重言式（永真式）2.当最后结果为0时为矛盾式（永假式）3.当最后结果只能化成某个命题变项或公式时为可满足式析取范式与合取范式简单析取式：p,﹁p,p∨q,﹁p∨q,p∨﹁q,,﹁p∨﹁q,﹁p∨﹁q∨r等（这里可以发现的是里面都只含有析取联结词，简单析取式结构就是由析取联结词和命题变项组成的一个公式）简单合取式：p,﹁p,p∧q,﹁p∧q,p∧﹁q,,﹁p∧﹁q,﹁p∧﹁q∧r等（这里可以发现的是里面都只含有合取联结词，简单合取式结构就是由合取联结词和命题变项组成的一个公式）课本中的定理：命题变项及其否定统称为文字。

离散数学课件-5-一阶逻辑等值演算与推理第五章一阶逻辑等值演算与推理§1 一阶逻辑等值式与置换规则定义：A，B两个谓词公式，若A?B是永真式，则称A与B是等值的，记为A?B。

常用等值式：第一组：命题逻辑中常用等值式的代换实例第二组：一阶逻辑中的特有等值式1．消去量词当D={a1, a2,…, a n}时，有①?xA(x)?A(a1)∧A(a2)∧…∧A(a n)②?xA(x)?A(a1)∨A(a2)∨…∨A(a n)2．量词否定①??xA(x)??x?A(x)②﹁?xA(x)??x?A(x)3．辖域收缩与扩张①?x(A(x)∨B)??xA(x)∨B②?x(A(x)∧B)??xA(x)∧B③?x(A(x)∨B)??xA(x)∨B④?x(A(x)∧B)??xA(x)∧B4．量词分配①?x(A(x)∧B(x))??xA(x)∧?xB(x)②?x(A(x)∨B(x))??xA(x)∨?xB(x)演算规则：1．置换规则：φ(A)：含A的谓词公式φ(B)：用公式B替换φ(A)中所有A之后的公式若A?B，则φ(A)?φ(B)。

2．换名规则：设A是谓词公式，把A中某指导变元对应的全部约束出现替换为A中未出现过的符号，而A中其余部分不变，设所得谓词公式为A′，则A?A′。

3．代替规则设A是谓词公式，把A中某个体变项的全部自由出现替换为A中未出现过的符号，而A中其余部分不变，设所得公式为A′，则A?A′。

例①?xF(x,y,z)→?yG(x,y,z)sF(s,y,z)→?tG(x,t,z) 换名②?x(F(x,y)→?yG(x,y,z))x(F(x,t)→?yG(s,y,z)) 代替例给定解释I：D I ={2,3}，a：2，b：3G(x,y)：G(a, a)=G(a, b)=G(b, a)=1，G(b, b)=0F(x)：F(a)=0，F(b)=1① ?x(F(x)∧G(x,a))(F(a)∧G(a,a))∧(F(b)∧G(b,a))?(0∧1)∧(1∧1)? 0② ?x?yG(x,y)x(G(x,a)∧G(x,b))(G(a,a)∧G(a,b))∨(G(b,a)∧G(b,b))(1∧1)∨(1∧0)1例证明：﹁?x(F(x)→G(x))??x(F(x)∧﹁G(x)) 解：﹁?x(F(x)→G(x))﹁?x(﹁F(x)∨G(x))x﹁(﹁F(x)∨(G(x)x(F(x)∧﹁G(x))§2 前束范式定义：设A是谓词公式，若A有如下形式Q1x1Q2x2…Q k x k B其中Q i(1≤i≤k)为?或?，B为不含量词的公式，则称A为前束范式。

5.1 一阶逻辑等值式与置换规则定义5.1设A，B是一阶逻辑中任意两个公式，若A B是永真式，则称A与B 是等值的。

记做A B，称A B是等值式。

谓词逻辑中关于联结词的等值式与命题逻辑中相关等值式类似。

下面主要讨论关于量词的等值式。

一、基本等值式第一组代换实例由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式，因而第二章的16组等值式给出的代换实例都是一阶逻辑的等值式的模式。

例如：xF(x)┐┐xF(x)x y(F(x,y)→G(x,y))┐┐x y(F(x,y)→G(x,y))等都是(2.1)式的代换实例。

又如：F(x)→G(y)┐F(x)∨G(y)x(F(x)→G(y))→zH(z)┐x(F(x)→G(y))∨zH(z))等都是(2.1)式的代换实例。

第二组消去量词等值式设个体域为有限域D={a1,a2,…,a n}，则有(1)xA(x)A(a1)∧A(a2)∧…∧A(a n)(2)xA(x)A(a1)∨A(a2)∨…∨A(a n) (5.1)第三组量词否定等值式设A(x)是任意的含有自由出现个体变项x的公式，则(1)┐xA(x)x┐A(x)(2)┐xA(x)x┐A(x)(5.2)(5.2)式的直观解释是容易的。

对于(1)式，“并不是所有的x都有性质A”与“存在x没有性质A”是一回事。

对于(2)式，“不存在有性质A的x”与“所有x都没有性质A”是一回事。

第四组量词辖域收缩与扩张等值式设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则(1)x(A(x)∨B)xA(x)∨Bx(A(x)∧B)xA(x)∧Bx(A(x)→B)xA(x)→Bx(B→A(x))B→xA(x) (5.3)(2)x(A(x)∨B)xA(x)∨Bx(A(x)∧B)xA(x)∧Bx(A(x)→B)xA(x)→Bx(B→A(x))B→xA(x) (5.4)注意：这些等值式的条件。

第五组量词分配等值式设A(x)，B(x)是任意的含自由出现个体变项x的公式，则(1)x(A(x)∧B(x)）xA(x)∧xB(x)(2)x(A(x)∨B(x)）xA(x)∨xB(x) (5.5)二、基本规则1．置换规则设Φ(A)是含公式A的公式，Φ(B)是用公式B取代Φ(A)中所有的A之后的公式，若A B，则Φ(A)Φ(B).一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同，只是在这里A，B 是一阶逻辑公式。