离散数学(1) | 命题逻辑的基本概念

本文及其系列文章用于离散数学（1）科目的期末考试复习

命题逻辑

命题

命题是一个陈述句，并且可以判断真或假

命题常元，就是\(True\)和\(False\)

命题变项(变元) 一般用大写字母表示,如\(P、Q\)等

简单命题（原子命题) 指的是不包含任何联结词的命题，不可再分割

符合命题 指的是简单命题用联结词构成的新命题

联结词

否定词\(\neg\)，即not。

\[\begin{array}{|c|c|}P&{\neg P}\\0&1\\1&0\end{array} \]

合取词\(\land\)，即and

\[\begin{array}{|cc|c|}P&Q&{P\land Q}\\0&0&0\\0&1&0\\1&0&0\\1&1&1\end{array} \]

析取词\(\lor\)，即or

\[\begin{array}{|cc|c|}P&Q&{P\lor Q}\\0&0&0\\0&1&1\\1&0&1\\1&1&1\end{array} \]

蕴含词\(\rightarrow\)，可以理解为“推导出”

\[\begin{array}{|cc|c|}P&Q&{P\rightarrow Q}\\0&0&1\\0&1&1\\1&0&0\\1&1&1\end{array} \]

双条件词\(\leftrightarrow\)，可以理解为“当且仅当”

\[\begin{array}{|cc|c|}P&Q&{P\leftrightarrow Q}\\0&0&1\\0&1&0\\1&0&0\\1&1&1\end{array} \]

一般认为，联结词的运算优先级排列为\(\neg ，\land ， \lor ，\rightarrow ，\leftrightarrow\)

合式公式定义

这是一个递归定义。

1. 简单命题是合式公式
2. 如果\(A\)是合式公式，那么\(\neg A\)也是合式公式
3. 如果\(A,B\)是合式公式，那么\(A\land B,A\lor B,A\rightarrow B,A\leftrightarrow B\)是合式公式
4. 当且仅当经过有限次使用\(1,2,3\)所组成的符号串才是合式公式

公式分类

对于某个命题公式\(X\)

• 如果\(X\)在任何的解释\(I\)下都为真，
  那么称之为重言式(永真式)

• 如果\(X\)在任何的解释\(I\)下都为假，那么称之为永假式。

• 如果存在一种解释\(I_0\)使得\(X\)为真，那么称之为可满足式。

代入规则

对于某个公式\(X\)，如果打算用公式\(Q\)来替换\(X\)中的\(P\)，那么这时候我可以记做\(\frac{P}{Q}\)

比如，在公式\(((R\lor S)\land((R\lor S)\rightarrow (P\lor Q)))\rightarrow (P\lor Q)\)中，我们需要用\(A,B\)来代换\((R\lor S),(P \lor Q)\)，这个时候我们会记\(\frac{A}{(R\lor S)},\frac{B}{(P \lor Q)}\)，用来确保过程用于规范。

为了保证带入后公式的真假性不发生变化，代入规则 要求如下：

1. 公式中被替换掉只能是命题变元，不能是不能够完全代入的复合命题

2. 如果对某个命题变项施以带入，那么对于公式中出现的所有同一命题变项代换同一个公式

波兰表达式

一般我们认为，离散数学中的波兰表达式用表达式的二叉树的遍历来做比较方便。

以\(P\lor Q\)为例子

• 中缀表达式就是常见的表达式，\(P\lor Q\)，表达二叉树的中序遍历
• 前缀表达式就是\(\lor \,P\, Q\)，表达二叉树的前序遍历
• 后缀表达式就是\(P \, Q \, \lor\)，表达二叉树的后序遍历

特别注意，如果遇到类似\(P\lor Q\lor R\)这样的情况，表达树是唯一的，因为我们一般会从前往后计算，所以这个式子本质上是这样的\((P\lor Q)\lor R\)。