第二章 命题逻辑

2.1 命题逻辑的基本概念

定义：命题（含真值的陈述句，无变量或悖论）

著名悖论：说谎者悖论、罗素悖论

如何区分原子命题和复合命题？是否有逻辑连接词（与或非）

2.2 命题逻辑公式的语法

定义

逻辑语言是逻辑公式的集合，逻辑公式是符号按一定规则形成的字符串

语法是构成逻辑公式的规则

逻辑语言的符号集：$\lnot, \land, \lor, \leftarrow, \leftrightarrow, ()$。命题变量使用小写字母。

逻辑运算符：$\lnot, \land, \lor, \leftarrow, \leftrightarrow$，不包括括号。

\wedge, \vee, \neg

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

• 归纳基：每个命题变量是公式（原子公式）
• 归纳步：若 $A, B$ 是公式，则 $\lnot A, (A \land B), (A \lor B), (A \rightarrow B)$ 是公式

归纳定义的命题逻辑公式，左右括号数相等，且等于逻辑运算符个数。

最后一步用到的归纳步是该公式的类型。

原子公式、否定式 ($\lnot$)、合取式 ($\land$)、析取式 ($\lor$)、蕴含式/条件式 (前件/前提 $\rightarrow$ 后件/结论)、双蕴含式/双条件式 ($\leftrightarrow$)

公式的归纳定义可以抽象成抽象语法树。

子公式：构造公式 $A$ 的过程中所有用到的公式，即抽象语法树上的所有节点对应的公式。

所有不同的子公式，统计时不要重复！

语法性质

运算符的优先级：非、与、或、蕴含、双蕴含

运算符的结合性：与、或、双蕴含左至右，蕴含右至左

2.3 命题逻辑公式的语义

语义：如何确定公式的真值

真值赋值函数：从命题变量集到真值集的函数 $\sigma : \boldsymbol{Var} \to \boldsymbol 2 = {0, 1}$

命题逻辑公式的语义定义基于真值赋值函数。

真值赋值函数根据语法结构来递归定义，真值计算也是按照抽象语法树后序遍历递归计算的

$$ \begin{aligned} \sigma(B \to C) &= \lnot (\sigma (B) \land \lnot \sigma (C)) \ \sigma(B \leftrightarrow C) &= \sigma(B) \land \sigma(C) \lor \lnot \sigma(B) \land \lnot \sigma(C) \ \end{aligned} $$

蕴含式只表示逻辑关系，不代表一般意义上的因果关系！

成真赋值、成假赋值

真值表，所有可能取值下的函数取值，列出来

快速绘制真值表？设置中间变量列（子公式），利用短路运算来快速确定取值。

永真式、矛盾式、可满足式、偶然式(非永真的可满足式)：用真值表判断即可。

永真式的否定是矛盾式，矛盾式的否定是永真式。

永真式的替换实例仍然是永真式：若 $A(p)$ 是永真式，其中 $p$ 是命题变量，那么对于任意公式 $B$，有 $A(B)$ 是永真式。

矛盾式的替换实例仍然是矛盾式。