命题逻辑表达式的重要性质

发表于

范式

命题逻辑里很多公式都是等值的：不论其中变项取什么值，两个公式都同真或同假(真值相等)

  • 表达同一个真值函项

  • 每一个真值函项都可以有许多不同的表达式

    • 有些种类的表达式具有特殊的意义和作用，可以显示真值函项的一些重要特征：范式

简单析取：支命题或是一命题变项，或是一命题变项的否定的析取式

  • 例：$¬p \bigvee q$, $p \bigvee ¬q \bigvee r \bigvee ¬r$

  • 简单析取的重要特征之一

    • 一简单析取 $A$ 是否为重言式当且仅当有一变项 $\pi$ ，$\pi$ 和它的否定 $¬\pi$ 都作为 $A$ 的支命题出现
    • 具有形式：$\pi \bigvee ¬\pi \bigvee B$

简单合取：支命题或是命题变项，或是命题变项的否定的合取式

  • 例如：$q$, $¬p \bigwedge ¬q$

  • 一简单合取 $A$ 是矛盾的当且仅当有一变项 $\pi$，$\pi$ 和它的否定 $¬\pi$ 都作为A的支命题出现

合取范式：支命题都是简单析取的合取式

  • 例如：$(¬p \bigvee q) \bigwedge (p \bigvee ¬q)$

  • 合取范式的作用在于显示重言式

  • 判定合取范式是不是重言式

    • 设合取范式A为：$A_1 \bigwedge A_2 \bigwedge … \bigwedge A_n$
    • 其中 $A_i(1 \leq i \leq n)$ 都是简单析取
    • 如果每一 $A_i$ 常真，则A也常真
    • A为重言式的充要条件是每一 $A_i$ 都是重言式

析取范式：支命题都是简单合取的析取式

  • 例如：$(¬p \bigwedge ¬q) \bigvee (p \bigwedge q)$

  • 析取范式的作用在于显示矛盾式

  • 判定析取范式是不是矛盾式

    • 析取范式是矛盾式当且仅当组成它的每一简单合取常假

范式存在定理：命题演算的每一公式都有与其等值的合取范式和析取范式

  • 求范式的步骤：
      1. 蕴涵和等值符的消去
      • $A \rightarrow B$ 换以 $¬A \bigvee B$
      • $A \leftrightarrow B$ 换以 $(¬A \bigvee B) \bigwedge (A \bigvee ¬B)$ 或 $(A \bigwedge B) \bigvee (¬A \bigwedge ¬B)$
      1. 否定符的内移和消去
      • $¬¬A$ 换以 $A$
      • $¬(A \bigvee B)$ 换以 $¬A \bigwedge ¬B$
      • $¬(A \bigwedge B)$ 换以 $¬A \bigvee ¬B$
      1. 关于合取和析取的置换
      • 合取和析取的各支可相互交换
      • 合取和析取的各支结合的次序可依需要而改变，据此可省略结合的括号
      • 分配：
        • $A \bigvee (B \bigwedge C)$ 换以 $(A \bigvee B) \bigwedge (A \bigvee C)$
        • $A \bigwedge (B \bigvee C)$ 换以 $(A \bigwedge B) \bigvee (A \bigwedge C)$

优范式

一般的合取范式和析取范式的缺点：一公式的合取范式或析取范式不是唯一的

优析取范式：满足以下条件的析取范式

  1. 每一出现在范式里的命题变项在每一简单合取里都出现

  2. 没有常假的简单合取

  3. 在简单合取里没有相同的支命题

  4. 对于命题变项极其否定给予一字典顺序，在范式里命题变项和简单合取都按照字典顺序排列

  • 字典顺序在本系统中指的是按照在命题所有的甲类符号表并依次插入其否定式而作出的排列
    • $[p, ¬p, q, ¬q, r, ¬r, s, ¬s, p_1, ¬p_1, …]$
    • 例如 $(p \bigwedge q) \bigvee (q \bigwedge ¬p)$ 和 $(¬p \bigwedge q) \bigvee (p \bigwedge q)$ 都不是优范式
  1. 没有相同的简单合取

优合取范式：定义同上，只将“析取”与“合取”字样互换，将2改为没有重言的简单析取

优范式唯一存在定理：每一公式都有一个唯一的优合取范式和一个唯一的优析取范式

范式的作用

判明公式的一些性质；论证命题演算的完整性；工程技术的线路设计方面……

合取范式的作用

  • 简易地判定一公式是否为重言式
    • 每一简单析取都是重言式则合取范式是重言式

析取方式的作用

  • 判别一公式是不是矛盾的
    • 每一简单合取都是矛盾的则析取范式是矛盾的

优析取范式的作用

  • 可以完全明确地列举出一公式的真假情况

  • 矛盾式的优析取范式为一零公式

    • 用优析取范式可判别一公式是否为矛盾式

优合取范式的作用

  • 重言式的优合取范式为一零公式
    • 判别重言式

  • 明确看出哪些真值函项的表达式里可以没有否定符

  • 一个由n个命题变项 $p_1, p_2, …, p_n$ 组成的真值函项可以不用 $¬$ 表达，当且仅当其优合取范式里没有 $¬p_1 \bigvee ¬p_2 \bigvee ¬p_3 \bigvee … \bigvee ¬p_n$这一简单析取(而用 $\rightarrow, \bigvee, \bigwedge$ 表达)

优范式的其它作用

  • 可以通过优范式判明两个含相同变项的公式是否表达同一真值函项

命题演算的一致性和完全性

  • 命题演算是一公理系统

  • 对于给定的公理系统和推演规则

    • 能推演出较多的真命题，把某一范围的真命题完全推演
    • 不能推演出逻辑矛盾(完全性和一致性)

推演的前提可以是任何公式或任何命题，证明的根据则是一公理系统的公理
只有从公理可推演的公式或命题才是可证的，才是定理

命题演算的一致性

一致性：无矛盾性

公理系统的一致性的定义

  • 一致性的古典定义：一公理系统是一致的，当且仅当不存在任何公式A，A和非A都在这系统里可证

  • 一致性的语义定义：一公理系统是一致的，当且仅当一切在这系统里可证的公式都是真的

  • 一致性的语法定义：一公理系统是一致的，当且仅当并非任一合式公式都在这系统里可证

证明公理系统的一致性，不仅要指出在系统里未曾推演出逻辑矛盾，而且还要证明系统里不可能推演出矛盾
无矛盾证明是一种不可能性的证明

一致性定理一：命题演算是语义一致的；命题演算的定理都是重言式

  • 命题演算的公理(只有四个)都是重言式
  • 应用命题演算的推演规则(三个：代入、分离和定义置换)，从重言式只能得到重言式

一致性定理二：命题演算是语法一致的；并非任一公式都是命题演算的定理

  • 既然一切定理都是重言式，那么非重言式，如 $p \bigvee q$ 就不是定理

一致性定理三：命题演算是在古典的意义下一致的；对任一公式A，A和¬A不能都是命题演算定理

  • 对于命题演算的任一公式A，有时A和¬A都不是重言式(如 $¬p \bigvee q$ 和 $¬(¬p \bigvee q)$)
  • 但是A和¬A不能同时都是重言式
    • 如果A是重言式，则¬A就是逻辑矛盾
    • 如果¬A是重言式，则A就是矛盾式
  • 由一致性定理一，只有重言式才是定理
    • A和¬A不能都是定理

命题演算的完全性

完全性：能不能包括某一范围内的一切真命题(是不是完全的)

公理系统的完全性的定义

  • 完全性的语义定义：一公理系统是完全的，当且仅当一切属于某一特定范围内的真命题都是在这系统里可证的

  • 完全性的语法定义：一公理系统是完全的，当且仅当如果把一个推演不出的公式作为公理，结果所得的系统就会是不一致的

    • 凡在一系统1里不可证的都是不能承认的，不是真的，勉强作为定理加到系统中就会产生逻辑矛盾

  • 完全性的古典定义：一公理系统是完全的，当且仅当对于任一合式公式A而言，或者A是可证的，或者¬A是可证的

    • 这种意义下的完全性是针对某些种类的公理系统而言
    • 这种系统里合式公式没有自由变项，命题演算不是这种公理系统
    • 这种意义下命题演算不是完全的(如 $¬p \bigvee q$ 和 $¬(¬p \bigvee q)$ 都不是重言式，都不是可证的)

完全性定理一：命题演算是语义完全的；一切重言式在命题演算里都是可证的

  • 设A为一重言式
  • A的一合取范式为B，则B也是一重言式，并且B为 $B_1 \bigwedge B_2 \bigwedge … \bigwedge B_n$，其中 $B_i(1 \leq i \leq n)$ 是简单析取
  • 则 $B_i$ 必是重言式
  • 每一 $B_i$ 里必有一变项 $\pi$，且 $\pi$ 和 $¬\pi$ 都作为 $B_i$ 的支命题出现
    • 每一 $B_i$ 多具有形式 $\pi \bigvee ¬\pi \bigvee C$
    • $p \bigvee ¬p$ 可证，则 $p \bigvee ¬p \bigvee q$ 可证，则每一 $B_i$ 都可证
  • 由定理 $├ p \rightarrow (q \rightarrow p \bigwedge q)$，$B_1 \bigwedge B_2 \bigwedge … \bigwedge B_n$ 可证
    • 故B可证，B是A(根据置换规则得到)的范式，故A也可证

完全性定理二：命题演算是语法完全的；如果把一不可证的公式作为公理，其结果将是不一致的

公理的独立性

独立性就是不可推演性

  • 根据已给定的推演规则，从一类公式推演不出某一类特定公式
  • 该公式对于这类公式就是独立的
  • 独立性总是相对于给定的推演规则而言的

独立性的定义：一公式集合M是独立的，如果M中的任意公式A都不能根据给定的推演规则从M中其它公式推演出来

  • 独立性和一致性不同，和完全性也有所不同

  • 一公理系统的诸公理，其中即使有不独立的，也不能算是很大的缺点

  • 独立性的证明是能不能推出的问题，也是不可能性的证明

算术解释方法：

  • 设给定一公式集合 ${ A_1, A_2, A_3, A_4 }$ 和 两个推演规则 $R_1$ 和 $R_2$
    • 求证：根据 $R_1$ 和 $R_2$ ，$A_4$ 对于 ${ A_1, A_2, A_3 }$ 是独立的

  • 反证法：

    • 假设 $A_4$ 不独立，可以从 ${ A_1, A_2, A_3 }$ 根据 $R_1$ 和 $R_2$ 推出
    • 下列断定必然成立：对任意性质 $\phi$
        1. $A_1$，$A_2$，$A_3$ 都有性质 $\phi$
        1. 应用公式 $R_1$ 和 $R_2$，从有性质 $\phi$ 的公式只能得到有性质 $\phi$ 的公式
    • 那么
        1. $A_4$ 必然有性质 $\phi$
    • 根据此断定，若存在某一性质 $\phi$
        1. $A_1$，$A_2$，$A_3$ 都有性质 $\phi$
        1. 应用 $R_1$ 和 $R_2$，从有性质 $\phi$ 的公式只能得到有性质 $\phi$ 的公式
    • 但是
      • $A_4$ 没有性质 $\phi$
    • 则
    • $A_4$ 是独立的

  • 满足独立性证明的抽象性质 $\phi$：通常采用的解释是赋予变项和公式以数值(算术解释方法)

引用

  1. 《数理逻辑引论》，王宪钧，北京大学出版社