工科离散数学课件 第二章 2_4_谓词公式的等价和蕴含(1) - 基本等价与蕴含关系(1) - 上.pptx

2.4 谓词公式的等价和蕴含众所周知，“没有不犯错误的人”与“所有人都犯错误”是等同的说法。这体现了基本的谓词公式的等价关系。建立这些关系是实现推理的基础。 2.4.1 基本等价与蕴含关系2.4 谓词公式的等价和蕴含-基本等价与蕴含关系1. 等价与蕴含[谓词公式等价]若两个谓词公式A和B有相同的论域，且在任何解释下A与B有相同的真值，则称谓词公式A与B等价，记作A?B 或A ≡B。示例： ?x (P(x)∨Q(x)) ? ?x (┐P(x)→Q(x)) ?x P(x) ? ?x P(x)[谓词公式蕴含]若两个谓词公式A和B有相同的论域，且在任何解释下A→B为1，则称谓词公式A蕴含B，记作A?B。 2.4 谓词公式的等价和蕴含-基本等价与蕴含关系2. 命题逻辑的推广——对命题公式的代换推导是得到谓词公式等价与蕴含关系的重要方法。示例：命题公式P→Q的代换实例：A(x)→B、 ?xA(x)→B(x)、 ?xA(x)→ ?x B(x) 、 ? xA(x)→ ?x B(x, y)[代换实例] 用谓词公式Q1, Q2, …, Qn代替命题公式A(P1, P2, …, Pn)中的原子 ，得到的公式为B，称B是A的“代换实例”。 2.4 谓词公式的等价和蕴含-基本等价与蕴含关系长见识：若命题公式A和B等价，则A和B的代换实例也等价。示例：因为P→Q ? ┐P∨Q ，所以，二者的代换实例等价：A(x)→B ? ┐A(x)∨B ?xA(x)→B(x) ? ┐?xA(x)∨B(x) ?xA(x)→ ?x B(x) ? ┐?xA(x)∨?x B(x) ? xA(x)→ ?x B(x, y) ? ┐? xA(x)∨?x B(x, y)Try it：命题逻辑的重言式的代换实例是谓词逻辑的重言式。 2.4 谓词公式的等价和蕴含-基本等价与蕴含关系3. 量词的转换[量词否定定律]全称量词和存在量词可利用┐联结词进行转换：┐?x A(x) ? ?x ┐A (x)┐?x A(x) ? ?x ┐A (x)量词否定定律=量词的德?摩根律。答：?x(x 0)。否定所有数都是正的 = 至少有一个数是负的。量词否定定律与论域无关。问：对任意论域?，如?= {1, -1, 0}。否定命题?x(x 0)会得到什么？答： ?x(x 0)。否定存在正数 = 所有数都是负的。问：对任意论域?，如? = {1, -1, 0}。否定命题 ?x(x 0)会得到什么？ 2.4 谓词公式的等价和蕴含-基本等价与蕴含关系Try it：量词否定定律在有限论域上的证明。设论域 ? = {a1, a2, ?, an}，有： ┐?x A(x) ? ┐(A(a1) ?A(a2) ? ? ?A(an)) ? (对偶原理)┐A(a1) ? ┐A(a2) ? ? ?┐A(an) ? ?x ┐A(x) ┐?x A(x) ? ┐(A(a1) ?A(a2) ? ? ?A(an)) ? (对偶原理) ┐A(a1) ?┐A(a2) ? ? ?┐A(an) ??x ┐A (x) 2.4 谓词公式的等价和蕴含-基本等价与蕴含关系解：若记M(x)：x是人，E(x)：x犯错误，符号化为：没有不犯错误的人： ┐?x(M(x) ?┐E(x)) 所有人都犯错误： ?x(M(x)→E(x))例2-23：符号推证：命题“没有不犯错误的人”等同于“所有人都犯错误”。有： ┐? x(M(x) ? ┐E(x)) ? ?x ┐(M(x) ?┐E(x)) ? ?x(┐M(x) ?E(x)) ? ?x(M(x)→E(x))