本文及其系列文章用于离散数学（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$。