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

等值的定义

给定两个命题公式$A,B$，以及在$A,B$中出现的所有命题变相$P_1,P_2,……,P_n$，那么公式$A,B$一共有$2^n$种解释。如果在所有的解释下有$A$和$B$的真值都相等，那么称$A$和$B$等值,记做$A=B$

  • 等值定理指的是，$A=B$的充要条件是$A\leftrightarrow B$是重言式

等值公式

这部分极其重要。

转换公式

  • $P\rightarrow Q=\neg P\lor Q$ ⭐️⭐️
  • $P\leftrightarrow Q=(P\land Q)\lor(\neg P\land\neg Q)=(P\lor\neg Q)\land(\neg P\lor Q)$ ⭐️

一般认为，在进行公式的转化和计算的时候，我们会把所有的蕴含和双蕴含转化为我们熟悉的与或非，这样计算会比较简单。

双重否定律

  • $\neg\neg P=P$

结合律

  • $(P\lor Q)\lor R=P\lor(Q\lor R)$
  • $(P\land Q)\land R=P\land(Q\land R)$
  • $(P\leftrightarrow Q)\leftrightarrow R=P\leftrightarrow(Q\leftrightarrow R)$
  • $(P\rightarrow Q)\rightarrow R\not=P\rightarrow(Q\rightarrow R)$ ⚠️

交换律

  • $P\lor Q=Q\lor P$
  • $P\land Q=Q\land P$
  • $P\leftrightarrow Q=Q\leftrightarrow P$
  • $P\rightarrow Q\not =Q\rightarrow P$ ⚠️

分配律

  • $P\lor(Q\land R)=(P\lor Q)\land(P\lor R)$⭐️
  • $P\land(Q\lor R)=(P\land Q)\lor(P\land R)$⭐️
  • $P\rightarrow(Q\rightarrow R)=(P\rightarrow Q)\rightarrow(P\rightarrow R)$
  • $P\leftrightarrow(Q\leftrightarrow R)\not=(P\leftrightarrow Q)\leftrightarrow(P\leftrightarrow R)$ ⚠️

摩根律

  • $\neg(P\lor Q)=\neg P\land\neg Q$ ⭐️⭐️
  • $\neg(P\land Q)=\neg P\lor\neg Q$ ⭐️⭐️

其他常用公式

  • $\neg P\rightarrow Q=\neg Q\rightarrow P$ ⭐️
  • $P\rightarrow(Q\rightarrow R)=(P\land Q)\rightarrow R$
  • $(P\rightarrow R)\land(Q\rightarrow R)=(P\lor Q)\rightarrow R$

置换和置换规则

对于公式$A$的子公式，用与之等值的公式代换称之为置换。

  • 置换规则指的是，公式$A$的子公式被置换后变成了公式$B$，那么有$A=B$

注意，置换和代入是有区别的。置换只要求对$A$的某一个子公式做代换，不强制要求对所有同一的子公式都做代换。

推理演算

指由已知等式出发推导出其余等式的过程，一般认为有真值表法和等值公式推导两种方法。

一般认为，除非试题特殊说明，我们都用等值公式推导这种方式。这部分需要多加练习，因为这是以后所有知识的基础。

例：求证$(\neg P\land (\neg Q\land R))\lor (Q\land R)\lor(P\land R)=R$

证明:$LHS\\=(\neg P\land (\neg Q\land R))\lor((Q\lor P)\land R)\\=((\neg P\land \neg Q)\land R)\lor((Q\lor P)\land R)\\=(\neg (P\lor Q)\land R)\lor((Q\lor P)\land R)\\=(\neg (P\lor Q)\lor (Q\lor P))\lor R\\=(\neg (P\lor Q)\lor (P\lor Q))\lor R\\=True\land R\\=R\\=RHS$

一般我们认为，到后面熟练之后，不需要写出每步运用了什么定理，也不需要每一步只用一个定理。以及可以把一些显而易见的步骤跳过节省时间。