西安电子科技大学：《离散数学》课程教学课件（题解）第二章 谓词逻辑 2-4 谓词演算的永真公式

西安电子科技大学离散数学软件学院第一篇数理逻辑第2章谓词逻辑E第7课时1.1 谓词和量词→第8课时1.2谓词公式之第9课时1.3谓词公式的翻译V第10课时1.4谓词演算的永真公式第11课时入1.5谓词演算的四个推理规则第12课时之1.6谓词逻辑推理及应用

西安电子科技大学 离散数学 软件学院 第一篇 数理逻辑 第7课时 1.1 谓词和量词 第2章 谓词逻辑 1.4 谓词演算的永真公式 1.2 谓词公式 1.5 谓词演算的四个推理规则 第8课时 第10课时 第11课时 第9课时 1.3 谓词公式的翻译 第12课时 1.6 谓词逻辑推理及应用

西安电子科技大学$2.4.1谓词等价公式软件学院谓词公式间的等价关系与变元的个体域相关给定任意两个谓词公式A和B，设其中的变元谓词公式A和B在E上等价有相同的个体域E，若A和B的任一赋值，它包括以下两方面：（1）对公式A和B中的相同谓词符号，指派同一个在个体域E上有确定含义的谓词（2）对公式A和B中的相同的个体变元指派论域E中同一确定的个体。若A和B的真值均相同，则称谓词公式A和B在个体域E上等价

西安电子科技大学 §2.4.1 谓词等价公式 软件学院 谓词公式A和B 在E上等价 谓词公式间的等价关系与变元的个体域相关 给定任意两个谓词公式A和B，设其中的变元 有相同的个体域E，若A和B的任一赋值，它 包括以下两方面： （1）对公式A和B中的相同谓词符号，指派 同一个在个体域E上有确定含义的谓词； （2）对公式A和B中的相同的个体变元指派 论域E中同一确定的个体。 若A和B的真值均相同，则称谓词公式A和B 在个体域E上等价

西安电子科技大学谓词等价公式$2.4.1软件学院家两个谓词公式A和B，如果A和B在任意的个谓词公式A和B体域上均等价，则称谓词公式A和B等价。等价例如：(Vx)(P(x)→Q(x)(Vx)(-P(x) V Q(x))个-(Vx)(P(x)→Q(x)(日x)(P(x) ^- Q(x)

西安电子科技大学 §2.4.1 谓词等价公式 软件学院 谓词公式A和B 等价 两个谓词公式A和B，如果A和B在任意的个 体域上均等价，则称谓词公式A和B等价。 例如： (∀x)(P(x)→Q(x)) ⇔ (∀x)(¬P(x) ∨ Q(x)) ¬(∀x)(P(x)→Q(x)) ⇔ (∃x)(P(x)∧¬ Q(x))

西安电子科技大学谓词等价式$2.4.1软件学院如果在任意的个体域上，在谓词公式A的任谓词永真式一赋值下，A的真值均为T，则称谓词公式A是永真式或有效式。如果在任意的个体域上，在谓词公式A的任谓词永假式一赋值下，A的真值均为F，则称谓词公式A是永假式或不可满足式

西安电子科技大学 §2.4.1 谓词等价式 软件学院 谓词永真式 如果在任意的个体域上，在谓词公式A 的任 一赋值下，A的真值均为T，则称谓词公式A 是永真式或有效式。 如果在任意的个体域上，在谓词公式A 的任 一赋值下，A的真值均为F，则称谓词公式A 是永假式或不可满足式。 谓词永假式

西安电子科技大学S2.4.2含量词的基本永真式软件学院命题等价式的推广使用命题演算中的等价式可以推广到谓词演算中使用。例如：命题等价式谓词等价式P-≤-PVQ(Vx)(P(×)-→Q(×)(Vx)(-P(×) V Q(×))(PV)≤-P-g-(Vx)R(×) VQ(y)台-(Vx)R(×) △-Q(y)-PVPET(日x)R(×) V (日x)R()台T

西安电子科技大学 §2.4.2 含量词的基本永真式 软件学院 一、命题等价式的推广使用 命题演算中的等价式可以推广到谓词演算中使用。 例如： ( ∀x)(P(x)→Q(x)) ⇔ ( ∀x)(¬P(x)∨Q(x)) ¬(( ∀x)R(x)∨Q(y)) ⇔¬( ∀x)R(x)∧¬Q(y) ¬( ∃x)R(x)∨( ∃x)R(x) ⇔ T → ⇔ ∨¬ QPQP ∨¬ )( ⇔ ∧¬ ¬QPQP ⇔∨¬ TPP 命题等价式 谓词等价式

西安电子科技大学S2.4.2含量词的基本永真式软件学院命题等价式的推广使用但要注意使用的形式：例如：(Vx)-P(x) VQ(x)(Vx)P(x)-Q(x)-(Vx)R(x) V Q(y)(Vx)-R(x) ^△-Q(y)T(Vx)R(x) V-R(x)

西安电子科技大学 §2.4.2 含量词的基本永真式 软件学院 一、命题等价式的推广使用 但要注意使用的形式： ( ∀x)P(x) →Q(x) ⇔ ( ∀x)¬P(x) ∨Q(x) / ( ∀x)R(x) ∨¬R(x) ⇔/ T ¬( ( ∀x)R(x) ∨ Q(y)) ⇔/ ( ∀x)¬R(x) ∧¬Q(y) 例如：

西安电子科技大学S2.4.2含量词的基本永真式软件学院二、量词的否定(1)(Vx)A(x)(3x)A(x)(2)7(x)A(x)(Vx)-A(x)证明（1）：(i)设I是谓词公式-(Vx)A(×)的任一赋值，如果I使得-(Vx)A()为真，则I使得(Vx)A(α)为假，即至少存在aED，使得A(a)为假，从而-A(a)为真，故(日x)-A(×)为真。(ii)如果I使得-(Vx)A(x)为假，则I使得(Vx)A(α)为真，即对于所有的个体aED，均有A(a)为真，从而-A(a)为假，故(日x)-A(×)为假。综上所述，有-(Vx)A(x)(日x)-A()成立

西安电子科技大学 §2.4.2 含量词的基本永真式 软件学院 二、量词的否定 ¬ ( ∀x)A(x) ⇔ ( ∃x) ¬A(x) ¬ ( ∃x)A(x) ⇔ ( ∀x) ¬A(x) （ 1 ） （ 2 ） (ii)如果I使得¬( ∀x)A(x)为假，则I使得( ∀x)A(x)为真，即对 于所有的个体a∈D，均有A(a)为真，从而¬A(a)为假，故 (∃x)¬A(x)为假。 (i)设I是谓词公式¬( ∀x)A(x)的任一赋值，如果I使得¬( ∀x)A(x) 为真，则I使得( ∀x)A(x)为假，即至少存在a∈D，使得A(a)为 假，从而¬A(a)为真，故( ∃x)¬A(x)为真。 综上所述，有¬( ∀x)A(x) ⇔(∃x)¬A(x)成立。 证明 （ 1 ） ：

西安电子科技大学S2.4.2含量词的基本永真式软件学院【例题】已以下（1）式成立，证明（2）式也成立。(1)-(Vx)A(x)(x)A(x)(2)-(x)A(x)(Vx)-A(X)证明：将式（1）中的A()用-A(×)代入，则有：-(Vx)-A(×)(x)--A(×)即:-(Vx) - A(x)(x)A(x)可得：(Vx) A(x)-(x)A(x)

西安电子科技大学 §2.4.2 含量词的基本永真式 软件学院 ¬ ( ∀x)A(x) ⇔ ( ∃x) ¬A(x) ¬ ( ∃x)A(x) ⇔ ( ∀x) ¬A(x) （ 1 ） （ 2 ） 【例题】已以下（1）式成立，证明（2）式也成立。 将式（1）中的A(x)用¬A(x)代入，则有： 证明： ¬( ∀x)¬A(x) ⇔ ( ∃x)¬¬A(x) ¬ ( ∀x) ¬ A(x) ⇔ ( ∃x)A(x) ( ∀x) ¬A(x) ⇔ ¬ ( ∃x)A(x) 即： 可得：

西安电子科技大学S2.4.2含量词的基本永真式软件学院家家三、量词的分配式(Vx)A(x) Λ (Vx)B(x)(1)(Vx)(A(x) ^B(x))例如：“中秋节晚会上，每个同学都吃了月饼且跳了舞”“中秋节晚会上，每个同学都吃了月饼且每个同学都跳了舞”这两个命题是等价的。全称量词√对入可分配

西安电子科技大学 §2.4.2 含量词的基本永真式 软件学院 三、量词的分配式 （ 1 ） ( ∀x)(A(x)∧B(x)) ⇔ ( ∀x)A(x)∧( ∀x)B(x) 全称量词 ∀ 对 ∧可分配 。 例如：“中秋节晚会上, 每个同学都吃了月饼且跳了舞” “中秋节晚会上, 每个同学都吃了月饼且每个同学都跳了舞” 这两个命题是等价的

西安电子科技大学S2.4.2含量词的基本永真式软件学院家三、量词的分配式(2）(日x)(A(×) V B(x)(日x)A(x) V (日x)B(x例如：“中秋节晚会上，有些同学吃了月饼或跳了舞”“中秋节晚会上，有些同学吃了月饼或有些同学跳了舞”这两个命题是等价的。存在量词日对V可分配

西安电子科技大学 §2.4.2 含量词的基本永真式 软件学院 三、量词的分配式 （ 2 ） ( ∃x)(A(x)∨B(x)) ⇔ ( ∃x)A(x)∨( ∃x)B(x) 存在量词 ∃ 对 ∨可分配 。 例如：“中秋节晚会上, 有些同学吃了月饼或跳了舞” “中秋节晚会上, 有些同学吃了月饼或有些同学跳了舞” 这两个命题是等价的