本文及其系列文章用于离散数学（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$的子公式，用与之等值的公式代换称之为置换。 ...

本文及其系列文章用于离散数学（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$ 合式公式定义 这是一个递归定义。 简单命题是合式公式 如果$A$是合式公式，那么$\neg A$也是合式公式 如果$A,B$是合式公式，那么$A\land B,A\lor B,A\rightarrow B,A\leftrightarrow B$是合式公式 当且仅当经过有限次使用$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)}$，用来确保过程用于规范。 ...