离散数学[4]-数理逻辑-谓词逻辑及形式系统

一、个体、谓词和量词

命题的解析

  •  命题逻辑中最小研究单位是原子命题, 并没有进一步的内部结构*

  • 定义:命题是对确定的对象作出判断的陈述句

〉 那么,对不确定的对象如何?(x>5) 〉 以及,进行不同条件下的判断如何?

〉 命题逻辑中的推理,关注真值的推演 〉 假言推理、归谬推理和穷举推理 〉 建立在重言式、代入和替换原理基础上 〉 命题逻辑中,命题之间相互独立,没有内在联系 〉 在经典的三段论推理中,命题逻辑有些力不从心

命题之间的内在联系

  •  三段论例子:

    • 大前提:p:所有的学校都有学生
    • 小前提:q:北京大学是学校
    • 结论:r:北京大学有学生
  • 命题逻辑的形式化结果:

    •  (p∧q)→r
    • 一个正确推理在命题逻辑中并不是永 真式
    • 常识:三个命题包含了某些有关联的 概念,并非相互独立

命题的结构分析

  • 命题:对确定的对象作出判断的陈述句
  •  被作判断的对象:个体
  •  作出的判断:谓词
  •  个体的数量:量词(所有、有些、没有)
  •  谓词逻辑将量词作用于个体,引入个体变元,讨论不确定的对象
  • 谓词逻辑也称作一阶逻辑(First Order Logic)
  • 如果将量词作用于谓词,引入谓词变 元,属于二阶逻辑研究范围

个体(individual)

  • 谓词逻辑中将一切被讨论的对象都称作个体。
  • 确定的个体常用a,b,c表示,称作个体常元(constants)
  •  不确定的个体常用x,y,z,u,v,w表示,称作个体变元(variables)
  •  被讨论对象的全体称作个体域(domainofindividuals),常记做D
  • 包含一切对象的个体域特称为全总域(universe),记做U

谓词(predicate)

  • 通常是谓语,称作谓词

〉 “北京大学是学校”中的“…是学校” 〉 “张三和李四是朋友”中的“…和… 是朋友” 或者“…和…是…”

  •  谓词中可以放置个体的空位个数称为谓词的元数

〉 单元、二元、三元谓词

谓词命名式

  • 将谓词中的个体空位用变元字母代替,称作谓词命名式
  • 常用大写字母P、Q、R等代表谓词,谓词命名式形如P(x)、Q(x,y)
  •  命名式中的变元字母并没有独立的含义,仅是占位符(place holder)

〉 “…是学校”记做SCHL(x) 〉 “…和…是朋友”记做FRD(x,y), 〉 “…和…是…”记做REL(x,y,r)

谓词填式

  • 将谓词中的个体空位用个体变元或常元代替,称作谓词填式
  • 谓词填式在形式上和命名式相同,但是属于不同的概念,需要根据上下文加以区分
  • 类似于编程语言中的函数说明(形参) 和函数调用(实参)之区分
  •  SCHL(北京大学)表示“北京大学是 学校”
  • FRD(张三,李四)表示“张三和李四是 朋友”
  • R(x)表示“x是实数”,x为个体变元
  • 当谓词填式中的个体都是常元时,它是一个命题,具有确定的真值

量词(quantifiers)

  • 指数量词“所有”和“有”
  • “所有”为全称量词(universalquantifier),记做(Any/All)
  • “有”为存在量词(existentialquantifier),记做(Exist)
  • 量词作用于谓词时需要引入一个指导变元,同时放在量词后面和谓词填式中:xP(x)、 xP(x)
  • 指导变元是不可取值代入的,称作约束变元(bound variables), 约束变元可以