离散数学知识点总结（2）：命题公式的类型 外汇基金债券利率计算方法有哪些种类型公式为

文章目录 命题公式命题常量和命题变元命题合式公式的递归式定义（well-Formed formula）联结词的优先级命题公式的种类重言式 / 永真式 （常见举例）矛盾式 / 不可满足式 / 永假式 （常见举例）可满足式 真值表判断合式公式的类型真值表的缺陷

命题公式 命题常量和命题变元

命题常量通常用大写字母表示，代表一个具体的命题： P P P：张三是法外狂徒。这是个命题常量，因为张三要么是法外狂徒，要么不是。

命题变元通常用小写字母表示，是命题公式的组成部分，我们通常用命题变元来表示命题公式，因为它并不代表具体的结果，因此，我们总是需要对公式中每个命题变元的真值进行指派（assignment）然后，判断整个命题公式的真值情况。

p → q p ightarrow q p→q 这里的 p , q p,q p,q 实际上我们都不知道他们代表的是什么，因此在我们人为给他们指派真值之前，没有人知道 p , q p,q p,q 到底真值是多少，因此 p → q p ightarrow q p→q 的真值也暂时是个未知的。

虽然我们规定了严格的大小写， 但是由于不同的书上有不同的写法，我们的材料又来自不同的地方，因此，大小写使用的较为混乱，但是并不影响理解，在这里做一下说明。

命题合式公式的递归式定义（well-Formed formula）

可以看到，四五之所以不是命题公式，是因为（4）中的 , , , 并不是联结词（5）中的联结词使用方式是错的， ∧ → wedge ightarrow ∧→ 的组合不是正确的联结词使用方式。 联结词的优先级

命题公式的种类

重言式 / 永真式 （常见举例）

矛盾式 / 不可满足式 / 永假式 （常见举例）

可满足式

可以用真值表来判断一个 合式公式 属于哪种类型。

真值表判断合式公式的类型

如下图，我们想判断合式公式： ( ￢ P ∧ Q ) → ( P → R ) (￢Pwedge Q) ightarrow(P ightarrow R) (￢P∧Q)→(P→R) 为三种类型中的哪一种。下图中所示，如果整个真值表最右边的这一列的值全部为真，即，左边 P , Q , R P, Q, R P,Q,R 被任意指派（assignment）真值的时候，这个命题公式的真值始终为 t t t 那么，这个合式公式就可以被称为是一个 “重言式 / 永真式（tautology）” 的命题公式。

Note：

当一个命题公式是 重言式 (tautology)，我们称这个合式公式是 有效的（valid）；否则如果我们能找到至少一种 P , Q , R P, Q, R P,Q,R 组合的情况使这个公式的真值为 f f f，我们把这种公式称为是 （non-valid 无效的）

当一个命题公式是 矛盾式 / 永假式 (contradiction)，我们称这个合式公式是 不可满足的（unsatisfiable），否则如果我们至少能找到一种 P , Q , R P, Q, R P,Q,R 组合的情况使这个公式的真值为真，我们把这种公式称为是 （satisfiable 可满足的）

重言式和永假式都只是 我们对公式类型的判断，并不代表内容上的意义。比如，我们举例：

p p p: 张三是法外狂徒 p → p p ightarrow p p→p：如果张三是法外狂徒，那么张三是法外狂徒。 这是一个重言式，因为这个公式的真值永远都是 t t t， 但是这句话可以看做一句废话。

真值表的缺陷

对于一个真值表来说，如果我们想得到一个合式公式的真值表从而判断它的公式类型；那么如果它本身包含了 n 个命题变元，例如： ( ￢ p ∧ q ) → ( p → r ) (￢pwedge q) ightarrow(p ightarrow r) (￢p∧q)→(p→r) 中出现了三个变元 p , q , r p,q,r p,q,r 这整个公式的真值表就要变成 2 n 2^n 2n 种指派方式（assignment）的组合；如果变元数量再增加，真值表会指数形式增长。

我们将会在