东南大学：《离散数学》课程教学资源（PPT课件讲稿）第五章 等值演算与推理

9第五章:等值演算与推理 豪 第一节:等值式与置换规则 第二节:前束范式 第三节:推理理论

1 第五章: 等值演算与推理 第一节：等值式与置换规则 第二节：前束范式 第三节：推理理论

9第五章:等值演算与推理 豪 口主要内容 阶逻辑等值式与基本的等值式 ●置换规则、换名规则、代替规则 ●前束范式 ●自然推理系统Nz及其推理规则 2

2 第五章: 等值演算与推理 ❑主要内容 ⚫ 一阶逻辑等值式与基本的等值式 ⚫ 置换规则、换名规则、代替规则 ⚫ 前束范式 ⚫ 自然推理系统NL 及其推理规则

9第五章:等值演算与推理 豪 第一节:等值式与置换规则 心第二节:前束范式 第三节:推理理论

3 第五章: 等值演算与推理 第一节：等值式与置换规则 第二节：前束范式 第三节：推理理论

951等值式与置换规则 豪 口等值式:公式A,B的等价式A4B为永 真式 ◆符号:A◇B,也称A逻辑恒等于B 等价定义:对任意解释 12A当且仅当|2B

4 ❑等值式：公式A，B的等价式A↔B为永 真式 ❖符号：AB，也称A逻辑恒等于B ❖等价定义：对任意解释I I ²A 当且仅当 I ²B 5.1 等值式与置换规则

951等值式与置换规则 豪 口第一类等值式:命题逻辑的重言式的代 换实例 理由:重言式的代换实例都是永真式 口例 令VXF(X)分--VXF(x) TA今A 令F(x)→G(x)台-F(x)VG(x) A→BAVB 5

5 ❑第一类等值式：命题逻辑的重言式的代 换实例 ❖理由：重言式的代换实例都是永真式 ❑例 ❖x F(x)    x F(x) ❖F(x) → G(x)   F(x)  G(x) ¬¬AA A→ B  ¬ A  B 5.1 等值式与置换规则

951等值式与置换规则 豪 口第二类等值式: 1.消去量词等值式 给定有限个体域D={a1,a2,an} VX A(X+Aa1) A(a2A.A A(an XA(x)分A(a1)vA(a)v…vA(an) 2.量词否定等值式 x在公式A(x)中自由出现 VXA(X)冷3xA(x) 彐XA(x)分Vx-A(x) 6

6 ❑ 第二类等值式： 1. 消去量词等值式 给定有限个体域 D={a1,a2,…,an} 2. 量词否定等值式 x在公式A(x)中自由出现 x A(x)  A(a1)  A(a2) …  A(an) x A(x)  A(a1)  A(a2)  …  A(an) x A(x)  x  A(x) x A(x)  x  A(x) 5.1 等值式与置换规则

951等值式与置换规则 豪 口例:设个体域为D=,b,C},将下面公式 的量词消去 1, VX F( v 3y G 台(F(a)∧F(b)∧F(c)v(G(a)vG(b)G(c) 2.( VX F(Xv Go) 丑X→F(x)∧y-G(y) 台(-F(a)y-F(b)=F(c)∧ (-G(a)∧-G(b)∧-G(c) 7

7 ❑ 例：设个体域为D＝{a, b, c}，将下面公式 的量词消去 1. x F(x)  y G(y) 2. (x F(x)  y G(y))  (F(a)  F(b)  F(c))  (G(a)  G(b)  G(c))  x  F(x)  y  G(y)  ( F(a)   F(b)   F(c))  ( G(a)   G(b)  G(c)) 5.1 等值式与置换规则

951等值式与置换规则 豪 口第二类等值式: 3.量词辖域收缩与扩张等值式 x在公式A(x)中自由出现,但不在B中自由出现 (aVX (A(XvBeVX A(X)v B 1b)X(A(x)AB)分VXA(x)∧B (1c)X(A(x)→B)分丑XA(x)→B (1dxX(B→A(x)冷B→VXA(X (2a 3X((x)vB)+ 3x A(x)v B (2b)彐X(A(x)∧B)兮彐XA(x)∧B (2c 3X(A(x)>B)B VXA(x)->B (2d(B→A(x)分B→彐XA(x) 8

8 ❑ 第二类等值式： 3. 量词辖域收缩与扩张等值式 x在公式A(x)中自由出现，但不在B中自由出现 (1a) x (A(x)  B)  x A(x)  B (1b) x (A(x)  B)  x A(x)  B (1c) x (A(x) → B)  x A(x) → B (1d) x (B → A(x))  B → x A(x) (2a) x (A(x)  B)  x A(x)  B (2b) x (A(x)  B)  x A(x)  B (2c) x (A(x) → B)  x A(x) → B (2d) x (B → A(x))  B → x A(x) 5.1 等值式与置换规则

951等值式与置换规则 豪 口第二类等值式: 4.量词分配等值式 x在公式A(X)和B(x)中自由出现 (1)Vx(A(x)∧B(X)分XA(x)∧XB(X) (2 3x (A(X)VB(X)+3X AXv3XB(X (3)3x(A(X)→B(X)分VXA(xX)→XB(X)

9 ❑ 第二类等值式： 4. 量词分配等值式 x在公式A(x)和B(x)中自由出现 (2) x (A(x)  B(x))   x A(x)  x B(x) (1) x (A(x)  B(x))  x A(x)  x B(x) (3) x (A(x) → B(x))  x A(x) →x B(x) 5.1 等值式与置换规则

951等值式与置换规则 豪 A下列等值式不成立! x在公式A(x)和B(x)中自由出现 (1)VX (A(X)vB()) VX()v VX B(x) 提示:任意实数或者是有理数或者是无理数 或者任意实数是有理数或者任意实数是无理数 (2)丑X(A(X)∧B(x)冷丑A(x)∧丑XB(x) 提示:存在实数既是有理数又是无理数 存在实数是有理数或者存在实数是无理数 10

10 下列等值式不成立！ x在公式A(x)和B(x)中自由出现 (2) x (A(x)  B(x))  x A(x)  x B(x) (1) x (A(x)  B(x))  x A(x)  x B(x) 提示：任意实数或者是有理数或者是无理数 或者任意实数是有理数或者任意实数是无理数 提示：存在实数既是有理数又是无理数 存在实数是有理数或者存在实数是无理数 5.1 等值式与置换规则