数理逻辑笔记(一)——命题演算


命题演算

数理逻辑笔记(一)—— 命题演算

这里是菜鸡的求生现场,菜鸡大二的一门 8 周的课--数理逻辑结课了,觉得这门课挺有意思,学好后能变成逻辑鬼才(手动狗头),不想学过就扔,还是把它总结一下扔到这里叭,这篇文章是数理逻辑的第一篇,剩下的两篇为:谓词演算、形式推理,谓词演算是命题演算的细节化表达,形式推理是一种证明逻辑的好用方法。以后回顾时则需而看。

 

1. 命题

概念:命题是可辩别真假的陈述语句(也就是说不能辩别真假的、不是陈述句的都不是命题)

注意: 有些命题本身存在真假,但是目前不能确定其真假,同样认为其是一个命题,例:其他星球上存在智慧生命

 

2. 形式化

就是将使用自然语言的命题使用符号表示出来

  • 否定
  • 合取
    • 并且······
    • 不仅······而且······
    • 既······又······
    • 既然······仍然······
  • 析取
    • 或者 (注意有时候表递进)
    • 不是······就是······
    • 可能······可能······
  • 蕴含 (不强调因果且没有因果连词的时候不是蕴含而是合取)
    • 如果······则······
    • 除非······才······
    • 只有······才······(尤其注意这个要从右向左进行蕴含)
  • 等价
    • 除非不······否则······
    • 当且仅当

例题:

1.如果 能被 2 整除,则 能被 2 整除

解:令 能被 2 整除

能被 2 整除

形式化:

 

2.只有充分发扬民主,才能充分调动人民群众的积极性

解: 令 我们充分发扬民主

我们充分调动人民群众的积极性

形式化:

注意:无主语的简单命题形式化要加上主语

 

3. 公式和指派

  • 公式 = 命题变项() + 真值联结词 = 子公式 + 真值联结词
  • 指派 :给公式中的命题变项赋值(赋真假)
    • 成真指派:使得命题为真
    • 成假指派:使得命题为假
  • 可满足、不可满足(永假, )、永真、可能性 的关系c4eee45a-ed3a-49b4-a5e7-c347ed049990-1312838

 

4. 逻辑蕴含、逻辑等价

逻辑蕴含

形式:,左边称为前提,右边称为结论

定义:任意 使得 为真,则 必为真

基本逻辑蕴含式

  1. (合取分析式)
  2. (析取构成式)
  3. (充足理由律,假言推理、肯定分离式)
  4. (假言推理、否定后件式)
  5. (换质位律,否定后件式)
  6. (相容选言推理、否定肯定式)
  7. (假言三段论)
  8. (二难推理,简单构成式)
  9. (排中律)
  10. (无矛盾律)
  11. (同一律)

 

基本蕴含变换

  • 以下三条等价

  • 以下五条等价

证明方法

  1. 真值表
  2. 指派分析
    • 构造法

  • 逆否证法

    • 无义证法

    • 平凡证法

    例题:

    证明逻辑蕴含

    证:令

    对任意指派

    ,则

    假设 ,则 ,矛盾,故

    所以

    即证

 

逻辑等价

形式:,左边称为左边,右边称为右边

定义: 共真假

基本逻辑等价式

  1. (双重否定律)
  2. (幂等律)
  3. (结合律)
  4. (吸收律,重要)
  5. (交换律)
  6. (分配律)
  7. (逆否率,重要)
  8. (否定深入,重要)
  9. (归约律,极其重要)
  10. (化简律)

证明方法

  1. 真值表
  2. 指派分析
  3. 等价变换例题:利用变换法证明逻辑等价式:证:

注意:使用等价变换证明的时候把原因注明在后面

 

5. 替换定理、代入定理

替换定理: 是含有子公式 的公式,将其中 用子公式 替换,从而得到 (这个过程记为 )。如果 ,则

代入定理: 是含有命题变项 的公式,将其中 用子公式 替换,从而得到 (这个过程记为 )。如果 ,则

替换定理:子公式等价 => 公式等价

代入定理:公式永真 => 公式永真

 

6. 对偶与内否

对偶式

  1. 不含
  2. 记为

 

内否式

  1. 不含
  2. 记为

 

基本性质

  1. (对合律)
  2. (反身律)
  3. (交换律)
  4. (分配律)
  5. (分配律)
  6. (对偶律)
  7. (对偶律)

另外,非、对偶、内否的顺序可以任意调换:

 

否定深入定理

定理:设公式不含,则

“否定深入”的解释:设 , 那么,利用否定深入定理得到,也就是 从公式外部深入到了命题变项之前,这就是“否定深入”的直观理解

 

对偶定理

  1. 等价于
  2. 等价于

 

7. 联结词集

二元真值函项扩展

  • 异或
  • 与非(先与后非)
  • 或非(先或后非)

 

真值函项

  • 定义:
  • 举例:
    • 一元:
    • 二元:
  • 例题:表中给出了三元真值函项 w 的真值,请用 w 表示
    p q r w(p,q,r)
    t t t f
    t t f f
    t f t f
    f t t f
    f t f f
    f f t f
    f f f t

    根据表格得:

    则:

    (p' 任意取值)

    (p’ 任意取值)

    (p', p'', p''' 任意取值)

    注:一般做这种题时先观察真值表,像上面这道 t 少,就从 t 下手,什么时候 w 才为真?当然是任意一个 t 情况满足即可,因此将所有 t 情况用析取()连起来就是 w 的表达式了。当然 f 少时可以从 f 下手,一样的思路,不过求出的是 ,需要取个反

 

联结词集与全功能集

联结词集:真值函项集的任意子集,如:

全功能集:一个联结词集,对于任意真值函项 f, 都可用该联结词集中的联结词表达,称为全功能集

极小全功能集:若全功能集 A 中的每一个联结词,都不能用其余联结词表达,则称 A 时一个极小全功能集

定理: 都是极小全功能集

证明方法:

  • 证明全功能:找出一个已有全功能集,然后将其中的联结词用待证集合表示出来
  • 证明极小:说明待证集合中的符号都不能用剩余符号表示

 

8. 范式

定义:公式的规范形式,只含

析取范式:主干靠析取()连接

  • 举例:

合取范式:主干靠析取()连接

  • 举例:

主范式:每个公式的主析取范式(MDNF)、主合取范式有且只有一个,就是将命题变项按照二进制格式排序,然后化为角标表示。注意:主析取范式单项用 m 表示,角标从大向小排列,主合取范式单项用 M 表示,角标从小到大排列

  • 性质:角标互补,比如如果有两个变项,则
  • 举例: 按照二进制排列为 101(=5),因此应该表示为
  • 求取方法
    • 联结词归约(消蕴含关系)
    • 否定深入
    • 且非调整
    • 化简
    • 补足变项
    • 合并同类项
  • 例题
    1. 求公式 的 MDNF

    注:因此对应的主合取范式为

    1. 求公式 的 MDNF

      注:因此对应的主合取范式为