离散数学命题逻辑等值演算

离散数学课件-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为前束范式。

离散数学-第二章命题逻辑等值演算习题及答案本页仅作为文档封面，使用时可以删除This document is for reference only-rar21year.March第二章作业评分要求：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 同一律真值表法2. (p→q)∧(p→r)⇔p→(q∧r)等值演算法(p→q)∧(p→r)⇔ (¬p∨q)∧(¬p∨r)蕴含等值式⇔ ¬p∨(q∧r)析取对合取的分配律⇔ p→(q∧r)蕴含等值式3. ¬(p↔q)⇔(p∨q)∧¬(p∧q)等值演算法¬(p↔q)⇔ ¬( (p→q)∧(q→p) )等价等值式⇔ ¬( (¬p∨q)∧(¬q∨p) )蕴含等值式⇔ ¬( (¬p∧¬q)∨(p∧q) )合取对析取分配律, 矛盾律, 同一律⇔ (p∨q)∧¬(p∧q)德摩根律4. (p∧¬q)∨(¬p∧q)⇔(p∨q)∧¬(p∧q)等值演算法(p∧¬q)∨(¬p∧q)⇔ (p∨q)∧¬(p∧q)析取对合取分配律, 排中律, 同一律说明: 用真值表法和解逻辑方程法证明相当于证明为永真式.等值演算法证明时每一步后面最好注明理由以加深印象, 熟练后可以不写. 由于等值演算法证明具有较强的技巧性, 平时应注意总结心得.二. 求下列公式的主析取范式与主合取范式(等值演算法与用成真赋值或成假赋值求解都至少使用一次):1.2.3.4.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)p q r(p q) (q r)00010011010001111000101011001111013724 M5 M6.。