《离散数学 》课件第2章 谓词逻辑.ppt

***********************************************************证明(采用反证法，CP规则的方法由学生完成)：1)?((?x)P(x)∨(?x)Q(x)) P(附加前提)2)?(?x)P(x)∧?(?x)Q(x) T,1),E3)?(?x)P(x) T,2),I4)?(?x)Q(x) T,2),I5)(?x)?P(x) T,3),E6)?P(c) ES,5)证明(?x)(P(x)∨Q(x))?(?x)P(x)∨(?x)Q(x)7)(?x)?Q(x) T,4),E8)?Q(c) US,7)9)?P(c)∧?Q(c) T,6),8),I10)?(P(c)∨Q(c)) T,9),E11)(?x)(P(x)∨Q(x)) P12)(P(c)∨Q(c)) US,11)13)?(P(c)∨Q(c))∧(P(c)∨Q(c))T,10),12)谓词逻辑推理的难点（1）在推导过程中，如既要使用规则US又要使用规则ES消去公式中的量词，而且选用的个体是同一个符号，则必须先先使用规则ES，再使用规则US。然后再使用命题演算中的推理规则，最后使用规则UG或规则EG引入量词，得到所要的结论。（2）如一个变量是用规则ES消去量词，对该变量在添加量词时，则只能使用规则EG，而不能使用规则UG；如使用规则US消去量词，对该变量在添加量词时，则可使用规则EG和规则UG。谓词逻辑推理的难点（续）（3）如有两个含有存在量词的公式，当用规则ES消去量词时，不能选用同样的一个常量符号来取代两个公式中的变元，而应用不同的常量符号来取代它们。（4）在用规则US和规则ES消去量词时，此量词必须位于整个公式的最前端。谓词逻辑推理的难点（续）（5）在添加量词(?x)、(?x)时，所选用的x不能在公式G(c)或G(y)中以任何约束出现。（6）在使用EG规则引入存在量词(?x)，此x不得仅为G(c)或G(y)中的函数变元。在使用UG规则引入全称量词(?x)时，此x不得为G(y)中的函数变元(因该函数变元不得作为自由变元)。谓词逻辑推理的应用每个喜欢步行的人都不喜欢坐汽车；每个人或者喜欢坐汽车或者喜欢骑自行车；有的人不喜欢骑自行车。因而有的人不喜欢步行。证明设H(x)：x是人；P(x)：x喜欢坐汽车；Q(x)：x喜欢骑自行车；R(x)：x喜欢步行。则上述语句可符号化为：(?x)(H(x)∧R(x)→P(x))，(?x)(H(x)→P(x)∨Q(x))，(?x)(H(x)∧Q(x))?(?x)(H(x)∧R(x))(1)(?x)(H(x)∧Q(x))P(2)H(c)∧Q(c)ES，(1)(3)H(c)T，(2)(4)Q(c)T，(2)(5)(?x)(H(x)→P(x)∨Q(x))P(6)H(c)→P(c)∨Q(c)US，(5)(7)P(c)∨Q(c)T，(3)，(6)，I(8)P(c)T，(4)，(7)，I(9)(?x)(H(x)∧R(x)→P(x))P(10)H(c)∧R(c)→P(c)US，(9)(11)(H(c)∧R(c))T，(8)，(10)，I(12)H(c)∨R(c)T，(11)，E(13)R(c)T，(3)，(12)，I(14)H(c)∧R(c)T，(3)，(13)，I(15)(?x)(H(x)∧R(x))EG，(14)证明下述论断的正确性：所有的哺乳动物都是脊椎动物；并非所有的哺乳动物都是胎生动物；故有些脊椎动物不是胎生的。证明设谓词如下： P(x)：x是哺乳动物； Q(x)：x是脊椎动物； R(x)：x是胎生动物。则有：(?x)(P(x)?Q(x)),?(?x)(P(x)?R(x)) ?(?x)(Q(x)∧?R(x))请看下面推导：1)?(?x)(P(x)?R