命题逻辑详解

命题逻辑详解

文章目录

• 命题逻辑详解
  • 一.命题逻辑的基本概念
    • 1.命题与真值
    • 2.原子命题与复合命题
  • 二.命题逻辑公式的语法
    • 1.命题逻辑公式的归纳定义：
    • 2.抽象语法树
    • 3.子公式：
    • 4.语法性质
    • 5.命题逻辑公式的简写
  • 三.命题逻辑公式的语义
    • 1.命题逻辑公式的真值表
    • 2.命题逻辑公式的分类
  • 四.命题逻辑的等值演算
    • 1.逻辑等值定义：
    • 2.定理：
    • 3.等值演算
    • 4.命题逻辑公式的范式
  • 五.命题逻辑的推理理论
    • 1.推理的有效性
    • 2.命题逻辑的自然推理系统
    • 3.构造验证推理有效性的论证
  • 六.命题逻辑的应用
    • 1.自然语言命题的符号化
    • 2.普通逻辑问题的符号化分析
    • 3.算法性质的逻辑分析
    • 3.算法性质的逻辑分析

命题之间的真值关系是逻辑研究的基本问题。

一.命题逻辑的基本概念

1.命题与真值

命题：是具有真假值的陈述句，或为真，或为假。

注意：以下两种陈述句不是命题：

​ 1）含有变量的句子。（如：x是5的倍数）

​ 只有确定了x是某类事物中的具体个体，或对x使用量词进行量化之后才能得到命题。（如：存在整数x,使 x是5的倍数）

​ 2）被认为是悖论的句子。（如：我说的这句话是假的）这个句子就没有真值。

真值：命题的真假值。一个为真，一个为假，即{0，1}或{F，T}

2.原子命题与复合命题

原子命题：其中没有逻辑联结词，不再进行分解。又称为简单命题。

复合命题：可以分解出更简单的命题作为子命题，其真值由子命题的真值唯一确定。

注意：原子命题的真值由它是否符合客观实际或是否符合人们的认知决定；复合命题的真值由原子命题的真值和逻辑联结词的性质决定。

二.命题逻辑公式的语法

命题逻辑公式的符号集包括元素： ∧和 ， ∨或 ， →蕴含 ， ↔双蕴含 , ¬否 和左右圆括号（，）这两个辅助符号。

1.命题逻辑公式的归纳定义：

1）归纳基：每个命题变量都是命题逻辑公式；

2）归纳步：(i)如果A是命题逻辑公式，则（¬A）（否定式）也是命题逻辑公式；（ii）如果A和B是命题逻辑公式，则（A∧B）（合取式），（A∨B）（析取式），（A →B）（蕴含式），（A↔B）（双蕴含式）都是命题逻辑公式。

2.抽象语法树

定义：将公式的构造用二叉树表示，称为抽象语法树，简称AST

优点：可以快速判断公式类型（由最后一步所使用的逻辑运算符决定）；可以容易的给出每一步的公式构造。

3.子公式：

定义：构造命题逻辑公式是用到的公式称为子公式，包括其本身。它的每个子公式对应抽象语法树里的一棵子树。

4.语法性质

1）任意命题逻辑公式包含的左圆括号数等于右圆括号数，等于公式的逻辑运算符数。（可由结构归纳法证明）

2）如果一个命题逻辑公式不是命题变量，则作为符号串存在且仅存在一个点满足：这个位置的字符是逻辑运算符；它左边的子符号串以左圆括号开头，其中左圆括号比右圆括号多一个，其右边以右圆括号结束，其中右圆括号比左圆括号多一个。

p.s.性质二给出了判断一个符号串是否为命题逻辑公式的方法：扫描找到该位置，分为左子串和右子串，再分别递归判定，直到不存在这样的位置。

5.命题逻辑公式的简写

为了避免使用圆括号，人们规定了运算符的优先级和结合性：

1）逻辑运算符从高到低的顺序： ¬，∧ ， ∨ ， → ， ↔

2）规定：∧ ， ∨ ，↔从左至右结合，→从右至左结合

三.命题逻辑公式的语义

这里所说的命题逻辑公式的语义是指如何确定命题逻辑公式的真值。

一个命题逻辑公式的真值计算过程是后序遍历抽象语法树的过程，即由叶子顶点的命题变量的真值得到它的父亲节点对应公式的真值，然后再得到上一层内部顶点对应公式的真值等，一直到根的对应公式，即整个公式的真值。

1.命题逻辑公式的真值表

定义：以表格的形式给出公式在任意真值赋值下的真值。

性质：命题逻辑公式的真值只与它包含的命题变量得真值有关，因此含有n个命题变量的公式的真值表有2^n行

**p.s.**关于蕴含式（易错）：A →B，当A真值为假时，蕴含式的真值为真；当A的真值为真时，蕴含式的真值等于B的真值

2.命题逻辑公式的分类

从真值情况进行分类：1）永真式（重言式）2）矛盾式（永假式）3）偶然式（非永真的可满足式）

判断一个命题逻辑公式是否为永真式的基本方法是构造该公式的真值表。若最后一列都为1，则是永真式。

定理：设命题逻辑公式A是永真式，p是在A中出现的一个命题变量，则使用任意命题逻辑公式B替换A中出现的 所有p，得到的公式A’也是永真式。

四.命题逻辑的等值演算

命题逻辑的等值演算是判断这两个命题逻辑公式是否逻辑等值的基本方法。

1.逻辑等值定义：

对任意的真值赋值，命题逻辑公式A和B的真值都相同，则称A和B逻辑等值，简称等值，记为A ≡ B。

也称A ≡ B为逻辑等值式。（注意不是命题逻辑公式）

例如：命题逻辑公式p→q与 ¬p∨q等值

p.s.（技巧）

1）验证两个命题逻辑公式是否逻辑等值的基本方法是构造这两个公式的真值表，比较在相同的真值赋值下真值是否相同

2）逻辑运算或，与满足交换律，结合律和幂等律。

3）逻辑等值有传递性。

2.定理：

1）A ≡ B当且仅当公式A↔B是永真式。

2）设命题逻辑公式B是A的子公式，且B与B‘逻辑等值。假若使用B’置换公式A的一处或多处子公式B得到的式子是A‘，则A与A’逻辑等值。

3.等值演算

定义：为验证A ≡ B，只要将A变换到与它等值的A‘，再变换，直到变换为B；或从B等值变换为A；或将A和B都等值变换为C。这样的等值变换过程称为等值演算。

4.命题逻辑公式的范式

定义：

析取范式：是一个或多个合取式的析取，其中的合取式都是一个或多个文字的合取；文字指命题变量或命题变量的否定。这种一个或多个文字的合取的公式称为简单合取式。

合取范式: 是一个或多个析取式的合取,其中的析取式都是一个或多个文字的析取。这种一个或多个文字的析取的公式称为简单析取式。

注意：每个命题逻辑公式都有与它逻辑等值的析取范式和合取范式。而且是唯一的（化简以后更容易判断真值^^)

极小项：若含有n个命题变量的合取式恰好是n个文字的合取，每个文字对应不同的命题变量，该合取式称为极小项。含有n个命题变量的主析取范式公式是零个或多个极小项的析取。

极大项：若含有n个命题变量的析取式恰好是n个文字的析取，每个文字对应不同的命题变量，该析取式称为极大项。含有n个命题变量的主合取范式公式是零个或多个极大项的析取。

p.s.永真式没有成假赋值，因此其主合取范式不含有任何极大项。

​ 可以说一个与公式逻辑等值的主析取范式与主合取范式是该公式的真值表的另一种表达形式。

​ 公式包含的命题变量比较多时，列真值表的计算量大，利用等值演算可能更方便。

​ 极大项和极小项的概念可以类比线性代数中的最小线性无关向量集合等。

​ 公式的主析取范式的极小项编码与其主合取范式的极大项编码集互补。（看成二进制的互为反码）

五.命题逻辑的推理理论

推理：是从一组做为前提的命题得到一个作为结论的命题的过程。如果这个过程能够保证当前所有前提都为真的情况下得到的结论必然为真，则称推理是有效的。

1.推理的有效性

定义：称推理A，B，C，…,N ⇒ X是有效的，若（AvB∧Cv…vN）→X是永真式。

**注意：推理的有效性并不保证结论是真的！**因为不能保证前提是真的。

2.命题逻辑的自然推理系统

构造真值表法和等值演算法都可用于验证推理的有效性。

但是构造真值表效率太低，等值演算法不贴近人们的日常生活，对人们的构造和分析有效推理缺乏指导意义。

**命题逻辑的自然推理系统的特点：**1）引入中间结论进行分解。2）运用公理化思维方式，套用推理规则。

推理规则的实例：分别使用具体的命题逻辑公式替换推理规则中的每个字母的所有出现后得到的推理。

3.构造验证推理有效性的论证

验证推理有效性的论证的构造从某种程度上就是归纳构造。利用中间结论，可以从推理论证开始进行分析。

**注意：**只能利用具体的公式替换规则中的字母，不能替换规则中的子公式。

**后序遍历：**遍历树的顶点时只要保证在所有以儿子顶点为根的子树遍历以后才遍历父亲顶点即可。

**p.s.**推理的每一步应该清楚所用的规则或原理，以注释的形式标注（不能跳步！！！

​ 可以使用附加前提法和反证法

六.命题逻辑的应用

1.自然语言命题的符号化

自然语言命题转换为逻辑公式的过程也称为自然语言命题的符号化。命题逻辑公式由命题变量和逻辑运算符构成。

转化过程：

1）判定命题

2）找原子命题

3）不同的原子命题用不同的命题变量符号表示

4）分析句子中逻辑联结词所表达的逻辑含义

2.普通逻辑问题的符号化分析

逻辑按照其历史发展阶段和类型可以分为传统逻辑和现代逻辑，从17世纪末德国哲学家莱布尼茨提出用数学方法处理演绎逻辑从而诞生数理逻辑之前的逻辑学称为传统逻辑学，数理逻辑诞生以来的逻辑学称为现代逻辑。

我们将在传统逻辑中用自然语言分析和求解的问题称为普通逻辑问题。

常见的三种问题：

1）给出一些条件，寻找满足这些条件的情况或方案。（利用等值演算法）

2）给出从一些前提得到一个结论的推理，验证推理的有效性（利用推理理论）

3）给出一些前提，讨论从这些前提出发通过有效的推理将得到怎样的结论（利用推理理论）

3.算法性质的逻辑分析

程序设计语言中的条件表达式就是逻辑公式。条件就是具有真假值的命题。

辑**问题。

常见的三种问题：

1）给出一些条件，寻找满足这些条件的情况或方案。（利用等值演算法）

2）给出从一些前提得到一个结论的推理，验证推理的有效性（利用推理理论）

3）给出一些前提，讨论从这些前提出发通过有效的推理将得到怎样的结论（利用推理理论）

3.算法性质的逻辑分析

程序设计语言中的条件表达式就是逻辑公式。条件就是具有真假值的命题。